simgear/nasal/hash.c

   1 #include "nasal.h"
   2 #include "data.h"
   3
   4 static void realloc(naRef hash)
   5 {
   6     struct naHash* h = hash.ref.ptr.hash;
   7     int i, sz, oldsz = h->size;
   8     int oldcols = h->table ? 1 << h->lgalloced : 0;
   9
  10     // Keep a handle to our original objects
  11     struct HashNode* oldnodes = h->nodes;
  12     struct HashNode** oldtable = h->table;
  13
  14     // Figure out how big we need to be (start with a minimum size of
  15     // 16 entries)
  16     for(i=3; 1<<i < oldsz; i++);
  17     h->lgalloced = i+1;
  18
  19     // Allocate new ones (note that all the records are allocated in a
  20     // single chunk, to avoid zillions of tiny node allocations)
  21     sz = 1<<h->lgalloced;
  22     h->nodes = naAlloc(sz * (sizeof(struct HashNode) + sizeof(void*)));
  23     h->table = (struct HashNode**)(((char*)h->nodes) + sz*sizeof(struct HashNode));
  24     naBZero(h->table, sz * sizeof(void*));
  25     h->nextnode = 0;
  26     h->size = 0;
  27
  28     // Re-insert everything from scratch
  29     for(i=0; i<oldcols; i++) {
  30         struct HashNode* hn = oldtable[i];
  31         while(hn) {
  32             naHash_set(hash, hn->key, hn->val);
  33             hn = hn->next;
  34         }
  35     }
  36
  37     // Free the old memory
  38     naFree(oldnodes);
  39 }
  40
  41 // Computes a hash code for a given scalar
  42 static unsigned int hashcode(naRef r)
  43 {
  44     if(IS_NUM(r))
  45     {
  46         // Numbers get the number as a hash.  Just use the bits and
  47         // xor them together.  Note assumption that sizeof(double) >=
  48         // 2*sizeof(int).
  49         unsigned int* p = (unsigned int*)&(r.num);
  50         return p[0] ^ p[1];
  51     } else {
  52         // This is Daniel Bernstein's djb2 hash function that I found
  53         // on the web somewhere.  It appears to work pretty well.
  54         unsigned int i, hash = 5831;
  55         for(i=0; i<r.ref.ptr.str->len; i++)
  56             hash = (hash * 33) ^ r.ref.ptr.str->data[i];
  57         return hash;
  58     }
  59 }
  60
  61 // Which column in a given hash does the key correspond to.
  62 static unsigned int hashcolumn(struct naHash* h, naRef key)
  63 {
  64     // Multiply by a big number, and take the top N bits.  Note
  65     // assumption that sizeof(unsigned int) == 4.
  66     return (2654435769u * hashcode(key)) >> (32 - h->lgalloced);
  67 }
  68
  69 struct HashNode* find(struct naHash* h, naRef key)
  70 {
  71     struct HashNode* hn;
  72     if(h->table == 0)
  73         return 0;
  74     hn = h->table[hashcolumn(h, key)];
  75     while(hn) {
  76         if(naEqual(key, hn->key))
  77             return hn;
  78         hn = hn->next;
  79     }
  80     return 0;
  81 }
  82
  83 void naHash_init(naRef hash)
  84 {
  85     struct naHash* h = hash.ref.ptr.hash;
  86     h->size = 0;
  87     h->lgalloced = 0;
  88     h->table = 0;
  89     h->nodes = 0;
  90 }
  91
  92 // Make a temporary string on the stack
  93 static naRef tmpStr(struct naStr* str, char* key)
  94 {
  95     char* p = key;
  96     while(*p) { p++; }
  97     str->len = p - key;
  98     str->data = key;
  99     return naObj(T_STR, (struct naObj*)str);
 100 }
 101
 102 naRef naHash_cget(naRef hash, char* key)
 103 {
 104     struct naStr str;
 105     naRef result, key2 = tmpStr(&str, key);
 106     if(naHash_get(hash, key2, &result))
 107         return result;
 108     return naNil();
 109 }
 110
 111 void naHash_cset(naRef hash, char* key, naRef val)
 112 {
 113     struct naStr str;
 114     naRef key2 = tmpStr(&str, key);
 115     naHash_tryset(hash, key2, val);
 116 }
 117
 118 int naHash_get(naRef hash, naRef key, naRef* out)
 119 {
 120     struct naHash* h = hash.ref.ptr.hash;
 121     struct HashNode* n;
 122     if(!IS_HASH(hash)) return 0;
 123     n = find(h, key);
 124     if(n) {
 125         *out = n->val;
 126         return 1;
 127     } else {
 128         *out = naNil();
 129         return 0;
 130     }
 131 }
 132
 133 // Simpler version.  Don't create a new node if the value isn't there
 134 int naHash_tryset(naRef hash, naRef key, naRef val)
 135 {
 136     struct HashNode* n;
 137     if(!IS_HASH(hash)) return 0;
 138     n = find(hash.ref.ptr.hash, key);
 139     if(n) n->val = val;
 140     return n != 0;
 141 }
 142
 143 void naHash_set(naRef hash, naRef key, naRef val)
 144 {
 145     struct naHash* h = hash.ref.ptr.hash;
 146     unsigned int col;
 147     struct HashNode* n;
 148
 149     if(!IS_HASH(hash)) return;
 150
 151     n = find(h, key);
 152     if(n) {
 153         n->val = val;
 154         return;
 155     }
 156
 157     if(h->size+1 >= 1<<h->lgalloced)
 158         realloc(hash);
 159
 160     col = hashcolumn(h, key);
 161     n = h->nodes + h->nextnode++;
 162     n->key = key;
 163     n->val = val;
 164     n->next = h->table[col];
 165     h->table[col] = n;
 166     h->size++;
 167 }
 168
 169 // FIXME: this implementation does a realloc() after each delete, and
 170 // is therefore needlessly O(N).  (The reason is that this avoids the
 171 // need to keep a free list around for the much more common case of
 172 // adding a new value.  Modifying an existing value is O(1), of
 173 // course.)
 174 void naHash_delete(naRef hash, naRef key)
 175 {
 176     struct naHash* h = hash.ref.ptr.hash;
 177     int col;
 178     struct HashNode *last=0, *hn;
 179     if(!IS_HASH(hash)) return;
 180     col = hashcolumn(h, key);
 181     hn = h->table[col];
 182     while(hn) {
 183         if(naEqual(hn->key, key)) {
 184             if(last == 0) h->table[col] = hn->next;
 185             else last->next = hn->next;
 186             h->size--;
 187             realloc(hash);
 188             return;
 189         }
 190         last = hn;
 191         hn = hn->next;
 192     }
 193 }
 194
 195 void naHash_keys(naRef dst, naRef hash)
 196 {
 197     struct naHash* h = hash.ref.ptr.hash;
 198     int i;
 199     if(!IS_HASH(hash) || !h->table) return;
 200     for(i=0; i<(1<<h->lgalloced); i++) {
 201         struct HashNode* hn = h->table[i];
 202         while(hn) {
 203             naVec_append(dst, hn->key);
 204             hn = hn->next;
 205         }
 206     }
 207 }
 208
 209 int naHash_size(naRef h)
 210 {
 211     if(!IS_HASH(h)) return 0;
 212     return h.ref.ptr.hash->size;
 213 }
 214
 215 void naHash_gcclean(struct naHash* h)
 216 {
 217     naFree(h->nodes);
 218     h->nodes = 0;
 219     h->size = 0;
 220     h->lgalloced = 0;
 221     h->table = 0;
 222     h->nextnode = 0;
 223 }