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* hashrealloc(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     while(key[str->len]) str->len++;
 123     *out = naNil();
 124     out->ref.ptr.str = str;
 125 }
 126
 127 naRef naHash_cget(naRef hash, char* key)
 128 {
 129     struct naStr str;
 130     naRef result, key2;
 131     tmpStr(&key2, &str, key);
 132     if(naHash_get(hash, key2, &result))
 133         return result;
 134     return naNil();
 135 }
 136
 137 void naHash_cset(naRef hash, char* key, naRef val)
 138 {
 139     struct naStr str;
 140     naRef key2;
 141     tmpStr(&key2, &str, key);
 142     naHash_tryset(hash, key2, val);
 143 }
 144
 145 int naHash_get(naRef hash, naRef key, naRef* out)
 146 {
 147     if(IS_HASH(hash)) {
 148         struct HashNode* n = find(hash.ref.ptr.hash, key);
 149         if(n) { *out = n->val; return 1; }
 150     }
 151     return 0;
 152 }
 153
 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)
 156 {
 157     if(IS_HASH(hash)) {
 158         struct HashNode* n = find(hash.ref.ptr.hash, key);
 159         if(n) n->val = val;
 160         return n != 0;
 161     }
 162     return 0;
 163 }
 164
 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
 168 // code.
 169 void naHash_newsym(struct naHash* hash, naRef* sym, naRef* val)
 170 {
 171     int col;
 172     struct HashRec* h = hash->rec;
 173     while(!h || h->size >= 1<<h->lgalloced)
 174         h = hashrealloc(hash);
 175     col = (HASH_MAGIC * sym->ref.ptr.str->hashcode) >> (32 - h->lgalloced);
 176     INSERT(h, *sym, *val, col);
 177 }
 178
 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)
 186 {
 187     struct HashNode* hn = node;
 188     while(hn && (hn = hn->next) != 0)
 189         if(count-- <= 0) { node->next = 0; return; }
 190 }
 191
 192 void naHash_set(naRef hash, naRef key, naRef val)
 193 {
 194     int col;
 195     struct HashRec* h;
 196     struct HashNode* n;
 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 = hashrealloc(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);
 205 }
 206
 207 void naHash_delete(naRef hash, naRef key)
 208 {
 209     struct HashRec* h = hash.ref.ptr.hash->rec;
 210     int col;
 211     struct HashNode *last=0, *hn;
 212     if(!IS_HASH(hash) || !h) return;
 213     col = hashcolumn(h, key);
 214     hn = h->table[col];
 215     while(hn) {
 216         if(EQUAL(hn->key, key)) {
 217             if(last == 0) h->table[col] = hn->next;
 218             else last->next = hn->next;
 219             h->dels++;
 220             return;
 221         }
 222         last = hn;
 223         hn = hn->next;
 224     }
 225 }
 226
 227 void naHash_keys(naRef dst, naRef hash)
 228 {
 229     int i;
 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];
 234         while(hn) {
 235             naVec_append(dst, hn->key);
 236             hn = hn->next;
 237         }
 238     }
 239 }
 240
 241 int naHash_size(naRef hash)
 242 {
 243     struct HashRec* h = hash.ref.ptr.hash->rec;
 244     if(!IS_HASH(hash) || !h) return 0;
 245     return h->size - h->dels;
 246 }
 247
 248 void naHash_gcclean(struct naHash* h)
 249 {
 250     naFree(h->rec);
 251     h->rec = 0;
 252 }