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) { |
