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* realloc(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     for(lga=0; 1<<lga <= need; lga++);
  58     cols = 1<<lga;
  59     h = naAlloc(sizeof(struct HashRec) +
  60                 cols * (sizeof(struct HashNode*) + sizeof(struct HashNode)));
  61     naBZero(h, sizeof(struct HashRec) + cols * sizeof(struct HashNode*));
  62
  63     h->lgalloced = lga;
  64     h->nodes = (struct HashNode*)(((char*)h)
  65                                   + sizeof(struct HashRec)
  66                                   + cols * sizeof(struct HashNode*));
  67     for(lga=0; h0 != 0 && lga<(1<<h0->lgalloced); lga++) {
  68         struct HashNode* hn = h0->table[lga];
  69         while(hn) {
  70             INSERT(h, hn->key, hn->val, hashcolumn(h, hn->key));
  71             hn = hn->next;
  72         }
  73     }
  74     naGC_swapfree((void**)&hash->rec, h);
  75     return h;
  76 }
  77
  78 // Special, optimized version of naHash_get for the express purpose of
  79 // looking up symbols in the local variables hash (OP_LOCAL is by far
  80 // the most common opcode and deserves some special case
  81 // optimization).  Elides all the typing checks that are normally
  82 // required, presumes that the key is a string and has had its
  83 // hashcode precomputed, checks only for object identity, and inlines
  84 // the column computation.
  85 int naHash_sym(struct naHash* hash, struct naStr* sym, naRef* out)
  86 {
  87     struct HashRec* h = hash->rec;
  88     if(h) {
  89         int col = (HASH_MAGIC * sym->hashcode) >> (32 - h->lgalloced);
  90         struct HashNode* hn = h->table[col];
  91         while(hn) {
  92             if(hn->key.ref.ptr.str == sym) {
  93                 *out = hn->val;
  94                 return 1;
  95             }
  96             hn = hn->next;
  97         }
  98     }
  99     return 0;
 100 }
 101
 102 static struct HashNode* find(struct naHash* hash, naRef key)
 103 {
 104     struct HashRec* h = hash->rec;
 105     if(h) {
 106         struct HashNode* hn = h->table[hashcolumn(h, key)];
 107         while(hn) {
 108             if(EQUAL(key, hn->key))
 109                 return hn;
 110             hn = hn->next;
 111         }
 112     }
 113     return 0;
 114 }
 115
 116 // Make a temporary string on the stack
 117 static void tmpStr(naRef* out, struct naStr* str, char* key)
 118 {
 119     str->len = 0;
 120     str->data = key;
 121     while(key[str->len]) str->len++;
 122     *out = naNil();
 123     out->ref.ptr.str = str;
 124 }
 125
 126 naRef naHash_cget(naRef hash, char* key)
 127 {
 128     struct naStr str;
 129     naRef result, key2;
 130     tmpStr(&key2, &str, key);
 131     if(naHash_get(hash, key2, &result))
 132         return result;
 133     return naNil();
 134 }
 135
 136 void naHash_cset(naRef hash, char* key, naRef val)
 137 {
 138     struct naStr str;
 139     naRef key2;
 140     tmpStr(&key2, &str, key);
 141     naHash_tryset(hash, key2, val);
 142 }
 143
 144 int naHash_get(naRef hash, naRef key, naRef* out)
 145 {
 146     if(IS_HASH(hash)) {
 147         struct HashNode* n = find(hash.ref.ptr.hash, key);
 148         if(n) { *out = n->val; return 1; }
 149     }
 150     return 0;
 151 }
 152
 153 // Simpler version.  Don't create a new node if the value isn't there
 154 int naHash_tryset(naRef hash, naRef key, naRef val)
 155 {
 156     if(IS_HASH(hash)) {
 157         struct HashNode* n = find(hash.ref.ptr.hash, key);
 158         if(n) n->val = val;
 159         return n != 0;
 160     }
 161     return 0;
 162 }
 163
 164 // Special purpose optimization for use in function call setups.  Sets
 165 // a value that is known *not* to be present in the hash table.  As
 166 // for naHash_sym, the key must be a string with a precomputed hash
 167 // code.
 168 void naHash_newsym(struct naHash* hash, naRef* sym, naRef* val)
 169 {
 170     int col;
 171     struct HashRec* h = hash->rec;
 172     if(!h || h->size >= 1<<h->lgalloced)
 173         h = realloc(hash);
 174     col = (HASH_MAGIC * sym->ref.ptr.str->hashcode) >> (32 - h->lgalloced);
 175     INSERT(h, *sym, *val, col);
 176 }
 177
 178 // The cycle check is an integrity requirement for multithreading,
 179 // where raced inserts can potentially cause cycles.  This ensures
 180 // that the "last" thread to hold a reference to an inserted node
 181 // breaks any cycles that might have happened (at the expense of
 182 // potentially dropping items out of the hash).  Under normal
 183 // circumstances, chains will be very short and this will be fast.
 184 static void chkcycle(struct HashNode* node, int count)
 185 {
 186     struct HashNode* hn = node;
 187     while(hn && (hn = hn->next) != 0)
 188         if(count-- <= 0) { node->next = 0; return; }
 189 }
 190
 191 void naHash_set(naRef hash, naRef key, naRef val)
 192 {
 193     int col;
 194     struct HashRec* h;
 195     struct HashNode* n;
 196     if(!IS_HASH(hash)) return;
 197     if((n = find(hash.ref.ptr.hash, key))) { n->val = val; return; }
 198     h = hash.ref.ptr.hash->rec;
 199     while(!h || h->size >= 1<<h->lgalloced)
 200         h = realloc(hash.ref.ptr.hash);
 201     col = hashcolumn(h, key);
 202     INSERT(h, key, val, hashcolumn(h, key));
 203     chkcycle(h->table[col], h->size - h->dels);
 204 }
 205
 206 void naHash_delete(naRef hash, naRef key)
 207 {
 208     struct HashRec* h = hash.ref.ptr.hash->rec;
 209     int col;
 210     struct HashNode *last=0, *hn;
 211     if(!IS_HASH(hash) || !h) return;
 212     col = hashcolumn(h, key);
 213     hn = h->table[col];
 214     while(hn) {
 215         if(EQUAL(hn->key, key)) {
 216             if(last == 0) h->table[col] = hn->next;
 217             else last->next = hn->next;
 218             h->dels++;
 219             return;
 220         }
 221         last = hn;
 222         hn = hn->next;
 223     }
 224 }
 225
 226 void naHash_keys(naRef dst, naRef hash)
 227 {
 228     int i;
 229     struct HashRec* h = hash.ref.ptr.hash->rec;
 230     if(!IS_HASH(hash) || !h) return;
 231     for(i=0; i<(1<<h->lgalloced); i++) {
 232         struct HashNode* hn = h->table[i];
 233         while(hn) {
 234             naVec_append(dst, hn->key);
 235             hn = hn->next;
 236         }
 237     }
 238 }
 239
 240 int naHash_size(naRef hash)
 241 {
 242     struct HashRec* h = hash.ref.ptr.hash->rec;
 243     if(!IS_HASH(hash) || !h) return 0;
 244     return h->size - h->dels;
 245 }
 246
 247 void naHash_gcclean(struct naHash* h)
 248 {
 249     naFree(h->rec);
 250     h->rec = 0;
 251 }