lua

A copy of the Lua development repository
Log | Files | Refs | README

commit 534c3a64d3b47585b415f229aa03af35f9a4796e
parent b9c98cd4d97774d703a48fefd56c66f552e0cd83
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date:   Tue, 25 Apr 2000 13:54:47 -0300

small optimizations for table access

Diffstat:
Mlbuiltin.c | 24++++++++++++------------
Mlobject.c | 5+++--
Mlobject.h | 5++---
Mltable.c | 48+++++++++++++++++++++++++++++++++++++-----------
Mltable.h | 6+++---
5 files changed, 57 insertions(+), 31 deletions(-)

diff --git a/lbuiltin.c b/lbuiltin.c @@ -1,5 +1,5 @@ /* -** $Id: lbuiltin.c,v 1.105 2000/04/14 17:44:20 roberto Exp roberto $ +** $Id: lbuiltin.c,v 1.106 2000/04/17 19:23:12 roberto Exp roberto $ ** Built-in functions ** See Copyright Notice in lua.h */ @@ -321,7 +321,7 @@ void luaB_call (lua_State *L) { /* push arg[1...n] */ luaD_checkstack(L, narg); for (i=0; i<narg; i++) - *(L->top++) = *luaH_getint(L, arg, i+1); + *(L->top++) = *luaH_getnum(arg, i+1); status = lua_callfunction(L, f); if (err != LUA_NOOBJECT) { /* restore old error method */ lua_pushobject(L, err); @@ -434,7 +434,7 @@ void luaB_foreachi (lua_State *L) { for (i=1; i<=n; i++) { *(L->top++) = *f; ttype(L->top) = TAG_NUMBER; nvalue(L->top++) = i; - *(L->top++) = *luaH_getint(L, t, i); + *(L->top++) = *luaH_getnum(t, i); luaD_call(L, L->top-3, 1); if (ttype(L->top-1) != TAG_NIL) return; @@ -513,7 +513,7 @@ void luaB_tremove (lua_State *L) { int n = (int)getnarg(L, a); int pos = luaL_opt_int(L, 2, n); if (n <= 0) return; /* table is "empty" */ - luaA_pushobject(L, luaH_getint(L, a, pos)); /* result = a[pos] */ + luaA_pushobject(L, luaH_getnum(a, pos)); /* result = a[pos] */ for ( ;pos<n; pos++) luaH_move(L, a, pos+1, pos); /* a[pos] = a[pos+1] */ luaV_setn(L, a, n-1); /* a.n = n-1 */ @@ -529,7 +529,7 @@ void luaB_tremove (lua_State *L) { static void swap (lua_State *L, Hash *a, int i, int j) { TObject temp; - temp = *luaH_getint(L, a, i); + temp = *luaH_getnum(a, i); luaH_move(L, a, j, i); luaH_setint(L, a, j, &temp); } @@ -556,26 +556,26 @@ static void auxsort (lua_State *L, Hash *a, int l, int u, lua_Object f) { while (l < u) { /* for tail recursion */ int i, j; /* sort elements a[l], a[(l+u)/2] and a[u] */ - if (sort_comp(L, f, luaH_getint(L, a, u), luaH_getint(L, a, l))) + if (sort_comp(L, f, luaH_getnum(a, u), luaH_getnum(a, l))) swap(L, a, l, u); /* a[u]<a[l] */ if (u-l == 1) break; /* only 2 elements */ i = (l+u)/2; - *P = *luaH_getint(L, a, i); /* P = a[i] */ - if (sort_comp(L, f, P, luaH_getint(L, a, l))) /* a[i]<a[l]? */ + *P = *luaH_getnum(a, i); /* P = a[i] */ + if (sort_comp(L, f, P, luaH_getnum(a, l))) /* a[i]<a[l]? */ swap(L, a, l, i); - else if (sort_comp(L, f, luaH_getint(L, a, u), P)) /* a[u]<a[i]? */ + else if (sort_comp(L, f, luaH_getnum(a, u), P)) /* a[u]<a[i]? */ swap(L, a, i, u); if (u-l == 2) break; /* only 3 elements */ - *P = *luaH_getint(L, a, i); /* save pivot on stack (GC) */ + *P = *luaH_getnum(a, i); /* save pivot on stack (GC) */ swap(L, 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] */ /* repeat i++ until a[i] >= P */ - while (sort_comp(L, f, luaH_getint(L, a, ++i), P)) + while (sort_comp(L, f, luaH_getnum(a, ++i), P)) if (i>u) lua_error(L, "invalid order function for sorting"); /* repeat j-- until a[j] <= P */ - while (sort_comp(L, f, P, luaH_getint(L, a, --j))) + while (sort_comp(L, f, P, luaH_getnum(a, --j))) if (j<l) lua_error(L, "invalid order function for sorting"); if (j<i) break; swap(L, a, i, j); diff --git a/lobject.c b/lobject.c @@ -1,5 +1,5 @@ /* -** $Id: lobject.c,v 1.35 2000/03/29 20:19:20 roberto Exp roberto $ +** $Id: lobject.c,v 1.36 2000/03/31 16:28:45 roberto Exp roberto $ ** Some generic functions over Lua objects ** See Copyright Notice in lua.h */ @@ -32,7 +32,8 @@ unsigned long luaO_power2 (unsigned long n) { } -int luaO_equalval (const TObject *t1, const TObject *t2) { +int luaO_equalObj (const TObject *t1, const TObject *t2) { + if (ttype(t1) != ttype(t2)) return 0; switch (ttype(t1)) { case TAG_NUMBER: return nvalue(t1) == nvalue(t2); diff --git a/lobject.h b/lobject.h @@ -1,5 +1,5 @@ /* -** $Id: lobject.h,v 1.59 2000/03/31 16:28:45 roberto Exp roberto $ +** $Id: lobject.h,v 1.60 2000/04/10 19:20:24 roberto Exp roberto $ ** Type definitions for Lua objects ** See Copyright Notice in lua.h */ @@ -180,8 +180,7 @@ extern const TObject luaO_nilobject; unsigned long luaO_power2 (unsigned long n); -#define luaO_equalObj(t1,t2) (ttype(t1) == ttype(t2) && luaO_equalval(t1,t2)) -int luaO_equalval (const TObject *t1, const TObject *t2); +int luaO_equalObj (const TObject *t1, const TObject *t2); int luaO_redimension (lua_State *L, int oldsize); int luaO_str2d (const char *s, Number *result); diff --git a/ltable.c b/ltable.c @@ -1,5 +1,5 @@ /* -** $Id: ltable.c,v 1.38 2000/03/29 20:19:20 roberto Exp roberto $ +** $Id: ltable.c,v 1.39 2000/03/31 16:28:45 roberto Exp roberto $ ** Lua tables (hash) ** See Copyright Notice in lua.h */ @@ -60,11 +60,12 @@ Node *luaH_mainposition (const Hash *t, const TObject *key) { } LUA_ASSERT(L, h%(unsigned int)t->size == (h&((unsigned int)t->size-1)), "a&(x-1) == a%x, for x power of 2"); - return &t->node[h&((unsigned int)t->size-1)]; + return &t->node[h&(t->size-1)]; } -const TObject *luaH_get (lua_State *L, const Hash *t, const TObject *key) { +static const TObject *luaH_getany (lua_State *L, const Hash *t, + const TObject *key) { Node *n = luaH_mainposition(t, key); if (!n) lua_error(L, "unexpected type to index table"); @@ -77,6 +78,39 @@ const TObject *luaH_get (lua_State *L, const Hash *t, const TObject *key) { } +/* specialized version for numbers */ +const TObject *luaH_getnum (const Hash *t, Number key) { + Node *n = &t->node[(unsigned long)(long)key&(t->size-1)]; + do { + if (ttype(&n->key) == TAG_NUMBER && nvalue(&n->key) == key) + return &n->val; + n = n->next; + } while (n); + return &luaO_nilobject; /* key not found */ +} + + +/* specialized version for strings */ +static const TObject *luaH_getstr (const Hash *t, TString *key) { + Node *n = &t->node[key->hash&(t->size-1)]; + do { + if (ttype(&n->key) == TAG_STRING && tsvalue(&n->key) == key) + return &n->val; + n = n->next; + } while (n); + return &luaO_nilobject; /* key not found */ +} + + +const TObject *luaH_get (lua_State *L, const Hash *t, const TObject *key) { + switch (ttype(key)) { + case TAG_NUMBER: return luaH_getnum(t, nvalue(key)); + case TAG_STRING: return luaH_getstr(t, tsvalue(key)); + default: return luaH_getany(L, t, key); + } +} + + int luaH_pos (lua_State *L, const Hash *t, const TObject *key) { const TObject *v = luaH_get(L, t, key); return (v == &luaO_nilobject) ? -1 : /* key not found */ @@ -214,11 +248,3 @@ void luaH_setint (lua_State *L, Hash *t, int key, const TObject *val) { luaH_set(L, t, &index, val); } - -const TObject *luaH_getint (lua_State *L, const Hash *t, int key) { - TObject index; - ttype(&index) = TAG_NUMBER; - nvalue(&index) = key; - return luaH_get(L, t, &index); -} - diff --git a/ltable.h b/ltable.h @@ -1,5 +1,5 @@ /* -** $Id: ltable.h,v 1.17 1999/11/23 13:58:02 roberto Exp roberto $ +** $Id: ltable.h,v 1.18 1999/12/07 12:05:34 roberto Exp roberto $ ** Lua tables (hash) ** See Copyright Notice in lua.h */ @@ -14,7 +14,7 @@ #define key(n) (&(n)->key) #define val(n) (&(n)->val) -#define luaH_move(L, t,from,to) (luaH_setint(L, t, to, luaH_getint(L, t, from))) +#define luaH_move(L, t,from,to) (luaH_setint(L, t, to, luaH_getnum(t, from))) Hash *luaH_new (lua_State *L, int nhash); void luaH_free (lua_State *L, Hash *t); @@ -22,7 +22,7 @@ const TObject *luaH_get (lua_State *L, const Hash *t, const TObject *key); void luaH_set (lua_State *L, Hash *t, const TObject *key, const TObject *val); int luaH_pos (lua_State *L, const Hash *t, const TObject *r); void luaH_setint (lua_State *L, Hash *t, int key, const TObject *val); -const TObject *luaH_getint (lua_State *L, const Hash *t, int key); +const TObject *luaH_getnum (const Hash *t, Number key); unsigned long luaH_hash (lua_State *L, const TObject *key); /* exported only for debugging */