src/ltable.c

   1 /*
   2 ** $Id: ltable.c,v 1.12 1998/01/28 16:50:33 roberto Exp $
   3 ** Lua tables (hash)
   4 ** See Copyright Notice in lua.h
   5 */
   6
   7 #include <stdlib.h>
   8
   9 #include "lauxlib.h"
  10 #include "lmem.h"
  11 #include "lobject.h"
  12 #include "lstate.h"
  13 #include "ltable.h"
  14 #include "lua.h"
  15
  16
  17 #define gcsize(n)       (1+(n/16))
  18
  19 #define nuse(t)         ((t)->nuse)
  20 #define nodevector(t)   ((t)->node)
  21
  22
  23 #define REHASH_LIMIT    0.70    /* avoid more than this % full */
  24
  25 #define TagDefault LUA_T_ARRAY;
  26
  27
  28
  29 static long int hashindex (TObject *ref)
  30 {
  31   long int h;
  32   switch (ttype(ref)) {
  33     case LUA_T_NUMBER:
  34       h = (long int)nvalue(ref);
  35       break;
  36     case LUA_T_STRING: case LUA_T_USERDATA:
  37       h = (IntPoint)tsvalue(ref);
  38       break;
  39     case LUA_T_ARRAY:
  40       h = (IntPoint)avalue(ref);
  41       break;
  42     case LUA_T_PROTO:
  43       h = (IntPoint)tfvalue(ref);
  44       break;
  45     case LUA_T_CPROTO:
  46       h = (IntPoint)fvalue(ref);
  47       break;
  48     case LUA_T_CLOSURE:
  49       h = (IntPoint)clvalue(ref);
  50       break;
  51     default:
  52       lua_error("unexpected type to index table");
  53       h = 0;  /* to avoid warnings */
  54   }
  55   return (h >= 0 ? h : -(h+1));
  56 }
  57
  58
  59 static int present (Hash *t, TObject *key)
  60 {
  61   int tsize = nhash(t);
  62   long int h = hashindex(key);
  63   int h1 = h%tsize;
  64   TObject *rf = ref(node(t, h1));
  65   if (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf)) {
  66     int h2 = h%(tsize-2) + 1;
  67     do {
  68       h1 += h2;
  69       if (h1 >= tsize) h1 -= tsize;
  70       rf = ref(node(t, h1));
  71     } while (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf));
  72   }
  73   return h1;
  74 }
  75
  76
  77 /*
  78 ** Alloc a vector node
  79 */
  80 static Node *hashnodecreate (int nhash)
  81 {
  82   Node *v = luaM_newvector(nhash, Node);
  83   int i;
  84   for (i=0; i<nhash; i++)
  85     ttype(ref(&v[i])) = LUA_T_NIL;
  86   return v;
  87 }
  88
  89 /*
  90 ** Delete a hash
  91 */
  92 static void hashdelete (Hash *t)
  93 {
  94   luaM_free(nodevector(t));
  95   luaM_free(t);
  96 }
  97
  98
  99 void luaH_free (Hash *frees)
 100 {
 101   while (frees) {
 102     Hash *next = (Hash *)frees->head.next;
 103     L->nblocks -= gcsize(frees->nhash);
 104     hashdelete(frees);
 105     frees = next;
 106   }
 107 }
 108
 109
 110 Hash *luaH_new (int nhash)
 111 {
 112   Hash *t = luaM_new(Hash);
 113   nhash = luaO_redimension((int)((float)nhash/REHASH_LIMIT));
 114   nodevector(t) = hashnodecreate(nhash);
 115   nhash(t) = nhash;
 116   nuse(t) = 0;
 117   t->htag = TagDefault;
 118   luaO_insertlist(&(L->roottable), (GCnode *)t);
 119   L->nblocks += gcsize(nhash);
 120   return t;
 121 }
 122
 123
 124 static int newsize (Hash *t)
 125 {
 126   Node *v = t->node;
 127   int size = nhash(t);
 128   int realuse = 0;
 129   int i;
 130   for (i=0; i<size; i++) {
 131     if (ttype(ref(v+i)) != LUA_T_NIL && ttype(val(v+i)) != LUA_T_NIL)
 132       realuse++;
 133   }
 134   if (2*(realuse+1) <= size)  /* +1 is the new element */
 135     return size;  /* don't need to grow, just rehash */
 136   else
 137     return luaO_redimension(size);
 138 }
 139
 140 static void rehash (Hash *t)
 141 {
 142   int nold = nhash(t);
 143   Node *vold = nodevector(t);
 144   int nnew = newsize(t);
 145   int i;
 146   nodevector(t) = hashnodecreate(nnew);
 147   nhash(t) = nnew;
 148   for (i=0; i<nold; i++) {
 149     Node *n = vold+i;
 150     if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) != LUA_T_NIL)
 151       *node(t, present(t, ref(n))) = *n;  /* copy old node to luaM_new hash */
 152   }
 153   L->nblocks += gcsize(nnew)-gcsize(nold);
 154   luaM_free(vold);
 155 }
 156
 157 /*
 158 ** If the hash node is present, return its pointer, otherwise return
 159 ** null.
 160 */
 161 TObject *luaH_get (Hash *t, TObject *ref)
 162 {
 163  int h = present(t, ref);
 164  if (ttype(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h));
 165  else return NULL;
 166 }
 167
 168
 169 /*
 170 ** If the hash node is present, return its pointer, otherwise create a luaM_new
 171 ** node for the given reference and also return its pointer.
 172 */
 173 TObject *luaH_set (Hash *t, TObject *ref)
 174 {
 175   Node *n = node(t, present(t, ref));
 176   if (ttype(ref(n)) == LUA_T_NIL) {
 177     nuse(t)++;
 178     if ((float)nuse(t) > (float)nhash(t)*REHASH_LIMIT) {
 179       rehash(t);
 180       n = node(t, present(t, ref));
 181     }
 182     *ref(n) = *ref;
 183     ttype(val(n)) = LUA_T_NIL;
 184   }
 185   return (val(n));
 186 }
 187
 188
 189 static Node *hashnext (Hash *t, int i)
 190 {
 191   Node *n;
 192   int tsize = nhash(t);
 193   if (i >= tsize)
 194     return NULL;
 195   n = node(t, i);
 196   while (ttype(ref(n)) == LUA_T_NIL || ttype(val(n)) == LUA_T_NIL) {
 197     if (++i >= tsize)
 198       return NULL;
 199     n = node(t, i);
 200   }
 201   return node(t, i);
 202 }
 203
 204 Node *luaH_next (TObject *o, TObject *r)
 205 {
 206   Hash *t = avalue(o);
 207   if (ttype(r) == LUA_T_NIL)
 208     return hashnext(t, 0);
 209   else {
 210     int i = present(t, r);
 211     Node *n = node(t, i);
 212     luaL_arg_check(ttype(ref(n))!=LUA_T_NIL && ttype(val(n))!=LUA_T_NIL,
 213                    2, "key not found");
 214     return hashnext(t, i+1);
 215   }
 216 }