commit b3fe203c36b673bd01c45bf39dbb3cf6daa6d852
parent 9c142740c107fef2ff7f8ea8554222a2114f2a38
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Tue, 7 Dec 1999 10:05:12 -0200
keep it simple
Diffstat:
M | ltable.c | | | 58 | ++++++++++++++-------------------------------------------- |
1 file changed, 14 insertions(+), 44 deletions(-)
diff --git a/ltable.c b/ltable.c
@@ -1,5 +1,5 @@
/*
-** $Id: ltable.c,v 1.30 1999/11/22 13:12:07 roberto Exp roberto $
+** $Id: ltable.c,v 1.31 1999/11/26 18:59:20 roberto Exp roberto $
** Lua tables (hash)
** See Copyright Notice in lua.h
*/
@@ -40,7 +40,7 @@
** returns the `main' position of an element in a table (that is, the index
** of its hash value)
*/
-Node *luaH_mainposition (lua_State *L, const Hash *t, const TObject *key) {
+Node *luaH_mainposition (const Hash *t, const TObject *key) {
unsigned long h;
switch (ttype(key)) {
case LUA_T_NUMBER:
@@ -62,8 +62,7 @@ Node *luaH_mainposition (lua_State *L, const Hash *t, const TObject *key) {
h = IntPoint(L, clvalue(key));
break;
default:
- lua_error(L, "unexpected type to index table");
- h = 0; /* to avoid warnings */
+ return NULL; /* invalid 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");
@@ -72,13 +71,15 @@ Node *luaH_mainposition (lua_State *L, const Hash *t, const TObject *key) {
const TObject *luaH_get (lua_State *L, const Hash *t, const TObject *key) {
- Node *n = luaH_mainposition(L, t, key);
- do {
+ Node *n = luaH_mainposition(t, key);
+ if (!n)
+ lua_error(L, "unexpected type to index table");
+ else do {
if (luaO_equalObj(key, &n->key))
return &n->val;
n = n->next;
} while (n);
- return &luaO_nilobject;
+ return &luaO_nilobject; /* key not found */
}
@@ -140,49 +141,16 @@ static int newsize (const Hash *t) {
}
-/*
-** the rehash is done in two stages: first, we insert only the elements whose
-** main position is free, to avoid needless collisions. In the second stage,
-** we insert the other elements.
-*/
static void rehash (lua_State *L, Hash *t) {
int oldsize = t->size;
Node *nold = t->node;
int i;
L->nblocks -= gcsize(L, oldsize);
setnodevector(L, t, newsize(t)); /* create new array of nodes */
- /* first loop; set only elements that can go in their main positions */
for (i=0; i<oldsize; i++) {
Node *old = nold+i;
- if (ttype(&old->val) == LUA_T_NIL)
- old->next = NULL; /* `remove' it for next loop */
- else {
- Node *mp = luaH_mainposition(L, t, &old->key); /* new main position */
- if (ttype(&mp->key) == LUA_T_NIL) { /* is it empty? */
- mp->key = old->key; /* put element there */
- mp->val = old->val;
- old->next = NULL; /* `remove' it for next loop */
- }
- else /* it will be copied in next loop */
- old->next = mp; /* to be used in next loop */
- }
- }
- /* update `firstfree' */
- while (ttype(&t->firstfree->key) != LUA_T_NIL) t->firstfree--;
- /* second loop; update elements with colision */
- for (i=0; i<oldsize; i++) {
- Node *old = nold+i;
- if (old->next) { /* wasn't already `removed'? */
- Node *mp = old->next; /* main position */
- Node *e = t->firstfree; /* actual position */
- e->key = old->key; /* put element in the free position */
- e->val = old->val;
- e->next = mp->next; /* chain actual position in main position's list */
- mp->next = e;
- do { /* update `firstfree' */
- t->firstfree--;
- } while (ttype(&t->firstfree->key) != LUA_T_NIL);
- }
+ if (ttype(&old->val) != LUA_T_NIL)
+ luaH_set(L, t, &old->key, &old->val);
}
luaM_free(L, nold); /* free old array */
}
@@ -202,8 +170,10 @@ static void rehash (lua_State *L, Hash *t) {
** (this happens when we use `luaH_move'), there is no problem.
*/
void luaH_set (lua_State *L, Hash *t, const TObject *key, const TObject *val) {
- Node *mp = luaH_mainposition(L, t, key);
+ Node *mp = luaH_mainposition(t, key);
Node *n = mp;
+ if (!mp)
+ lua_error(L, "unexpected type to index table");
do { /* check whether `key' is somewhere in the chain */
if (luaO_equalObj(key, &n->key)) {
n->val = *val; /* update value */
@@ -217,7 +187,7 @@ void luaH_set (lua_State *L, Hash *t, const TObject *key, const TObject *val) {
n = t->firstfree; /* get a free place */
/* is colliding node out of its main position? (can only happens if
its position if after "firstfree") */
- if (mp > n && (othern=luaH_mainposition(L, t, &mp->key)) != mp) {
+ if (mp > n && (othern=luaH_mainposition(t, &mp->key)) != mp) {
/* yes; move colliding node into free position */
while (othern->next != mp) othern = othern->next; /* find previous */
othern->next = n; /* redo the chain with `n' in place of `mp' */