diff options
Diffstat (limited to 'src/pkg/runtime/hashmap_fast.c')
| -rw-r--r-- | src/pkg/runtime/hashmap_fast.c | 149 |
1 files changed, 149 insertions, 0 deletions
diff --git a/src/pkg/runtime/hashmap_fast.c b/src/pkg/runtime/hashmap_fast.c new file mode 100644 index 000000000..2169f4c30 --- /dev/null +++ b/src/pkg/runtime/hashmap_fast.c @@ -0,0 +1,149 @@ +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Fast hashmap lookup specialized to a specific key type. +// Included by hashmap.c once for each specialized type. + +// Note that this code differs from hash_lookup in that +// it returns a pointer to the result, not the result itself. +// The returned pointer is only valid until the next GC +// point, so the caller must dereference it before then. + +// +build ignore + +#pragma textflag 7 +void +HASH_LOOKUP1(MapType *t, Hmap *h, KEYTYPE key, byte *value) +{ + uintptr hash; + uintptr bucket; + Bucket *b; + uint8 top; + uintptr i; + KEYTYPE *k; + byte *v; + + if(debug) { + runtime·prints("runtime.mapaccess1_fastXXX: map="); + runtime·printpointer(h); + runtime·prints("; key="); + t->key->alg->print(t->key->size, &key); + runtime·prints("\n"); + } + if(h == nil || h->count == 0) { + value = empty_value; + FLUSH(&value); + return; + } + if(raceenabled) + runtime·racereadpc(h, runtime·getcallerpc(&t), HASH_LOOKUP1); + if(docheck) + check(t, h); + + if(h->B == 0 && (h->count == 1 || QUICKEQ(key))) { + // One-bucket table. Don't hash, just check each bucket entry. + b = (Bucket*)h->buckets; + for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) { + if(b->tophash[i] != 0 && EQFUNC(key, *k)) { + value = v; + FLUSH(&value); + return; + } + } + } else { + hash = h->hash0; + HASHFUNC(&hash, sizeof(KEYTYPE), &key); + bucket = hash & (((uintptr)1 << h->B) - 1); + if(h->oldbuckets != nil) + grow_work(t, h, bucket); + b = (Bucket*)(h->buckets + bucket * (offsetof(Bucket, data[0]) + BUCKETSIZE * sizeof(KEYTYPE) + BUCKETSIZE * h->valuesize)); + top = hash >> (sizeof(uintptr)*8 - 8); + if(top == 0) + top = 1; + do { + for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) { + if(b->tophash[i] == top && EQFUNC(key, *k)) { + value = v; + FLUSH(&value); + return; + } + } + b = b->overflow; + } while(b != nil); + } + value = empty_value; + FLUSH(&value); +} + +#pragma textflag 7 +void +HASH_LOOKUP2(MapType *t, Hmap *h, KEYTYPE key, byte *value, bool res) +{ + uintptr hash; + uintptr bucket; + Bucket *b; + uint8 top; + uintptr i; + KEYTYPE *k; + byte *v; + + if(debug) { + runtime·prints("runtime.mapaccess2_fastXXX: map="); + runtime·printpointer(h); + runtime·prints("; key="); + t->key->alg->print(t->key->size, &key); + runtime·prints("\n"); + } + if(h == nil || h->count == 0) { + value = empty_value; + res = false; + FLUSH(&value); + FLUSH(&res); + return; + } + if(raceenabled) + runtime·racereadpc(h, runtime·getcallerpc(&t), HASH_LOOKUP2); + if(docheck) + check(t, h); + + if(h->B == 0 && (h->count == 1 || QUICKEQ(key))) { + // One-bucket table. Don't hash, just check each bucket entry. + b = (Bucket*)h->buckets; + for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) { + if(b->tophash[i] != 0 && EQFUNC(key, *k)) { + value = v; + res = true; + FLUSH(&value); + FLUSH(&res); + return; + } + } + } else { + hash = h->hash0; + HASHFUNC(&hash, sizeof(KEYTYPE), &key); + bucket = hash & (((uintptr)1 << h->B) - 1); + if(h->oldbuckets != nil) + grow_work(t, h, bucket); + b = (Bucket*)(h->buckets + bucket * (offsetof(Bucket, data[0]) + BUCKETSIZE * sizeof(KEYTYPE) + BUCKETSIZE * h->valuesize)); + top = hash >> (sizeof(uintptr)*8 - 8); + if(top == 0) + top = 1; + do { + for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) { + if(b->tophash[i] == top && EQFUNC(key, *k)) { + value = v; + res = true; + FLUSH(&value); + FLUSH(&res); + return; + } + } + b = b->overflow; + } while(b != nil); + } + value = empty_value; + res = false; + FLUSH(&value); + FLUSH(&res); +} |