summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ltable.c43
-rw-r--r--ltable.h11
-rw-r--r--ltests.c4
3 files changed, 35 insertions, 23 deletions
diff --git a/ltable.c b/ltable.c
index 286ca38b..0e80237c 100644
--- a/ltable.c
+++ b/ltable.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: ltable.c,v 2.29 2005/12/22 16:19:56 roberto Exp roberto $ 2** $Id: ltable.c,v 2.30 2006/01/10 12:51:53 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*/
@@ -70,7 +70,9 @@
70 70
71 71
72 72
73const Node luaH_dummynode_ = { 73#define dummynode (&dummynode_)
74
75static const Node dummynode_ = {
74 {{NULL}, LUA_TNIL}, /* value */ 76 {{NULL}, LUA_TNIL}, /* value */
75 {{{NULL}, LUA_TNIL, NULL}} /* key */ 77 {{{NULL}, LUA_TNIL, NULL}} /* key */
76}; 78};
@@ -95,7 +97,7 @@ static Node *hashnum (const Table *t, lua_Number n) {
95** returns the `main' position of an element in a table (that is, the index 97** returns the `main' position of an element in a table (that is, the index
96** of its hash value) 98** of its hash value)
97*/ 99*/
98Node *luaH_mainposition (const Table *t, const TValue *key) { 100static Node *mainposition (const Table *t, const TValue *key) {
99 switch (ttype(key)) { 101 switch (ttype(key)) {
100 case LUA_TNUMBER: 102 case LUA_TNUMBER:
101 return hashnum(t, nvalue(key)); 103 return hashnum(t, nvalue(key));
@@ -139,7 +141,7 @@ static int findindex (lua_State *L, Table *t, StkId key) {
139 if (0 < i && i <= t->sizearray) /* is `key' inside array part? */ 141 if (0 < i && i <= t->sizearray) /* is `key' inside array part? */
140 return i-1; /* yes; that's the index (corrected to C) */ 142 return i-1; /* yes; that's the index (corrected to C) */
141 else { 143 else {
142 Node *n = luaH_mainposition(t, key); 144 Node *n = mainposition(t, key);
143 do { /* check whether `key' is somewhere in the chain */ 145 do { /* check whether `key' is somewhere in the chain */
144 /* key may be dead already, but it is ok to use it in `next' */ 146 /* key may be dead already, but it is ok to use it in `next' */
145 if (luaO_rawequalObj(key2tval(n), key) || 147 if (luaO_rawequalObj(key2tval(n), key) ||
@@ -270,7 +272,7 @@ static void setarrayvector (lua_State *L, Table *t, int size) {
270static void setnodevector (lua_State *L, Table *t, int size) { 272static void setnodevector (lua_State *L, Table *t, int size) {
271 int lsize; 273 int lsize;
272 if (size == 0) { /* no elements to hash part? */ 274 if (size == 0) { /* no elements to hash part? */
273 t->node = cast(Node *, luaH_dummynode); /* use common `dummynode' */ 275 t->node = cast(Node *, dummynode); /* use common `dummynode' */
274 lsize = 0; 276 lsize = 0;
275 } 277 }
276 else { 278 else {
@@ -317,13 +319,13 @@ static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
317 if (!ttisnil(gval(old))) 319 if (!ttisnil(gval(old)))
318 setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old)); 320 setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old));
319 } 321 }
320 if (nold != luaH_dummynode) 322 if (nold != dummynode)
321 luaM_freearray(L, nold, twoto(oldhsize), Node); /* free old array */ 323 luaM_freearray(L, nold, twoto(oldhsize), Node); /* free old array */
322} 324}
323 325
324 326
325void luaH_resizearray (lua_State *L, Table *t, int nasize) { 327void luaH_resizearray (lua_State *L, Table *t, int nasize) {
326 int nsize = (t->node == luaH_dummynode) ? 0 : sizenode(t); 328 int nsize = (t->node == dummynode) ? 0 : sizenode(t);
327 resize(L, t, nasize, nsize); 329 resize(L, t, nasize, nsize);
328} 330}
329 331
@@ -362,7 +364,7 @@ Table *luaH_new (lua_State *L, int narray, int nhash) {
362 t->array = NULL; 364 t->array = NULL;
363 t->sizearray = 0; 365 t->sizearray = 0;
364 t->lsizenode = 0; 366 t->lsizenode = 0;
365 t->node = cast(Node *, luaH_dummynode); 367 t->node = cast(Node *, dummynode);
366 setarrayvector(L, t, narray); 368 setarrayvector(L, t, narray);
367 setnodevector(L, t, nhash); 369 setnodevector(L, t, nhash);
368 return t; 370 return t;
@@ -370,7 +372,7 @@ Table *luaH_new (lua_State *L, int narray, int nhash) {
370 372
371 373
372void luaH_free (lua_State *L, Table *t) { 374void luaH_free (lua_State *L, Table *t) {
373 if (t->node != luaH_dummynode) 375 if (t->node != dummynode)
374 luaM_freearray(L, t->node, sizenode(t), Node); 376 luaM_freearray(L, t->node, sizenode(t), Node);
375 luaM_freearray(L, t->array, t->sizearray, TValue); 377 luaM_freearray(L, t->array, t->sizearray, TValue);
376 luaM_free(L, t); 378 luaM_free(L, t);
@@ -395,16 +397,16 @@ static Node *getfreepos (Table *t) {
395** position), new key goes to an empty position. 397** position), new key goes to an empty position.
396*/ 398*/
397static TValue *newkey (lua_State *L, Table *t, const TValue *key) { 399static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
398 Node *mp = luaH_mainposition(t, key); 400 Node *mp = mainposition(t, key);
399 if (!ttisnil(gval(mp)) || mp == luaH_dummynode) { 401 if (!ttisnil(gval(mp)) || mp == dummynode) {
400 Node *othern; 402 Node *othern;
401 Node *n = getfreepos(t); /* get a free place */ 403 Node *n = getfreepos(t); /* get a free place */
402 if (n == NULL) { /* cannot find a free place? */ 404 if (n == NULL) { /* cannot find a free place? */
403 rehash(L, t, key); /* grow table */ 405 rehash(L, t, key); /* grow table */
404 return luaH_set(L, t, key); /* re-insert key into grown table */ 406 return luaH_set(L, t, key); /* re-insert key into grown table */
405 } 407 }
406 lua_assert(n != luaH_dummynode); 408 lua_assert(n != dummynode);
407 othern = luaH_mainposition(t, key2tval(mp)); 409 othern = mainposition(t, key2tval(mp));
408 if (othern != mp) { /* is colliding node out of its main position? */ 410 if (othern != mp) { /* is colliding node out of its main position? */
409 /* yes; move colliding node into free position */ 411 /* yes; move colliding node into free position */
410 while (gnext(othern) != mp) othern = gnext(othern); /* find previous */ 412 while (gnext(othern) != mp) othern = gnext(othern); /* find previous */
@@ -477,7 +479,7 @@ const TValue *luaH_get (Table *t, const TValue *key) {
477 /* else go through */ 479 /* else go through */
478 } 480 }
479 default: { 481 default: {
480 Node *n = luaH_mainposition(t, key); 482 Node *n = mainposition(t, key);
481 do { /* check whether `key' is somewhere in the chain */ 483 do { /* check whether `key' is somewhere in the chain */
482 if (luaO_rawequalObj(key2tval(n), key)) 484 if (luaO_rawequalObj(key2tval(n), key))
483 return gval(n); /* that's it */ 485 return gval(n); /* that's it */
@@ -568,8 +570,19 @@ int luaH_getn (Table *t) {
568 return i; 570 return i;
569 } 571 }
570 /* else must find a boundary in hash part */ 572 /* else must find a boundary in hash part */
571 else if (t->node == luaH_dummynode) /* hash part is empty? */ 573 else if (t->node == dummynode) /* hash part is empty? */
572 return j; /* that is easy... */ 574 return j; /* that is easy... */
573 else return unbound_search(t, j); 575 else return unbound_search(t, j);
574} 576}
575 577
578
579
580#if defined(LUA_DEBUG)
581
582Node *luaH_mainposition (const Table *t, const TValue *key) {
583 return mainposition(t, key);
584}
585
586int luaH_isdummy (Node *n) { return n == dummynode; }
587
588#endif
diff --git a/ltable.h b/ltable.h
index 836842da..e87597fd 100644
--- a/ltable.h
+++ b/ltable.h
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: ltable.h,v 2.8 2005/06/06 13:30:25 roberto Exp roberto $ 2** $Id: ltable.h,v 2.9 2006/01/10 12:51:53 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*/
@@ -30,12 +30,11 @@ LUAI_FUNC void luaH_free (lua_State *L, Table *t);
30LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key); 30LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key);
31LUAI_FUNC int luaH_getn (Table *t); 31LUAI_FUNC int luaH_getn (Table *t);
32 32
33/* exported only for debugging */
34LUAI_FUNC Node *luaH_mainposition (const Table *t, const TValue *key);
35
36#define luaH_dummynode (&luaH_dummynode_)
37 33
38LUAI_DATA const Node luaH_dummynode_; 34#if defined(LUA_DEBUG)
35LUAI_FUNC Node *luaH_mainposition (const Table *t, const TValue *key);
36LUAI_FUNC int luaH_isdummy (Node *n);
37#endif
39 38
40 39
41#endif 40#endif
diff --git a/ltests.c b/ltests.c
index 739a011a..3c077a1c 100644
--- a/ltests.c
+++ b/ltests.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: ltests.c,v 2.34 2005/12/22 16:19:56 roberto Exp roberto $ 2** $Id: ltests.c,v 2.35 2006/01/10 12:50:00 roberto Exp roberto $
3** Internal Module for Debugging of the Lua Implementation 3** Internal Module for Debugging of the Lua Implementation
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -564,7 +564,7 @@ static int table_query (lua_State *L) {
564 t = hvalue(obj_at(L, 1)); 564 t = hvalue(obj_at(L, 1));
565 if (i == -1) { 565 if (i == -1) {
566 lua_pushinteger(L, t->sizearray); 566 lua_pushinteger(L, t->sizearray);
567 lua_pushinteger(L, t->node == luaH_dummynode ? 0 : sizenode(t)); 567 lua_pushinteger(L, luaH_isdummy(t->node) ? 0 : sizenode(t));
568 lua_pushinteger(L, t->lastfree - t->node); 568 lua_pushinteger(L, t->lastfree - t->node);
569 } 569 }
570 else if (i < t->sizearray) { 570 else if (i < t->sizearray) {