lua.lua/hash.c

/*
** hash.c
** hash manager for lua
*/

char *rcs_hash="$Id: hash.c,v 2.42 1997/05/08 20:43:30 roberto Exp roberto $";


#include "luamem.h"
#include "opcode.h"
#include "hash.h"
#include "table.h"
#include "lua.h"
#include "auxlib.h"


#define nhash(t)	((t)->nhash)
#define nuse(t)		((t)->nuse)
#define markarray(t)    ((t)->mark)
#define nodevector(t)	((t)->node)
#define node(t,i)	(&(t)->node[i])
#define ref(n)		(&(n)->ref)
#define val(n)		(&(n)->val)


#define REHASH_LIMIT    0.70    /* avoid more than this % full */

#define TagDefault LUA_T_ARRAY;


static Hash *listhead = NULL;


/* hash dimensions values */
static Long dimensions[] = 
 {5L, 11L, 23L, 47L, 97L, 197L, 397L, 797L, 1597L, 3203L, 6421L,
  12853L, 25717L, 51437L, 102811L, 205619L, 411233L, 822433L,
  1644817L, 3289613L, 6579211L, 13158023L, MAX_INT};

int luaI_redimension (int nhash)
{
 int i;
 for (i=0; dimensions[i]<MAX_INT; i++)
 {
  if (dimensions[i] > nhash)
   return dimensions[i];
 }
 lua_error("table overflow");
 return 0;  /* to avoid warnings */
}


int lua_equalObj (TObject *t1, TObject *t2)
{
  if (ttype(t1) != ttype(t2)) return 0;
  switch (ttype(t1))
  {
    case LUA_T_NIL: return 1;
    case LUA_T_NUMBER: return nvalue(t1) == nvalue(t2);
    case LUA_T_STRING: case LUA_T_USERDATA: return svalue(t1) == svalue(t2);
    case LUA_T_ARRAY: return avalue(t1) == avalue(t2);
    case LUA_T_FUNCTION: return t1->value.tf == t2->value.tf;
    case LUA_T_CFUNCTION: return fvalue(t1) == fvalue(t2);
    default:
     lua_error("internal error in `lua_equalObj'");
     return 0; /* UNREACHEABLE */
  }
}


static long int hashindex (TObject *ref)
{
  long int h;
  switch (ttype(ref)) {
    case LUA_T_NUMBER:
      h = (long int)nvalue(ref); break;
    case LUA_T_STRING: case LUA_T_USERDATA:
      h = tsvalue(ref)->hash; break;
    case LUA_T_FUNCTION:
      h = (IntPoint)ref->value.tf; break;
    case LUA_T_CFUNCTION:
      h = (IntPoint)fvalue(ref); break;
    case LUA_T_ARRAY:
      h = (IntPoint)avalue(ref); break;
    default:
      lua_error ("unexpected type to index table");
      h = 0;  /* UNREACHEABLE */
  }
  if (h < 0) h = -h;
  return h;
}


static int present (Hash *t, TObject *key)
{
  long int h = hashindex(key);
  int tsize = nhash(t);
  int h1 = h%tsize;
  TObject *rf = ref(node(t, h1));
  if (ttype(rf) != LUA_T_NIL && !lua_equalObj(key, rf)) {
    int h2 = h%(tsize-2) + 1;
    do {
      h1 = (h1+h2)%tsize;
      rf = ref(node(t, h1));
    } while (ttype(rf) != LUA_T_NIL && !lua_equalObj(key, rf));
  }
  return h1;
}


/*
** Alloc a vector node 
*/
static Node *hashnodecreate (int nhash)
{
 int i;
 Node *v = newvector (nhash, Node);
 for (i=0; i<nhash; i++)
   ttype(ref(&v[i])) = LUA_T_NIL;
 return v;
}

/*
** Create a new hash. Return the hash pointer or NULL on error.
*/
static Hash *hashcreate (int nhash)
{
 Hash *t = new(Hash);
 nhash = luaI_redimension((int)((float)nhash/REHASH_LIMIT));
 nodevector(t) = hashnodecreate(nhash);
 nhash(t) = nhash;
 nuse(t) = 0;
 markarray(t) = 0;
 t->htag = TagDefault;
 return t;
}

/*
** Delete a hash
*/
static void hashdelete (Hash *t)
{
 luaI_free (nodevector(t));
 luaI_free(t);
}


/*
** Mark a hash and check its elements 
*/
void lua_hashmark (Hash *h)
{
 if (markarray(h) == 0)
 {
  int i;
  markarray(h) = 1;
  for (i=0; i<nhash(h); i++)
  {
   Node *n = node(h,i);
   if (ttype(ref(n)) != LUA_T_NIL)
   {
    lua_markobject(&n->ref);
    lua_markobject(&n->val);
   }
  }
 } 
}


void luaI_hashcallIM (Hash *l)
{
  TObject t;
  ttype(&t) = LUA_T_ARRAY;
  for (; l; l=l->next) {
    avalue(&t) = l;
    luaI_gcIM(&t);
  }
}


void luaI_hashfree (Hash *frees)
{
  while (frees) {
    Hash *next = frees->next;
    hashdelete(frees);
    frees = next;
  }
}

 
Hash *luaI_hashcollector (long *acum)
{
  Hash *curr_array = listhead, *prev = NULL, *frees = NULL;
  long counter = 0;
  while (curr_array != NULL) {
    Hash *next = curr_array->next;
    if (markarray(curr_array) != 1) {
      if (prev == NULL)
        listhead = next;
      else
        prev->next = next;
      curr_array->next = frees;
      frees = curr_array;
      ++counter;
    }
    else {
      markarray(curr_array) = 0;
      prev = curr_array;
    }
    curr_array = next;
  }
  *acum += counter;
  return frees;
}


/*
** Create a new array
** This function inserts the new array in the array list. It also
** executes garbage collection if the number of arrays created
** exceed a pre-defined range.
*/
Hash *lua_createarray (int nhash)
{
 Hash *array;
 lua_pack();
 array = hashcreate(nhash);
 array->next = listhead;
 listhead = array;
 return array;
}


/*
** Rehash:
** Check if table has deleted slots. It it has, it does not need to
** grow, since rehash will reuse them.
*/
static int emptyslots (Hash *t)
{
  int i;
  for (i=nhash(t)-1; i>=0; i--) {
    Node *n = node(t, i);
    if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) == LUA_T_NIL)
      return 1;
  }
  return 0;
}

static void rehash (Hash *t)
{
  int   nold = nhash(t);
  Node *vold = nodevector(t);
  int i;
  if (!emptyslots(t))
    nhash(t) = luaI_redimension(nhash(t));
  nodevector(t) = hashnodecreate(nhash(t));
  for (i=0; i<nold; i++) {
    Node *n = vold+i;
    if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) != LUA_T_NIL)
      *node(t, present(t, ref(n))) = *n;  /* copy old node to new hash */
  }
  luaI_free(vold);
}

/*
** If the hash node is present, return its pointer, otherwise return
** null.
*/
TObject *lua_hashget (Hash *t, TObject *ref)
{
 int h = present(t, ref);
 if (ttype(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h));
 else return NULL;
}


/*
** If the hash node is present, return its pointer, otherwise create a new
** node for the given reference and also return its pointer.
*/
TObject *lua_hashdefine (Hash *t, TObject *ref)
{
  Node *n = node(t, present(t, ref));
  if (ttype(ref(n)) == LUA_T_NIL) {
    nuse(t)++;
    if ((float)nuse(t) > (float)nhash(t)*REHASH_LIMIT) {
      rehash(t);
      n = node(t, present(t, ref));
    }
    *ref(n) = *ref;
    ttype(val(n)) = LUA_T_NIL;
  }
  return (val(n));
}


/*
** Internal function to manipulate arrays. 
** Given an array object and a reference value, return the next element
** in the hash.
** This function pushs the element value and its reference to the stack.
*/
static void hashnext (Hash *t, int i)
{
  Node *n;
  int tsize = nhash(t);
  if (i >= tsize)
    return;
  n = node(t, i);
  while (ttype(ref(n)) == LUA_T_NIL || ttype(val(n)) == LUA_T_NIL) {
    if (++i >= tsize)
      return;
    n = node(t, i);
  }
  luaI_pushobject(ref(node(t,i)));
  luaI_pushobject(val(node(t,i)));
}

void lua_next (void)
{
  Hash *t;
  lua_Object o = lua_getparam(1);
  lua_Object r = lua_getparam(2);
  luaL_arg_check(lua_istable(o), 1, "table expected");
  luaL_arg_check(r != LUA_NOOBJECT, 2, "value expected");
  t = avalue(luaI_Address(o));
  if (lua_isnil(r))
    hashnext(t, 0);
  else
    hashnext(t, present(t, luaI_Address(r))+1);
}