gcc/testsuite/go.test/test/hashmap.go

   1 // $G $F.go && $L $F.$A && ./$A.out
   2
   3 // Copyright 2009 The Go Authors. All rights reserved.
   4 // Use of this source code is governed by a BSD-style
   5 // license that can be found in the LICENSE file.
   6
   7 package main
   8
   9 // ----------------------------------------------------------------------------
  10 // Helper functions
  11
  12 func ASSERT(p bool) {
  13         if !p {
  14                 // panic 0
  15         }
  16 }
  17
  18
  19 // ----------------------------------------------------------------------------
  20 // Implementation of the HashMap
  21
  22 type KeyType interface {
  23         Hash() uint32
  24         Match(other KeyType) bool
  25 }
  26
  27
  28 type ValueType interface {
  29         // empty interface
  30 }
  31
  32
  33 type Entry struct {
  34         key KeyType
  35         value ValueType
  36 }
  37
  38
  39 type Array [1024]Entry
  40
  41 type HashMap struct {
  42         map_ *Array
  43         log2_capacity_ uint32
  44         occupancy_ uint32
  45 }
  46
  47
  48 func (m *HashMap) capacity() uint32 {
  49         return 1 << m.log2_capacity_
  50 }
  51
  52
  53 func (m *HashMap) Clear() {
  54         // Mark all entries as empty.
  55         var i uint32 = m.capacity() - 1
  56         for i > 0 {
  57                 m.map_[i].key = nil
  58                 i = i - 1
  59         }
  60         m.occupancy_ = 0
  61 }
  62
  63
  64 func (m *HashMap) Initialize (initial_log2_capacity uint32) {
  65         m.log2_capacity_ = initial_log2_capacity
  66         m.map_ = new(Array)
  67         m.Clear()
  68 }
  69
  70
  71 func (m *HashMap) Probe (key KeyType) *Entry {
  72         ASSERT(key != nil)
  73
  74         var i uint32 = key.Hash() % m.capacity()
  75         ASSERT(0 <= i && i < m.capacity())
  76
  77         ASSERT(m.occupancy_ < m.capacity())     // guarantees loop termination
  78         for m.map_[i].key != nil && !m.map_[i].key.Match(key) {
  79                 i++
  80                 if i >= m.capacity() {
  81                         i = 0
  82                 }
  83         }
  84
  85         return &m.map_[i]
  86 }
  87
  88
  89 func (m *HashMap) Lookup (key KeyType, insert bool) *Entry {
  90         // Find a matching entry.
  91         var p *Entry = m.Probe(key)
  92                 if p.key != nil {
  93                 return p
  94         }
  95
  96         // No entry found; insert one if necessary.
  97         if insert {
  98                 p.key = key
  99                 p.value = nil
 100                 m.occupancy_++
 101
 102                 // Grow the map if we reached >= 80% occupancy.
 103                 if m.occupancy_ + m.occupancy_/4 >= m.capacity() {
 104                         m.Resize()
 105                         p = m.Probe(key)
 106                 }
 107
 108                 return p
 109         }
 110
 111         // No entry found and none inserted.
 112         return nil
 113 }
 114
 115
 116 func (m *HashMap) Resize() {
 117         var hmap *Array = m.map_
 118         var n uint32 = m.occupancy_
 119
 120         // Allocate a new map of twice the current size.
 121         m.Initialize(m.log2_capacity_ << 1)
 122
 123         // Rehash all current entries.
 124         var i uint32 = 0
 125         for n > 0 {
 126                 if hmap[i].key != nil {
 127                         m.Lookup(hmap[i].key, true).value = hmap[i].value
 128                         n = n - 1
 129                 }
 130                 i++
 131         }
 132 }
 133
 134
 135 // ----------------------------------------------------------------------------
 136 // Test code
 137
 138 type Number struct {
 139         x uint32
 140 }
 141
 142
 143 func (n *Number) Hash() uint32 {
 144         return n.x * 23
 145 }
 146
 147
 148 func (n *Number) Match(other KeyType) bool {
 149         // var y *Number = other
 150         // return n.x == y.x
 151         return false
 152 }
 153
 154
 155 func MakeNumber (x uint32) *Number {
 156         var n *Number = new(Number)
 157         n.x = x
 158         return n
 159 }
 160
 161
 162 func main() {
 163         // func (n int) int { return n + 1; }(1)
 164
 165         //print "HashMap - gri 2/8/2008\n"
 166
 167         var hmap *HashMap = new(HashMap)
 168         hmap.Initialize(0)
 169
 170         var x1 *Number = MakeNumber(1001)
 171         var x2 *Number = MakeNumber(2002)
 172         var x3 *Number = MakeNumber(3003)
 173         _, _, _ = x1, x2, x3
 174
 175         // this doesn't work I think...
 176         //hmap.Lookup(x1, true)
 177         //hmap.Lookup(x2, true)
 178         //hmap.Lookup(x3, true)
 179
 180         //print "done\n"
 181 }