src/hash.c

   1 /*
   2 ** hash.c
   3 ** hash manager for lua
   4 */
   5
   6 char *rcs_hash="$Id: hash.c,v 2.30 1996/05/06 14:30:27 roberto Exp $";
   7
   8
   9 #include "mem.h"
  10 #include "opcode.h"
  11 #include "hash.h"
  12 #include "table.h"
  13 #include "lua.h"
  14
  15
  16 #define nhash(t)        ((t)->nhash)
  17 #define nuse(t)         ((t)->nuse)
  18 #define markarray(t)    ((t)->mark)
  19 #define nodevector(t)   ((t)->node)
  20 #define node(t,i)       (&(t)->node[i])
  21 #define ref(n)          (&(n)->ref)
  22 #define val(n)          (&(n)->val)
  23
  24
  25 #define REHASH_LIMIT    0.70    /* avoid more than this % full */
  26
  27
  28 static Hash *listhead = NULL;
  29
  30
  31 /* hash dimensions values */
  32 static Long dimensions[] =
  33  {3L, 5L, 7L, 11L, 23L, 47L, 97L, 197L, 397L, 797L, 1597L, 3203L, 6421L,
  34   12853L, 25717L, 51437L, 102811L, 205619L, 411233L, 822433L,
  35   1644817L, 3289613L, 6579211L, 13158023L, MAX_INT};
  36
  37 int luaI_redimension (int nhash)
  38 {
  39  int i;
  40  for (i=0; dimensions[i]<MAX_INT; i++)
  41  {
  42   if (dimensions[i] > nhash)
  43    return dimensions[i];
  44  }
  45  lua_error("table overflow");
  46  return 0;  /* to avoid warnings */
  47 }
  48
  49 static int hashindex (Hash *t, Object *ref)             /* hash function */
  50 {
  51  switch (tag(ref))
  52  {
  53   case LUA_T_NIL:
  54    lua_error ("unexpected type to index table");
  55    return -1;  /* UNREACHEABLE */
  56   case LUA_T_NUMBER:
  57    return (((int)nvalue(ref))%nhash(t));
  58   case LUA_T_STRING:
  59    return (int)((tsvalue(ref)->hash)%nhash(t));  /* make it a valid index */
  60   case LUA_T_FUNCTION:
  61    return (((IntPoint)ref->value.tf)%nhash(t));
  62   case LUA_T_CFUNCTION:
  63    return (((IntPoint)fvalue(ref))%nhash(t));
  64   case LUA_T_ARRAY:
  65    return (((IntPoint)avalue(ref))%nhash(t));
  66   default:  /* user data */
  67    return (((IntPoint)uvalue(ref))%nhash(t));
  68  }
  69 }
  70
  71 int lua_equalObj (Object *t1, Object *t2)
  72 {
  73   if (tag(t1) != tag(t2)) return 0;
  74   switch (tag(t1))
  75   {
  76     case LUA_T_NIL: return 1;
  77     case LUA_T_NUMBER: return nvalue(t1) == nvalue(t2);
  78     case LUA_T_STRING: return svalue(t1) == svalue(t2);
  79     case LUA_T_ARRAY: return avalue(t1) == avalue(t2);
  80     case LUA_T_FUNCTION: return t1->value.tf == t2->value.tf;
  81     case LUA_T_CFUNCTION: return fvalue(t1) == fvalue(t2);
  82     default: return uvalue(t1) == uvalue(t2);
  83   }
  84 }
  85
  86 static int present (Hash *t, Object *ref)
  87 {
  88  int h = hashindex(t, ref);
  89  while (tag(ref(node(t, h))) != LUA_T_NIL)
  90  {
  91   if (lua_equalObj(ref, ref(node(t, h))))
  92     return h;
  93   h = (h+1) % nhash(t);
  94  }
  95  return h;
  96 }
  97
  98
  99 /*
 100 ** Alloc a vector node
 101 */
 102 static Node *hashnodecreate (int nhash)
 103 {
 104  int i;
 105  Node *v = newvector (nhash, Node);
 106  for (i=0; i<nhash; i++)
 107    tag(ref(&v[i])) = LUA_T_NIL;
 108  return v;
 109 }
 110
 111 /*
 112 ** Create a new hash. Return the hash pointer or NULL on error.
 113 */
 114 static Hash *hashcreate (int nhash)
 115 {
 116  Hash *t = new(Hash);
 117  nhash = luaI_redimension((int)((float)nhash/REHASH_LIMIT));
 118  nodevector(t) = hashnodecreate(nhash);
 119  nhash(t) = nhash;
 120  nuse(t) = 0;
 121  markarray(t) = 0;
 122  return t;
 123 }
 124
 125 /*
 126 ** Delete a hash
 127 */
 128 static void hashdelete (Hash *t)
 129 {
 130  luaI_free (nodevector(t));
 131  luaI_free(t);
 132 }
 133
 134
 135 /*
 136 ** Mark a hash and check its elements
 137 */
 138 void lua_hashmark (Hash *h)
 139 {
 140  if (markarray(h) == 0)
 141  {
 142   int i;
 143   markarray(h) = 1;
 144   for (i=0; i<nhash(h); i++)
 145   {
 146    Node *n = node(h,i);
 147    if (tag(ref(n)) != LUA_T_NIL)
 148    {
 149     lua_markobject(&n->ref);
 150     lua_markobject(&n->val);
 151    }
 152   }
 153  }
 154 }
 155
 156
 157 static void call_fallbacks (void)
 158 {
 159   Hash *curr_array;
 160   Object t;
 161   tag(&t) = LUA_T_ARRAY;
 162   for (curr_array = listhead; curr_array; curr_array = curr_array->next)
 163     if (markarray(curr_array) != 1)
 164     {
 165       avalue(&t) = curr_array;
 166       luaI_gcFB(&t);
 167     }
 168   tag(&t) = LUA_T_NIL;
 169   luaI_gcFB(&t);  /* end of list */
 170 }
 171
 172
 173 /*
 174 ** Garbage collection to arrays
 175 ** Delete all unmarked arrays.
 176 */
 177 Long lua_hashcollector (void)
 178 {
 179  Hash *curr_array = listhead, *prev = NULL;
 180  Long counter = 0;
 181  call_fallbacks();
 182  while (curr_array != NULL)
 183  {
 184   Hash *next = curr_array->next;
 185   if (markarray(curr_array) != 1)
 186   {
 187    if (prev == NULL) listhead = next;
 188    else              prev->next = next;
 189    hashdelete(curr_array);
 190    ++counter;
 191   }
 192   else
 193   {
 194    markarray(curr_array) = 0;
 195    prev = curr_array;
 196   }
 197   curr_array = next;
 198  }
 199  return counter;
 200 }
 201
 202
 203 /*
 204 ** Create a new array
 205 ** This function inserts the new array in the array list. It also
 206 ** executes garbage collection if the number of arrays created
 207 ** exceed a pre-defined range.
 208 */
 209 Hash *lua_createarray (int nhash)
 210 {
 211  Hash *array;
 212  lua_pack();
 213  array = hashcreate(nhash);
 214  array->next = listhead;
 215  listhead = array;
 216  return array;
 217 }
 218
 219
 220 /*
 221 ** Re-hash
 222 */
 223 static void rehash (Hash *t)
 224 {
 225  int i;
 226  int   nold = nhash(t);
 227  Node *vold = nodevector(t);
 228  nhash(t) = luaI_redimension(nhash(t));
 229  nodevector(t) = hashnodecreate(nhash(t));
 230  for (i=0; i<nold; i++)
 231  {
 232   Node *n = vold+i;
 233   if (tag(ref(n)) != LUA_T_NIL && tag(val(n)) != LUA_T_NIL)
 234    *node(t, present(t, ref(n))) = *n;  /* copy old node to new hahs */
 235  }
 236  luaI_free(vold);
 237 }
 238
 239 /*
 240 ** If the hash node is present, return its pointer, otherwise return
 241 ** null.
 242 */
 243 Object *lua_hashget (Hash *t, Object *ref)
 244 {
 245  int h = present(t, ref);
 246  if (tag(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h));
 247  else return NULL;
 248 }
 249
 250
 251 /*
 252 ** If the hash node is present, return its pointer, otherwise create a new
 253 ** node for the given reference and also return its pointer.
 254 */
 255 Object *lua_hashdefine (Hash *t, Object *ref)
 256 {
 257  int   h;
 258  Node *n;
 259  h = present(t, ref);
 260  n = node(t, h);
 261  if (tag(ref(n)) == LUA_T_NIL)
 262  {
 263   nuse(t)++;
 264   if ((float)nuse(t) > (float)nhash(t)*REHASH_LIMIT)
 265   {
 266    rehash(t);
 267    h = present(t, ref);
 268    n = node(t, h);
 269   }
 270   *ref(n) = *ref;
 271   tag(val(n)) = LUA_T_NIL;
 272  }
 273  return (val(n));
 274 }
 275
 276
 277 /*
 278 ** Internal function to manipulate arrays.
 279 ** Given an array object and a reference value, return the next element
 280 ** in the hash.
 281 ** This function pushs the element value and its reference to the stack.
 282 */
 283 static void hashnext (Hash *t, int i)
 284 {
 285  if (i >= nhash(t))
 286  {
 287   lua_pushnil(); lua_pushnil();
 288   return;
 289  }
 290  while (tag(ref(node(t,i))) == LUA_T_NIL || tag(val(node(t,i))) == LUA_T_NIL)
 291  {
 292   if (++i >= nhash(t))
 293   {
 294    lua_pushnil(); lua_pushnil();
 295    return;
 296   }
 297  }
 298  luaI_pushobject(ref(node(t,i)));
 299  luaI_pushobject(val(node(t,i)));
 300 }
 301
 302 void lua_next (void)
 303 {
 304  Hash   *t;
 305  lua_Object o = lua_getparam(1);
 306  lua_Object r = lua_getparam(2);
 307  if (o == LUA_NOOBJECT || r == LUA_NOOBJECT)
 308    lua_error ("too few arguments to function `next'");
 309  if (lua_getparam(3) != LUA_NOOBJECT)
 310    lua_error ("too many arguments to function `next'");
 311  if (!lua_istable(o))
 312    lua_error ("first argument of function `next' is not a table");
 313  t = avalue(luaI_Address(o));
 314  if (lua_isnil(r))
 315  {
 316   hashnext(t, 0);
 317  }
 318  else
 319  {
 320   int h = present (t, luaI_Address(r));
 321   hashnext(t, h+1);
 322  }
 323 }