1 files changed, 62 insertions, 77 deletions

diff --git a/src/lstring.c b/src/lstring.c
index fd7cc580..fa974ae9 100644
--- a/src/lstring.c
+++ b/src/lstring.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.c,v 1.13 1998/06/19 16:14:09 roberto Exp $
+** $Id: lstring.c,v 1.19 1999/02/26 15:49:53 roberto Exp $
 ** String table (keeps all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -14,7 +14,9 @@
 #include "lua.h"
 
 
-#define NUM_HASHS  61
+#define NUM_HASHSTR	31
+#define NUM_HASHUDATA	31
+#define NUM_HASHS  (NUM_HASHSTR+NUM_HASHUDATA)
 
 
 #define gcsizestring(l)	(1+(l/64))  /* "weight" for a string with length 'l' */
@@ -25,8 +27,7 @@ static TaggedString EMPTY = {{NULL, 2}, 0L, 0,
                             {{{LUA_T_NIL, {NULL}}, 0L}}, {0}};
 
 
-void luaS_init (void)
-{
+void luaS_init (void) {
   int i;
   L->string_root = luaM_newvector(NUM_HASHS, stringtable);
   for (i=0; i<NUM_HASHS; i++) {
@@ -37,16 +38,14 @@ void luaS_init (void)
 }
 
 
-static unsigned long hash_s (char *s, long l)
-{
-  unsigned long h = 0;
+static unsigned long hash_s (char *s, long l) {
+  unsigned long h = 0;  /* seed */
   while (l--)
-    h = ((h<<5)-h)^(unsigned char)*(s++);
+      h = h ^ ((h<<5)+(h>>2)+(unsigned char)*(s++));
   return h;
 }
 
-static int newsize (stringtable *tb)
-{
+static int newsize (stringtable *tb) {
   int size = tb->size;
   int realuse = 0;
   int i;
@@ -54,16 +53,11 @@ static int newsize (stringtable *tb)
   for (i=0; i<size; i++)
     if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY)
       realuse++;
-  if (2*(realuse+1) <= size)  /* +1 is the new element */
-    return size;  /* don't need to grow, just rehash to clear EMPTYs */
-  else
-    return luaO_redimension(size);
+  return luaO_redimension((realuse+1)*2);  /* +1 is the new element */
 }
 
 
-static void grow (stringtable *tb)
-{
-  
+static void grow (stringtable *tb) {
   int ns = newsize(tb);
   TaggedString **newhash = luaM_newvector(ns, TaggedString *);
   int i;
@@ -73,10 +67,13 @@ static void grow (stringtable *tb)
   tb->nuse = 0;
   for (i=0; i<tb->size; i++) {
     if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY) {
-      int h = tb->hash[i]->hash%ns;
-      while (newhash[h])
-        h = (h+1)%ns;
-      newhash[h] = tb->hash[i];
+      unsigned long h = tb->hash[i]->hash;
+      int h1 = h%ns;
+      while (newhash[h1]) {
+        h1 += (h&(ns-2)) + 1;  /* double hashing */
+        if (h1 >= ns) h1 -= ns;
+      }
+      newhash[h1] = tb->hash[i];
       tb->nuse++;
     }
   }
@@ -86,8 +83,7 @@ static void grow (stringtable *tb)
 }
 
 
-static TaggedString *newone_s (char *str, long l, unsigned long h)
-{
+static TaggedString *newone_s (char *str, long l, unsigned long h) {
   TaggedString *ts = (TaggedString *)luaM_malloc(sizeof(TaggedString)+l);
   memcpy(ts->str, str, l);
   ts->str[l] = 0;  /* ending 0 */
@@ -101,8 +97,7 @@ static TaggedString *newone_s (char *str, long l, unsigned long h)
   return ts;
 }
 
-static TaggedString *newone_u (char *buff, int tag, unsigned long h)
-{
+static TaggedString *newone_u (char *buff, int tag, unsigned long h) {
   TaggedString *ts = luaM_new(TaggedString);
   ts->u.d.v = buff;
   ts->u.d.tag = (tag == LUA_ANYTAG) ? 0 : tag;
@@ -114,82 +109,79 @@ static TaggedString *newone_u (char *buff, int tag, unsigned long h)
   return ts;
 }
 
-static TaggedString *insert_s (char *str, long l, stringtable *tb)
-{
+static TaggedString *insert_s (char *str, long l, stringtable *tb) {
   TaggedString *ts;
   unsigned long h = hash_s(str, l);
   int size = tb->size;
-  int i;
   int j = -1;
+  int h1;
   if ((long)tb->nuse*3 >= (long)size*2) {
     grow(tb);
     size = tb->size;
   }
-  for (i = h%size; (ts = tb->hash[i]) != NULL; ) {
+  h1 = h%size;
+  while ((ts = tb->hash[h1]) != NULL) {
     if (ts == &EMPTY)
-      j = i;
-    else if (ts->constindex >= 0 &&
-             ts->u.s.len == l &&
-             (memcmp(str, ts->str, l) == 0))
+      j = h1;
+    else if (ts->u.s.len == l && (memcmp(str, ts->str, l) == 0))
       return ts;
-    if (++i == size) i=0;
+    h1 += (h&(size-2)) + 1;  /* double hashing */
+    if (h1 >= size) h1 -= size;
   }
   /* not found */
   if (j != -1)  /* is there an EMPTY space? */
-    i = j;
+    h1 = j;
   else
     tb->nuse++;
-  ts = tb->hash[i] = newone_s(str, l, h);
+  ts = tb->hash[h1] = newone_s(str, l, h);
   return ts;
 }
 
-static TaggedString *insert_u (void *buff, int tag, stringtable *tb)
-{
+
+static TaggedString *insert_u (void *buff, int tag, stringtable *tb) {
   TaggedString *ts;
   unsigned long h = (unsigned long)buff;
   int size = tb->size;
-  int i;
   int j = -1;
+  int h1;
   if ((long)tb->nuse*3 >= (long)size*2) {
     grow(tb);
     size = tb->size;
   }
-  for (i = h%size; (ts = tb->hash[i]) != NULL; ) {
+  h1 = h%size;
+  while ((ts = tb->hash[h1]) != NULL) {
     if (ts == &EMPTY)
-      j = i;
-    else if (ts->constindex < 0 &&  /* is a udata? */
-             (tag == ts->u.d.tag || tag == LUA_ANYTAG) &&
-             buff == ts->u.d.v)
+      j = h1;
+    else if ((tag == ts->u.d.tag || tag == LUA_ANYTAG) && buff == ts->u.d.v)
       return ts;
-    if (++i == size) i=0;
+    h1 += (h&(size-2)) + 1;  /* double hashing */
+    if (h1 >= size) h1 -= size;
   }
   /* not found */
   if (j != -1)  /* is there an EMPTY space? */
-    i = j;
+    h1 = j;
   else
     tb->nuse++;
-  ts = tb->hash[i] = newone_u(buff, tag, h);
+  ts = tb->hash[h1] = newone_u(buff, tag, h);
   return ts;
 }
 
-TaggedString *luaS_createudata (void *udata, int tag)
-{
-  return insert_u(udata, tag, &L->string_root[(unsigned)udata%NUM_HASHS]);
+
+TaggedString *luaS_createudata (void *udata, int tag) {
+  int t = ((unsigned)udata%NUM_HASHUDATA)+NUM_HASHSTR;
+  return insert_u(udata, tag, &L->string_root[t]);
 }
 
-TaggedString *luaS_newlstr (char *str, long l)
-{
-  int i = (l==0)?0:(unsigned char)str[0];
-  return insert_s(str, l, &L->string_root[i%NUM_HASHS]);
+TaggedString *luaS_newlstr (char *str, long l) {
+  int t = (l==0) ? 0 : ((int)((unsigned char)str[0]*l))%NUM_HASHSTR;
+  return insert_s(str, l, &L->string_root[t]);
 }
 
-TaggedString *luaS_new (char *str)
-{
+TaggedString *luaS_new (char *str) {
   return luaS_newlstr(str, strlen(str));
 }
 
-TaggedString *luaS_newfixedstring (char *str)
-{
+TaggedString *luaS_newfixedstring (char *str) {
   TaggedString *ts = luaS_new(str);
   if (ts->head.marked == 0)
     ts->head.marked = 2;  /* avoid GC */
@@ -197,8 +189,7 @@ TaggedString *luaS_newfixedstring (char *str)
 }
 
 
-void luaS_free (TaggedString *l)
-{
+void luaS_free (TaggedString *l) {
   while (l) {
     TaggedString *next = (TaggedString *)l->head.next;
     L->nblocks -= (l->constindex == -1) ? 1 : gcsizestring(l->u.s.len);
@@ -212,8 +203,7 @@ void luaS_free (TaggedString *l)
 ** Garbage collection functions.
 */
 
-static void remove_from_list (GCnode *l)
-{
+static void remove_from_list (GCnode *l) {
   while (l) {
     GCnode *next = l->next;
     while (next && !next->marked)
@@ -223,8 +213,7 @@ static void remove_from_list (GCnode *l)
 }
 
 
-TaggedString *luaS_collector (void)
-{
+TaggedString *luaS_collector (void) {
   TaggedString *frees = NULL;
   int i;
   remove_from_list(&(L->rootglobal));
@@ -247,18 +236,18 @@ TaggedString *luaS_collector (void)
 }
 
 
-TaggedString *luaS_collectudata (void)
-{
+TaggedString *luaS_collectudata (void) {
   TaggedString *frees = NULL;
   int i;
   L->rootglobal.next = NULL;  /* empty list of globals */
-  for (i=0; i<NUM_HASHS; i++) {
+  for (i=NUM_HASHSTR; i<NUM_HASHS; i++) {
     stringtable *tb = &L->string_root[i];
     int j;
     for (j=0; j<tb->size; j++) {
       TaggedString *t = tb->hash[j];
-      if (t == NULL || t == &EMPTY || t->constindex != -1)
-        continue;  /* get only user data */
+      if (t == NULL || t == &EMPTY)
+        continue;
+      LUA_ASSERT(t->constindex == -1, "must be userdata");
       t->head.next = (GCnode *)frees;
       frees = t;
       tb->hash[j] = &EMPTY;
@@ -268,8 +257,7 @@ TaggedString *luaS_collectudata (void)
 }
 
 
-void luaS_freeall (void)
-{
+void luaS_freeall (void) {
   int i;
   for (i=0; i<NUM_HASHS; i++) {
     stringtable *tb = &L->string_root[i];
@@ -285,8 +273,7 @@ void luaS_freeall (void)
 }
 
 
-void luaS_rawsetglobal (TaggedString *ts, TObject *newval)
-{
+void luaS_rawsetglobal (TaggedString *ts, TObject *newval) {
   ts->u.s.globalval = *newval;
   if (ts->head.next == (GCnode *)ts) {  /* is not in list? */
     ts->head.next = L->rootglobal.next;
@@ -295,8 +282,7 @@ void luaS_rawsetglobal (TaggedString *ts, TObject *newval)
 }
 
 
-char *luaS_travsymbol (int (*fn)(TObject *))
-{
+char *luaS_travsymbol (int (*fn)(TObject *)) {
   TaggedString *g;
   for (g=(TaggedString *)L->rootglobal.next; g; g=(TaggedString *)g->head.next)
     if (fn(&g->u.s.globalval))
@@ -305,8 +291,7 @@ char *luaS_travsymbol (int (*fn)(TObject *))
 }
 
 
-int luaS_globaldefined (char *name)
-{
+int luaS_globaldefined (char *name) {
   TaggedString *ts = luaS_new(name);
   return ts->u.s.globalval.ttype != LUA_T_NIL;
 }