src/ltable.c

   1 /*
   2 ** $Id: ltable.c,v 1.22 1999/05/21 19:41:49 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 TagDefault LUA_T_ARRAY;
  24
  25
  26
  27 static long int hashindex (TObject *ref) {
  28   long int h;
  29   switch (ttype(ref)) {
  30     case LUA_T_NUMBER:
  31       h = (long int)nvalue(ref);
  32       break;
  33     case LUA_T_STRING: case LUA_T_USERDATA:
  34       h = (IntPoint)tsvalue(ref);
  35       break;
  36     case LUA_T_ARRAY:
  37       h = (IntPoint)avalue(ref);
  38       break;
  39     case LUA_T_PROTO:
  40       h = (IntPoint)tfvalue(ref);
  41       break;
  42     case LUA_T_CPROTO:
  43       h = (IntPoint)fvalue(ref);
  44       break;
  45     case LUA_T_CLOSURE:
  46       h = (IntPoint)clvalue(ref);
  47       break;
  48     default:
  49       lua_error("unexpected type to index table");
  50       h = 0;  /* to avoid warnings */
  51   }
  52   return (h >= 0 ? h : -(h+1));
  53 }
  54
  55
  56 Node *luaH_present (Hash *t, TObject *key) {
  57   int tsize = nhash(t);
  58   long int h = hashindex(key);
  59   int h1 = h%tsize;
  60   Node *n = node(t, h1);
  61   /* keep looking until an entry with "ref" equal to key or nil */
  62   while ((ttype(ref(n)) == ttype(key)) ? !luaO_equalval(key, ref(n))
  63                                        : ttype(ref(n)) != LUA_T_NIL) {
  64     h1 += (h&(tsize-2)) + 1;  /* double hashing */
  65     if (h1 >= tsize) h1 -= tsize;
  66     n = node(t, h1);
  67   }
  68   return n;
  69 }
  70
  71
  72 void luaH_free (Hash *frees) {
  73   while (frees) {
  74     Hash *next = (Hash *)frees->head.next;
  75     L->nblocks -= gcsize(frees->nhash);
  76     luaM_free(nodevector(frees));
  77     luaM_free(frees);
  78     frees = next;
  79   }
  80 }
  81
  82
  83 static Node *hashnodecreate (int nhash) {
  84   Node *v = luaM_newvector(nhash, Node);
  85   int i;
  86   for (i=0; i<nhash; i++)
  87     ttype(ref(&v[i])) = ttype(val(&v[i])) = LUA_T_NIL;
  88   return v;
  89 }
  90
  91
  92 Hash *luaH_new (int nhash) {
  93   Hash *t = luaM_new(Hash);
  94   nhash = luaO_redimension(nhash*3/2);
  95   nodevector(t) = hashnodecreate(nhash);
  96   nhash(t) = nhash;
  97   nuse(t) = 0;
  98   t->htag = TagDefault;
  99   luaO_insertlist(&(L->roottable), (GCnode *)t);
 100   L->nblocks += gcsize(nhash);
 101   return t;
 102 }
 103
 104
 105 static int newsize (Hash *t) {
 106   Node *v = t->node;
 107   int size = nhash(t);
 108   int realuse = 0;
 109   int i;
 110   for (i=0; i<size; i++) {
 111     if (ttype(val(v+i)) != LUA_T_NIL)
 112       realuse++;
 113   }
 114   return luaO_redimension((realuse+1)*2);  /* +1 is the new element */
 115 }
 116
 117
 118 static void rehash (Hash *t) {
 119   int nold = nhash(t);
 120   Node *vold = nodevector(t);
 121   int nnew = newsize(t);
 122   int i;
 123   nodevector(t) = hashnodecreate(nnew);
 124   nhash(t) = nnew;
 125   nuse(t) = 0;
 126   for (i=0; i<nold; i++) {
 127     Node *n = vold+i;
 128     if (ttype(val(n)) != LUA_T_NIL) {
 129       *luaH_present(t, ref(n)) = *n;  /* copy old node to new hash */
 130       nuse(t)++;
 131     }
 132   }
 133   L->nblocks += gcsize(nnew)-gcsize(nold);
 134   luaM_free(vold);
 135 }
 136
 137
 138 void luaH_set (Hash *t, TObject *ref, TObject *val) {
 139   Node *n = luaH_present(t, ref);
 140   if (ttype(ref(n)) != LUA_T_NIL)
 141     *val(n) = *val;
 142   else {
 143     TObject buff;
 144     buff = *val;  /* rehash may invalidate this address */
 145     if ((long)nuse(t)*3L > (long)nhash(t)*2L) {
 146       rehash(t);
 147       n = luaH_present(t, ref);
 148     }
 149     nuse(t)++;
 150     *ref(n) = *ref;
 151     *val(n) = buff;
 152   }
 153 }
 154
 155
 156 int luaH_pos (Hash *t, TObject *r) {
 157   Node *n = luaH_present(t, r);
 158   luaL_arg_check(ttype(val(n)) != LUA_T_NIL, 2, "key not found");
 159   return n-(t->node);
 160 }
 161
 162
 163 void luaH_setint (Hash *t, int ref, TObject *val) {
 164   TObject index;
 165   ttype(&index) = LUA_T_NUMBER;
 166   nvalue(&index) = ref;
 167   luaH_set(t, &index, val);
 168 }
 169
 170
 171 TObject *luaH_getint (Hash *t, int ref) {
 172   TObject index;
 173   ttype(&index) = LUA_T_NUMBER;
 174   nvalue(&index) = ref;
 175   return luaH_get(t, &index);
 176 }
 177