diff options
-rw-r--r-- | ltable.c | 43 | ||||
-rw-r--r-- | ltable.h | 11 | ||||
-rw-r--r-- | ltests.c | 4 |
3 files changed, 35 insertions, 23 deletions
@@ -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 | ||
73 | const Node luaH_dummynode_ = { | 73 | #define dummynode (&dummynode_) |
74 | |||
75 | static 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 | */ |
98 | Node *luaH_mainposition (const Table *t, const TValue *key) { | 100 | static 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) { | |||
270 | static void setnodevector (lua_State *L, Table *t, int size) { | 272 | static 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 | ||
325 | void luaH_resizearray (lua_State *L, Table *t, int nasize) { | 327 | void 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 | ||
372 | void luaH_free (lua_State *L, Table *t) { | 374 | void 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 | */ |
397 | static TValue *newkey (lua_State *L, Table *t, const TValue *key) { | 399 | static 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 | |||
582 | Node *luaH_mainposition (const Table *t, const TValue *key) { | ||
583 | return mainposition(t, key); | ||
584 | } | ||
585 | |||
586 | int luaH_isdummy (Node *n) { return n == dummynode; } | ||
587 | |||
588 | #endif | ||
@@ -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); | |||
30 | LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key); | 30 | LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key); |
31 | LUAI_FUNC int luaH_getn (Table *t); | 31 | LUAI_FUNC int luaH_getn (Table *t); |
32 | 32 | ||
33 | /* exported only for debugging */ | ||
34 | LUAI_FUNC Node *luaH_mainposition (const Table *t, const TValue *key); | ||
35 | |||
36 | #define luaH_dummynode (&luaH_dummynode_) | ||
37 | 33 | ||
38 | LUAI_DATA const Node luaH_dummynode_; | 34 | #if defined(LUA_DEBUG) |
35 | LUAI_FUNC Node *luaH_mainposition (const Table *t, const TValue *key); | ||
36 | LUAI_FUNC int luaH_isdummy (Node *n); | ||
37 | #endif | ||
39 | 38 | ||
40 | 39 | ||
41 | #endif | 40 | #endif |
@@ -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) { |