src/hash.c

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