Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(106)

Side by Side Diff: test/hashmap.go

Issue 2157041: code review 2157041: test: remove semiocolons. (Closed)
Patch Set: code review 2157041: test: remove semiocolons. Created 14 years, 7 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View unified diff | Download patch
« no previous file with comments | « test/gc1.go ('k') | test/helloworld.go » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 }
OLDNEW
« no previous file with comments | « test/gc1.go ('k') | test/helloworld.go » ('j') | no next file with comments »

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b