4 static void realloc(naRef hash)
6 struct naHash* h = hash.ref.ptr.hash;
7 int i, sz, oldsz = h->size;
8 int oldcols = h->table ? 1 << h->lgalloced : 0;
10 // Keep a handle to our original objects
11 struct HashNode* oldnodes = h->nodes;
12 struct HashNode** oldtable = h->table;
14 // Figure out how big we need to be (start with a minimum size of
16 for(i=3; 1<<i < oldsz; i++);
19 // Allocate new ones (note that all the records are allocated in a
20 // single chunk, to avoid zillions of tiny node allocations)
22 h->nodes = naAlloc(sz * (sizeof(struct HashNode) + sizeof(void*)));
23 h->table = (struct HashNode**)(((char*)h->nodes) + sz*sizeof(struct HashNode));
24 naBZero(h->table, sz * sizeof(void*));
28 // Re-insert everything from scratch
29 for(i=0; i<oldcols; i++) {
30 struct HashNode* hn = oldtable[i];
32 naHash_set(hash, hn->key, hn->val);
37 // Free the old memory
41 // Computes a hash code for a given scalar
42 static unsigned int hashcode(naRef r)
46 // Numbers get the number as a hash. Just use the bits and
47 // xor them together. Note assumption that sizeof(double) >=
49 unsigned int* p = (unsigned int*)&(r.num);
52 // This is Daniel Bernstein's djb2 hash function that I found
53 // on the web somewhere. It appears to work pretty well.
54 unsigned int i, hash = 5831;
55 for(i=0; i<r.ref.ptr.str->len; i++)
56 hash = (hash * 33) ^ r.ref.ptr.str->data[i];
61 // Which column in a given hash does the key correspond to.
62 static unsigned int hashcolumn(struct naHash* h, naRef key)
64 // Multiply by a big number, and take the top N bits. Note
65 // assumption that sizeof(unsigned int) == 4.
66 return (2654435769u * hashcode(key)) >> (32 - h->lgalloced);
69 struct HashNode* find(struct naHash* h, naRef key)
74 hn = h->table[hashcolumn(h, key)];
76 if(naEqual(key, hn->key))
83 void naHash_init(naRef hash)
85 struct naHash* h = hash.ref.ptr.hash;
92 // Make a temporary string on the stack
93 static naRef tmpStr(struct naStr* str, char* key)
99 return naObj(T_STR, (struct naObj*)str);
102 naRef naHash_cget(naRef hash, char* key)
105 naRef result, key2 = tmpStr(&str, key);
106 if(naHash_get(hash, key2, &result))
111 void naHash_cset(naRef hash, char* key, naRef val)
114 naRef key2 = tmpStr(&str, key);
115 naHash_tryset(hash, key2, val);
118 int naHash_get(naRef hash, naRef key, naRef* out)
120 struct naHash* h = hash.ref.ptr.hash;
122 if(!IS_HASH(hash)) return 0;
133 // Simpler version. Don't create a new node if the value isn't there
134 int naHash_tryset(naRef hash, naRef key, naRef val)
137 if(!IS_HASH(hash)) return 0;
138 n = find(hash.ref.ptr.hash, key);
143 void naHash_set(naRef hash, naRef key, naRef val)
145 struct naHash* h = hash.ref.ptr.hash;
149 if(!IS_HASH(hash)) return;
157 if(h->size+1 >= 1<<h->lgalloced)
160 col = hashcolumn(h, key);
161 n = h->nodes + h->nextnode++;
164 n->next = h->table[col];
169 // FIXME: this implementation does a realloc() after each delete, and
170 // is therefore needlessly O(N). (The reason is that this avoids the
171 // need to keep a free list around for the much more common case of
172 // adding a new value. Modifying an existing value is O(1), of
174 void naHash_delete(naRef hash, naRef key)
176 struct naHash* h = hash.ref.ptr.hash;
178 struct HashNode *last=0, *hn;
179 if(!IS_HASH(hash)) return;
180 col = hashcolumn(h, key);
183 if(naEqual(hn->key, key)) {
184 if(last == 0) h->table[col] = hn->next;
185 else last->next = hn->next;
195 void naHash_keys(naRef dst, naRef hash)
197 struct naHash* h = hash.ref.ptr.hash;
199 if(!IS_HASH(hash) || !h->table) return;
200 for(i=0; i<(1<<h->lgalloced); i++) {
201 struct HashNode* hn = h->table[i];
203 naVec_append(dst, hn->key);
209 int naHash_size(naRef h)
211 if(!IS_HASH(h)) return 0;
212 return h.ref.ptr.hash->size;
215 void naHash_gcclean(struct naHash* h)