diff options
Diffstat (limited to 'src/pkg/runtime/hashmap.goc')
| -rw-r--r-- | src/pkg/runtime/hashmap.goc | 1078 |
1 files changed, 1078 insertions, 0 deletions
diff --git a/src/pkg/runtime/hashmap.goc b/src/pkg/runtime/hashmap.goc new file mode 100644 index 000000000..3327bed65 --- /dev/null +++ b/src/pkg/runtime/hashmap.goc @@ -0,0 +1,1078 @@ +// Copyright 2009 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. + +package runtime +#include "runtime.h" +#include "arch_GOARCH.h" +#include "malloc.h" +#include "type.h" +#include "race.h" +#include "hashmap.h" +#include "typekind.h" +#include "../../cmd/ld/textflag.h" + +enum +{ + docheck = 0, // check invariants before and after every op. Slow!!! + debug = 0, // print every operation + checkgc = 0 || docheck, // check interaction of mallocgc() with the garbage collector +}; +static void +check(MapType *t, Hmap *h) +{ + uintptr bucket, oldbucket; + Bucket *b; + uintptr i; + uintptr hash; + uintgo cnt; + uint8 top; + bool eq; + byte *k, *v; + + cnt = 0; + + // check buckets + for(bucket = 0; bucket < (uintptr)1 << h->B; bucket++) { + for(b = (Bucket*)(h->buckets + bucket * h->bucketsize); b != nil; b = b->overflow) { + for(i = 0, k = (byte*)b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) { + if(b->tophash[i] == Empty) + continue; + if(b->tophash[i] > Empty && b->tophash[i] < MinTopHash) + runtime·throw("evacuated cell in buckets"); + cnt++; + t->key->alg->equal(&eq, t->key->size, IK(h, k), IK(h, k)); + if(!eq) + continue; // NaN! + hash = h->hash0; + t->key->alg->hash(&hash, t->key->size, IK(h, k)); + top = hash >> (8*sizeof(uintptr) - 8); + if(top < MinTopHash) + top += MinTopHash; + if(top != b->tophash[i]) + runtime·throw("bad hash"); + } + } + } + + // check oldbuckets + if(h->oldbuckets != nil) { + for(oldbucket = 0; oldbucket < (uintptr)1 << (h->B - 1); oldbucket++) { + b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize); + for(; b != nil; b = b->overflow) { + for(i = 0, k = (byte*)b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) { + if(b->tophash[i] < MinTopHash) + continue; + if(oldbucket < h->nevacuate) + runtime·throw("unevacuated entry in an evacuated bucket"); + cnt++; + t->key->alg->equal(&eq, t->key->size, IK(h, k), IK(h, k)); + if(!eq) + continue; // NaN! + hash = h->hash0; + t->key->alg->hash(&hash, t->key->size, IK(h, k)); + top = hash >> (8*sizeof(uintptr) - 8); + if(top < MinTopHash) + top += MinTopHash; + if(top != b->tophash[i]) + runtime·throw("bad hash (old)"); + } + } + } + } + + if(cnt != h->count) { + runtime·printf("%D %D\n", (uint64)cnt, (uint64)h->count); + runtime·throw("entries missing"); + } +} + +static void +hash_init(MapType *t, Hmap *h, uint32 hint) +{ + uint8 B; + byte *buckets; + uintptr keysize, valuesize, bucketsize; + uint8 flags; + + flags = 0; + + // figure out how big we have to make everything + keysize = t->key->size; + if(keysize > MAXKEYSIZE) { + flags |= IndirectKey; + keysize = sizeof(byte*); + } + valuesize = t->elem->size; + if(valuesize > MAXVALUESIZE) { + flags |= IndirectValue; + valuesize = sizeof(byte*); + } + bucketsize = offsetof(Bucket, data[0]) + (keysize + valuesize) * BUCKETSIZE; + if(bucketsize != t->bucket->size) { + runtime·printf("runtime: bucketsize=%p but t->bucket->size=%p; t=%S\n", bucketsize, t->bucket->size, *t->string); + runtime·throw("bucketsize wrong"); + } + + // invariants we depend on. We should probably check these at compile time + // somewhere, but for now we'll do it here. + if(t->key->align > BUCKETSIZE) + runtime·throw("key align too big"); + if(t->elem->align > BUCKETSIZE) + runtime·throw("value align too big"); + if(t->key->size % t->key->align != 0) + runtime·throw("key size not a multiple of key align"); + if(t->elem->size % t->elem->align != 0) + runtime·throw("value size not a multiple of value align"); + if(BUCKETSIZE < 8) + runtime·throw("bucketsize too small for proper alignment"); + if((offsetof(Bucket, data[0]) & (t->key->align-1)) != 0) + runtime·throw("need padding in bucket (key)"); + if((offsetof(Bucket, data[0]) & (t->elem->align-1)) != 0) + runtime·throw("need padding in bucket (value)"); + + // find size parameter which will hold the requested # of elements + B = 0; + while(hint > BUCKETSIZE && hint > LOAD * ((uintptr)1 << B)) + B++; + + // allocate initial hash table + // If hint is large zeroing this memory could take a while. + if(checkgc) mstats.next_gc = mstats.heap_alloc; + if(B == 0) { + // done lazily later. + buckets = nil; + } else { + buckets = runtime·cnewarray(t->bucket, (uintptr)1 << B); + } + + // initialize Hmap + h->count = 0; + h->B = B; + h->flags = flags; + h->keysize = keysize; + h->valuesize = valuesize; + h->bucketsize = bucketsize; + h->hash0 = runtime·fastrand1(); + h->buckets = buckets; + h->oldbuckets = nil; + h->nevacuate = 0; + if(docheck) + check(t, h); +} + +// Moves entries in oldbuckets[i] to buckets[i] and buckets[i+2^k]. +// We leave the original bucket intact, except for marking the topbits +// entries as evacuated, so that iterators can still iterate through the old buckets. +static void +evacuate(MapType *t, Hmap *h, uintptr oldbucket) +{ + Bucket *b; + Bucket *x, *y; + Bucket *newx, *newy; + uintptr xi, yi; + uintptr newbit; + uintptr hash; + uintptr i; + byte *k, *v; + byte *xk, *yk, *xv, *yv; + uint8 top; + bool eq; + + b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize); + newbit = (uintptr)1 << (h->B - 1); + + if(!evacuated(b)) { + // TODO: reuse overflow buckets instead of using new ones, if there + // is no iterator using the old buckets. (If !OldIterator.) + + x = (Bucket*)(h->buckets + oldbucket * h->bucketsize); + y = (Bucket*)(h->buckets + (oldbucket + newbit) * h->bucketsize); + xi = 0; + yi = 0; + xk = (byte*)x->data; + yk = (byte*)y->data; + xv = xk + h->keysize * BUCKETSIZE; + yv = yk + h->keysize * BUCKETSIZE; + for(; b != nil; b = b->overflow) { + for(i = 0, k = (byte*)b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) { + top = b->tophash[i]; + if(top == Empty) { + b->tophash[i] = EvacuatedEmpty; + continue; + } + if(top < MinTopHash) + runtime·throw("bad state"); + + // Compute hash to make our evacuation decision (whether we need + // to send this key/value to bucket x or bucket y). + hash = h->hash0; + t->key->alg->hash(&hash, t->key->size, IK(h, k)); + if((h->flags & Iterator) != 0) { + t->key->alg->equal(&eq, t->key->size, IK(h, k), IK(h, k)); + if(!eq) { + // If key != key (NaNs), then the hash could be (and probably + // will be) entirely different from the old hash. Moreover, + // it isn't reproducible. Reproducibility is required in the + // presence of iterators, as our evacuation decision must + // match whatever decision the iterator made. + // Fortunately, we have the freedom to send these keys either + // way. Also, tophash is meaningless for these kinds of keys. + // We let the low bit of tophash drive the evacuation decision. + // We recompute a new random tophash for the next level so + // these keys will get evenly distributed across all buckets + // after multiple grows. + if((top & 1) != 0) + hash |= newbit; + else + hash &= ~newbit; + top = hash >> (8*sizeof(uintptr)-8); + if(top < MinTopHash) + top += MinTopHash; + } + } + + if((hash & newbit) == 0) { + b->tophash[i] = EvacuatedX; + if(xi == BUCKETSIZE) { + if(checkgc) mstats.next_gc = mstats.heap_alloc; + newx = runtime·cnew(t->bucket); + x->overflow = newx; + x = newx; + xi = 0; + xk = (byte*)x->data; + xv = xk + h->keysize * BUCKETSIZE; + } + x->tophash[xi] = top; + if((h->flags & IndirectKey) != 0) { + *(byte**)xk = *(byte**)k; // copy pointer + } else { + t->key->alg->copy(t->key->size, xk, k); // copy value + } + if((h->flags & IndirectValue) != 0) { + *(byte**)xv = *(byte**)v; + } else { + t->elem->alg->copy(t->elem->size, xv, v); + } + xi++; + xk += h->keysize; + xv += h->valuesize; + } else { + b->tophash[i] = EvacuatedY; + if(yi == BUCKETSIZE) { + if(checkgc) mstats.next_gc = mstats.heap_alloc; + newy = runtime·cnew(t->bucket); + y->overflow = newy; + y = newy; + yi = 0; + yk = (byte*)y->data; + yv = yk + h->keysize * BUCKETSIZE; + } + y->tophash[yi] = top; + if((h->flags & IndirectKey) != 0) { + *(byte**)yk = *(byte**)k; + } else { + t->key->alg->copy(t->key->size, yk, k); + } + if((h->flags & IndirectValue) != 0) { + *(byte**)yv = *(byte**)v; + } else { + t->elem->alg->copy(t->elem->size, yv, v); + } + yi++; + yk += h->keysize; + yv += h->valuesize; + } + } + } + + // Unlink the overflow buckets & clear key/value to help GC. + if((h->flags & OldIterator) == 0) { + b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize); + b->overflow = nil; + runtime·memclr((byte*)b->data, h->bucketsize - offsetof(Bucket, data[0])); + } + } + + // Advance evacuation mark + if(oldbucket == h->nevacuate) { + h->nevacuate = oldbucket + 1; + if(oldbucket + 1 == newbit) // newbit == # of oldbuckets + // Growing is all done. Free old main bucket array. + h->oldbuckets = nil; + } + if(docheck) + check(t, h); +} + +static void +grow_work(MapType *t, Hmap *h, uintptr bucket) +{ + uintptr noldbuckets; + + noldbuckets = (uintptr)1 << (h->B - 1); + + // make sure we evacuate the oldbucket corresponding + // to the bucket we're about to use + evacuate(t, h, bucket & (noldbuckets - 1)); + + // evacuate one more oldbucket to make progress on growing + if(h->oldbuckets != nil) + evacuate(t, h, h->nevacuate); +} + +static void +hash_grow(MapType *t, Hmap *h) +{ + byte *old_buckets; + byte *new_buckets; + uint8 flags; + + // allocate a bigger hash table + if(h->oldbuckets != nil) + runtime·throw("evacuation not done in time"); + old_buckets = h->buckets; + if(checkgc) mstats.next_gc = mstats.heap_alloc; + new_buckets = runtime·cnewarray(t->bucket, (uintptr)1 << (h->B + 1)); + flags = (h->flags & ~(Iterator | OldIterator)); + if((h->flags & Iterator) != 0) + flags |= OldIterator; + + // commit the grow (atomic wrt gc) + h->B++; + h->flags = flags; + h->oldbuckets = old_buckets; + h->buckets = new_buckets; + h->nevacuate = 0; + + // the actual copying of the hash table data is done incrementally + // by grow_work() and evacuate(). + if(docheck) + check(t, h); +} + +// returns ptr to value associated with key *keyp, or nil if none. +// if it returns non-nil, updates *keyp to point to the currently stored key. +static byte* +hash_lookup(MapType *t, Hmap *h, byte **keyp) +{ + void *key; + uintptr hash; + uintptr bucket, oldbucket; + Bucket *b; + uint8 top; + uintptr i; + bool eq; + byte *k, *k2, *v; + + key = *keyp; + if(docheck) + check(t, h); + if(h->count == 0) + return nil; + hash = h->hash0; + t->key->alg->hash(&hash, t->key->size, key); + bucket = hash & (((uintptr)1 << h->B) - 1); + if(h->oldbuckets != nil) { + oldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1); + b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize); + if(evacuated(b)) { + b = (Bucket*)(h->buckets + bucket * h->bucketsize); + } + } else { + b = (Bucket*)(h->buckets + bucket * h->bucketsize); + } + top = hash >> (sizeof(uintptr)*8 - 8); + if(top < MinTopHash) + top += MinTopHash; + do { + for(i = 0, k = (byte*)b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) { + if(b->tophash[i] == top) { + k2 = IK(h, k); + t->key->alg->equal(&eq, t->key->size, key, k2); + if(eq) { + *keyp = k2; + return IV(h, v); + } + } + } + b = b->overflow; + } while(b != nil); + return nil; +} + +// Specialized versions of mapaccess1 for specific types. +// See ./hashmap_fast.c and ../../cmd/gc/walk.c. +#define HASH_LOOKUP1 runtime·mapaccess1_fast32 +#define HASH_LOOKUP2 runtime·mapaccess2_fast32 +#define KEYTYPE uint32 +#define HASHFUNC runtime·algarray[AMEM32].hash +#define FASTKEY(x) true +#define QUICK_NE(x,y) ((x) != (y)) +#define QUICK_EQ(x,y) true +#define SLOW_EQ(x,y) true +#define MAYBE_EQ(x,y) true +#include "hashmap_fast.c" + +#undef HASH_LOOKUP1 +#undef HASH_LOOKUP2 +#undef KEYTYPE +#undef HASHFUNC +#undef FASTKEY +#undef QUICK_NE +#undef QUICK_EQ +#undef SLOW_EQ +#undef MAYBE_EQ + +#define HASH_LOOKUP1 runtime·mapaccess1_fast64 +#define HASH_LOOKUP2 runtime·mapaccess2_fast64 +#define KEYTYPE uint64 +#define HASHFUNC runtime·algarray[AMEM64].hash +#define FASTKEY(x) true +#define QUICK_NE(x,y) ((x) != (y)) +#define QUICK_EQ(x,y) true +#define SLOW_EQ(x,y) true +#define MAYBE_EQ(x,y) true +#include "hashmap_fast.c" + +#undef HASH_LOOKUP1 +#undef HASH_LOOKUP2 +#undef KEYTYPE +#undef HASHFUNC +#undef FASTKEY +#undef QUICK_NE +#undef QUICK_EQ +#undef SLOW_EQ +#undef MAYBE_EQ + +#ifdef GOARCH_amd64 +#define CHECKTYPE uint64 +#endif +#ifdef GOARCH_amd64p32 +#define CHECKTYPE uint32 +#endif +#ifdef GOARCH_386 +#define CHECKTYPE uint32 +#endif +#ifdef GOARCH_arm +// can't use uint32 on arm because our loads aren't aligned. +// TODO: use uint32 for arm v6+? +#define CHECKTYPE uint8 +#endif + +#define HASH_LOOKUP1 runtime·mapaccess1_faststr +#define HASH_LOOKUP2 runtime·mapaccess2_faststr +#define KEYTYPE String +#define HASHFUNC runtime·algarray[ASTRING].hash +#define FASTKEY(x) ((x).len < 32) +#define QUICK_NE(x,y) ((x).len != (y).len) +#define QUICK_EQ(x,y) ((x).str == (y).str) +#define SLOW_EQ(x,y) runtime·memeq((x).str, (y).str, (x).len) +#define MAYBE_EQ(x,y) (*(CHECKTYPE*)(x).str == *(CHECKTYPE*)(y).str && *(CHECKTYPE*)((x).str + (x).len - sizeof(CHECKTYPE)) == *(CHECKTYPE*)((y).str + (x).len - sizeof(CHECKTYPE))) +#include "hashmap_fast.c" + +static void +hash_insert(MapType *t, Hmap *h, void *key, void *value) +{ + uintptr hash; + uintptr bucket; + uintptr i; + bool eq; + Bucket *b; + Bucket *newb; + uint8 *inserti; + byte *insertk, *insertv; + uint8 top; + byte *k, *v; + byte *kmem, *vmem; + + if(docheck) + check(t, h); + hash = h->hash0; + t->key->alg->hash(&hash, t->key->size, key); + if(h->buckets == nil) + h->buckets = runtime·cnewarray(t->bucket, 1); + + again: + bucket = hash & (((uintptr)1 << h->B) - 1); + if(h->oldbuckets != nil) + grow_work(t, h, bucket); + b = (Bucket*)(h->buckets + bucket * h->bucketsize); + top = hash >> (sizeof(uintptr)*8 - 8); + if(top < MinTopHash) + top += MinTopHash; + inserti = nil; + insertk = nil; + insertv = nil; + while(true) { + for(i = 0, k = (byte*)b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) { + if(b->tophash[i] != top) { + if(b->tophash[i] == Empty && inserti == nil) { + inserti = &b->tophash[i]; + insertk = k; + insertv = v; + } + continue; + } + t->key->alg->equal(&eq, t->key->size, key, IK(h, k)); + if(!eq) + continue; + // already have a mapping for key. Update it. + t->key->alg->copy(t->key->size, IK(h, k), key); // Need to update key for keys which are distinct but equal (e.g. +0.0 and -0.0) + t->elem->alg->copy(t->elem->size, IV(h, v), value); + if(docheck) + check(t, h); + return; + } + if(b->overflow == nil) + break; + b = b->overflow; + } + + // did not find mapping for key. Allocate new cell & add entry. + if(h->count >= LOAD * ((uintptr)1 << h->B) && h->count >= BUCKETSIZE) { + hash_grow(t, h); + goto again; // Growing the table invalidates everything, so try again + } + + if(inserti == nil) { + // all current buckets are full, allocate a new one. + if(checkgc) mstats.next_gc = mstats.heap_alloc; + newb = runtime·cnew(t->bucket); + b->overflow = newb; + inserti = newb->tophash; + insertk = (byte*)newb->data; + insertv = insertk + h->keysize * BUCKETSIZE; + } + + // store new key/value at insert position + if((h->flags & IndirectKey) != 0) { + if(checkgc) mstats.next_gc = mstats.heap_alloc; + kmem = runtime·cnew(t->key); + *(byte**)insertk = kmem; + insertk = kmem; + } + if((h->flags & IndirectValue) != 0) { + if(checkgc) mstats.next_gc = mstats.heap_alloc; + vmem = runtime·cnew(t->elem); + *(byte**)insertv = vmem; + insertv = vmem; + } + t->key->alg->copy(t->key->size, insertk, key); + t->elem->alg->copy(t->elem->size, insertv, value); + *inserti = top; + h->count++; + if(docheck) + check(t, h); +} + +static void +hash_remove(MapType *t, Hmap *h, void *key) +{ + uintptr hash; + uintptr bucket; + Bucket *b; + uint8 top; + uintptr i; + byte *k, *v; + bool eq; + + if(docheck) + check(t, h); + if(h->count == 0) + return; + hash = h->hash0; + t->key->alg->hash(&hash, t->key->size, key); + bucket = hash & (((uintptr)1 << h->B) - 1); + if(h->oldbuckets != nil) + grow_work(t, h, bucket); + b = (Bucket*)(h->buckets + bucket * h->bucketsize); + top = hash >> (sizeof(uintptr)*8 - 8); + if(top < MinTopHash) + top += MinTopHash; + do { + for(i = 0, k = (byte*)b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) { + if(b->tophash[i] != top) + continue; + t->key->alg->equal(&eq, t->key->size, key, IK(h, k)); + if(!eq) + continue; + + if((h->flags & IndirectKey) != 0) { + *(byte**)k = nil; + } else { + t->key->alg->copy(t->key->size, k, nil); + } + if((h->flags & IndirectValue) != 0) { + *(byte**)v = nil; + } else { + t->elem->alg->copy(t->elem->size, v, nil); + } + + b->tophash[i] = Empty; + h->count--; + + // TODO: consolidate buckets if they are mostly empty + // can only consolidate if there are no live iterators at this size. + if(docheck) + check(t, h); + return; + } + b = b->overflow; + } while(b != nil); +} + +// TODO: shrink the map, the same way we grow it. + +// iterator state: +// bucket: the current bucket ID +// b: the current Bucket in the chain +// i: the next offset to check in the current bucket +static void +hash_iter_init(MapType *t, Hmap *h, Hiter *it) +{ + uint32 old; + + if(sizeof(Hiter) / sizeof(uintptr) != 10) { + runtime·throw("hash_iter size incorrect"); // see ../../cmd/gc/reflect.c + } + it->t = t; + it->h = h; + + // grab snapshot of bucket state + it->B = h->B; + it->buckets = h->buckets; + + // iterator state + it->bucket = 0; + it->offset = runtime·fastrand1() & (BUCKETSIZE - 1); + it->done = false; + it->bptr = nil; + + // Remember we have an iterator. + // Can run concurrently with another hash_iter_init(). + for(;;) { + old = h->flags; + if((old&(Iterator|OldIterator)) == (Iterator|OldIterator)) + break; + if(runtime·cas(&h->flags, old, old|Iterator|OldIterator)) + break; + } + + if(h->buckets == nil) { + // Empty map. Force next hash_next to exit without + // evaluating h->bucket. + it->done = true; + } +} + +// initializes it->key and it->value to the next key/value pair +// in the iteration, or nil if we've reached the end. +static void +hash_next(Hiter *it) +{ + Hmap *h; + MapType *t; + uintptr bucket, oldbucket; + uintptr hash; + Bucket *b; + uintptr i, offi; + intptr check_bucket; + bool eq; + byte *k, *v; + byte *rk, *rv; + + h = it->h; + t = it->t; + bucket = it->bucket; + b = it->bptr; + i = it->i; + check_bucket = it->check_bucket; + +next: + if(b == nil) { + if(it->done) { + // end of iteration + it->key = nil; + it->value = nil; + return; + } + if(h->oldbuckets != nil && it->B == h->B) { + // Iterator was started in the middle of a grow, and the grow isn't done yet. + // If the bucket we're looking at hasn't been filled in yet (i.e. the old + // bucket hasn't been evacuated) then we need to iterate through the old + // bucket and only return the ones that will be migrated to this bucket. + oldbucket = bucket & (((uintptr)1 << (it->B - 1)) - 1); + b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize); + if(!evacuated(b)) { + check_bucket = bucket; + } else { + b = (Bucket*)(it->buckets + bucket * h->bucketsize); + check_bucket = -1; + } + } else { + b = (Bucket*)(it->buckets + bucket * h->bucketsize); + check_bucket = -1; + } + bucket++; + if(bucket == ((uintptr)1 << it->B)) { + bucket = 0; + it->done = true; + } + i = 0; + } + for(; i < BUCKETSIZE; i++) { + offi = (i + it->offset) & (BUCKETSIZE - 1); + k = (byte*)b->data + h->keysize * offi; + v = (byte*)b->data + h->keysize * BUCKETSIZE + h->valuesize * offi; + if(b->tophash[offi] != Empty && b->tophash[offi] != EvacuatedEmpty) { + if(check_bucket >= 0) { + // Special case: iterator was started during a grow and the + // grow is not done yet. We're working on a bucket whose + // oldbucket has not been evacuated yet. Or at least, it wasn't + // evacuated when we started the bucket. So we're iterating + // through the oldbucket, skipping any keys that will go + // to the other new bucket (each oldbucket expands to two + // buckets during a grow). + t->key->alg->equal(&eq, t->key->size, IK(h, k), IK(h, k)); + if(eq) { + // If the item in the oldbucket is not destined for + // the current new bucket in the iteration, skip it. + hash = h->hash0; + t->key->alg->hash(&hash, t->key->size, IK(h, k)); + if((hash & (((uintptr)1 << it->B) - 1)) != check_bucket) { + continue; + } + } else { + // Hash isn't repeatable if k != k (NaNs). We need a + // repeatable and randomish choice of which direction + // to send NaNs during evacuation. We'll use the low + // bit of tophash to decide which way NaNs go. + // NOTE: this case is why we need two evacuate tophash + // values, evacuatedX and evacuatedY, that differ in + // their low bit. + if(check_bucket >> (it->B - 1) != (b->tophash[offi] & 1)) { + continue; + } + } + } + if(b->tophash[offi] != EvacuatedX && b->tophash[offi] != EvacuatedY) { + // this is the golden data, we can return it. + it->key = IK(h, k); + it->value = IV(h, v); + } else { + // The hash table has grown since the iterator was started. + // The golden data for this key is now somewhere else. + t->key->alg->equal(&eq, t->key->size, IK(h, k), IK(h, k)); + if(eq) { + // Check the current hash table for the data. + // This code handles the case where the key + // has been deleted, updated, or deleted and reinserted. + // NOTE: we need to regrab the key as it has potentially been + // updated to an equal() but not identical key (e.g. +0.0 vs -0.0). + rk = IK(h, k); + rv = hash_lookup(t, it->h, &rk); + if(rv == nil) + continue; // key has been deleted + it->key = rk; + it->value = rv; + } else { + // if key!=key then the entry can't be deleted or + // updated, so we can just return it. That's lucky for + // us because when key!=key we can't look it up + // successfully in the current table. + it->key = IK(h, k); + it->value = IV(h, v); + } + } + it->bucket = bucket; + it->bptr = b; + it->i = i + 1; + it->check_bucket = check_bucket; + return; + } + } + b = b->overflow; + i = 0; + goto next; +} + +// +/// interfaces to go runtime +// + +func reflect·ismapkey(typ *Type) (ret bool) { + ret = typ != nil && typ->alg->hash != runtime·nohash; +} + +static Hmap* +makemap_c(MapType *typ, int64 hint) +{ + Hmap *h; + Type *key; + + key = typ->key; + + if(sizeof(Hmap) > 48) + runtime·panicstring("hmap too large"); + + if(hint < 0 || (int32)hint != hint) + runtime·panicstring("makemap: size out of range"); + + if(key->alg->hash == runtime·nohash) + runtime·throw("runtime.makemap: unsupported map key type"); + + h = runtime·cnew(typ->hmap); + hash_init(typ, h, hint); + + // these calculations are compiler dependent. + // figure out offsets of map call arguments. + + if(debug) { + runtime·printf("makemap: map=%p; keysize=%p; valsize=%p; keyalg=%p; valalg=%p\n", + h, key->size, typ->elem->size, key->alg, typ->elem->alg); + } + + return h; +} + +func makemap(typ *MapType, hint int64) (ret *Hmap) { + ret = makemap_c(typ, hint); +} + +func reflect·makemap(t *MapType) (ret *Hmap) { + ret = makemap_c(t, 0); +} + +// NOTE: The returned pointer may keep the whole map live, so don't +// hold onto it for very long. +#pragma textflag NOSPLIT +func mapaccess1(t *MapType, h *Hmap, key *byte) (val *byte) { + if(raceenabled && h != nil) { + runtime·racereadpc(h, runtime·getcallerpc(&t), runtime·mapaccess1); + runtime·racereadobjectpc(key, t->key, runtime·getcallerpc(&t), runtime·mapaccess1); + } + if(h == nil || h->count == 0) { + val = t->elem->zero; + } else { + val = hash_lookup(t, h, &key); + if(val == nil) + val = t->elem->zero; + } + + if(debug) { + runtime·prints("runtime.mapaccess1: map="); + runtime·printpointer(h); + runtime·prints("; key="); + t->key->alg->print(t->key->size, key); + runtime·prints("; val="); + t->elem->alg->print(t->elem->size, val); + runtime·prints("\n"); + } +} + +// NOTE: The returned pointer keeps the whole map live, so don't +// hold onto it for very long. +#pragma textflag NOSPLIT +func mapaccess2(t *MapType, h *Hmap, key *byte) (val *byte, pres bool) { + if(raceenabled && h != nil) { + runtime·racereadpc(h, runtime·getcallerpc(&t), runtime·mapaccess2); + runtime·racereadobjectpc(key, t->key, runtime·getcallerpc(&t), runtime·mapaccess2); + } + + if(h == nil || h->count == 0) { + val = t->elem->zero; + pres = false; + } else { + val = hash_lookup(t, h, &key); + if(val == nil) { + val = t->elem->zero; + pres = false; + } else { + pres = true; + } + } + + if(debug) { + runtime·prints("runtime.mapaccess2: map="); + runtime·printpointer(h); + runtime·prints("; key="); + t->key->alg->print(t->key->size, key); + runtime·prints("; val="); + t->elem->alg->print(t->elem->size, val); + runtime·prints("; pres="); + runtime·printbool(pres); + runtime·prints("\n"); + } +} + +#pragma textflag NOSPLIT +func reflect·mapaccess(t *MapType, h *Hmap, key *byte) (val *byte) { + if(h == nil) + val = nil; + else { + if(raceenabled) { + runtime·racereadpc(h, runtime·getcallerpc(&t), reflect·mapaccess); + runtime·racereadobjectpc(key, t->key, runtime·getcallerpc(&t), reflect·mapaccess); + } + val = hash_lookup(t, h, &key); + } +} + +#pragma textflag NOSPLIT +func mapassign1(t *MapType, h *Hmap, key *byte, val *byte) { + if(h == nil) + runtime·panicstring("assignment to entry in nil map"); + + if(raceenabled) { + runtime·racewritepc(h, runtime·getcallerpc(&t), runtime·mapassign1); + runtime·racereadobjectpc(key, t->key, runtime·getcallerpc(&t), runtime·mapassign1); + runtime·racereadobjectpc(val, t->elem, runtime·getcallerpc(&t), runtime·mapassign1); + } + + hash_insert(t, h, key, val); + + if(debug) { + runtime·prints("mapassign1: map="); + runtime·printpointer(h); + runtime·prints("; key="); + t->key->alg->print(t->key->size, key); + runtime·prints("; val="); + t->elem->alg->print(t->elem->size, val); + runtime·prints("\n"); + } +} + +#pragma textflag NOSPLIT +func mapdelete(t *MapType, h *Hmap, key *byte) { + if(h == nil) + return; + + if(raceenabled) { + runtime·racewritepc(h, runtime·getcallerpc(&t), runtime·mapdelete); + runtime·racereadobjectpc(key, t->key, runtime·getcallerpc(&t), runtime·mapdelete); + } + + hash_remove(t, h, key); + + if(debug) { + runtime·prints("mapdelete: map="); + runtime·printpointer(h); + runtime·prints("; key="); + t->key->alg->print(t->key->size, key); + runtime·prints("\n"); + } +} + +#pragma textflag NOSPLIT +func reflect·mapassign(t *MapType, h *Hmap, key *byte, val *byte) { + if(h == nil) + runtime·panicstring("assignment to entry in nil map"); + if(raceenabled) { + runtime·racewritepc(h, runtime·getcallerpc(&t), reflect·mapassign); + runtime·racereadobjectpc(key, t->key, runtime·getcallerpc(&t), reflect·mapassign); + runtime·racereadobjectpc(val, t->elem, runtime·getcallerpc(&t), reflect·mapassign); + } + + hash_insert(t, h, key, val); + + if(debug) { + runtime·prints("mapassign: map="); + runtime·printpointer(h); + runtime·prints("; key="); + t->key->alg->print(t->key->size, key); + runtime·prints("; val="); + t->elem->alg->print(t->elem->size, val); + runtime·prints("\n"); + } +} + +#pragma textflag NOSPLIT +func reflect·mapdelete(t *MapType, h *Hmap, key *byte) { + if(h == nil) + return; // see bug 8051 + if(raceenabled) { + runtime·racewritepc(h, runtime·getcallerpc(&t), reflect·mapdelete); + runtime·racereadobjectpc(key, t->key, runtime·getcallerpc(&t), reflect·mapdelete); + } + hash_remove(t, h, key); + + if(debug) { + runtime·prints("mapdelete: map="); + runtime·printpointer(h); + runtime·prints("; key="); + t->key->alg->print(t->key->size, key); + runtime·prints("\n"); + } +} + +#pragma textflag NOSPLIT +func mapiterinit(t *MapType, h *Hmap, it *Hiter) { + // Clear pointer fields so garbage collector does not complain. + it->key = nil; + it->value = nil; + it->t = nil; + it->h = nil; + it->buckets = nil; + it->bptr = nil; + + if(h == nil || h->count == 0) { + it->key = nil; + return; + } + if(raceenabled) + runtime·racereadpc(h, runtime·getcallerpc(&t), runtime·mapiterinit); + hash_iter_init(t, h, it); + hash_next(it); + if(debug) { + runtime·prints("runtime.mapiterinit: map="); + runtime·printpointer(h); + runtime·prints("; iter="); + runtime·printpointer(it); + runtime·prints("; key="); + runtime·printpointer(it->key); + runtime·prints("\n"); + } +} + +func reflect·mapiterinit(t *MapType, h *Hmap) (it *Hiter) { + it = runtime·mal(sizeof *it); + runtime·mapiterinit(t, h, it); +} + +#pragma textflag NOSPLIT +func mapiternext(it *Hiter) { + if(raceenabled) + runtime·racereadpc(it->h, runtime·getcallerpc(&it), runtime·mapiternext); + + hash_next(it); + if(debug) { + runtime·prints("runtime.mapiternext: iter="); + runtime·printpointer(it); + runtime·prints("; key="); + runtime·printpointer(it->key); + runtime·prints("\n"); + } +} + +func reflect·mapiternext(it *Hiter) { + runtime·mapiternext(it); +} + +func reflect·mapiterkey(it *Hiter) (key *byte) { + key = it->key; +} + +#pragma textflag NOSPLIT +func reflect·maplen(h *Hmap) (len int) { + if(h == nil) + len = 0; + else { + len = h->count; + if(raceenabled) + runtime·racereadpc(h, runtime·getcallerpc(&h), reflect·maplen); + } +} + +// exported value for testing +float64 runtime·hashLoad = LOAD; |