OLD | NEW |
1 // Copyright 2013 The Go Authors. All rights reserved. | 1 // Copyright 2013 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 // Fast hashmap lookup specialized to a specific key type. | 5 // Fast hashmap lookup specialized to a specific key type. |
6 // Included by hashmap.c once for each specialized type. | 6 // Included by hashmap.c once for each specialized type. |
7 | 7 |
8 // Note that this code differs from hash_lookup in that | 8 // Note that this code differs from hash_lookup in that |
9 // it returns a pointer to the result, not the result itself. | 9 // it returns a pointer to the result, not the result itself. |
10 // The returned pointer is only valid until the next GC | 10 // The returned pointer is only valid until the next GC |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
45 // One-bucket table. Don't hash, just check each bucket entry. | 45 // One-bucket table. Don't hash, just check each bucket entry. |
46 b = (Bucket*)h->buckets; | 46 b = (Bucket*)h->buckets; |
47 for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i
< BUCKETSIZE; i++, k++, v += h->valuesize) { | 47 for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i
< BUCKETSIZE; i++, k++, v += h->valuesize) { |
48 if(b->tophash[i] != 0 && EQFUNC(key, *k)) { | 48 if(b->tophash[i] != 0 && EQFUNC(key, *k)) { |
49 value = v; | 49 value = v; |
50 FLUSH(&value); | 50 FLUSH(&value); |
51 return; | 51 return; |
52 } | 52 } |
53 } | 53 } |
54 } else { | 54 } else { |
55 » » hash = h->hash0; | 55 » » if(HASHCACHE && m->lasthmap == (uintptr)h && |
56 » » HASHFUNC(&hash, sizeof(KEYTYPE), &key); | 56 » » m->lastkey == KEYVALUE(key) && m->lastlen == KEYLEN(key)) { |
| 57 » » » hash = m->lasthash; |
| 58 » » } else { |
| 59 » » » hash = h->hash0; |
| 60 » » » HASHFUNC(&hash, sizeof(KEYTYPE), &key); |
| 61 » » » if(HASHCACHE) { |
| 62 » » » » m->lasthmap = (uintptr)h; |
| 63 » » » » m->lastkey = KEYVALUE(key); |
| 64 » » » » m->lastlen = KEYLEN(key); |
| 65 » » » » m->lasthash = hash; |
| 66 » » » } |
| 67 » » } |
57 bucket = hash & (((uintptr)1 << h->B) - 1); | 68 bucket = hash & (((uintptr)1 << h->B) - 1); |
58 if(h->oldbuckets != nil) | 69 if(h->oldbuckets != nil) |
59 grow_work(t, h, bucket); | 70 grow_work(t, h, bucket); |
60 b = (Bucket*)(h->buckets + bucket * (offsetof(Bucket, data[0]) +
BUCKETSIZE * sizeof(KEYTYPE) + BUCKETSIZE * h->valuesize)); | 71 b = (Bucket*)(h->buckets + bucket * (offsetof(Bucket, data[0]) +
BUCKETSIZE * sizeof(KEYTYPE) + BUCKETSIZE * h->valuesize)); |
61 top = hash >> (sizeof(uintptr)*8 - 8); | 72 top = hash >> (sizeof(uintptr)*8 - 8); |
62 if(top == 0) | 73 if(top == 0) |
63 top = 1; | 74 top = 1; |
64 do { | 75 do { |
65 for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKET
SIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) { | 76 for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKET
SIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) { |
66 if(b->tophash[i] == top && EQFUNC(key, *k)) { | 77 if(b->tophash[i] == top && EQFUNC(key, *k)) { |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
113 for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i
< BUCKETSIZE; i++, k++, v += h->valuesize) { | 124 for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i
< BUCKETSIZE; i++, k++, v += h->valuesize) { |
114 if(b->tophash[i] != 0 && EQFUNC(key, *k)) { | 125 if(b->tophash[i] != 0 && EQFUNC(key, *k)) { |
115 value = v; | 126 value = v; |
116 res = true; | 127 res = true; |
117 FLUSH(&value); | 128 FLUSH(&value); |
118 FLUSH(&res); | 129 FLUSH(&res); |
119 return; | 130 return; |
120 } | 131 } |
121 } | 132 } |
122 } else { | 133 } else { |
123 » » hash = h->hash0; | 134 » » if(HASHCACHE && m->lasthmap == (uintptr)h && |
124 » » HASHFUNC(&hash, sizeof(KEYTYPE), &key); | 135 » » m->lastkey == KEYVALUE(key) && m->lastlen == KEYLEN(key)) { |
| 136 » » » hash = m->lasthash; |
| 137 » » } else { |
| 138 » » » hash = h->hash0; |
| 139 » » » HASHFUNC(&hash, sizeof(KEYTYPE), &key); |
| 140 » » » if(HASHCACHE) { |
| 141 » » » » m->lasthmap = (uintptr)h; |
| 142 » » » » m->lastkey = KEYVALUE(key); |
| 143 » » » » m->lastlen = KEYLEN(key); |
| 144 » » » » m->lasthash = hash; |
| 145 » » » } |
| 146 » » } |
125 bucket = hash & (((uintptr)1 << h->B) - 1); | 147 bucket = hash & (((uintptr)1 << h->B) - 1); |
126 if(h->oldbuckets != nil) | 148 if(h->oldbuckets != nil) |
127 grow_work(t, h, bucket); | 149 grow_work(t, h, bucket); |
128 b = (Bucket*)(h->buckets + bucket * (offsetof(Bucket, data[0]) +
BUCKETSIZE * sizeof(KEYTYPE) + BUCKETSIZE * h->valuesize)); | 150 b = (Bucket*)(h->buckets + bucket * (offsetof(Bucket, data[0]) +
BUCKETSIZE * sizeof(KEYTYPE) + BUCKETSIZE * h->valuesize)); |
129 top = hash >> (sizeof(uintptr)*8 - 8); | 151 top = hash >> (sizeof(uintptr)*8 - 8); |
130 if(top == 0) | 152 if(top == 0) |
131 top = 1; | 153 top = 1; |
132 do { | 154 do { |
133 for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKET
SIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) { | 155 for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKET
SIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) { |
134 if(b->tophash[i] == top && EQFUNC(key, *k)) { | 156 if(b->tophash[i] == top && EQFUNC(key, *k)) { |
135 value = v; | 157 value = v; |
136 res = true; | 158 res = true; |
137 FLUSH(&value); | 159 FLUSH(&value); |
138 FLUSH(&res); | 160 FLUSH(&res); |
139 return; | 161 return; |
140 } | 162 } |
141 } | 163 } |
142 b = b->overflow; | 164 b = b->overflow; |
143 } while(b != nil); | 165 } while(b != nil); |
144 } | 166 } |
145 value = empty_value; | 167 value = empty_value; |
146 res = false; | 168 res = false; |
147 FLUSH(&value); | 169 FLUSH(&value); |
148 FLUSH(&res); | 170 FLUSH(&res); |
149 } | 171 } |
OLD | NEW |