aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
diff options
context:
space:
mode:
Diffstat (limited to 'ltable.c')
-rw-r--r--ltable.c45
1 files changed, 4 insertions, 41 deletions
diff --git a/ltable.c b/ltable.c
index 947f1813..e16fe5da 100644
--- a/ltable.c
+++ b/ltable.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: ltable.c,v 1.26 1999/10/14 19:13:31 roberto Exp roberto $ 2** $Id: ltable.c,v 1.27 1999/10/19 13:33:22 roberto Exp roberto $
3** Lua tables (hash) 3** Lua tables (hash)
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -38,7 +38,7 @@
38** returns the `main' position of an element in a table (that is, the index 38** returns the `main' position of an element in a table (that is, the index
39** of its hash value) 39** of its hash value)
40*/ 40*/
41static Node *luaH_mainposition (const Hash *t, const TObject *key) { 41Node *luaH_mainposition (const Hash *t, const TObject *key) {
42 unsigned long h; 42 unsigned long h;
43 switch (ttype(key)) { 43 switch (ttype(key)) {
44 case LUA_T_NUMBER: 44 case LUA_T_NUMBER:
@@ -90,7 +90,7 @@ static Node *hashnodecreate (int nhash) {
90 Node *v = luaM_newvector(nhash, Node); 90 Node *v = luaM_newvector(nhash, Node);
91 int i; 91 int i;
92 for (i=0; i<nhash; i++) { 92 for (i=0; i<nhash; i++) {
93 ttype(key(&v[i])) = ttype(val(&v[i])) = LUA_T_NIL; 93 ttype(&v[i].key) = ttype(&v[i].val) = LUA_T_NIL;
94 v[i].next = NULL; 94 v[i].next = NULL;
95 } 95 }
96 return v; 96 return v;
@@ -129,48 +129,13 @@ static int newsize (const Hash *t) {
129 int realuse = 0; 129 int realuse = 0;
130 int i; 130 int i;
131 for (i=0; i<size; i++) { 131 for (i=0; i<size; i++) {
132 if (ttype(val(v+i)) != LUA_T_NIL) 132 if (ttype(&v[i].val) != LUA_T_NIL)
133 realuse++; 133 realuse++;
134 } 134 }
135 return luaO_redimension(realuse*2); 135 return luaO_redimension(realuse*2);
136} 136}
137 137
138 138
139#ifdef DEBUG
140/* check invariant of a table */
141static int listfind (const Node *m, const Node *n) {
142 do {
143 if (m==n) return 1;
144 m = m->next;
145 } while (m);
146 return 0;
147}
148
149static int check_invariant (const Hash *t, int filled) {
150 Node *n;
151 for (n=t->node; n<t->firstfree; n++) {
152 TObject *key = &n->key;
153 LUA_ASSERT(ttype(key) == LUA_T_NIL || n == luaH_mainposition(t, key),
154 "all elements before firstfree are empty or in their main positions");
155 }
156 if (!filled)
157 LUA_ASSERT(ttype(&(n++)->key) == LUA_T_NIL, "firstfree must be empty");
158 else
159 LUA_ASSERT(n == t->node, "table cannot have empty places");
160 for (; n<t->node+t->size; n++) {
161 TObject *key = &n->key;
162 Node *mp = luaH_mainposition(t, key);
163 LUA_ASSERT(ttype(key) != LUA_T_NIL,
164 "cannot exist empty elements after firstfree");
165 LUA_ASSERT(n == mp || luaH_mainposition(t, &mp->key) == mp,
166 "either an element or its colliding element is in its main position");
167 LUA_ASSERT(listfind(mp,n), "element is in its main position list");
168 }
169 return 1;
170}
171#endif
172
173
174/* 139/*
175** the rehash is done in two stages: first, we insert only the elements whose 140** the rehash is done in two stages: first, we insert only the elements whose
176** main position is free, to avoid needless collisions. In the second stage, 141** main position is free, to avoid needless collisions. In the second stage,
@@ -180,7 +145,6 @@ static void rehash (Hash *t) {
180 int oldsize = t->size; 145 int oldsize = t->size;
181 Node *nold = t->node; 146 Node *nold = t->node;
182 int i; 147 int i;
183 LUA_ASSERT(check_invariant(t, 1), "invalid table");
184 L->nblocks -= gcsize(oldsize); 148 L->nblocks -= gcsize(oldsize);
185 setnodevector(t, newsize(t)); /* create new array of nodes */ 149 setnodevector(t, newsize(t)); /* create new array of nodes */
186 /* first loop; set only elements that can go in their main positions */ 150 /* first loop; set only elements that can go in their main positions */
@@ -216,7 +180,6 @@ static void rehash (Hash *t) {
216 } while (ttype(&t->firstfree->key) != LUA_T_NIL); 180 } while (ttype(&t->firstfree->key) != LUA_T_NIL);
217 } 181 }
218 } 182 }
219 LUA_ASSERT(check_invariant(t, 0), "invalid table");
220 luaM_free(nold); /* free old array */ 183 luaM_free(nold); /* free old array */
221} 184}
222 185