aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-15 10:48:52 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-15 10:48:52 -0300
commit8a4419b119ea9d03bb20b208587b0bbd6f473cdc (patch)
tree7919241030f9956e5ff64e783611b4d90f049c44
parent9a91fe1640ddbe5b55e7454541059372b971f400 (diff)
downloadlua-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.c53
1 files changed, 28 insertions, 25 deletions
diff --git a/ltable.c b/ltable.c
index 0192d039..981e9df4 100644
--- a/ltable.c
+++ b/ltable.c
@@ -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*/
124static const Node dummynode_ = { 130static 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 */
413static size_t sizehash (Table *t) {
414 return cast_sizet(sizenode(t)) * sizeof(Node) + extraLastfree(t);
415}
416
417
403static void freehash (lua_State *L, Table *t) { 418static 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
857size_t luaH_size (Table *t) { 866size_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 */