shotgun/lib/hash.c

   1 #include "shotgun/lib/shotgun.h"
   2 #include "shotgun/lib/tuple.h"
   3 #include "shotgun/lib/hash.h"
   4 #include "shotgun/lib/lookuptable.h"
   5
   6 /* MINSIZE MUST be a power of 2 */
   7 #define MINSIZE 16
   8
   9 #define Increments 16
  10
  11 #define find_bin(hash, total) (hash & (total - 1))
  12
  13 OBJECT hash_new(STATE) {
  14   OBJECT hsh;
  15   hsh = hash_allocate(state);
  16   hash_setup(state, hsh, MINSIZE);
  17   return hsh;
  18 }
  19
  20 /* size MUST be a power of 2 */
  21 OBJECT hash_new_sized(STATE, int size) {
  22   OBJECT hsh;
  23   hsh = hash_allocate(state);
  24   hash_setup(state, hsh, size);
  25   return hsh;
  26 }
  27
  28 void hash_setup(STATE, OBJECT hsh, int size) {
  29   int sz;
  30   sz = size == 0 ? MINSIZE : size;
  31   // TODO: Remove @keys field
  32   hash_set_keys(hsh, Qnil);
  33   hash_set_values(hsh, tuple_new(state, sz));
  34   hash_set_bins(hsh, I2N(sz));
  35   hash_set_entries(hsh, I2N(0));
  36   hash_set_default(hsh, Qnil);
  37 }
  38
  39 OBJECT hash_dup(STATE, OBJECT hsh) {
  40   int sz, i;
  41   OBJECT dup, cv, vals, ent, next, lst, tmp;
  42
  43   sz = N2I(hash_get_bins(hsh));
  44   dup = hash_new_sized(state, sz);
  45   SET_CLASS(dup, object_class(state, hsh));
  46
  47   hash_set_bins(dup, I2N(sz));
  48   hash_set_entries(dup, hash_get_entries(hsh));
  49   hash_set_default(dup, hash_get_default(hsh));
  50   // TODO: Remove @keys field
  51   hash_set_keys(dup, Qnil);
  52
  53   cv = hash_get_values(hsh);
  54
  55   vals = tuple_new(state, sz);
  56   hash_set_values(dup, vals);
  57
  58   for(i = 0; i < sz; i++) {
  59     tmp = tuple_at(state, cv, i);
  60     if(NIL_P(tmp)) continue;
  61
  62     ent = tuple_dup(state, tmp);
  63     tuple_put(state, vals, i, ent);
  64
  65     next = tuple_at(state, ent, 3);
  66     lst = ent;
  67     while(!NIL_P(next)) {
  68       next = tuple_dup(state, next);
  69       tuple_put(state, lst, 3, next);
  70       lst = next;
  71       next = tuple_at(state, next, 3);
  72     }
  73   }
  74
  75   return dup;
  76 }
  77
  78 static OBJECT entry_new(STATE, unsigned int hsh, OBJECT key, OBJECT data) {
  79   OBJECT tup = tuple_new(state, 4);
  80   tuple_put(state, tup, 0, I2N(hsh));
  81   tuple_put(state, tup, 1, key);
  82   tuple_put(state, tup, 2, data);
  83   tuple_put(state, tup, 3, Qnil);
  84   return tup;
  85 }
  86
  87 static OBJECT entry_append(STATE, OBJECT top, OBJECT nxt) {
  88   OBJECT cur, last;
  89   int depth = 1;
  90   cur = tuple_at(state, top, 3);
  91   last = top;
  92   while(!NIL_P(cur)) {
  93     last = cur;
  94     cur = tuple_at(state, cur, 3);
  95     depth++;
  96   }
  97
  98   // printf("Inserted new key to hash %d levels deep.\n", depth);
  99   tuple_put(state, last, 3, nxt);
 100   return nxt;
 101 }
 102
 103 static OBJECT add_entry(STATE, OBJECT h, unsigned int hsh, OBJECT ent) {
 104   unsigned int bin, bins;
 105   OBJECT entry;
 106
 107
 108   bins = (unsigned int)N2I(hash_get_bins(h));
 109   bin = find_bin(hsh, bins);
 110
 111   entry = tuple_at(state, hash_get_values(h), bin);
 112
 113   if(NIL_P(entry)) {
 114     tuple_put(state, hash_get_values(h), bin, ent);
 115   } else {
 116     entry_append(state, entry, ent);
 117   }
 118
 119   hash_set_entries(h, I2N(N2I(hash_get_entries(h)) + 1));
 120   return ent;
 121 }
 122
 123 /* TODO: Why do we use signed int for bins and then use a
 124  * loop like for(i = 0; i < bins; i++) ?
 125  */
 126 void hash_redistribute(STATE, OBJECT hsh) {
 127   int i, bins, size;
 128   unsigned int bin, hash;
 129   OBJECT values, new_values, entry, next, slot;
 130
 131   bins = N2I(hash_get_bins(hsh));
 132   values = hash_get_values(hsh);
 133
 134   /* TODO: calculate the size both up and down.
 135    * i.e. don't assume we're only growing
 136    */
 137   size = bins * 2;
 138   new_values = tuple_new(state, size);
 139
 140   // printf("Hash redistribute %p, %d => %d (%d)\n", hsh, bins, size, N2I(hash_get_entries(hsh)));
 141
 142   for(i = 0; i < bins; i++) {
 143     entry = tuple_at(state, values, i);
 144
 145     while(!NIL_P(entry)) {
 146       next = tuple_at(state, entry, 3);
 147       tuple_put(state, entry, 3, Qnil);
 148
 149       hash = N2I(tuple_at(state, entry, 0));
 150       bin = find_bin(hash, size);
 151       slot = tuple_at(state, new_values, bin);
 152
 153       if(NIL_P(slot)) {
 154         tuple_put(state, new_values, bin, entry);
 155       } else {
 156         entry_append(state, slot, entry);
 157       }
 158
 159       entry = next;
 160     }
 161   }
 162
 163   hash_set_values(hsh, new_values);
 164   hash_set_bins(hsh, I2N(size));
 165 }
 166
 167 OBJECT hash_find_entry(STATE, OBJECT h, unsigned int hsh) {
 168   unsigned int bin, bins;
 169   OBJECT entry, th;
 170
 171   bins = (unsigned int)N2I(hash_get_bins(h));
 172   bin = find_bin(hsh, bins);
 173   entry = tuple_at(state, hash_get_values(h), bin);
 174
 175   // printf("start: %x, %ud, %d, %d\n", entry, hsh, bin, N2I(hash_get_bins(h)));
 176
 177   while(!NIL_P(entry)) {
 178     // printf("entry: %x\n", entry);
 179     th = tuple_at(state, entry, 0);
 180     if(N2I(th) == hsh) {
 181       return entry;
 182     }
 183     entry = tuple_at(state, entry, 3);
 184   }
 185   return Qnil;
 186 }
 187
 188 OBJECT hash_add(STATE, OBJECT h, unsigned int hsh, OBJECT key, OBJECT data) {
 189   OBJECT entry;
 190   int i;
 191
 192   // printf("hash_add: adding %od\n",hsh);
 193   entry = hash_find_entry(state, h, hsh);
 194
 195   if(RTEST(entry)) {
 196     tuple_put(state, entry, 2, data);
 197     return data;
 198   }
 199
 200   if(hash_redistribute_p(h)) {
 201     hash_redistribute(state, h);
 202   }
 203
 204   i = N2I(hash_get_entries(h));
 205   entry = entry_new(state, hsh, key, data);
 206   add_entry(state, h, hsh, entry);
 207   return data;
 208 }
 209
 210 /* Sets key/value pair to hash */
 211 OBJECT hash_set(STATE, OBJECT hash, OBJECT key, OBJECT val) {
 212   return hash_add(state, hash, object_hash_int(state, key), key, val);
 213 }
 214
 215 OBJECT hash_get(STATE, OBJECT hash, unsigned int hsh) {
 216   OBJECT entry;
 217
 218   entry = hash_find_entry(state, hash, hsh);
 219   if(RTEST(entry)) {
 220     return tuple_at(state, entry, 2);
 221   }
 222
 223   return Qnil;
 224 }
 225
 226 /* Find the +value+ for +key+, having hash value +hash+.
 227  * Uses +==+ to verify the key in the table matches +key+.
 228  * Return TRUE if key was found, and *value will be filled. */
 229 int hash_lookup(STATE, OBJECT tbl, OBJECT key, unsigned int hash, OBJECT *value) {
 230   OBJECT ent, hk;
 231
 232   ent = hash_find_entry(state, tbl, hash);
 233   if(REFERENCE_P(ent)) {
 234     while(N2I(tuple_at(state, ent, 0)) == hash) {
 235       hk = tuple_at(state, ent, 1);
 236       if(hk == key) {
 237         *value = tuple_at(state, ent, 2);
 238         return TRUE;
 239       }
 240
 241       ent = tuple_at(state, ent, 3);
 242       if(NIL_P(ent)) break;
 243     }
 244   }
 245
 246   return FALSE;
 247 }
 248
 249 /* Find the +value+ for +key+, having hash value +hash+.
 250  * Uses +compare+ to verify the key in the table matches +key+.
 251  * Return TRUE if key was found, and *value will be filled. */
 252 int hash_lookup2(STATE, int (*compare)(STATE, OBJECT, OBJECT),
 253     OBJECT tbl, OBJECT key, unsigned int hash, OBJECT *value) {
 254   OBJECT ent, hk;
 255
 256   ent = hash_find_entry(state, tbl, hash);
 257   if(REFERENCE_P(ent)) {
 258     while(N2I(tuple_at(state, ent, 0)) == hash) {
 259       hk = tuple_at(state, ent, 1);
 260       if(compare(state, hk, key)) {
 261         *value = tuple_at(state, ent, 2);
 262         return TRUE;
 263       }
 264
 265       ent = tuple_at(state, ent, 3);
 266       if(NIL_P(ent)) break;
 267     }
 268   }
 269
 270   return FALSE;
 271 }
 272
 273 void hash_assign(STATE, int (*compare)(STATE, OBJECT, OBJECT), OBJECT tbl,
 274     OBJECT key, unsigned int hash, OBJECT value) {
 275   OBJECT base, ent, hk;
 276
 277   base = ent = hash_find_entry(state, tbl, hash);
 278   if(REFERENCE_P(ent)) {
 279     while(N2I(tuple_at(state, ent, 0)) == hash) {
 280       hk = tuple_at(state, ent, 1);
 281       if(compare(state, hk, key)) {
 282         tuple_put(state, ent, 2, value);
 283         return;
 284       }
 285
 286       ent = tuple_at(state, ent, 3);
 287       if(NIL_P(ent)) break;
 288     }
 289
 290   }
 291
 292   if(hash_redistribute_p(tbl)) {
 293     hash_redistribute(state, tbl);
 294   }
 295
 296   if(REFERENCE_P(base)) {
 297     ent = entry_new(state, hash, key, value);
 298     entry_append(state, base, ent);
 299     hash_set_entries(tbl, I2N(N2I(hash_get_entries(tbl)) + 1));
 300     return;
 301   }
 302
 303   ent = entry_new(state, hash, key, value);
 304   add_entry(state, tbl, hash, ent);
 305 }
 306
 307 /* This version of hash_get returns Qundef if the entry was not found.
 308  * This is handy when you need to tell the difference between:
 309  * x = {} and x = {:a => nil}
 310  */
 311
 312 OBJECT hash_get_undef(STATE, OBJECT hash, unsigned int hsh) {
 313   OBJECT entry;
 314
 315   entry = hash_find_entry(state, hash, hsh);
 316   if(RTEST(entry)) {
 317     return tuple_at(state, entry, 2);
 318   } else {
 319     return Qundef;
 320   }
 321 }
 322
 323 OBJECT hash_delete(STATE, OBJECT self, unsigned int hsh) {
 324   unsigned int bin;
 325   OBJECT entry, th, lk, val, lst;
 326
 327   bin = find_bin(hsh, N2I(hash_get_bins(self)));
 328   entry = tuple_at(state, hash_get_values(self), bin);
 329
 330   lst = Qnil;
 331
 332   while(!NIL_P(entry)) {
 333     th = tuple_at(state, entry, 0);
 334     lk = tuple_at(state, entry, 3);
 335
 336     if(N2I(th) == hsh) {
 337       val = tuple_at(state, entry, 2);
 338       if(NIL_P(lst)) {
 339         tuple_put(state, hash_get_values(self), bin, lk);
 340       } else {
 341         tuple_put(state, lst, 3, lk);
 342       }
 343       hash_set_entries(self, I2N(N2I(hash_get_entries(self)) - 1));
 344       return val;
 345     }
 346
 347     lst = entry;
 348     entry = lk;
 349   }
 350
 351   return Qnil;
 352 }
 353
 354 OBJECT hash_s_from_tuple(STATE, OBJECT tup) {
 355   OBJECT hsh, key, val;
 356   int i, fel;
 357   hsh = hash_new(state);
 358
 359   fel = tuple_fields(state, tup);
 360   i = 0;
 361   while(i < fel) {
 362     key = tuple_at(state, tup, i);
 363     val = tuple_at(state, tup, i + 1);
 364     i += 2;
 365     hash_set(state, hsh, key, val);
 366   }
 367
 368   return hsh;
 369 }
 370
 371 OBJECT csm_find(STATE, OBJECT csm, OBJECT key) {
 372   OBJECT t, val;
 373   int i;
 374
 375   for(i = 0; i < CSM_SIZE; i += 2) {
 376     t = tuple_at(state, csm, i);
 377
 378     if(t == key) {
 379       val = tuple_at(state, csm, i + 1);
 380       // printf("Found %s: %s\n", _inspect(key), _inspect(val));
 381       return val;
 382     }
 383   }
 384
 385   //printf("Unable to find ivar %s\n", _inspect(key));
 386
 387   return Qnil;
 388 }
 389
 390 OBJECT csm_add(STATE, OBJECT csm, OBJECT key, OBJECT val) {
 391   int i;
 392   OBJECT tmp;
 393
 394   for(i = 0; i < CSM_SIZE; i += 2) {
 395     tmp = tuple_at(state, csm, i);
 396     if(tmp == key || NIL_P(tmp)) {
 397       // printf("Added ivar %s at %d\n", _inspect(key), i);
 398       tuple_put(state, csm, i, key);
 399       tuple_put(state, csm, i + 1, val);
 400       return Qtrue;
 401     }
 402   }
 403
 404   return Qfalse;
 405 }
 406
 407 OBJECT csm_into_hash(STATE, OBJECT csm) {
 408   int i;
 409   OBJECT k, hsh;
 410
 411   hsh = hash_new(state);
 412
 413   for(i = 0; i < CSM_SIZE; i += 2) {
 414     k = tuple_at(state, csm, i);
 415     if(!NIL_P(k)) {
 416       hash_set(state, hsh, k, tuple_at(state, csm, i + 1));
 417     }
 418   }
 419
 420   return hsh;
 421 }
 422
 423 OBJECT csm_into_lookuptable(STATE, OBJECT csm) {
 424   int i;
 425   OBJECT k, tbl;
 426
 427   tbl = lookuptable_new(state);
 428
 429   for(i = 0; i < CSM_SIZE; i += 2) {
 430     k = tuple_at(state, csm, i);
 431     if(!NIL_P(k)) {
 432       lookuptable_store(state, tbl, k, tuple_at(state, csm, i + 1));
 433     }
 434   }
 435
 436   return tbl;
 437 }