-static void realloc(naRef hash)
-{
- struct naHash* h = hash.ref.ptr.hash;
- int i, sz, oldsz = h->size;
- int oldcols = h->table ? 1 << h->lgalloced : 0;
-
- // Keep a handle to our original objects
- struct HashNode* oldnodes = h->nodes;
- struct HashNode** oldtable = h->table;
-
- // Figure out how big we need to be (start with a minimum size of
- // 16 entries)
- for(i=3; 1<<i < oldsz; i++);
- h->lgalloced = i+1;
-
- // Allocate new ones (note that all the records are allocated in a
- // single chunk, to avoid zillions of tiny node allocations)
- sz = 1<<h->lgalloced;
- h->nodes = naAlloc(sz * (sizeof(struct HashNode) + sizeof(void*)));
- h->table = (struct HashNode**)(((char*)h->nodes) + sz*sizeof(struct HashNode));
- naBZero(h->table, sz * sizeof(void*));
- h->nextnode = 0;
- h->size = 0;
-
- // Re-insert everything from scratch
- for(i=0; i<oldcols; i++) {
- struct HashNode* hn = oldtable[i];
- while(hn) {
- naHash_set(hash, hn->key, hn->val);
- hn = hn->next;
+/* A HashRec lives in a single allocated block. The layout is the
+ * header struct, then a table of 2^lgsz hash entries (key/value
+ * pairs), then an index table of 2*2^lgsz integers storing index
+ * values into the entry table. There are two tokens needed for
+ * "unused" and "used but empty". */
+
+#define ENT_EMPTY -1
+#define ENT_DELETED -2
+
+typedef struct { naRef key, val; } HashEnt;
+
+typedef struct HashRec {
+ int size; /* number of active entries */
+ int lgsz; /* base-2 logarithm of the allocated (!) size */
+ int next; /* next entry to use */
+} HashRec;
+
+#define REC(h) (PTR(h).hash->rec)
+#define POW2(n) (1<<(n))
+#define NCELLS(hr) (2*POW2((hr)->lgsz))
+#define ROUNDUPOFF(n,m) ((((n)+(m-1))/m)*m)-(n)
+#define ALIGN(p,sz) (((char*)p)+ROUNDUPOFF(((size_t)p)%sz,sz))
+#define ENTS(h) ((HashEnt*)ALIGN(&((HashRec*)h)[1],sizeof(naRef)))
+#define TAB(h) ((int*)&(ENTS(h)[1<<(h)->lgsz]))
+#define HBITS(hr,code) ((hr)->lgsz ? ((code)>>(32-(hr)->lgsz)) : 0)
+
+#define LROT(h,n) (((h)<<n)|((h)>>((8*sizeof(h))-n)))
+static unsigned int mix32(unsigned int h)
+{
+ h ^= 0x2e63823a; h += LROT(h, 15); h -= LROT(h, 9);
+ h += LROT(h, 4); h -= LROT(h, 1); h ^= LROT(h, 2);
+ return h;
+}
+static unsigned int hash32(const unsigned char* in, int len)
+{
+ unsigned int h = len, val = 0;
+ int i, count = 0;
+ for(i=0; i<len; i++) {
+ val = (val<<8) ^ in[i];
+ if(++count == 4) {
+ h = mix32(h ^ val);
+ val = count = 0;