diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-11-15 10:48:52 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-11-15 10:48:52 -0300 |
commit | 8a4419b119ea9d03bb20b208587b0bbd6f473cdc (patch) | |
tree | 7919241030f9956e5ff64e783611b4d90f049c44 | |
parent | 9a91fe1640ddbe5b55e7454541059372b971f400 (diff) | |
download | lua-8a4419b119ea9d03bb20b208587b0bbd6f473cdc.tar.gz lua-8a4419b119ea9d03bb20b208587b0bbd6f473cdc.tar.bz2 lua-8a4419b119ea9d03bb20b208587b0bbd6f473cdc.zip |
Dummy node has a non-nil key
That allows 'getfreepos' to treat it like a regular hash part that has
a deleted entry.
-rw-r--r-- | ltable.c | 53 |
1 files changed, 28 insertions, 25 deletions
@@ -121,9 +121,15 @@ typedef union { | |||
121 | 121 | ||
122 | #define dummynode (&dummynode_) | 122 | #define dummynode (&dummynode_) |
123 | 123 | ||
124 | /* | ||
125 | ** Common hash part for tables with empty hash parts. That allows all | ||
126 | ** tables to have a hash part, avoding an extra check ("is there a hash | ||
127 | ** part?") when indexing. Its sole node has an empty value and a key | ||
128 | ** (DEADKEY, NULL) that is different from any valid TValue. | ||
129 | */ | ||
124 | static const Node dummynode_ = { | 130 | static const Node dummynode_ = { |
125 | {{NULL}, LUA_VEMPTY, /* value's value and type */ | 131 | {{NULL}, LUA_VEMPTY, /* value's value and type */ |
126 | LUA_VNIL, 0, {NULL}} /* key type, next, and key value */ | 132 | LUA_TDEADKEY, 0, {NULL}} /* key type, next, and key value */ |
127 | }; | 133 | }; |
128 | 134 | ||
129 | 135 | ||
@@ -400,16 +406,20 @@ int luaH_next (lua_State *L, Table *t, StkId key) { | |||
400 | } | 406 | } |
401 | 407 | ||
402 | 408 | ||
409 | /* Extra space in Node array if it has a lastfree entry */ | ||
410 | #define extraLastfree(t) (haslastfree(t) ? sizeof(Limbox) : 0) | ||
411 | |||
412 | /* 'node' size in bytes */ | ||
413 | static size_t sizehash (Table *t) { | ||
414 | return cast_sizet(sizenode(t)) * sizeof(Node) + extraLastfree(t); | ||
415 | } | ||
416 | |||
417 | |||
403 | static void freehash (lua_State *L, Table *t) { | 418 | static void freehash (lua_State *L, Table *t) { |
404 | if (!isdummy(t)) { | 419 | if (!isdummy(t)) { |
405 | /* 'node' size in bytes */ | 420 | /* get pointer to the beginning of Node array */ |
406 | size_t bsize = cast_sizet(sizenode(t)) * sizeof(Node); | 421 | char *arr = cast_charp(t->node) - extraLastfree(t); |
407 | char *arr = cast_charp(t->node); | 422 | luaM_freearray(L, arr, sizehash(t)); |
408 | if (haslastfree(t)) { | ||
409 | bsize += sizeof(Limbox); | ||
410 | arr -= sizeof(Limbox); | ||
411 | } | ||
412 | luaM_freearray(L, arr, bsize); | ||
413 | } | 423 | } |
414 | } | 424 | } |
415 | 425 | ||
@@ -572,8 +582,7 @@ static void numusehash (const Table *t, Counters *ct) { | |||
572 | while (i--) { | 582 | while (i--) { |
573 | Node *n = &t->node[i]; | 583 | Node *n = &t->node[i]; |
574 | if (isempty(gval(n))) { | 584 | if (isempty(gval(n))) { |
575 | /* entry was deleted; key cannot be nil */ | 585 | lua_assert(!keyisnil(n)); /* entry was deleted; key cannot be nil */ |
576 | lua_assert(isdummy(t) || !keyisnil(n)); | ||
577 | ct->deleted = 1; | 586 | ct->deleted = 1; |
578 | } | 587 | } |
579 | else { | 588 | else { |
@@ -855,13 +864,9 @@ Table *luaH_new (lua_State *L) { | |||
855 | 864 | ||
856 | 865 | ||
857 | size_t luaH_size (Table *t) { | 866 | size_t luaH_size (Table *t) { |
858 | size_t sz = sizeof(Table) | 867 | size_t sz = sizeof(Table) + luaH_realasize(t) * (sizeof(Value) + 1); |
859 | + luaH_realasize(t) * (sizeof(Value) + 1); | 868 | if (!isdummy(t)) |
860 | if (!isdummy(t)) { | 869 | sz += sizehash(t); |
861 | sz += sizenode(t) * sizeof(Node); | ||
862 | if (haslastfree(t)) | ||
863 | sz += sizeof(Limbox); | ||
864 | } | ||
865 | return sz; | 870 | return sz; |
866 | } | 871 | } |
867 | 872 | ||
@@ -887,13 +892,11 @@ static Node *getfreepos (Table *t) { | |||
887 | } | 892 | } |
888 | } | 893 | } |
889 | else { /* no 'lastfree' information */ | 894 | else { /* no 'lastfree' information */ |
890 | if (!isdummy(t)) { | 895 | unsigned i = sizenode(t); |
891 | unsigned i = sizenode(t); | 896 | while (i--) { /* do a linear search */ |
892 | while (i--) { /* do a linear search */ | 897 | Node *free = gnode(t, i); |
893 | Node *free = gnode(t, i); | 898 | if (keyisnil(free)) |
894 | if (keyisnil(free)) | 899 | return free; |
895 | return free; | ||
896 | } | ||
897 | } | 900 | } |
898 | } | 901 | } |
899 | return NULL; /* could not find a free place */ | 902 | return NULL; /* could not find a free place */ |