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