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* realloc(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;
122 while(key[str->len]) str->len++;
124 out->ref.ptr.str = str;
127 naRef naHash_cget(naRef hash, char* key)
131 tmpStr(&key2, &str, key);
132 if(naHash_get(hash, key2, &result))
137 void naHash_cset(naRef hash, char* key, naRef val)
141 tmpStr(&key2, &str, key);
142 naHash_tryset(hash, key2, val);
145 int naHash_get(naRef hash, naRef key, naRef* out)
148 struct HashNode* n = find(hash.ref.ptr.hash, key);
149 if(n) { *out = n->val; return 1; }
154 // Simpler version. Don't create a new node if the value isn't there
155 int naHash_tryset(naRef hash, naRef key, naRef val)
158 struct HashNode* n = find(hash.ref.ptr.hash, key);
165 // Special purpose optimization for use in function call setups. Sets
166 // a value that is known *not* to be present in the hash table. As
167 // for naHash_sym, the key must be a string with a precomputed hash
169 void naHash_newsym(struct naHash* hash, naRef* sym, naRef* val)
172 struct HashRec* h = hash->rec;
173 while(!h || h->size >= 1<<h->lgalloced)
175 col = (HASH_MAGIC * sym->ref.ptr.str->hashcode) >> (32 - h->lgalloced);
176 INSERT(h, *sym, *val, col);
179 // The cycle check is an integrity requirement for multithreading,
180 // where raced inserts can potentially cause cycles. This ensures
181 // that the "last" thread to hold a reference to an inserted node
182 // breaks any cycles that might have happened (at the expense of
183 // potentially dropping items out of the hash). Under normal
184 // circumstances, chains will be very short and this will be fast.
185 static void chkcycle(struct HashNode* node, int count)
187 struct HashNode* hn = node;
188 while(hn && (hn = hn->next) != 0)
189 if(count-- <= 0) { node->next = 0; return; }
192 void naHash_set(naRef hash, naRef key, naRef val)
197 if(!IS_HASH(hash)) return;
198 if((n = find(hash.ref.ptr.hash, key))) { n->val = val; return; }
199 h = hash.ref.ptr.hash->rec;
200 while(!h || h->size >= 1<<h->lgalloced)
201 h = realloc(hash.ref.ptr.hash);
202 col = hashcolumn(h, key);
203 INSERT(h, key, val, hashcolumn(h, key));
204 chkcycle(h->table[col], h->size - h->dels);
207 void naHash_delete(naRef hash, naRef key)
209 struct HashRec* h = hash.ref.ptr.hash->rec;
211 struct HashNode *last=0, *hn;
212 if(!IS_HASH(hash) || !h) return;
213 col = hashcolumn(h, key);
216 if(EQUAL(hn->key, key)) {
217 if(last == 0) h->table[col] = hn->next;
218 else last->next = hn->next;
227 void naHash_keys(naRef dst, naRef hash)
230 struct HashRec* h = hash.ref.ptr.hash->rec;
231 if(!IS_HASH(hash) || !h) return;
232 for(i=0; i<(1<<h->lgalloced); i++) {
233 struct HashNode* hn = h->table[i];
235 naVec_append(dst, hn->key);
241 int naHash_size(naRef hash)
243 struct HashRec* h = hash.ref.ptr.hash->rec;
244 if(!IS_HASH(hash) || !h) return 0;
245 return h->size - h->dels;
248 void naHash_gcclean(struct naHash* h)