src/ltable.c

   1 /*
   2 ** $Id: ltable.c,v 1.58 2000/10/26 12:47:05 roberto Exp $
   3 ** Lua tables (hash)
   4 ** See Copyright Notice in lua.h
   5 */
   6
   7
   8 /*
   9 ** Implementation of tables (aka arrays, objects, or hash tables);
  10 ** uses a mix of chained scatter table with Brent's variation.
  11 ** A main invariant of these tables is that, if an element is not
  12 ** in its main position (i.e. the `original' position that its hash gives
  13 ** to it), then the colliding element is in its own main position.
  14 ** In other words, there are collisions only when two elements have the
  15 ** same main position (i.e. the same hash values for that table size).
  16 ** Because of that, the load factor of these tables can be 100% without
  17 ** performance penalties.
  18 */
  19
  20
  21 #include "lua.h"
  22
  23 #include "lmem.h"
  24 #include "lobject.h"
  25 #include "lstate.h"
  26 #include "lstring.h"
  27 #include "ltable.h"
  28
  29
  30 #define gcsize(L, n)    (sizeof(Hash)+(n)*sizeof(Node))
  31
  32
  33
  34 #define TagDefault LUA_TTABLE
  35
  36
  37
  38 /*
  39 ** returns the `main' position of an element in a table (that is, the index
  40 ** of its hash value)
  41 */
  42 Node *luaH_mainposition (const Hash *t, const TObject *key) {
  43   unsigned long h;
  44   switch (ttype(key)) {
  45     case LUA_TNUMBER:
  46       h = (unsigned long)(long)nvalue(key);
  47       break;
  48     case LUA_TSTRING:
  49       h = tsvalue(key)->u.s.hash;
  50       break;
  51     case LUA_TUSERDATA:
  52       h = IntPoint(tsvalue(key));
  53       break;
  54     case LUA_TTABLE:
  55       h = IntPoint(hvalue(key));
  56       break;
  57     case LUA_TFUNCTION:
  58       h = IntPoint(clvalue(key));
  59       break;
  60     default:
  61       return NULL;  /* invalid key */
  62   }
  63   LUA_ASSERT(h%(unsigned int)t->size == (h&((unsigned int)t->size-1)),
  64             "a&(x-1) == a%x, for x power of 2");
  65   return &t->node[h&(t->size-1)];
  66 }
  67
  68
  69 static const TObject *luaH_getany (lua_State *L, const Hash *t,
  70                                    const TObject *key) {
  71   Node *n = luaH_mainposition(t, key);
  72   if (!n)
  73     lua_error(L, "table index is nil");
  74   else do {
  75     if (luaO_equalObj(key, &n->key))
  76       return &n->val;
  77     n = n->next;
  78   } while (n);
  79   return &luaO_nilobject;  /* key not found */
  80 }
  81
  82
  83 /* specialized version for numbers */
  84 const TObject *luaH_getnum (const Hash *t, Number key) {
  85   Node *n = &t->node[(unsigned long)(long)key&(t->size-1)];
  86   do {
  87     if (ttype(&n->key) == LUA_TNUMBER && nvalue(&n->key) == key)
  88       return &n->val;
  89     n = n->next;
  90   } while (n);
  91   return &luaO_nilobject;  /* key not found */
  92 }
  93
  94
  95 /* specialized version for strings */
  96 const TObject *luaH_getstr (const Hash *t, TString *key) {
  97   Node *n = &t->node[key->u.s.hash&(t->size-1)];
  98   do {
  99     if (ttype(&n->key) == LUA_TSTRING && tsvalue(&n->key) == key)
 100       return &n->val;
 101     n = n->next;
 102   } while (n);
 103   return &luaO_nilobject;  /* key not found */
 104 }
 105
 106
 107 const TObject *luaH_get (lua_State *L, const Hash *t, const TObject *key) {
 108   switch (ttype(key)) {
 109     case LUA_TNUMBER: return luaH_getnum(t, nvalue(key));
 110     case LUA_TSTRING: return luaH_getstr(t, tsvalue(key));
 111     default:         return luaH_getany(L, t, key);
 112   }
 113 }
 114
 115
 116 Node *luaH_next (lua_State *L, const Hash *t, const TObject *key) {
 117   int i;
 118   if (ttype(key) == LUA_TNIL)
 119     i = 0;  /* first iteration */
 120   else {
 121     const TObject *v = luaH_get(L, t, key);
 122     if (v == &luaO_nilobject)
 123       lua_error(L, "invalid key for `next'");
 124     i = (int)(((const char *)v -
 125                (const char *)(&t->node[0].val)) / sizeof(Node)) + 1;
 126   }
 127   for (; i<t->size; i++) {
 128     Node *n = node(t, i);
 129     if (ttype(val(n)) != LUA_TNIL)
 130       return n;
 131   }
 132   return NULL;  /* no more elements */
 133 }
 134
 135
 136 /*
 137 ** try to remove a key without value from a table. To avoid problems with
 138 ** hash, change `key' for a number with the same hash.
 139 */
 140 void luaH_remove (Hash *t, TObject *key) {
 141   if (ttype(key) == LUA_TNUMBER ||
 142        (ttype(key) == LUA_TSTRING && tsvalue(key)->len <= 30))
 143   return;  /* do not remove numbers nor small strings */
 144   else {
 145     /* try to find a number `n' with the same hash as `key' */
 146     Node *mp = luaH_mainposition(t, key);
 147     int n = mp - &t->node[0];
 148     /* make sure `n' is not in `t' */
 149     while (luaH_getnum(t, n) != &luaO_nilobject) {
 150       if (n >= MAX_INT - t->size)
 151         return;  /* give up; (to avoid overflow) */
 152       n += t->size;
 153     }
 154     ttype(key) = LUA_TNUMBER;
 155     nvalue(key) = n;
 156     LUA_ASSERT(luaH_mainposition(t, key) == mp, "cannot change hash");
 157   }
 158 }
 159
 160
 161 static void setnodevector (lua_State *L, Hash *t, lint32 size) {
 162   int i;
 163   if (size > MAX_INT)
 164     lua_error(L, "table overflow");
 165   t->node = luaM_newvector(L, size, Node);
 166   for (i=0; i<(int)size; i++) {
 167     ttype(&t->node[i].key) = ttype(&t->node[i].val) = LUA_TNIL;
 168     t->node[i].next = NULL;
 169   }
 170   L->nblocks += gcsize(L, size) - gcsize(L, t->size);
 171   t->size = size;
 172   t->firstfree = &t->node[size-1];  /* first free position to be used */
 173 }
 174
 175
 176 Hash *luaH_new (lua_State *L, int size) {
 177   Hash *t = luaM_new(L, Hash);
 178   t->htag = TagDefault;
 179   t->next = L->roottable;
 180   L->roottable = t;
 181   t->mark = t;
 182   t->size = 0;
 183   L->nblocks += gcsize(L, 0);
 184   t->node = NULL;
 185   setnodevector(L, t, luaO_power2(size));
 186   return t;
 187 }
 188
 189
 190 void luaH_free (lua_State *L, Hash *t) {
 191   L->nblocks -= gcsize(L, t->size);
 192   luaM_free(L, t->node);
 193   luaM_free(L, t);
 194 }
 195
 196
 197 static int numuse (const Hash *t) {
 198   Node *v = t->node;
 199   int size = t->size;
 200   int realuse = 0;
 201   int i;
 202   for (i=0; i<size; i++) {
 203     if (ttype(&v[i].val) != LUA_TNIL)
 204       realuse++;
 205   }
 206   return realuse;
 207 }
 208
 209
 210 static void rehash (lua_State *L, Hash *t) {
 211   int oldsize = t->size;
 212   Node *nold = t->node;
 213   int nelems = numuse(t);
 214   int i;
 215   LUA_ASSERT(nelems<=oldsize, "wrong count");
 216   if (nelems >= oldsize-oldsize/4)  /* using more than 3/4? */
 217     setnodevector(L, t, (lint32)oldsize*2);
 218   else if (nelems <= oldsize/4 &&  /* less than 1/4? */
 219            oldsize > MINPOWER2)
 220     setnodevector(L, t, oldsize/2);
 221   else
 222     setnodevector(L, t, oldsize);
 223   for (i=0; i<oldsize; i++) {
 224     Node *old = nold+i;
 225     if (ttype(&old->val) != LUA_TNIL)
 226       *luaH_set(L, t, &old->key) = old->val;
 227   }
 228   luaM_free(L, nold);  /* free old array */
 229 }
 230
 231
 232 /*
 233 ** inserts a key into a hash table; first, check whether key is
 234 ** already present; if not, check whether key's main position is free;
 235 ** if not, check whether colliding node is in its main position or not;
 236 ** if it is not, move colliding node to an empty place and put new key
 237 ** in its main position; otherwise (colliding node is in its main position),
 238 ** new key goes to an empty position.
 239 */
 240 TObject *luaH_set (lua_State *L, Hash *t, const TObject *key) {
 241   Node *mp = luaH_mainposition(t, key);
 242   Node *n = mp;
 243   if (!mp)
 244     lua_error(L, "table index is nil");
 245   do {  /* check whether `key' is somewhere in the chain */
 246     if (luaO_equalObj(key, &n->key))
 247       return &n->val;  /* that's all */
 248     else n = n->next;
 249   } while (n);
 250   /* `key' not found; must insert it */
 251   if (ttype(&mp->key) != LUA_TNIL) {  /* main position is not free? */
 252     Node *othern;  /* main position of colliding node */
 253     n = t->firstfree;  /* get a free place */
 254     /* is colliding node out of its main position? (can only happens if
 255        its position is after "firstfree") */
 256     if (mp > n && (othern=luaH_mainposition(t, &mp->key)) != mp) {
 257       /* yes; move colliding node into free position */
 258       while (othern->next != mp) othern = othern->next;  /* find previous */
 259       othern->next = n;  /* redo the chain with `n' in place of `mp' */
 260       *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
 261       mp->next = NULL;  /* now `mp' is free */
 262     }
 263     else {  /* colliding node is in its own main position */
 264       /* new node will go into free position */
 265       n->next = mp->next;  /* chain new position */
 266       mp->next = n;
 267       mp = n;
 268     }
 269   }
 270   mp->key = *key;
 271   for (;;) {  /* correct `firstfree' */
 272     if (ttype(&t->firstfree->key) == LUA_TNIL)
 273       return &mp->val;  /* OK; table still has a free place */
 274     else if (t->firstfree == t->node) break;  /* cannot decrement from here */
 275     else (t->firstfree)--;
 276   }
 277   rehash(L, t);  /* no more free places */
 278   return luaH_set(L, t, key);  /* `rehash' invalidates this insertion */
 279 }
 280
 281
 282 TObject *luaH_setint (lua_State *L, Hash *t, int key) {
 283   TObject index;
 284   ttype(&index) = LUA_TNUMBER;
 285   nvalue(&index) = key;
 286   return luaH_set(L, t, &index);
 287 }
 288
 289
 290 void luaH_setstrnum (lua_State *L, Hash *t, TString *key, Number val) {
 291   TObject *value, index;
 292   ttype(&index) = LUA_TSTRING;
 293   tsvalue(&index) = key;
 294   value = luaH_set(L, t, &index);
 295   ttype(value) = LUA_TNUMBER;
 296   nvalue(value) = val;
 297 }
 298
 299
 300 const TObject *luaH_getglobal (lua_State *L, const char *name) {
 301   return luaH_getstr(L->gt, luaS_new(L, name));
 302 }
 303