simgear/nasal/hash.c

   1 #include "nasal.h"
   2 #include "data.h"
   3
   4 #define MIN_HASH_SIZE 4
   5
   6 #define EQUAL(a, b) (((a).ref.reftag == (b).ref.reftag \
   7                       && (a).ref.ptr.obj == (b).ref.ptr.obj) \
   8                      || naEqual(a, b))
   9
  10 #define HASH_MAGIC 2654435769u
  11
  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;                              \
  19         }} while(0)
  20
  21 // Computes a hash code for a given scalar
  22 static unsigned int hashcode(naRef r)
  23 {
  24     if(IS_NUM(r))
  25     {
  26         // Numbers get the number as a hash.  Just use the bits and
  27         // xor them together.  Note assumption that sizeof(double) >=
  28         // 2*sizeof(int).
  29         unsigned int* p = (unsigned int*)&(r.num);
  30         return p[0] ^ p[1];
  31     } else if(r.ref.ptr.str->hashcode) {
  32         return r.ref.ptr.str->hashcode;
  33     } else {
  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;
  40         return hash;
  41     }
  42 }
  43
  44 // Which column in a given hash does the key correspond to.
  45 static unsigned int hashcolumn(struct HashRec* h, naRef key)
  46 {
  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);
  50 }
  51
  52 static struct HashRec* resize(struct naHash* hash)
  53 {
  54     struct HashRec *h, *h0 = hash->rec;
  55     int lga, cols, need = h0 ? h0->size - h0->dels : MIN_HASH_SIZE;
  56
  57     if(need < MIN_HASH_SIZE) need = MIN_HASH_SIZE;
  58     for(lga=0; 1<<lga <= need; lga++);
  59     cols = 1<<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*));
  63
  64     h->lgalloced = lga;
  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];
  70         while(hn) {
  71             INSERT(h, hn->key, hn->val, hashcolumn(h, hn->key));
  72             hn = hn->next;
  73         }
  74     }
  75     naGC_swapfree((void**)&hash->rec, h);
  76     return h;
  77 }
  78
  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)
  87 {
  88     struct HashRec* h = hash->rec;
  89     if(h) {
  90         int col = (HASH_MAGIC * sym->hashcode) >> (32 - h->lgalloced);
  91         struct HashNode* hn = h->table[col];
  92         while(hn) {
  93             if(hn->key.ref.ptr.str == sym) {
  94                 *out = hn->val;
  95                 return 1;
  96             }
  97             hn = hn->next;
  98         }
  99     }
 100     return 0;
 101 }
 102
 103 static struct HashNode* find(struct naHash* hash, naRef key)
 104 {
 105     struct HashRec* h = hash->rec;
 106     if(h) {
 107         struct HashNode* hn = h->table[hashcolumn(h, key)];
 108         while(hn) {
 109             if(EQUAL(key, hn->key))
 110                 return hn;
 111             hn = hn->next;
 112         }
 113     }
 114     return 0;
 115 }
 116
 117 // Make a temporary string on the stack
 118 static void tmpStr(naRef* out, struct naStr* str, char* key)
 119 {
 120     str->len = 0;
 121     str->data = (unsigned char*)key;
 122     str->hashcode = 0;
 123     while(key[str->len]) str->len++;
 124     *out = naNil();
 125     out->ref.ptr.str = str;
 126 }
 127
 128 naRef naHash_cget(naRef hash, char* key)
 129 {
 130     struct naStr str;
 131     naRef result, key2;
 132     tmpStr(&key2, &str, key);
 133     if(naHash_get(hash, key2, &result))
 134         return result;
 135     return naNil();
 136 }
 137
 138 void naHash_cset(naRef hash, char* key, naRef val)
 139 {
 140     struct naStr str;
 141     naRef key2;
 142     tmpStr(&key2, &str, key);
 143     naHash_tryset(hash, key2, val);
 144 }
 145
 146 int naHash_get(naRef hash, naRef key, naRef* out)
 147 {
 148     if(IS_HASH(hash)) {
 149         struct HashNode* n = find(hash.ref.ptr.hash, key);
 150         if(n) { *out = n->val; return 1; }
 151     }
 152     return 0;
 153 }
 154
 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)
 157 {
 158     if(IS_HASH(hash)) {
 159         struct HashNode* n = find(hash.ref.ptr.hash, key);
 160         if(n) n->val = val;
 161         return n != 0;
 162     }
 163     return 0;
 164 }
 165
 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
 169 // code.
 170 void naHash_newsym(struct naHash* hash, naRef* sym, naRef* val)
 171 {
 172     int col;
 173     struct HashRec* h = hash->rec;
 174     while(!h || h->size >= 1<<h->lgalloced)
 175         h = resize(hash);
 176     col = (HASH_MAGIC * sym->ref.ptr.str->hashcode) >> (32 - h->lgalloced);
 177     INSERT(h, *sym, *val, col);
 178 }
 179
 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)
 187 {
 188     struct HashNode* hn = node;
 189     while(hn && (hn = hn->next) != 0)
 190         if(count-- <= 0) { node->next = 0; return; }
 191 }
 192
 193 void naHash_set(naRef hash, naRef key, naRef val)
 194 {
 195     int col;
 196     struct HashRec* h;
 197     struct HashNode* n;
 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);
 206 }
 207
 208 void naHash_delete(naRef hash, naRef key)
 209 {
 210     struct HashRec* h = hash.ref.ptr.hash->rec;
 211     int col;
 212     struct HashNode *last=0, *hn;
 213     if(!IS_HASH(hash) || !h) return;
 214     col = hashcolumn(h, key);
 215     hn = h->table[col];
 216     while(hn) {
 217         if(EQUAL(hn->key, key)) {
 218             if(last == 0) h->table[col] = hn->next;
 219             else last->next = hn->next;
 220             h->dels++;
 221             return;
 222         }
 223         last = hn;
 224         hn = hn->next;
 225     }
 226 }
 227
 228 void naHash_keys(naRef dst, naRef hash)
 229 {
 230     int i;
 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];
 235         while(hn) {
 236             naVec_append(dst, hn->key);
 237             hn = hn->next;
 238         }
 239     }
 240 }
 241
 242 int naHash_size(naRef hash)
 243 {
 244     struct HashRec* h = hash.ref.ptr.hash->rec;
 245     if(!IS_HASH(hash) || !h) return 0;
 246     return h->size - h->dels;
 247 }
 248
 249 void naHash_gcclean(struct naHash* h)
 250 {
 251     naFree(h->rec);
 252     h->rec = 0;
 253 }