lua

commit 33c49f7fa03cf7e3bf7bb3aa697dc567d910c661
parent 0df6635711230ab306710056f621b6da59fac5ea
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date:   Thu, 22 Aug 2013 12:21:23 -0300

some details over new implementation of string table

Diffstat:
M
lstate.h
 | 
8
++++----
M
lstring.c
 | 
34
++++++++++++++++++----------------
M
ltests.c
 | 
4
++--

3 files changed, 24 insertions(+), 22 deletions(-)
diff --git a/lstate.h b/lstate.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.h,v 2.86 2013/08/21 19:21:16 roberto Exp roberto $
+** $Id: lstate.h,v 2.87 2013/08/21 20:09:51 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -59,9 +59,9 @@ struct lua_longjmp;  /* defined in ldo.c */
 
 typedef struct stringtable {
   TString **hash;
-  unsigned int nuse;  /* number of elements */
-  unsigned int empty;  /* number of available empty slots */
-  unsigned int size;
+  int nuse;  /* number of elements */
+  int empty;  /* number of available empty slots */
+  int size;
 } stringtable;
 
 
diff --git a/lstring.c b/lstring.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.c,v 2.28 2013/08/05 16:58:28 roberto Exp roberto $
+** $Id: lstring.c,v 2.29 2013/08/21 19:21:16 roberto Exp roberto $
 ** String table (keeps all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -13,6 +13,7 @@
 #include "lua.h"
 
 #include "ldebug.h"
+#include "ldo.h"
 #include "lmem.h"
 #include "lobject.h"
 #include "lstate.h"
@@ -24,7 +25,7 @@
 
 
 /* second hash (for double hash) */
-#define h2(h1,hash,size)	lmod(h1 + ((hash % 31) | 1), size)
+#define h2(h1,hash,size)	lmod(h1 + ((hash % 61) | 1), size)
 
 
 /*
@@ -116,19 +117,18 @@ static TString *createstrobj (lua_State *L, const char *str, size_t l,
 
 
 static void rehash (lua_State *L, stringtable *tb) {
-  int newsize;
-  if (tb->nuse < tb->size / 2) {  /* using less than half the size? */
-    if (tb->nuse < tb->size / 4)  /* using less than half of that? */
-      newsize = tb->size / 2;  /* shrink table */
-    else
-      newsize = tb->size;  /* keep size (but reorganize table) */
+  int size = tb->size;
+  if (tb->nuse < size / 2) {  /* using less than half the size? */
+    if (tb->nuse < size / 4)  /* using less than half of that? */
+      size /= 2;  /* shrink table */
+    /* else keep size (but reorganize table) */
   }
   else {  /* table must grow */
-    if (tb->size >= MAX_INT/2)
-      luaG_runerror(L, "string-table overflow: too many strings");
-    newsize = tb->size * 2;
+    if (size >= MAX_INT/2)  /* avoid arith. overflow */
+      luaD_throw(L, LUA_ERRMEM);  /* regular errors need new strings... */
+    size *= 2;
   }
-  luaS_resize(L, newsize);
+  luaS_resize(L, size);
 }
 
 
@@ -154,12 +154,10 @@ static TString *internshrstr (lua_State *L, const char *str, size_t l) {
   stringtable *tb = &G(L)->strt;
   int vacant = -1;
   int h1;
-  if (tb->empty <= 0)
-    rehash(L, tb);
   h1 = lmod(hash, tb->size);  /* previous call can changed 'size' */
   while ((ts = tb->hash[h1]) != NULL) {  /* search the string in hash table */
     if (ts == VACANTK) {
-      if (vacant < 0) vacant = h1;  /* keep track of a vacant place */
+      if (vacant < 0) vacant = h1;  /* keep track of first vacant place */
     }
     else if (l == ts->tsv.len &&
             (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
@@ -174,12 +172,16 @@ static TString *internshrstr (lua_State *L, const char *str, size_t l) {
     }
     h1 = h2(h1, hash, tb->size);
   }
+  if (tb->empty <= 0) {  /* no more empty spaces? */
+    rehash(L, tb);
+    return internshrstr(L, str, l);  /* recompute insertion with new size */
+  }
   ts = createstrobj(L, str, l, LUA_TSHRSTR, hash);
   tb->nuse++;
   if (vacant < 0)  /* found no vacant place? */
     tb->empty--;  /* will have to use the empty place */
   else
-    h1 = vacant;  /* insert string into vacant place */
+    h1 = vacant;  /* use vacant place */
   tb->hash[h1] = ts;
   return ts;
 }
diff --git a/ltests.c b/ltests.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltests.c,v 2.146 2013/08/20 17:46:34 roberto Exp roberto $
+** $Id: ltests.c,v 2.147 2013/08/21 19:21:16 roberto Exp roberto $
 ** Internal Module for Debugging of the Lua Implementation
 ** See Copyright Notice in lua.h
 */
@@ -747,7 +747,7 @@ static int string_query (lua_State *L) {
     lua_pushinteger(L ,tb->size);
     return 2;
   }
-  else if ((unsigned int)s < tb->size) {
+  else if (s < tb->size) {
     TString *ts = tb->hash[s];
     setsvalue2s(L, L->top, ts);
     api_incr_top(L);