aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
diff options
context:
space:
mode:
Diffstat (limited to 'ltable.c')
-rw-r--r--ltable.c55
1 files changed, 37 insertions, 18 deletions
diff --git a/ltable.c b/ltable.c
index d3e90696..21a54f81 100644
--- a/ltable.c
+++ b/ltable.c
@@ -408,21 +408,22 @@ static void freehash (lua_State *L, Table *t) {
408** not the real size of the array, the key still can be in the array 408** not the real size of the array, the key still can be in the array
409** part. In this case, do the "Xmilia trick" to check whether 'key-1' 409** part. In this case, do the "Xmilia trick" to check whether 'key-1'
410** is smaller than the real size. 410** is smaller than the real size.
411** The trick works as follow: let 'p' be an integer such that 411** The trick works as follow: let 'p' be the integer such that
412** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'. 412** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'. That is,
413** That is, 2^(p+1) is the real size of the array, and 'p' is the highest 413** 'p' is the highest 1-bit in 'alimit-1', and 2^(p+1) is the real size
414** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'. 414** of the array. What we have to check becomes 'key-1 < 2^(p+1)'. We
415** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will 415** compute '(key-1) & ~(alimit-1)', which we call 'res'; it will have
416** have the 'p' bit cleared. If the key is outside the array, that is, 416** the 'p' bit cleared. (It may also clear other bits smaller than 'p',
417** 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than 'p', 417** but no bit higher than 'p'.) If the key is outside the array, that
418** therefore it will be larger or equal to 'alimit', and the check 418** is, 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than
419** 'p', therefore it will be larger or equal to 'alimit', and the check
419** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than 420** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than
420** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller 421** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
421** than 2^p, therefore smaller than 'alimit', and the check succeeds. 422** than 2^p, therefore smaller than 'alimit', and the check succeeds.
422** As special cases, when 'alimit' is 0 the condition is trivially false, 423** As special cases, when 'alimit' is 0 the condition is trivially false,
423** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'. 424** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
424** If key is 0 or negative, 'res' will have its higher bit on, so that 425** If key is 0 or negative, 'res' will have its higher bit on, so that
425** if cannot be smaller than alimit. 426** it cannot be smaller than 'alimit'.
426*/ 427*/
427static int keyinarray (Table *t, lua_Integer key) { 428static int keyinarray (Table *t, lua_Integer key) {
428 lua_Unsigned alimit = t->alimit; 429 lua_Unsigned alimit = t->alimit;
@@ -788,11 +789,11 @@ static Node *getfreepos (Table *t) {
788 789
789 790
790/* 791/*
791** inserts a new key into a hash table; first, check whether key's main 792** Inserts a new key into a hash table; first, check whether key's main
792** position is free. If not, check whether colliding node is in its main 793** position is free. If not, check whether colliding node is in its main
793** position or not: if it is not, move colliding node to an empty place and 794** position or not: if it is not, move colliding node to an empty place
794** put new key in its main position; otherwise (colliding node is in its main 795** and put new key in its main position; otherwise (colliding node is in
795** position), new key goes to an empty position. 796** its main position), new key goes to an empty position.
796*/ 797*/
797static void luaH_newkey (lua_State *L, Table *t, const TValue *key, 798static void luaH_newkey (lua_State *L, Table *t, const TValue *key,
798 TValue *value) { 799 TValue *value) {
@@ -987,6 +988,16 @@ static int finishnodeset (Table *t, const TValue *slot, TValue *val) {
987} 988}
988 989
989 990
991static int rawfinishnodeset (const TValue *slot, TValue *val) {
992 if (isabstkey(slot))
993 return 0; /* no slot with that key */
994 else {
995 setobj(((lua_State*)NULL), cast(TValue*, slot), val);
996 return 1; /* success */
997 }
998}
999
1000
990int luaH_psetint (Table *t, lua_Integer key, TValue *val) { 1001int luaH_psetint (Table *t, lua_Integer key, TValue *val) {
991 if (keyinarray(t, key)) { 1002 if (keyinarray(t, key)) {
992 lu_byte *tag = getArrTag(t, key - 1); 1003 lu_byte *tag = getArrTag(t, key - 1);
@@ -1063,12 +1074,20 @@ void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) {
1063} 1074}
1064 1075
1065 1076
1077/*
1078** Ditto for a GC barrier. (No need to invalidate the TM cache, as
1079** integers cannot be keys to metamethods.)
1080*/
1066void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { 1081void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
1067 int hres = luaH_psetint(t, key, value); 1082 if (keyinarray(t, key))
1068 if (hres != HOK) { 1083 obj2arr(t, key, value);
1069 TValue k; 1084 else {
1070 setivalue(&k, key); 1085 int ok = rawfinishnodeset(getintfromhash(t, key), value);
1071 luaH_finishset(L, t, &k, value, hres); 1086 if (!ok) {
1087 TValue k;
1088 setivalue(&k, key);
1089 luaH_newkey(L, t, &k, value);
1090 }
1072 } 1091 }
1073} 1092}
1074 1093