Imported Upstream version 1.4upstream/1.4

1 files changed, 0 insertions, 1078 deletions

diff --git a/src/pkg/runtime/hashmap.goc b/src/pkg/runtime/hashmap.goc
deleted file mode 100644
index 3327bed65..000000000
--- a/src/pkg/runtime/hashmap.goc
+++ /dev/null
@@ -1,1078 +0,0 @@
-// 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;