commit 9747f3c87a205d9aa914a650686d6dc4accde1d9
parent 12d9731a49530c4190142da3621f8508a629ca88
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Thu, 8 May 1997 17:43:10 -0300
double hashing + tables do not grow if there are empty slots
Diffstat:
| M | hash.c | | | 177 | ++++++++++++++++++++++++++++++++++++++++++------------------------------------- |
1 file changed, 94 insertions(+), 83 deletions(-)
diff --git a/hash.c b/hash.c
@@ -3,7 +3,7 @@
** hash manager for lua
*/
-char *rcs_hash="$Id: hash.c,v 2.40 1997/04/04 15:35:37 roberto Exp roberto $";
+char *rcs_hash="$Id: hash.c,v 2.41 1997/04/06 14:08:08 roberto Exp roberto $";
#include "luamem.h"
@@ -33,7 +33,7 @@ static Hash *listhead = NULL;
/* hash dimensions values */
static Long dimensions[] =
- {3L, 5L, 7L, 11L, 23L, 47L, 97L, 197L, 397L, 797L, 1597L, 3203L, 6421L,
+ {5L, 11L, 23L, 47L, 97L, 197L, 397L, 797L, 1597L, 3203L, 6421L,
12853L, 25717L, 51437L, 102811L, 205619L, 411233L, 822433L,
1644817L, 3289613L, 6579211L, 13158023L, MAX_INT};
@@ -49,7 +49,26 @@ int luaI_redimension (int nhash)
return 0; /* to avoid warnings */
}
-static int hashindex (Hash *t, TObject *ref) /* hash function */
+
+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)) {
@@ -68,36 +87,24 @@ static int hashindex (Hash *t, TObject *ref) /* hash function */
h = 0; /* UNREACHEABLE */
}
if (h < 0) h = -h;
- return h%nhash(t); /* make it a valid index */
+ return h;
}
-int lua_equalObj (TObject *t1, TObject *t2)
+
+static int present (Hash *t, TObject *key)
{
- 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 */
+ 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));
}
-}
-
-static int present (Hash *t, TObject *ref)
-{
- int h = hashindex(t, ref);
- while (ttype(ref(node(t, h))) != LUA_T_NIL)
- {
- if (lua_equalObj(ref, ref(node(t, h))))
- return h;
- h = (h+1) % nhash(t);
- }
- return h;
+ return h1;
}
@@ -221,22 +228,35 @@ Hash *lua_createarray (int nhash)
/*
-** Re-hash
+** 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 i;
- int nold = nhash(t);
- Node *vold = nodevector(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 hahs */
- }
- luaI_free(vold);
+ 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);
}
/*
@@ -257,23 +277,17 @@ TObject *lua_hashget (Hash *t, TObject *ref)
*/
TObject *lua_hashdefine (Hash *t, TObject *ref)
{
- int h;
- Node *n;
- h = present(t, ref);
- n = node(t, h);
- if (ttype(ref(n)) == LUA_T_NIL)
- {
- nuse(t)++;
- if ((float)nuse(t) > (float)nhash(t)*REHASH_LIMIT)
- {
- rehash(t);
- h = present(t, ref);
- n = node(t, h);
+ 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;
}
- *ref(n) = *ref;
- ttype(val(n)) = LUA_T_NIL;
- }
- return (val(n));
+ return (val(n));
}
@@ -285,33 +299,30 @@ TObject *lua_hashdefine (Hash *t, TObject *ref)
*/
static void hashnext (Hash *t, int i)
{
- if (i >= nhash(t))
- return;
- while (ttype(ref(node(t,i))) == LUA_T_NIL ||
- ttype(val(node(t,i))) == LUA_T_NIL)
- {
- if (++i >= nhash(t))
- return;
- }
- luaI_pushobject(ref(node(t,i)));
- luaI_pushobject(val(node(t,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
- {
- int h = present (t, luaI_Address(r));
- hashnext(t, h+1);
- }
+ 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);
}
