simgear/nasal/hash.c

   1 #include <string.h>
   2 #include "nasal.h"
   3 #include "data.h"
   4
   5 /* A HashRec lives in a single allocated block.  The layout is the
   6  * header struct, then a table of 2^lgsz hash entries (key/value
   7  * pairs), then an index table of 2*2^lgsz integers storing index
   8  * values into the entry table.  There are two tokens needed for
   9  * "unused" and "used but empty". */
  10
  11 #define ENT_EMPTY -1
  12 #define ENT_DELETED -2
  13
  14 typedef struct { naRef key, val; } HashEnt;
  15
  16 typedef struct HashRec {
  17     int size; /* number of active entries */
  18     int lgsz; /* base-2 logarithm of the allocated (!) size */
  19     int next; /* next entry to use */
  20 } HashRec;
  21
  22 #define REC(h) (PTR(h).hash->rec)
  23 #define POW2(n) (1<<(n))
  24 #define NCELLS(hr) (2*POW2((hr)->lgsz))
  25 #define ROUNDUPOFF(n,m) ((((n)+(m-1))/m)*m)-(n)
  26 #define ALIGN(p,sz) (((char*)p)+ROUNDUPOFF(((size_t)p)%sz,sz))
  27 #define ENTS(h) ((HashEnt*)ALIGN(&((HashRec*)h)[1],sizeof(naRef)))
  28 #define TAB(h) ((int*)&(ENTS(h)[1<<(h)->lgsz]))
  29 #define HBITS(hr,code) ((hr)->lgsz ? ((code)>>(32-(hr)->lgsz)) : 0)
  30
  31 #define LROT(h,n) (((h)<<n)|((h)>>((8*sizeof(h))-n)))
  32 static unsigned int mix32(unsigned int h)
  33 {
  34     h ^= 0x2e63823a;  h += LROT(h, 15); h -= LROT(h, 9);
  35     h += LROT(h, 4);  h -= LROT(h, 1);  h ^= LROT(h, 2);
  36     return h;
  37 }
  38 static unsigned int hash32(const unsigned char* in, int len)
  39 {
  40     unsigned int h = len, val = 0;
  41     int i, count = 0;
  42     for(i=0; i<len; i++) {
  43         val = (val<<8) ^ in[i];
  44         if(++count == 4) {
  45             h = mix32(h ^ val);
  46             val = count = 0;
  47         }
  48     }
  49     return mix32(h ^ val);
  50 }
  51
  52 static unsigned int refhash(naRef key)
  53 {
  54     if(IS_STR(key)) {
  55         struct naStr* s = PTR(key).str;
  56         if(s->hashcode) return s->hashcode;
  57         return s->hashcode = hash32((void*)naStr_data(key), naStr_len(key));
  58     } else { /* must be a number */
  59         union { double d; unsigned int u[2]; } n;
  60         n.d = key.num == -0.0 ? 0.0 : key.num; /* remember negative zero! */
  61         return mix32(mix32(n.u[0]) ^ n.u[1]);
  62     }
  63 }
  64
  65 static int equal(naRef a, naRef b)
  66 {
  67     if(IS_NUM(a)) return a.num == b.num;
  68     if(PTR(a).obj == PTR(b).obj) return 1;
  69     if(naStr_len(a) != naStr_len(b)) return 0;
  70     return memcmp(naStr_data(a), naStr_data(b), naStr_len(a)) == 0;
  71 }
  72
  73 /* Returns the index of a cell that either contains a matching key, or
  74  * is the empty slot to receive a new insertion. */
  75 static int findcell(struct HashRec *hr, naRef key, unsigned int hash)
  76 {
  77     int i, mask = POW2(hr->lgsz+1)-1, step = (2*hash+1) & mask;
  78     for(i=HBITS(hr,hash); TAB(hr)[i] != ENT_EMPTY; i=(i+step)&mask)
  79         if(TAB(hr)[i] != ENT_DELETED && equal(key, ENTS(hr)[TAB(hr)[i]].key))
  80             break;
  81     return i;
  82 }
  83
  84 static void hashset(HashRec* hr, naRef key, naRef val)
  85 {
  86     int ent, cell = findcell(hr, key, refhash(key));
  87     if((ent = TAB(hr)[cell]) == ENT_EMPTY) {
  88         ent = hr->next++;
  89         if(ent >= NCELLS(hr)) return; /* race protection, don't overrun */
  90         TAB(hr)[cell] = ent;
  91         hr->size++;
  92         ENTS(hr)[ent].key = key;
  93     }
  94     ENTS(hr)[ent].val = val;
  95 }
  96
  97 static int recsize(int lgsz)
  98 {
  99     HashRec hr;
 100     hr.lgsz = lgsz;
 101     return (int)((char*)&TAB(&hr)[POW2(lgsz+1)] - (char*)&hr) + sizeof(naRef);
 102 }
 103
 104 static HashRec* resize(struct naHash* hash)
 105 {
 106     HashRec *hr = hash->rec, *hr2;
 107     int i, lgsz = 0;
 108     if(hr) {
 109         int oldsz = hr->size;
 110         while(oldsz) { oldsz >>= 1; lgsz++; }
 111     }
 112     hr2 = naAlloc(recsize(lgsz));
 113     hr2->size = hr2->next = 0;
 114     hr2->lgsz = lgsz;
 115     for(i=0; i<(2*(1<<lgsz)); i++)
 116         TAB(hr2)[i] = ENT_EMPTY;
 117     for(i=0; hr && i < POW2(hr->lgsz+1); i++)
 118         if(TAB(hr)[i] >= 0)
 119             hashset(hr2, ENTS(hr)[TAB(hr)[i]].key, ENTS(hr)[TAB(hr)[i]].val);
 120     naGC_swapfree((void*)&hash->rec, hr2);
 121     return hr2;
 122 }
 123
 124 int naHash_size(naRef h) { return REC(h) ? REC(h)->size : 0; }
 125
 126 int naHash_get(naRef hash, naRef key, naRef* out)
 127 {
 128     HashRec* hr = REC(hash);
 129     if(hr) {
 130         int ent, cell = findcell(hr, key, refhash(key));
 131         if((ent = TAB(hr)[cell]) < 0) return 0;
 132         *out = ENTS(hr)[ent].val;
 133         return 1;
 134     }
 135     return 0;
 136 }
 137
 138 void naHash_set(naRef hash, naRef key, naRef val)
 139 {
 140     HashRec* hr = REC(hash);
 141     if(!hr || hr->next >= POW2(hr->lgsz))
 142         hr = resize(PTR(hash).hash);
 143     hashset(hr, key, val);
 144 }
 145
 146 void naHash_delete(naRef hash, naRef key)
 147 {
 148     HashRec* hr = REC(hash);
 149     if(hr) {
 150         int cell = findcell(hr, key, refhash(key));
 151         if(TAB(hr)[cell] >= 0) {
 152             TAB(hr)[cell] = ENT_DELETED;
 153             if(--hr->size < POW2(hr->lgsz-1))
 154                 resize(PTR(hash).hash);
 155         }
 156     }
 157 }
 158
 159 void naHash_keys(naRef dst, naRef hash)
 160 {
 161     int i;
 162     HashRec* hr = REC(hash);
 163     for(i=0; hr && i < NCELLS(hr); i++)
 164         if(TAB(hr)[i] >= 0)
 165             naVec_append(dst, ENTS(hr)[TAB(hr)[i]].key);
 166 }
 167
 168 void naiGCMarkHash(naRef hash)
 169 {
 170     int i;
 171     HashRec* hr = REC(hash);
 172     for(i=0; hr && i < NCELLS(hr); i++)
 173         if(TAB(hr)[i] >= 0) {
 174             naiGCMark(ENTS(hr)[TAB(hr)[i]].key);
 175             naiGCMark(ENTS(hr)[TAB(hr)[i]].val);
 176         }
 177 }
 178
 179 static void tmpStr(naRef* out, struct naStr* str, const char* key)
 180 {
 181     str->type = T_STR;
 182     str->hashcode = str->emblen = 0;
 183     str->data.ref.ptr = (unsigned char*)key;
 184     str->data.ref.len = strlen(key);
 185     SETPTR(*out, str);
 186 }
 187
 188 int naMember_cget(naRef obj, const char* field, naRef* out)
 189 {
 190     naRef key; struct naStr str;
 191     tmpStr(&key, &str, field);
 192     return naMember_get(obj, key, out);
 193 }
 194
 195 naRef naHash_cget(naRef hash, char* key)
 196 {
 197     struct naStr str;
 198     naRef result, key2;
 199     tmpStr(&key2, &str, key);
 200     return naHash_get(hash, key2, &result) ? result : naNil();
 201 }
 202
 203 void naHash_cset(naRef hash, char* key, naRef val)
 204 {
 205     naRef key2; struct naStr str;
 206     tmpStr(&key2, &str, key);
 207     naiHash_tryset(hash, key2, val);
 208 }
 209
 210 int naiHash_tryset(naRef hash, naRef key, naRef val)
 211 {
 212     HashRec* hr = REC(hash);
 213     if(hr) {
 214         int ent, cell = findcell(hr, key, refhash(key));
 215         if((ent = TAB(hr)[cell]) >= 0) { ENTS(hr)[ent].val = val; return 1; }
 216     }
 217     return 0;
 218 }
 219
 220 void naiGCHashClean(struct naHash* h)
 221 {
 222     naFree(h->rec);
 223     h->rec = 0;
 224 }
 225
 226 /* Optimized naHash_get for looking up local variables (OP_LOCAL is by
 227  * far the most common opcode and deserves some special case
 228  * optimization).  Assumes that the key is an interned symbol
 229  * (i.e. the hash code is precomputed, and we only need to test for
 230  * pointer identity). */
 231 int naiHash_sym(struct naHash* hash, struct naStr* sym, naRef* out)
 232 {
 233     HashRec* hr = hash->rec;
 234     if(hr) {
 235         int* tab = TAB(hr);
 236         HashEnt* ents = ENTS(hr);
 237         unsigned int hc = sym->hashcode;
 238         int cell, mask = POW2(hr->lgsz+1) - 1, step = (2*hc+1) & mask;
 239         for(cell=HBITS(hr,hc); tab[cell] != ENT_EMPTY; cell=(cell+step)&mask)
 240             if(tab[cell]!=ENT_DELETED && sym==PTR(ents[tab[cell]].key).str) {
 241                 *out = ents[tab[cell]].val;
 242                 return 1;
 243             }
 244     }
 245     return 0;
 246 }
 247
 248
 249 /* As above, a special naHash_set for setting local variables.
 250  * Assumes that the key is interned, and also that it isn't already
 251  * present in the hash. */
 252 void naiHash_newsym(struct naHash* hash, naRef* sym, naRef* val)
 253 {
 254     HashRec* hr = hash->rec;
 255     int mask, step, cell, ent;
 256     struct naStr *s = PTR(*sym).str;
 257     if(!hr || hr->next >= POW2(hr->lgsz))
 258         hr = resize(hash);
 259     mask = POW2(hr->lgsz+1) - 1;
 260     step = (2*s->hashcode+1) & mask;
 261     cell = HBITS(hr, s->hashcode);
 262     while(TAB(hr)[cell] != ENT_EMPTY)
 263         cell = (cell + step) & mask;
 264     ent = hr->next++;
 265     if(ent >= NCELLS(hr)) return; /* race protection, don't overrun */
 266     TAB(hr)[cell] = ent;
 267     hr->size++;
 268     ENTS(hr)[TAB(hr)[cell]].key = *sym;
 269     ENTS(hr)[TAB(hr)[cell]].val = *val;
 270 }
 271