From 4e9f2d13d5b6fa71ca480394e0b7e75463d4aeec Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Thu, 14 Oct 1999 17:13:31 -0200 Subject: new implementation of hash tables. --- lbuiltin.c | 73 +++++++++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 49 insertions(+), 24 deletions(-) (limited to 'lbuiltin.c') diff --git a/lbuiltin.c b/lbuiltin.c index f3fbce43..f2821bdb 100644 --- a/lbuiltin.c +++ b/lbuiltin.c @@ -1,5 +1,5 @@ /* -** $Id: lbuiltin.c,v 1.65 1999/10/07 19:04:30 roberto Exp roberto $ +** $Id: lbuiltin.c,v 1.66 1999/10/11 16:13:11 roberto Exp roberto $ ** Built-in functions ** See Copyright Notice in lua.h */ @@ -44,13 +44,13 @@ static void pushtagstring (TaggedString *s) { static real getsize (const Hash *h) { real max = 0; - int i = nhash(h); + int i = h->size; Node *n = h->node; while (i--) { - if (ttype(ref(n)) == LUA_T_NUMBER && + if (ttype(key(n)) == LUA_T_NUMBER && ttype(val(n)) != LUA_T_NIL && - nvalue(ref(n)) > max) - max = nvalue(ref(n)); + nvalue(key(n)) > max) + max = nvalue(key(n)); n++; } return max; @@ -59,7 +59,7 @@ static real getsize (const Hash *h) { static real getnarg (const Hash *a) { TObject index; - TObject *value; + const TObject *value; /* value = table.n */ ttype(&index) = LUA_T_STRING; tsvalue(&index) = luaS_new("n"); @@ -337,7 +337,13 @@ static void luaB_nextvar (void) { static void luaB_next (void) { const Hash *a = gethash(1); const TObject *k = luaA_Address(luaL_nonnullarg(2)); - int i = (ttype(k) == LUA_T_NIL) ? 0 : luaH_pos(a, k)+1; + int i; /* will get first element after `i' */ + if (ttype(k) == LUA_T_NIL) + i = 0; /* get first */ + else { + i = luaH_pos(a, k)+1; + luaL_arg_check(i != 0, 2, "key not found"); + } if (luaA_next(a, i) == 0) lua_pushnil(); } @@ -408,7 +414,7 @@ static void luaB_foreachi (void) { stack may be reallocated by the call. Moreover, some C compilers do not initialize structs, so we must do the assignment after the declaration */ f = *luaA_Address(luaL_functionarg(2)); - luaD_checkstack(3); /* for f, ref, and val */ + luaD_checkstack(3); /* for f, key, and val */ for (i=1; i<=n; i++) { *(L->stack.top++) = f; ttype(L->stack.top) = LUA_T_NUMBER; nvalue(L->stack.top++) = i; @@ -426,12 +432,12 @@ static void luaB_foreach (void) { int i; TObject f; /* see comment in 'foreachi' */ f = *luaA_Address(luaL_functionarg(2)); - luaD_checkstack(3); /* for f, ref, and val */ - for (i=0; inhash; i++) { + luaD_checkstack(3); /* for f, key, and val */ + for (i=0; isize; i++) { const Node *nd = &(a->node[i]); if (ttype(val(nd)) != LUA_T_NIL) { *(L->stack.top++) = f; - *(L->stack.top++) = *ref(nd); + *(L->stack.top++) = *key(nd); *(L->stack.top++) = *val(nd); luaD_calln(2, 1); if (ttype(L->stack.top-1) != LUA_T_NIL) @@ -531,36 +537,37 @@ static int sort_comp (lua_Object f, const TObject *a, const TObject *b) { } static void auxsort (Hash *a, int l, int u, lua_Object f) { + StkId P = L->stack.top - L->stack.stack; /* temporary place for pivot */ + L->stack.top++; + ttype(L->stack.stack+P) = LUA_T_NIL; while (l < u) { /* for tail recursion */ - TObject *P; int i, j; /* sort elements a[l], a[(l+u)/2] and a[u] */ - if (sort_comp(f, luaH_getint(a, u), luaH_getint(a, l))) /* a[l]>a[u]? */ + if (sort_comp(f, luaH_getint(a, u), luaH_getint(a, l))) /* a[u]a[i]? */ + *(L->stack.stack+P) = *luaH_getint(a, i); /* P = a[i] */ + if (sort_comp(f, L->stack.stack+P, luaH_getint(a, l))) /* a[i]a[u]? */ + else if (sort_comp(f, luaH_getint(a, u), L->stack.stack+P)) /* a[u]stack.top++; - *P = *luaH_getint(a, i); /* save pivot on stack (for GC) */ + *(L->stack.stack+P) = *luaH_getint(a, i); /* save pivot on stack (for GC) */ swap(a, i, u-1); /* put median element as pivot (a[u-1]) */ /* a[l] <= P == a[u-1] <= a[u], only needs to sort from l+1 to u-2 */ i = l; j = u-1; - for (;;) { - /* invariant: a[l..i] <= P <= a[j..u] */ - while (sort_comp(f, luaH_getint(a, ++i), P)) /* stop when a[i] >= P */ + for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */ + /* repeat i++ until a[i] >= P */ + while (sort_comp(f, luaH_getint(a, ++i), L->stack.stack+P)) if (i>u) lua_error("invalid order function for sorting"); - while (sort_comp(f, P, luaH_getint(a, --j))) /* stop when a[j] <= P */ + /* repeat j-- until a[j] <= P */ + while (sort_comp(f, (L->stack.stack+P), luaH_getint(a, --j))) if (jstack.top--; /* remove pivot from stack */ /* a[l..i-1] <= a[i] == P <= a[i+1..u] */ /* adjust so that smaller "half" is in [j..i] and larger one in [l..u] */ if (i-l < u-i) { @@ -571,6 +578,7 @@ static void auxsort (Hash *a, int l, int u, lua_Object f) { } auxsort(a, j, i, f); /* call recursively the smaller one */ } /* repeat the routine for the larger one */ + L->stack.top--; /* remove pivot from stack */ } static void luaB_sort (void) { @@ -608,7 +616,23 @@ static void mem_query (void) { static void hash_query (void) { const TObject *o = luaA_Address(luaL_nonnullarg(1)); - lua_pushnumber(luaH_hashindex(o)); + luaL_arg_check(ttype(o) == LUA_T_STRING, 1, "string expected"); + lua_pushnumber(tsvalue(o)->hash); +} + + +static void table_query (void) { + const Hash *t = avalue(luaA_Address(luaL_tablearg(1))); + int i = luaL_opt_int(2, -1); + if (i == -1) { + lua_pushnumber(t->size); + lua_pushnumber(t->firstfree - t->node); + } + else if (i < t->size) { + luaA_pushobject(&t->node[i].key); + luaA_pushobject(&t->node[i].val); + lua_pushnumber(t->node[i].next == NULL ? 0 : t->node[i].next - t->node); + } } @@ -715,6 +739,7 @@ static const struct luaL_reg builtin_funcs[] = { {"extra", extra_services}, {"hash", hash_query}, {"querystr", query_strings}, + {"querytab", table_query}, {"testC", testC}, {"totalmem", mem_query}, #endif -- cgit v1.2.3-55-g6feb