diff options
Diffstat (limited to 'ltable.c')
-rw-r--r-- | ltable.c | 45 |
1 files changed, 4 insertions, 41 deletions
@@ -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 | */ |
41 | static Node *luaH_mainposition (const Hash *t, const TObject *key) { | 41 | Node *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 */ | ||
141 | static 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 | |||
149 | static 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 | ||