hash.c

   1 /*
   2 ** hash.c
   3 ** hash manager for lua
   4 ** Luiz Henrique de Figueiredo - 17 Aug 90
   5 ** Modified by Waldemar Celes Filho
   6 ** 12 May 93
   7 */
   8
   9 #include <string.h>
  10 #include <stdlib.h>
  11
  12 #include "opcode.h"
  13 #include "hash.h"
  14 #include "inout.h"
  15 #include "table.h"
  16 #include "lua.h"
  17
  18 #define streq(s1,s2)    (strcmp(s1,s2)==0)
  19 #define strneq(s1,s2)   (strcmp(s1,s2)!=0)
  20
  21 #define new(s)          ((s *)malloc(sizeof(s)))
  22 #define newvector(n,s)  ((s *)calloc(n,sizeof(s)))
  23
  24 #define nhash(t)        ((t)->nhash)
  25 #define nodelist(t)     ((t)->list)
  26 #define list(t,i)       ((t)->list[i])
  27 #define ref_tag(n)      (tag(&(n)->ref))
  28 #define ref_nvalue(n)   (nvalue(&(n)->ref))
  29 #define ref_svalue(n)   (svalue(&(n)->ref))
  30
  31 static int head (Hash *t, Object *ref)          /* hash function */
  32 {
  33  if (tag(ref) == T_NUMBER) return (((int)nvalue(ref))%nhash(t));
  34  else if (tag(ref) == T_STRING)
  35  {
  36   int h;
  37   char *name = svalue(ref);
  38   for (h=0; *name!=0; name++)           /* interpret name as binary number */
  39   {
  40    h <<= 8;
  41    h  += (unsigned char) *name;         /* avoid sign extension */
  42    h  %= nhash(t);                      /* make it a valid index */
  43   }
  44   return h;
  45  }
  46  else
  47  {
  48   lua_reportbug ("unexpected type to index table");
  49   return -1;
  50  }
  51 }
  52
  53 static Node *present(Hash *t, Object *ref, int h)
  54 {
  55  Node *n=NULL, *p;
  56  if (tag(ref) == T_NUMBER)
  57  {
  58   for (p=NULL,n=list(t,h); n!=NULL; p=n, n=n->next)
  59    if (ref_tag(n) == T_NUMBER && nvalue(ref) == ref_nvalue(n)) break;
  60  }
  61  else if (tag(ref) == T_STRING)
  62  {
  63   for (p=NULL,n=list(t,h); n!=NULL; p=n, n=n->next)
  64    if (ref_tag(n) == T_STRING && streq(svalue(ref),ref_svalue(n))) break;
  65  }
  66  if (n==NULL)                           /* name not present */
  67   return NULL;
  68 #if 0
  69  if (p!=NULL)                           /* name present but not first */
  70  {
  71   p->next=n->next;                      /* move-to-front self-organization */
  72   n->next=list(t,h);
  73   list(t,h)=n;
  74  }
  75 #endif
  76  return n;
  77 }
  78
  79 static void freelist (Node *n)
  80 {
  81  while (n)
  82  {
  83   Node *next = n->next;
  84   free (n);
  85   n = next;
  86  }
  87 }
  88
  89 /*
  90 ** Create a new hash. Return the hash pointer or NULL on error.
  91 */
  92 Hash *lua_hashcreate (unsigned int nhash)
  93 {
  94  Hash *t = new (Hash);
  95  if (t == NULL)
  96  {
  97   lua_error ("not enough memory");
  98   return NULL;
  99  }
 100  nhash(t) = nhash;
 101  markarray(t) = 0;
 102  nodelist(t) = newvector (nhash, Node*);
 103  if (nodelist(t) == NULL)
 104  {
 105   lua_error ("not enough memory");
 106   return NULL;
 107  }
 108  return t;
 109 }
 110
 111 /*
 112 ** Delete a hash
 113 */
 114 void lua_hashdelete (Hash *h)
 115 {
 116  int i;
 117  for (i=0; i<nhash(h); i++)
 118   freelist (list(h,i));
 119  free (nodelist(h));
 120  free(h);
 121 }
 122
 123 /*
 124 ** If the hash node is present, return its pointer, otherwise create a new
 125 ** node for the given reference and also return its pointer.
 126 ** On error, return NULL.
 127 */
 128 Object *lua_hashdefine (Hash *t, Object *ref)
 129 {
 130  int   h;
 131  Node *n;
 132  h = head (t, ref);
 133  if (h < 0) return NULL;
 134
 135  n = present(t, ref, h);
 136  if (n == NULL)
 137  {
 138   n = new(Node);
 139   if (n == NULL)
 140   {
 141    lua_error ("not enough memory");
 142    return NULL;
 143   }
 144   n->ref = *ref;
 145   tag(&n->val) = T_NIL;
 146   n->next = list(t,h);                  /* link node to head of list */
 147   list(t,h) = n;
 148  }
 149  return (&n->val);
 150 }
 151
 152 /*
 153 ** Mark a hash and check its elements
 154 */
 155 void lua_hashmark (Hash *h)
 156 {
 157  int i;
 158
 159  markarray(h) = 1;
 160
 161  for (i=0; i<nhash(h); i++)
 162  {
 163   Node *n;
 164   for (n = list(h,i); n != NULL; n = n->next)
 165   {
 166    lua_markobject (&n->ref);
 167    lua_markobject (&n->val);
 168   }
 169  }
 170 }
 171
 172
 173 /*
 174 ** Internal function to manipulate arrays.
 175 ** Given an array object and a reference value, return the next element
 176 ** in the hash.
 177 ** This function pushs the element value and its reference to the stack.
 178 */
 179 #include "lua.h"
 180 static void firstnode (Hash *a, int h)
 181 {
 182  if (h < nhash(a))
 183  {
 184   int i;
 185   for (i=h; i<nhash(a); i++)
 186   {
 187    if (list(a,i) != NULL && tag(&list(a,i)->val) != T_NIL)
 188    {
 189     lua_pushobject (&list(a,i)->ref);
 190     lua_pushobject (&list(a,i)->val);
 191     return;
 192    }
 193   }
 194  }
 195  lua_pushnil();
 196  lua_pushnil();
 197 }
 198 void lua_next (void)
 199 {
 200  Hash   *a;
 201  Object *o = lua_getparam (1);
 202  Object *r = lua_getparam (2);
 203  if (o == NULL || r == NULL)
 204  { lua_error ("too few arguments to function `next'"); return; }
 205  if (lua_getparam (3) != NULL)
 206  { lua_error ("too many arguments to function `next'"); return; }
 207  if (tag(o) != T_ARRAY)
 208  { lua_error ("first argument of function `next' is not a table"); return; }
 209  a = avalue(o);
 210  if (tag(r) == T_NIL)
 211  {
 212   firstnode (a, 0);
 213   return;
 214  }
 215  else
 216  {
 217   int h = head (a, r);
 218   if (h >= 0)
 219   {
 220    Node *n = list(a,h);
 221    while (n)
 222    {
 223     if (memcmp(&n->ref,r,sizeof(Object)) == 0)
 224     {
 225      if (n->next == NULL)
 226      {
 227       firstnode (a, h+1);
 228       return;
 229      }
 230      else if (tag(&n->next->val) != T_NIL)
 231      {
 232       lua_pushobject (&n->next->ref);
 233       lua_pushobject (&n->next->val);
 234       return;
 235      }
 236      else
 237      {
 238       Node *next = n->next->next;
 239       while (next != NULL && tag(&next->val) == T_NIL) next = next->next;
 240       if (next == NULL)
 241       {
 242        firstnode (a, h+1);
 243        return;
 244       }
 245       else
 246       {
 247        lua_pushobject (&next->ref);
 248        lua_pushobject (&next->val);
 249       }
 250       return;
 251      }
 252     }
 253     n = n->next;
 254    }
 255    if (n == NULL)
 256     lua_error ("error in function 'next': reference not found");
 257   }
 258  }
 259 }