4 #define MIN_HASH_SIZE 4
6 #define EQUAL(a, b) (((a).ref.reftag == (b).ref.reftag \
7 && (a).ref.ptr.obj == (b).ref.ptr.obj) \
10 #define HASH_MAGIC 2654435769u
12 #define INSERT(hh, hkey, hval, hcol) do { \
13 unsigned int cc = (hcol), iidx=(hh)->size++; \
14 if(iidx < (1<<(hh)->lgalloced)) { \
15 struct HashNode* hnn = &(hh)->nodes[iidx]; \
16 hnn->key = (hkey); hnn->val = (hval); \
17 hnn->next = (hh)->table[cc]; \
18 (hh)->table[cc] = hnn; \
21 // Computes a hash code for a given scalar
22 static unsigned int hashcode(naRef r)
26 // Numbers get the number as a hash. Just use the bits and
27 // xor them together. Note assumption that sizeof(double) >=
29 unsigned int* p = (unsigned int*)&(r.num);
31 } else if(r.ref.ptr.str->hashcode) {
32 return r.ref.ptr.str->hashcode;
34 // This is Daniel Bernstein's djb2 hash function that I found
35 // on the web somewhere. It appears to work pretty well.
36 unsigned int i, hash = 5831;
37 for(i=0; i<r.ref.ptr.str->len; i++)
38 hash = (hash * 33) ^ r.ref.ptr.str->data[i];
39 r.ref.ptr.str->hashcode = hash;
44 // Which column in a given hash does the key correspond to.
45 static unsigned int hashcolumn(struct HashRec* h, naRef key)
47 // Multiply by a big number, and take the top N bits. Note
48 // assumption that sizeof(unsigned int) == 4.
49 return (HASH_MAGIC * hashcode(key)) >> (32 - h->lgalloced);
52 static struct HashRec* resize(struct naHash* hash)
54 struct HashRec *h, *h0 = hash->rec;
55 int lga, cols, need = h0 ? h0->size - h0->dels : MIN_HASH_SIZE;
57 if(need < MIN_HASH_SIZE) need = MIN_HASH_SIZE;
58 for(lga=0; 1<<lga <= need; lga++);
60 h = naAlloc(sizeof(struct HashRec) +
61 cols * (sizeof(struct HashNode*) + sizeof(struct HashNode)));
62 naBZero(h, sizeof(struct HashRec) + cols * sizeof(struct HashNode*));
65 h->nodes = (struct HashNode*)(((char*)h)
66 + sizeof(struct HashRec)
67 + cols * sizeof(struct HashNode*));
68 for(lga=0; h0 != 0 && lga<(1<<h0->lgalloced); lga++) {
69 struct HashNode* hn = h0->table[lga];
71 INSERT(h, hn->key, hn->val, hashcolumn(h, hn->key));
75 naGC_swapfree((void**)&hash->rec, h);
79 // Special, optimized version of naHash_get for the express purpose of
80 // looking up symbols in the local variables hash (OP_LOCAL is by far
81 // the most common opcode and deserves some special case
82 // optimization). Elides all the typing checks that are normally
83 // required, presumes that the key is a string and has had its
84 // hashcode precomputed, checks only for object identity, and inlines
85 // the column computation.
86 int naHash_sym(struct naHash* hash, struct naStr* sym, naRef* out)
88 struct HashRec* h = hash->rec;
90 int col = (HASH_MAGIC * sym->hashcode) >> (32 - h->lgalloced);
91 struct HashNode* hn = h->table[col];
93 if(hn->key.ref.ptr.str == sym) {
103 static struct HashNode* find(struct naHash* hash, naRef key)
105 struct HashRec* h = hash->rec;
107 struct HashNode* hn = h->table[hashcolumn(h, key)];
109 if(EQUAL(key, hn->key))
117 // Make a temporary string on the stack
118 static void tmpStr(naRef* out, struct naStr* str, char* key)
121 str->data = (unsigned char*)key;
123 while(key[str->len]) str->len++;
125 out->ref.ptr.str = str;
128 naRef naHash_cget(naRef hash, char* key)
132 tmpStr(&key2, &str, key);
133 if(naHash_get(hash, key2, &result))
138 void naHash_cset(naRef hash, char* key, naRef val)
142 tmpStr(&key2, &str, key);
143 naHash_tryset(hash, key2, val);
146 int naHash_get(naRef hash, naRef key, naRef* out)
149 struct HashNode* n = find(hash.ref.ptr.hash, key);
150 if(n) { *out = n->val; return 1; }
155 // Simpler version. Don't create a new node if the value isn't there
156 int naHash_tryset(naRef hash, naRef key, naRef val)
159 struct HashNode* n = find(hash.ref.ptr.hash, key);
166 // Special purpose optimization for use in function call setups. Sets
167 // a value that is known *not* to be present in the hash table. As
168 // for naHash_sym, the key must be a string with a precomputed hash
170 void naHash_newsym(struct naHash* hash, naRef* sym, naRef* val)
173 struct HashRec* h = hash->rec;
174 while(!h || h->size >= 1<<h->lgalloced)
176 col = (HASH_MAGIC * sym->ref.ptr.str->hashcode) >> (32 - h->lgalloced);
177 INSERT(h, *sym, *val, col);
180 // The cycle check is an integrity requirement for multithreading,
181 // where raced inserts can potentially cause cycles. This ensures
182 // that the "last" thread to hold a reference to an inserted node
183 // breaks any cycles that might have happened (at the expense of
184 // potentially dropping items out of the hash). Under normal
185 // circumstances, chains will be very short and this will be fast.
186 static void chkcycle(struct HashNode* node, int count)
188 struct HashNode* hn = node;
189 while(hn && (hn = hn->next) != 0)
190 if(count-- <= 0) { node->next = 0; return; }
193 void naHash_set(naRef hash, naRef key, naRef val)
198 if(!IS_HASH(hash)) return;
199 if((n = find(hash.ref.ptr.hash, key))) { n->val = val; return; }
200 h = hash.ref.ptr.hash->rec;
201 while(!h || h->size >= 1<<h->lgalloced)
202 h = resize(hash.ref.ptr.hash);
203 col = hashcolumn(h, key);
204 INSERT(h, key, val, hashcolumn(h, key));
205 chkcycle(h->table[col], h->size - h->dels);
208 void naHash_delete(naRef hash, naRef key)
210 struct HashRec* h = hash.ref.ptr.hash->rec;
212 struct HashNode *last=0, *hn;
213 if(!IS_HASH(hash) || !h) return;
214 col = hashcolumn(h, key);
217 if(EQUAL(hn->key, key)) {
218 if(last == 0) h->table[col] = hn->next;
219 else last->next = hn->next;
228 void naHash_keys(naRef dst, naRef hash)
231 struct HashRec* h = hash.ref.ptr.hash->rec;
232 if(!IS_HASH(hash) || !h) return;
233 for(i=0; i<(1<<h->lgalloced); i++) {
234 struct HashNode* hn = h->table[i];
236 naVec_append(dst, hn->key);
242 int naHash_size(naRef hash)
244 struct HashRec* h = hash.ref.ptr.hash->rec;
245 if(!IS_HASH(hash) || !h) return 0;
246 return h->size - h->dels;
249 void naHash_gcclean(struct naHash* h)