18e3e3a7aSWarner Losh /* 2*0495ed39SKyle Evans ** $Id: ltable.c $ 38e3e3a7aSWarner Losh ** Lua tables (hash) 48e3e3a7aSWarner Losh ** See Copyright Notice in lua.h 58e3e3a7aSWarner Losh */ 68e3e3a7aSWarner Losh 78e3e3a7aSWarner Losh #define ltable_c 88e3e3a7aSWarner Losh #define LUA_CORE 98e3e3a7aSWarner Losh 108e3e3a7aSWarner Losh #include "lprefix.h" 118e3e3a7aSWarner Losh 128e3e3a7aSWarner Losh 138e3e3a7aSWarner Losh /* 148e3e3a7aSWarner Losh ** Implementation of tables (aka arrays, objects, or hash tables). 158e3e3a7aSWarner Losh ** Tables keep its elements in two parts: an array part and a hash part. 168e3e3a7aSWarner Losh ** Non-negative integer keys are all candidates to be kept in the array 178e3e3a7aSWarner Losh ** part. The actual size of the array is the largest 'n' such that 188e3e3a7aSWarner Losh ** more than half the slots between 1 and n are in use. 198e3e3a7aSWarner Losh ** Hash uses a mix of chained scatter table with Brent's variation. 208e3e3a7aSWarner Losh ** A main invariant of these tables is that, if an element is not 218e3e3a7aSWarner Losh ** in its main position (i.e. the 'original' position that its hash gives 228e3e3a7aSWarner Losh ** to it), then the colliding element is in its own main position. 238e3e3a7aSWarner Losh ** Hence even when the load factor reaches 100%, performance remains good. 248e3e3a7aSWarner Losh */ 258e3e3a7aSWarner Losh 268e3e3a7aSWarner Losh #include <math.h> 278e3e3a7aSWarner Losh #include <limits.h> 288e3e3a7aSWarner Losh 298e3e3a7aSWarner Losh #include "lua.h" 308e3e3a7aSWarner Losh 318e3e3a7aSWarner Losh #include "ldebug.h" 328e3e3a7aSWarner Losh #include "ldo.h" 338e3e3a7aSWarner Losh #include "lgc.h" 348e3e3a7aSWarner Losh #include "lmem.h" 358e3e3a7aSWarner Losh #include "lobject.h" 368e3e3a7aSWarner Losh #include "lstate.h" 378e3e3a7aSWarner Losh #include "lstring.h" 388e3e3a7aSWarner Losh #include "ltable.h" 398e3e3a7aSWarner Losh #include "lvm.h" 408e3e3a7aSWarner Losh 418e3e3a7aSWarner Losh 428e3e3a7aSWarner Losh /* 43*0495ed39SKyle Evans ** MAXABITS is the largest integer such that MAXASIZE fits in an 44*0495ed39SKyle Evans ** unsigned int. 458e3e3a7aSWarner Losh */ 468e3e3a7aSWarner Losh #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1) 47*0495ed39SKyle Evans 488e3e3a7aSWarner Losh 498e3e3a7aSWarner Losh /* 50*0495ed39SKyle Evans ** MAXASIZE is the maximum size of the array part. It is the minimum 51*0495ed39SKyle Evans ** between 2^MAXABITS and the maximum size that, measured in bytes, 52*0495ed39SKyle Evans ** fits in a 'size_t'. 53*0495ed39SKyle Evans */ 54*0495ed39SKyle Evans #define MAXASIZE luaM_limitN(1u << MAXABITS, TValue) 55*0495ed39SKyle Evans 56*0495ed39SKyle Evans /* 57*0495ed39SKyle Evans ** MAXHBITS is the largest integer such that 2^MAXHBITS fits in a 58*0495ed39SKyle Evans ** signed int. 598e3e3a7aSWarner Losh */ 608e3e3a7aSWarner Losh #define MAXHBITS (MAXABITS - 1) 618e3e3a7aSWarner Losh 628e3e3a7aSWarner Losh 63*0495ed39SKyle Evans /* 64*0495ed39SKyle Evans ** MAXHSIZE is the maximum size of the hash part. It is the minimum 65*0495ed39SKyle Evans ** between 2^MAXHBITS and the maximum size such that, measured in bytes, 66*0495ed39SKyle Evans ** it fits in a 'size_t'. 67*0495ed39SKyle Evans */ 68*0495ed39SKyle Evans #define MAXHSIZE luaM_limitN(1u << MAXHBITS, Node) 69*0495ed39SKyle Evans 70*0495ed39SKyle Evans 718e3e3a7aSWarner Losh #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) 728e3e3a7aSWarner Losh 738e3e3a7aSWarner Losh #define hashstr(t,str) hashpow2(t, (str)->hash) 748e3e3a7aSWarner Losh #define hashboolean(t,p) hashpow2(t, p) 758e3e3a7aSWarner Losh #define hashint(t,i) hashpow2(t, i) 768e3e3a7aSWarner Losh 778e3e3a7aSWarner Losh 788e3e3a7aSWarner Losh /* 798e3e3a7aSWarner Losh ** for some types, it is better to avoid modulus by power of 2, as 808e3e3a7aSWarner Losh ** they tend to have many 2 factors. 818e3e3a7aSWarner Losh */ 828e3e3a7aSWarner Losh #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) 838e3e3a7aSWarner Losh 848e3e3a7aSWarner Losh 858e3e3a7aSWarner Losh #define hashpointer(t,p) hashmod(t, point2uint(p)) 868e3e3a7aSWarner Losh 878e3e3a7aSWarner Losh 888e3e3a7aSWarner Losh #define dummynode (&dummynode_) 898e3e3a7aSWarner Losh 908e3e3a7aSWarner Losh static const Node dummynode_ = { 91*0495ed39SKyle Evans {{NULL}, LUA_VEMPTY, /* value's value and type */ 92*0495ed39SKyle Evans LUA_VNIL, 0, {NULL}} /* key type, next, and key value */ 938e3e3a7aSWarner Losh }; 948e3e3a7aSWarner Losh 958e3e3a7aSWarner Losh 96*0495ed39SKyle Evans static const TValue absentkey = {ABSTKEYCONSTANT}; 97*0495ed39SKyle Evans 98*0495ed39SKyle Evans 99*0495ed39SKyle Evans 1008e3e3a7aSWarner Losh /* 1018e3e3a7aSWarner Losh ** Hash for floating-point numbers. 1028e3e3a7aSWarner Losh ** The main computation should be just 1038e3e3a7aSWarner Losh ** n = frexp(n, &i); return (n * INT_MAX) + i 1048e3e3a7aSWarner Losh ** but there are some numerical subtleties. 1058e3e3a7aSWarner Losh ** In a two-complement representation, INT_MAX does not has an exact 1068e3e3a7aSWarner Losh ** representation as a float, but INT_MIN does; because the absolute 1078e3e3a7aSWarner Losh ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the 1088e3e3a7aSWarner Losh ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal 1098e3e3a7aSWarner Losh ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when 1108e3e3a7aSWarner Losh ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with 1118e3e3a7aSWarner Losh ** INT_MIN. 1128e3e3a7aSWarner Losh */ 1138e3e3a7aSWarner Losh #if !defined(l_hashfloat) 1148e3e3a7aSWarner Losh static int l_hashfloat (lua_Number n) { 1158e3e3a7aSWarner Losh int i; 1168e3e3a7aSWarner Losh lua_Integer ni; 1178e3e3a7aSWarner Losh n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN); 1188e3e3a7aSWarner Losh if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */ 1198e3e3a7aSWarner Losh lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL)); 1208e3e3a7aSWarner Losh return 0; 1218e3e3a7aSWarner Losh } 1228e3e3a7aSWarner Losh else { /* normal case */ 123*0495ed39SKyle Evans unsigned int u = cast_uint(i) + cast_uint(ni); 124*0495ed39SKyle Evans return cast_int(u <= cast_uint(INT_MAX) ? u : ~u); 1258e3e3a7aSWarner Losh } 1268e3e3a7aSWarner Losh } 1278e3e3a7aSWarner Losh #endif 1288e3e3a7aSWarner Losh 1298e3e3a7aSWarner Losh 1308e3e3a7aSWarner Losh /* 131*0495ed39SKyle Evans ** returns the 'main' position of an element in a table (that is, 132*0495ed39SKyle Evans ** the index of its hash value). The key comes broken (tag in 'ktt' 133*0495ed39SKyle Evans ** and value in 'vkl') so that we can call it on keys inserted into 134*0495ed39SKyle Evans ** nodes. 1358e3e3a7aSWarner Losh */ 136*0495ed39SKyle Evans static Node *mainposition (const Table *t, int ktt, const Value *kvl) { 137*0495ed39SKyle Evans switch (withvariant(ktt)) { 138*0495ed39SKyle Evans case LUA_VNUMINT: 139*0495ed39SKyle Evans return hashint(t, ivalueraw(*kvl)); 140*0495ed39SKyle Evans case LUA_VNUMFLT: 141*0495ed39SKyle Evans return hashmod(t, l_hashfloat(fltvalueraw(*kvl))); 142*0495ed39SKyle Evans case LUA_VSHRSTR: 143*0495ed39SKyle Evans return hashstr(t, tsvalueraw(*kvl)); 144*0495ed39SKyle Evans case LUA_VLNGSTR: 145*0495ed39SKyle Evans return hashpow2(t, luaS_hashlongstr(tsvalueraw(*kvl))); 146*0495ed39SKyle Evans case LUA_VFALSE: 147*0495ed39SKyle Evans return hashboolean(t, 0); 148*0495ed39SKyle Evans case LUA_VTRUE: 149*0495ed39SKyle Evans return hashboolean(t, 1); 150*0495ed39SKyle Evans case LUA_VLIGHTUSERDATA: 151*0495ed39SKyle Evans return hashpointer(t, pvalueraw(*kvl)); 152*0495ed39SKyle Evans case LUA_VLCF: 153*0495ed39SKyle Evans return hashpointer(t, fvalueraw(*kvl)); 1548e3e3a7aSWarner Losh default: 155*0495ed39SKyle Evans return hashpointer(t, gcvalueraw(*kvl)); 1568e3e3a7aSWarner Losh } 1578e3e3a7aSWarner Losh } 1588e3e3a7aSWarner Losh 1598e3e3a7aSWarner Losh 1608e3e3a7aSWarner Losh /* 161*0495ed39SKyle Evans ** Returns the main position of an element given as a 'TValue' 1628e3e3a7aSWarner Losh */ 163*0495ed39SKyle Evans static Node *mainpositionTV (const Table *t, const TValue *key) { 164*0495ed39SKyle Evans return mainposition(t, rawtt(key), valraw(key)); 1658e3e3a7aSWarner Losh } 166*0495ed39SKyle Evans 167*0495ed39SKyle Evans 168*0495ed39SKyle Evans /* 169*0495ed39SKyle Evans ** Check whether key 'k1' is equal to the key in node 'n2'. This 170*0495ed39SKyle Evans ** equality is raw, so there are no metamethods. Floats with integer 171*0495ed39SKyle Evans ** values have been normalized, so integers cannot be equal to 172*0495ed39SKyle Evans ** floats. It is assumed that 'eqshrstr' is simply pointer equality, so 173*0495ed39SKyle Evans ** that short strings are handled in the default case. 174*0495ed39SKyle Evans ** A true 'deadok' means to accept dead keys as equal to their original 175*0495ed39SKyle Evans ** values. All dead keys are compared in the default case, by pointer 176*0495ed39SKyle Evans ** identity. (Only collectable objects can produce dead keys.) Note that 177*0495ed39SKyle Evans ** dead long strings are also compared by identity. 178*0495ed39SKyle Evans ** Once a key is dead, its corresponding value may be collected, and 179*0495ed39SKyle Evans ** then another value can be created with the same address. If this 180*0495ed39SKyle Evans ** other value is given to 'next', 'equalkey' will signal a false 181*0495ed39SKyle Evans ** positive. In a regular traversal, this situation should never happen, 182*0495ed39SKyle Evans ** as all keys given to 'next' came from the table itself, and therefore 183*0495ed39SKyle Evans ** could not have been collected. Outside a regular traversal, we 184*0495ed39SKyle Evans ** have garbage in, garbage out. What is relevant is that this false 185*0495ed39SKyle Evans ** positive does not break anything. (In particular, 'next' will return 186*0495ed39SKyle Evans ** some other valid item on the table or nil.) 187*0495ed39SKyle Evans */ 188*0495ed39SKyle Evans static int equalkey (const TValue *k1, const Node *n2, int deadok) { 189*0495ed39SKyle Evans if ((rawtt(k1) != keytt(n2)) && /* not the same variants? */ 190*0495ed39SKyle Evans !(deadok && keyisdead(n2) && iscollectable(k1))) 191*0495ed39SKyle Evans return 0; /* cannot be same key */ 192*0495ed39SKyle Evans switch (keytt(n2)) { 193*0495ed39SKyle Evans case LUA_VNIL: case LUA_VFALSE: case LUA_VTRUE: 194*0495ed39SKyle Evans return 1; 195*0495ed39SKyle Evans case LUA_VNUMINT: 196*0495ed39SKyle Evans return (ivalue(k1) == keyival(n2)); 197*0495ed39SKyle Evans case LUA_VNUMFLT: 198*0495ed39SKyle Evans return luai_numeq(fltvalue(k1), fltvalueraw(keyval(n2))); 199*0495ed39SKyle Evans case LUA_VLIGHTUSERDATA: 200*0495ed39SKyle Evans return pvalue(k1) == pvalueraw(keyval(n2)); 201*0495ed39SKyle Evans case LUA_VLCF: 202*0495ed39SKyle Evans return fvalue(k1) == fvalueraw(keyval(n2)); 203*0495ed39SKyle Evans case ctb(LUA_VLNGSTR): 204*0495ed39SKyle Evans return luaS_eqlngstr(tsvalue(k1), keystrval(n2)); 205*0495ed39SKyle Evans default: 206*0495ed39SKyle Evans return gcvalue(k1) == gcvalueraw(keyval(n2)); 207*0495ed39SKyle Evans } 208*0495ed39SKyle Evans } 209*0495ed39SKyle Evans 210*0495ed39SKyle Evans 211*0495ed39SKyle Evans /* 212*0495ed39SKyle Evans ** True if value of 'alimit' is equal to the real size of the array 213*0495ed39SKyle Evans ** part of table 't'. (Otherwise, the array part must be larger than 214*0495ed39SKyle Evans ** 'alimit'.) 215*0495ed39SKyle Evans */ 216*0495ed39SKyle Evans #define limitequalsasize(t) (isrealasize(t) || ispow2((t)->alimit)) 217*0495ed39SKyle Evans 218*0495ed39SKyle Evans 219*0495ed39SKyle Evans /* 220*0495ed39SKyle Evans ** Returns the real size of the 'array' array 221*0495ed39SKyle Evans */ 222*0495ed39SKyle Evans LUAI_FUNC unsigned int luaH_realasize (const Table *t) { 223*0495ed39SKyle Evans if (limitequalsasize(t)) 224*0495ed39SKyle Evans return t->alimit; /* this is the size */ 225*0495ed39SKyle Evans else { 226*0495ed39SKyle Evans unsigned int size = t->alimit; 227*0495ed39SKyle Evans /* compute the smallest power of 2 not smaller than 'n' */ 228*0495ed39SKyle Evans size |= (size >> 1); 229*0495ed39SKyle Evans size |= (size >> 2); 230*0495ed39SKyle Evans size |= (size >> 4); 231*0495ed39SKyle Evans size |= (size >> 8); 232*0495ed39SKyle Evans size |= (size >> 16); 233*0495ed39SKyle Evans #if (UINT_MAX >> 30) > 3 234*0495ed39SKyle Evans size |= (size >> 32); /* unsigned int has more than 32 bits */ 235*0495ed39SKyle Evans #endif 236*0495ed39SKyle Evans size++; 237*0495ed39SKyle Evans lua_assert(ispow2(size) && size/2 < t->alimit && t->alimit < size); 238*0495ed39SKyle Evans return size; 239*0495ed39SKyle Evans } 240*0495ed39SKyle Evans } 241*0495ed39SKyle Evans 242*0495ed39SKyle Evans 243*0495ed39SKyle Evans /* 244*0495ed39SKyle Evans ** Check whether real size of the array is a power of 2. 245*0495ed39SKyle Evans ** (If it is not, 'alimit' cannot be changed to any other value 246*0495ed39SKyle Evans ** without changing the real size.) 247*0495ed39SKyle Evans */ 248*0495ed39SKyle Evans static int ispow2realasize (const Table *t) { 249*0495ed39SKyle Evans return (!isrealasize(t) || ispow2(t->alimit)); 250*0495ed39SKyle Evans } 251*0495ed39SKyle Evans 252*0495ed39SKyle Evans 253*0495ed39SKyle Evans static unsigned int setlimittosize (Table *t) { 254*0495ed39SKyle Evans t->alimit = luaH_realasize(t); 255*0495ed39SKyle Evans setrealasize(t); 256*0495ed39SKyle Evans return t->alimit; 257*0495ed39SKyle Evans } 258*0495ed39SKyle Evans 259*0495ed39SKyle Evans 260*0495ed39SKyle Evans #define limitasasize(t) check_exp(isrealasize(t), t->alimit) 261*0495ed39SKyle Evans 262*0495ed39SKyle Evans 263*0495ed39SKyle Evans 264*0495ed39SKyle Evans /* 265*0495ed39SKyle Evans ** "Generic" get version. (Not that generic: not valid for integers, 266*0495ed39SKyle Evans ** which may be in array part, nor for floats with integral values.) 267*0495ed39SKyle Evans ** See explanation about 'deadok' in function 'equalkey'. 268*0495ed39SKyle Evans */ 269*0495ed39SKyle Evans static const TValue *getgeneric (Table *t, const TValue *key, int deadok) { 270*0495ed39SKyle Evans Node *n = mainpositionTV(t, key); 271*0495ed39SKyle Evans for (;;) { /* check whether 'key' is somewhere in the chain */ 272*0495ed39SKyle Evans if (equalkey(key, n, deadok)) 273*0495ed39SKyle Evans return gval(n); /* that's it */ 274*0495ed39SKyle Evans else { 275*0495ed39SKyle Evans int nx = gnext(n); 276*0495ed39SKyle Evans if (nx == 0) 277*0495ed39SKyle Evans return &absentkey; /* not found */ 278*0495ed39SKyle Evans n += nx; 279*0495ed39SKyle Evans } 280*0495ed39SKyle Evans } 281*0495ed39SKyle Evans } 282*0495ed39SKyle Evans 283*0495ed39SKyle Evans 284*0495ed39SKyle Evans /* 285*0495ed39SKyle Evans ** returns the index for 'k' if 'k' is an appropriate key to live in 286*0495ed39SKyle Evans ** the array part of a table, 0 otherwise. 287*0495ed39SKyle Evans */ 288*0495ed39SKyle Evans static unsigned int arrayindex (lua_Integer k) { 289*0495ed39SKyle Evans if (l_castS2U(k) - 1u < MAXASIZE) /* 'k' in [1, MAXASIZE]? */ 290*0495ed39SKyle Evans return cast_uint(k); /* 'key' is an appropriate array index */ 291*0495ed39SKyle Evans else 292*0495ed39SKyle Evans return 0; 2938e3e3a7aSWarner Losh } 2948e3e3a7aSWarner Losh 2958e3e3a7aSWarner Losh 2968e3e3a7aSWarner Losh /* 2978e3e3a7aSWarner Losh ** returns the index of a 'key' for table traversals. First goes all 2988e3e3a7aSWarner Losh ** elements in the array part, then elements in the hash part. The 2998e3e3a7aSWarner Losh ** beginning of a traversal is signaled by 0. 3008e3e3a7aSWarner Losh */ 301*0495ed39SKyle Evans static unsigned int findindex (lua_State *L, Table *t, TValue *key, 302*0495ed39SKyle Evans unsigned int asize) { 3038e3e3a7aSWarner Losh unsigned int i; 3048e3e3a7aSWarner Losh if (ttisnil(key)) return 0; /* first iteration */ 305*0495ed39SKyle Evans i = ttisinteger(key) ? arrayindex(ivalue(key)) : 0; 306*0495ed39SKyle Evans if (i - 1u < asize) /* is 'key' inside array part? */ 3078e3e3a7aSWarner Losh return i; /* yes; that's the index */ 3088e3e3a7aSWarner Losh else { 309*0495ed39SKyle Evans const TValue *n = getgeneric(t, key, 1); 310*0495ed39SKyle Evans if (unlikely(isabstkey(n))) 3118e3e3a7aSWarner Losh luaG_runerror(L, "invalid key to 'next'"); /* key not found */ 312*0495ed39SKyle Evans i = cast_int(nodefromval(n) - gnode(t, 0)); /* key index in hash table */ 313*0495ed39SKyle Evans /* hash elements are numbered after array ones */ 314*0495ed39SKyle Evans return (i + 1) + asize; 3158e3e3a7aSWarner Losh } 3168e3e3a7aSWarner Losh } 3178e3e3a7aSWarner Losh 3188e3e3a7aSWarner Losh 3198e3e3a7aSWarner Losh int luaH_next (lua_State *L, Table *t, StkId key) { 320*0495ed39SKyle Evans unsigned int asize = luaH_realasize(t); 321*0495ed39SKyle Evans unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */ 322*0495ed39SKyle Evans for (; i < asize; i++) { /* try first array part */ 323*0495ed39SKyle Evans if (!isempty(&t->array[i])) { /* a non-empty entry? */ 324*0495ed39SKyle Evans setivalue(s2v(key), i + 1); 3258e3e3a7aSWarner Losh setobj2s(L, key + 1, &t->array[i]); 3268e3e3a7aSWarner Losh return 1; 3278e3e3a7aSWarner Losh } 3288e3e3a7aSWarner Losh } 329*0495ed39SKyle Evans for (i -= asize; cast_int(i) < sizenode(t); i++) { /* hash part */ 330*0495ed39SKyle Evans if (!isempty(gval(gnode(t, i)))) { /* a non-empty entry? */ 331*0495ed39SKyle Evans Node *n = gnode(t, i); 332*0495ed39SKyle Evans getnodekey(L, s2v(key), n); 333*0495ed39SKyle Evans setobj2s(L, key + 1, gval(n)); 3348e3e3a7aSWarner Losh return 1; 3358e3e3a7aSWarner Losh } 3368e3e3a7aSWarner Losh } 3378e3e3a7aSWarner Losh return 0; /* no more elements */ 3388e3e3a7aSWarner Losh } 3398e3e3a7aSWarner Losh 3408e3e3a7aSWarner Losh 341*0495ed39SKyle Evans static void freehash (lua_State *L, Table *t) { 342*0495ed39SKyle Evans if (!isdummy(t)) 343*0495ed39SKyle Evans luaM_freearray(L, t->node, cast_sizet(sizenode(t))); 344*0495ed39SKyle Evans } 345*0495ed39SKyle Evans 346*0495ed39SKyle Evans 3478e3e3a7aSWarner Losh /* 3488e3e3a7aSWarner Losh ** {============================================================= 3498e3e3a7aSWarner Losh ** Rehash 3508e3e3a7aSWarner Losh ** ============================================================== 3518e3e3a7aSWarner Losh */ 3528e3e3a7aSWarner Losh 3538e3e3a7aSWarner Losh /* 3548e3e3a7aSWarner Losh ** Compute the optimal size for the array part of table 't'. 'nums' is a 3558e3e3a7aSWarner Losh ** "count array" where 'nums[i]' is the number of integers in the table 3568e3e3a7aSWarner Losh ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of 3578e3e3a7aSWarner Losh ** integer keys in the table and leaves with the number of keys that 358*0495ed39SKyle Evans ** will go to the array part; return the optimal size. (The condition 359*0495ed39SKyle Evans ** 'twotoi > 0' in the for loop stops the loop if 'twotoi' overflows.) 3608e3e3a7aSWarner Losh */ 3618e3e3a7aSWarner Losh static unsigned int computesizes (unsigned int nums[], unsigned int *pna) { 3628e3e3a7aSWarner Losh int i; 3638e3e3a7aSWarner Losh unsigned int twotoi; /* 2^i (candidate for optimal size) */ 3648e3e3a7aSWarner Losh unsigned int a = 0; /* number of elements smaller than 2^i */ 3658e3e3a7aSWarner Losh unsigned int na = 0; /* number of elements to go to array part */ 3668e3e3a7aSWarner Losh unsigned int optimal = 0; /* optimal size for array part */ 3678e3e3a7aSWarner Losh /* loop while keys can fill more than half of total size */ 368e112e9d2SKyle Evans for (i = 0, twotoi = 1; 369e112e9d2SKyle Evans twotoi > 0 && *pna > twotoi / 2; 370e112e9d2SKyle Evans i++, twotoi *= 2) { 3718e3e3a7aSWarner Losh a += nums[i]; 3728e3e3a7aSWarner Losh if (a > twotoi/2) { /* more than half elements present? */ 3738e3e3a7aSWarner Losh optimal = twotoi; /* optimal size (till now) */ 3748e3e3a7aSWarner Losh na = a; /* all elements up to 'optimal' will go to array part */ 3758e3e3a7aSWarner Losh } 3768e3e3a7aSWarner Losh } 3778e3e3a7aSWarner Losh lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal); 3788e3e3a7aSWarner Losh *pna = na; 3798e3e3a7aSWarner Losh return optimal; 3808e3e3a7aSWarner Losh } 3818e3e3a7aSWarner Losh 3828e3e3a7aSWarner Losh 383*0495ed39SKyle Evans static int countint (lua_Integer key, unsigned int *nums) { 3848e3e3a7aSWarner Losh unsigned int k = arrayindex(key); 3858e3e3a7aSWarner Losh if (k != 0) { /* is 'key' an appropriate array index? */ 3868e3e3a7aSWarner Losh nums[luaO_ceillog2(k)]++; /* count as such */ 3878e3e3a7aSWarner Losh return 1; 3888e3e3a7aSWarner Losh } 3898e3e3a7aSWarner Losh else 3908e3e3a7aSWarner Losh return 0; 3918e3e3a7aSWarner Losh } 3928e3e3a7aSWarner Losh 3938e3e3a7aSWarner Losh 3948e3e3a7aSWarner Losh /* 3958e3e3a7aSWarner Losh ** Count keys in array part of table 't': Fill 'nums[i]' with 3968e3e3a7aSWarner Losh ** number of keys that will go into corresponding slice and return 3978e3e3a7aSWarner Losh ** total number of non-nil keys. 3988e3e3a7aSWarner Losh */ 3998e3e3a7aSWarner Losh static unsigned int numusearray (const Table *t, unsigned int *nums) { 4008e3e3a7aSWarner Losh int lg; 4018e3e3a7aSWarner Losh unsigned int ttlg; /* 2^lg */ 4028e3e3a7aSWarner Losh unsigned int ause = 0; /* summation of 'nums' */ 4038e3e3a7aSWarner Losh unsigned int i = 1; /* count to traverse all array keys */ 404*0495ed39SKyle Evans unsigned int asize = limitasasize(t); /* real array size */ 4058e3e3a7aSWarner Losh /* traverse each slice */ 4068e3e3a7aSWarner Losh for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { 4078e3e3a7aSWarner Losh unsigned int lc = 0; /* counter */ 4088e3e3a7aSWarner Losh unsigned int lim = ttlg; 409*0495ed39SKyle Evans if (lim > asize) { 410*0495ed39SKyle Evans lim = asize; /* adjust upper limit */ 4118e3e3a7aSWarner Losh if (i > lim) 4128e3e3a7aSWarner Losh break; /* no more elements to count */ 4138e3e3a7aSWarner Losh } 4148e3e3a7aSWarner Losh /* count elements in range (2^(lg - 1), 2^lg] */ 4158e3e3a7aSWarner Losh for (; i <= lim; i++) { 416*0495ed39SKyle Evans if (!isempty(&t->array[i-1])) 4178e3e3a7aSWarner Losh lc++; 4188e3e3a7aSWarner Losh } 4198e3e3a7aSWarner Losh nums[lg] += lc; 4208e3e3a7aSWarner Losh ause += lc; 4218e3e3a7aSWarner Losh } 4228e3e3a7aSWarner Losh return ause; 4238e3e3a7aSWarner Losh } 4248e3e3a7aSWarner Losh 4258e3e3a7aSWarner Losh 4268e3e3a7aSWarner Losh static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) { 4278e3e3a7aSWarner Losh int totaluse = 0; /* total number of elements */ 4288e3e3a7aSWarner Losh int ause = 0; /* elements added to 'nums' (can go to array part) */ 4298e3e3a7aSWarner Losh int i = sizenode(t); 4308e3e3a7aSWarner Losh while (i--) { 4318e3e3a7aSWarner Losh Node *n = &t->node[i]; 432*0495ed39SKyle Evans if (!isempty(gval(n))) { 433*0495ed39SKyle Evans if (keyisinteger(n)) 434*0495ed39SKyle Evans ause += countint(keyival(n), nums); 4358e3e3a7aSWarner Losh totaluse++; 4368e3e3a7aSWarner Losh } 4378e3e3a7aSWarner Losh } 4388e3e3a7aSWarner Losh *pna += ause; 4398e3e3a7aSWarner Losh return totaluse; 4408e3e3a7aSWarner Losh } 4418e3e3a7aSWarner Losh 4428e3e3a7aSWarner Losh 443*0495ed39SKyle Evans /* 444*0495ed39SKyle Evans ** Creates an array for the hash part of a table with the given 445*0495ed39SKyle Evans ** size, or reuses the dummy node if size is zero. 446*0495ed39SKyle Evans ** The computation for size overflow is in two steps: the first 447*0495ed39SKyle Evans ** comparison ensures that the shift in the second one does not 448*0495ed39SKyle Evans ** overflow. 449*0495ed39SKyle Evans */ 4508e3e3a7aSWarner Losh static void setnodevector (lua_State *L, Table *t, unsigned int size) { 4518e3e3a7aSWarner Losh if (size == 0) { /* no elements to hash part? */ 4528e3e3a7aSWarner Losh t->node = cast(Node *, dummynode); /* use common 'dummynode' */ 4538e3e3a7aSWarner Losh t->lsizenode = 0; 4548e3e3a7aSWarner Losh t->lastfree = NULL; /* signal that it is using dummy node */ 4558e3e3a7aSWarner Losh } 4568e3e3a7aSWarner Losh else { 4578e3e3a7aSWarner Losh int i; 4588e3e3a7aSWarner Losh int lsize = luaO_ceillog2(size); 459*0495ed39SKyle Evans if (lsize > MAXHBITS || (1u << lsize) > MAXHSIZE) 4608e3e3a7aSWarner Losh luaG_runerror(L, "table overflow"); 4618e3e3a7aSWarner Losh size = twoto(lsize); 4628e3e3a7aSWarner Losh t->node = luaM_newvector(L, size, Node); 4638e3e3a7aSWarner Losh for (i = 0; i < (int)size; i++) { 4648e3e3a7aSWarner Losh Node *n = gnode(t, i); 4658e3e3a7aSWarner Losh gnext(n) = 0; 466*0495ed39SKyle Evans setnilkey(n); 467*0495ed39SKyle Evans setempty(gval(n)); 4688e3e3a7aSWarner Losh } 4698e3e3a7aSWarner Losh t->lsizenode = cast_byte(lsize); 4708e3e3a7aSWarner Losh t->lastfree = gnode(t, size); /* all positions are free */ 4718e3e3a7aSWarner Losh } 4728e3e3a7aSWarner Losh } 4738e3e3a7aSWarner Losh 4748e3e3a7aSWarner Losh 475*0495ed39SKyle Evans /* 476*0495ed39SKyle Evans ** (Re)insert all elements from the hash part of 'ot' into table 't'. 477*0495ed39SKyle Evans */ 478*0495ed39SKyle Evans static void reinsert (lua_State *L, Table *ot, Table *t) { 4798e3e3a7aSWarner Losh int j; 480*0495ed39SKyle Evans int size = sizenode(ot); 481*0495ed39SKyle Evans for (j = 0; j < size; j++) { 482*0495ed39SKyle Evans Node *old = gnode(ot, j); 483*0495ed39SKyle Evans if (!isempty(gval(old))) { 4848e3e3a7aSWarner Losh /* doesn't need barrier/invalidate cache, as entry was 4858e3e3a7aSWarner Losh already present in the table */ 486*0495ed39SKyle Evans TValue k; 487*0495ed39SKyle Evans getnodekey(L, &k, old); 488*0495ed39SKyle Evans setobjt2t(L, luaH_set(L, t, &k), gval(old)); 4898e3e3a7aSWarner Losh } 4908e3e3a7aSWarner Losh } 491*0495ed39SKyle Evans } 492*0495ed39SKyle Evans 493*0495ed39SKyle Evans 494*0495ed39SKyle Evans /* 495*0495ed39SKyle Evans ** Exchange the hash part of 't1' and 't2'. 496*0495ed39SKyle Evans */ 497*0495ed39SKyle Evans static void exchangehashpart (Table *t1, Table *t2) { 498*0495ed39SKyle Evans lu_byte lsizenode = t1->lsizenode; 499*0495ed39SKyle Evans Node *node = t1->node; 500*0495ed39SKyle Evans Node *lastfree = t1->lastfree; 501*0495ed39SKyle Evans t1->lsizenode = t2->lsizenode; 502*0495ed39SKyle Evans t1->node = t2->node; 503*0495ed39SKyle Evans t1->lastfree = t2->lastfree; 504*0495ed39SKyle Evans t2->lsizenode = lsizenode; 505*0495ed39SKyle Evans t2->node = node; 506*0495ed39SKyle Evans t2->lastfree = lastfree; 507*0495ed39SKyle Evans } 508*0495ed39SKyle Evans 509*0495ed39SKyle Evans 510*0495ed39SKyle Evans /* 511*0495ed39SKyle Evans ** Resize table 't' for the new given sizes. Both allocations (for 512*0495ed39SKyle Evans ** the hash part and for the array part) can fail, which creates some 513*0495ed39SKyle Evans ** subtleties. If the first allocation, for the hash part, fails, an 514*0495ed39SKyle Evans ** error is raised and that is it. Otherwise, it copies the elements from 515*0495ed39SKyle Evans ** the shrinking part of the array (if it is shrinking) into the new 516*0495ed39SKyle Evans ** hash. Then it reallocates the array part. If that fails, the table 517*0495ed39SKyle Evans ** is in its original state; the function frees the new hash part and then 518*0495ed39SKyle Evans ** raises the allocation error. Otherwise, it sets the new hash part 519*0495ed39SKyle Evans ** into the table, initializes the new part of the array (if any) with 520*0495ed39SKyle Evans ** nils and reinserts the elements of the old hash back into the new 521*0495ed39SKyle Evans ** parts of the table. 522*0495ed39SKyle Evans */ 523*0495ed39SKyle Evans void luaH_resize (lua_State *L, Table *t, unsigned int newasize, 524*0495ed39SKyle Evans unsigned int nhsize) { 525*0495ed39SKyle Evans unsigned int i; 526*0495ed39SKyle Evans Table newt; /* to keep the new hash part */ 527*0495ed39SKyle Evans unsigned int oldasize = setlimittosize(t); 528*0495ed39SKyle Evans TValue *newarray; 529*0495ed39SKyle Evans /* create new hash part with appropriate size into 'newt' */ 530*0495ed39SKyle Evans setnodevector(L, &newt, nhsize); 531*0495ed39SKyle Evans if (newasize < oldasize) { /* will array shrink? */ 532*0495ed39SKyle Evans t->alimit = newasize; /* pretend array has new size... */ 533*0495ed39SKyle Evans exchangehashpart(t, &newt); /* and new hash */ 534*0495ed39SKyle Evans /* re-insert into the new hash the elements from vanishing slice */ 535*0495ed39SKyle Evans for (i = newasize; i < oldasize; i++) { 536*0495ed39SKyle Evans if (!isempty(&t->array[i])) 537*0495ed39SKyle Evans luaH_setint(L, t, i + 1, &t->array[i]); 538*0495ed39SKyle Evans } 539*0495ed39SKyle Evans t->alimit = oldasize; /* restore current size... */ 540*0495ed39SKyle Evans exchangehashpart(t, &newt); /* and hash (in case of errors) */ 541*0495ed39SKyle Evans } 542*0495ed39SKyle Evans /* allocate new array */ 543*0495ed39SKyle Evans newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue); 544*0495ed39SKyle Evans if (unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ 545*0495ed39SKyle Evans freehash(L, &newt); /* release new hash part */ 546*0495ed39SKyle Evans luaM_error(L); /* raise error (with array unchanged) */ 547*0495ed39SKyle Evans } 548*0495ed39SKyle Evans /* allocation ok; initialize new part of the array */ 549*0495ed39SKyle Evans exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */ 550*0495ed39SKyle Evans t->array = newarray; /* set new array part */ 551*0495ed39SKyle Evans t->alimit = newasize; 552*0495ed39SKyle Evans for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ 553*0495ed39SKyle Evans setempty(&t->array[i]); 554*0495ed39SKyle Evans /* re-insert elements from old hash part into new parts */ 555*0495ed39SKyle Evans reinsert(L, &newt, t); /* 'newt' now has the old hash */ 556*0495ed39SKyle Evans freehash(L, &newt); /* free old hash part */ 5578e3e3a7aSWarner Losh } 5588e3e3a7aSWarner Losh 5598e3e3a7aSWarner Losh 5608e3e3a7aSWarner Losh void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) { 5618e3e3a7aSWarner Losh int nsize = allocsizenode(t); 5628e3e3a7aSWarner Losh luaH_resize(L, t, nasize, nsize); 5638e3e3a7aSWarner Losh } 5648e3e3a7aSWarner Losh 5658e3e3a7aSWarner Losh /* 5668e3e3a7aSWarner Losh ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i 5678e3e3a7aSWarner Losh */ 5688e3e3a7aSWarner Losh static void rehash (lua_State *L, Table *t, const TValue *ek) { 5698e3e3a7aSWarner Losh unsigned int asize; /* optimal size for array part */ 5708e3e3a7aSWarner Losh unsigned int na; /* number of keys in the array part */ 5718e3e3a7aSWarner Losh unsigned int nums[MAXABITS + 1]; 5728e3e3a7aSWarner Losh int i; 5738e3e3a7aSWarner Losh int totaluse; 5748e3e3a7aSWarner Losh for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */ 575*0495ed39SKyle Evans setlimittosize(t); 5768e3e3a7aSWarner Losh na = numusearray(t, nums); /* count keys in array part */ 5778e3e3a7aSWarner Losh totaluse = na; /* all those keys are integer keys */ 5788e3e3a7aSWarner Losh totaluse += numusehash(t, nums, &na); /* count keys in hash part */ 5798e3e3a7aSWarner Losh /* count extra key */ 580*0495ed39SKyle Evans if (ttisinteger(ek)) 581*0495ed39SKyle Evans na += countint(ivalue(ek), nums); 5828e3e3a7aSWarner Losh totaluse++; 5838e3e3a7aSWarner Losh /* compute new size for array part */ 5848e3e3a7aSWarner Losh asize = computesizes(nums, &na); 5858e3e3a7aSWarner Losh /* resize the table to new computed sizes */ 5868e3e3a7aSWarner Losh luaH_resize(L, t, asize, totaluse - na); 5878e3e3a7aSWarner Losh } 5888e3e3a7aSWarner Losh 5898e3e3a7aSWarner Losh 5908e3e3a7aSWarner Losh 5918e3e3a7aSWarner Losh /* 5928e3e3a7aSWarner Losh ** }============================================================= 5938e3e3a7aSWarner Losh */ 5948e3e3a7aSWarner Losh 5958e3e3a7aSWarner Losh 5968e3e3a7aSWarner Losh Table *luaH_new (lua_State *L) { 597*0495ed39SKyle Evans GCObject *o = luaC_newobj(L, LUA_VTABLE, sizeof(Table)); 5988e3e3a7aSWarner Losh Table *t = gco2t(o); 5998e3e3a7aSWarner Losh t->metatable = NULL; 600*0495ed39SKyle Evans t->flags = cast_byte(maskflags); /* table has no metamethod fields */ 6018e3e3a7aSWarner Losh t->array = NULL; 602*0495ed39SKyle Evans t->alimit = 0; 6038e3e3a7aSWarner Losh setnodevector(L, t, 0); 6048e3e3a7aSWarner Losh return t; 6058e3e3a7aSWarner Losh } 6068e3e3a7aSWarner Losh 6078e3e3a7aSWarner Losh 6088e3e3a7aSWarner Losh void luaH_free (lua_State *L, Table *t) { 609*0495ed39SKyle Evans freehash(L, t); 610*0495ed39SKyle Evans luaM_freearray(L, t->array, luaH_realasize(t)); 6118e3e3a7aSWarner Losh luaM_free(L, t); 6128e3e3a7aSWarner Losh } 6138e3e3a7aSWarner Losh 6148e3e3a7aSWarner Losh 6158e3e3a7aSWarner Losh static Node *getfreepos (Table *t) { 6168e3e3a7aSWarner Losh if (!isdummy(t)) { 6178e3e3a7aSWarner Losh while (t->lastfree > t->node) { 6188e3e3a7aSWarner Losh t->lastfree--; 619*0495ed39SKyle Evans if (keyisnil(t->lastfree)) 6208e3e3a7aSWarner Losh return t->lastfree; 6218e3e3a7aSWarner Losh } 6228e3e3a7aSWarner Losh } 6238e3e3a7aSWarner Losh return NULL; /* could not find a free place */ 6248e3e3a7aSWarner Losh } 6258e3e3a7aSWarner Losh 6268e3e3a7aSWarner Losh 6278e3e3a7aSWarner Losh 6288e3e3a7aSWarner Losh /* 6298e3e3a7aSWarner Losh ** inserts a new key into a hash table; first, check whether key's main 6308e3e3a7aSWarner Losh ** position is free. If not, check whether colliding node is in its main 6318e3e3a7aSWarner Losh ** position or not: if it is not, move colliding node to an empty place and 6328e3e3a7aSWarner Losh ** put new key in its main position; otherwise (colliding node is in its main 6338e3e3a7aSWarner Losh ** position), new key goes to an empty position. 6348e3e3a7aSWarner Losh */ 6358e3e3a7aSWarner Losh TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) { 6368e3e3a7aSWarner Losh Node *mp; 6378e3e3a7aSWarner Losh TValue aux; 638*0495ed39SKyle Evans if (unlikely(ttisnil(key))) 639*0495ed39SKyle Evans luaG_runerror(L, "table index is nil"); 6408e3e3a7aSWarner Losh else if (ttisfloat(key)) { 641*0495ed39SKyle Evans lua_Number f = fltvalue(key); 6428e3e3a7aSWarner Losh lua_Integer k; 643*0495ed39SKyle Evans if (luaV_flttointeger(f, &k, F2Ieq)) { /* does key fit in an integer? */ 6448e3e3a7aSWarner Losh setivalue(&aux, k); 6458e3e3a7aSWarner Losh key = &aux; /* insert it as an integer */ 6468e3e3a7aSWarner Losh } 647*0495ed39SKyle Evans else if (unlikely(luai_numisnan(f))) 6488e3e3a7aSWarner Losh luaG_runerror(L, "table index is NaN"); 6498e3e3a7aSWarner Losh } 650*0495ed39SKyle Evans mp = mainpositionTV(t, key); 651*0495ed39SKyle Evans if (!isempty(gval(mp)) || isdummy(t)) { /* main position is taken? */ 6528e3e3a7aSWarner Losh Node *othern; 6538e3e3a7aSWarner Losh Node *f = getfreepos(t); /* get a free place */ 6548e3e3a7aSWarner Losh if (f == NULL) { /* cannot find a free place? */ 6558e3e3a7aSWarner Losh rehash(L, t, key); /* grow table */ 6568e3e3a7aSWarner Losh /* whatever called 'newkey' takes care of TM cache */ 6578e3e3a7aSWarner Losh return luaH_set(L, t, key); /* insert key into grown table */ 6588e3e3a7aSWarner Losh } 6598e3e3a7aSWarner Losh lua_assert(!isdummy(t)); 660*0495ed39SKyle Evans othern = mainposition(t, keytt(mp), &keyval(mp)); 6618e3e3a7aSWarner Losh if (othern != mp) { /* is colliding node out of its main position? */ 6628e3e3a7aSWarner Losh /* yes; move colliding node into free position */ 6638e3e3a7aSWarner Losh while (othern + gnext(othern) != mp) /* find previous */ 6648e3e3a7aSWarner Losh othern += gnext(othern); 6658e3e3a7aSWarner Losh gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */ 6668e3e3a7aSWarner Losh *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */ 6678e3e3a7aSWarner Losh if (gnext(mp) != 0) { 6688e3e3a7aSWarner Losh gnext(f) += cast_int(mp - f); /* correct 'next' */ 6698e3e3a7aSWarner Losh gnext(mp) = 0; /* now 'mp' is free */ 6708e3e3a7aSWarner Losh } 671*0495ed39SKyle Evans setempty(gval(mp)); 6728e3e3a7aSWarner Losh } 6738e3e3a7aSWarner Losh else { /* colliding node is in its own main position */ 6748e3e3a7aSWarner Losh /* new node will go into free position */ 6758e3e3a7aSWarner Losh if (gnext(mp) != 0) 6768e3e3a7aSWarner Losh gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */ 6778e3e3a7aSWarner Losh else lua_assert(gnext(f) == 0); 6788e3e3a7aSWarner Losh gnext(mp) = cast_int(f - mp); 6798e3e3a7aSWarner Losh mp = f; 6808e3e3a7aSWarner Losh } 6818e3e3a7aSWarner Losh } 682*0495ed39SKyle Evans setnodekey(L, mp, key); 683*0495ed39SKyle Evans luaC_barrierback(L, obj2gco(t), key); 684*0495ed39SKyle Evans lua_assert(isempty(gval(mp))); 6858e3e3a7aSWarner Losh return gval(mp); 6868e3e3a7aSWarner Losh } 6878e3e3a7aSWarner Losh 6888e3e3a7aSWarner Losh 6898e3e3a7aSWarner Losh /* 690*0495ed39SKyle Evans ** Search function for integers. If integer is inside 'alimit', get it 691*0495ed39SKyle Evans ** directly from the array part. Otherwise, if 'alimit' is not equal to 692*0495ed39SKyle Evans ** the real size of the array, key still can be in the array part. In 693*0495ed39SKyle Evans ** this case, try to avoid a call to 'luaH_realasize' when key is just 694*0495ed39SKyle Evans ** one more than the limit (so that it can be incremented without 695*0495ed39SKyle Evans ** changing the real size of the array). 6968e3e3a7aSWarner Losh */ 6978e3e3a7aSWarner Losh const TValue *luaH_getint (Table *t, lua_Integer key) { 698*0495ed39SKyle Evans if (l_castS2U(key) - 1u < t->alimit) /* 'key' in [1, t->alimit]? */ 6998e3e3a7aSWarner Losh return &t->array[key - 1]; 700*0495ed39SKyle Evans else if (!limitequalsasize(t) && /* key still may be in the array part? */ 701*0495ed39SKyle Evans (l_castS2U(key) == t->alimit + 1 || 702*0495ed39SKyle Evans l_castS2U(key) - 1u < luaH_realasize(t))) { 703*0495ed39SKyle Evans t->alimit = cast_uint(key); /* probably '#t' is here now */ 704*0495ed39SKyle Evans return &t->array[key - 1]; 705*0495ed39SKyle Evans } 7068e3e3a7aSWarner Losh else { 7078e3e3a7aSWarner Losh Node *n = hashint(t, key); 7088e3e3a7aSWarner Losh for (;;) { /* check whether 'key' is somewhere in the chain */ 709*0495ed39SKyle Evans if (keyisinteger(n) && keyival(n) == key) 7108e3e3a7aSWarner Losh return gval(n); /* that's it */ 7118e3e3a7aSWarner Losh else { 7128e3e3a7aSWarner Losh int nx = gnext(n); 7138e3e3a7aSWarner Losh if (nx == 0) break; 7148e3e3a7aSWarner Losh n += nx; 7158e3e3a7aSWarner Losh } 7168e3e3a7aSWarner Losh } 717*0495ed39SKyle Evans return &absentkey; 7188e3e3a7aSWarner Losh } 7198e3e3a7aSWarner Losh } 7208e3e3a7aSWarner Losh 7218e3e3a7aSWarner Losh 7228e3e3a7aSWarner Losh /* 7238e3e3a7aSWarner Losh ** search function for short strings 7248e3e3a7aSWarner Losh */ 7258e3e3a7aSWarner Losh const TValue *luaH_getshortstr (Table *t, TString *key) { 7268e3e3a7aSWarner Losh Node *n = hashstr(t, key); 727*0495ed39SKyle Evans lua_assert(key->tt == LUA_VSHRSTR); 7288e3e3a7aSWarner Losh for (;;) { /* check whether 'key' is somewhere in the chain */ 729*0495ed39SKyle Evans if (keyisshrstr(n) && eqshrstr(keystrval(n), key)) 7308e3e3a7aSWarner Losh return gval(n); /* that's it */ 7318e3e3a7aSWarner Losh else { 7328e3e3a7aSWarner Losh int nx = gnext(n); 7338e3e3a7aSWarner Losh if (nx == 0) 734*0495ed39SKyle Evans return &absentkey; /* not found */ 7358e3e3a7aSWarner Losh n += nx; 7368e3e3a7aSWarner Losh } 7378e3e3a7aSWarner Losh } 7388e3e3a7aSWarner Losh } 7398e3e3a7aSWarner Losh 7408e3e3a7aSWarner Losh 7418e3e3a7aSWarner Losh const TValue *luaH_getstr (Table *t, TString *key) { 742*0495ed39SKyle Evans if (key->tt == LUA_VSHRSTR) 7438e3e3a7aSWarner Losh return luaH_getshortstr(t, key); 7448e3e3a7aSWarner Losh else { /* for long strings, use generic case */ 7458e3e3a7aSWarner Losh TValue ko; 7468e3e3a7aSWarner Losh setsvalue(cast(lua_State *, NULL), &ko, key); 747*0495ed39SKyle Evans return getgeneric(t, &ko, 0); 7488e3e3a7aSWarner Losh } 7498e3e3a7aSWarner Losh } 7508e3e3a7aSWarner Losh 7518e3e3a7aSWarner Losh 7528e3e3a7aSWarner Losh /* 7538e3e3a7aSWarner Losh ** main search function 7548e3e3a7aSWarner Losh */ 7558e3e3a7aSWarner Losh const TValue *luaH_get (Table *t, const TValue *key) { 756*0495ed39SKyle Evans switch (ttypetag(key)) { 757*0495ed39SKyle Evans case LUA_VSHRSTR: return luaH_getshortstr(t, tsvalue(key)); 758*0495ed39SKyle Evans case LUA_VNUMINT: return luaH_getint(t, ivalue(key)); 759*0495ed39SKyle Evans case LUA_VNIL: return &absentkey; 760*0495ed39SKyle Evans case LUA_VNUMFLT: { 7618e3e3a7aSWarner Losh lua_Integer k; 762*0495ed39SKyle Evans if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */ 7638e3e3a7aSWarner Losh return luaH_getint(t, k); /* use specialized version */ 7648e3e3a7aSWarner Losh /* else... */ 7658e3e3a7aSWarner Losh } /* FALLTHROUGH */ 7668e3e3a7aSWarner Losh default: 767*0495ed39SKyle Evans return getgeneric(t, key, 0); 7688e3e3a7aSWarner Losh } 7698e3e3a7aSWarner Losh } 7708e3e3a7aSWarner Losh 7718e3e3a7aSWarner Losh 7728e3e3a7aSWarner Losh /* 7738e3e3a7aSWarner Losh ** beware: when using this function you probably need to check a GC 7748e3e3a7aSWarner Losh ** barrier and invalidate the TM cache. 7758e3e3a7aSWarner Losh */ 7768e3e3a7aSWarner Losh TValue *luaH_set (lua_State *L, Table *t, const TValue *key) { 7778e3e3a7aSWarner Losh const TValue *p = luaH_get(t, key); 778*0495ed39SKyle Evans if (!isabstkey(p)) 7798e3e3a7aSWarner Losh return cast(TValue *, p); 7808e3e3a7aSWarner Losh else return luaH_newkey(L, t, key); 7818e3e3a7aSWarner Losh } 7828e3e3a7aSWarner Losh 7838e3e3a7aSWarner Losh 7848e3e3a7aSWarner Losh void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { 7858e3e3a7aSWarner Losh const TValue *p = luaH_getint(t, key); 7868e3e3a7aSWarner Losh TValue *cell; 787*0495ed39SKyle Evans if (!isabstkey(p)) 7888e3e3a7aSWarner Losh cell = cast(TValue *, p); 7898e3e3a7aSWarner Losh else { 7908e3e3a7aSWarner Losh TValue k; 7918e3e3a7aSWarner Losh setivalue(&k, key); 7928e3e3a7aSWarner Losh cell = luaH_newkey(L, t, &k); 7938e3e3a7aSWarner Losh } 7948e3e3a7aSWarner Losh setobj2t(L, cell, value); 7958e3e3a7aSWarner Losh } 7968e3e3a7aSWarner Losh 7978e3e3a7aSWarner Losh 798*0495ed39SKyle Evans /* 799*0495ed39SKyle Evans ** Try to find a boundary in the hash part of table 't'. From the 800*0495ed39SKyle Evans ** caller, we know that 'j' is zero or present and that 'j + 1' is 801*0495ed39SKyle Evans ** present. We want to find a larger key that is absent from the 802*0495ed39SKyle Evans ** table, so that we can do a binary search between the two keys to 803*0495ed39SKyle Evans ** find a boundary. We keep doubling 'j' until we get an absent index. 804*0495ed39SKyle Evans ** If the doubling would overflow, we try LUA_MAXINTEGER. If it is 805*0495ed39SKyle Evans ** absent, we are ready for the binary search. ('j', being max integer, 806*0495ed39SKyle Evans ** is larger or equal to 'i', but it cannot be equal because it is 807*0495ed39SKyle Evans ** absent while 'i' is present; so 'j > i'.) Otherwise, 'j' is a 808*0495ed39SKyle Evans ** boundary. ('j + 1' cannot be a present integer key because it is 809*0495ed39SKyle Evans ** not a valid integer in Lua.) 810*0495ed39SKyle Evans */ 811*0495ed39SKyle Evans static lua_Unsigned hash_search (Table *t, lua_Unsigned j) { 812*0495ed39SKyle Evans lua_Unsigned i; 813*0495ed39SKyle Evans if (j == 0) j++; /* the caller ensures 'j + 1' is present */ 814*0495ed39SKyle Evans do { 815*0495ed39SKyle Evans i = j; /* 'i' is a present index */ 816*0495ed39SKyle Evans if (j <= l_castS2U(LUA_MAXINTEGER) / 2) 8178e3e3a7aSWarner Losh j *= 2; 818*0495ed39SKyle Evans else { 819*0495ed39SKyle Evans j = LUA_MAXINTEGER; 820*0495ed39SKyle Evans if (isempty(luaH_getint(t, j))) /* t[j] not present? */ 821*0495ed39SKyle Evans break; /* 'j' now is an absent index */ 822*0495ed39SKyle Evans else /* weird case */ 823*0495ed39SKyle Evans return j; /* well, max integer is a boundary... */ 8248e3e3a7aSWarner Losh } 825*0495ed39SKyle Evans } while (!isempty(luaH_getint(t, j))); /* repeat until an absent t[j] */ 826*0495ed39SKyle Evans /* i < j && t[i] present && t[j] absent */ 827*0495ed39SKyle Evans while (j - i > 1u) { /* do a binary search between them */ 828e112e9d2SKyle Evans lua_Unsigned m = (i + j) / 2; 829*0495ed39SKyle Evans if (isempty(luaH_getint(t, m))) j = m; 830*0495ed39SKyle Evans else i = m; 831*0495ed39SKyle Evans } 832*0495ed39SKyle Evans return i; 833*0495ed39SKyle Evans } 834*0495ed39SKyle Evans 835*0495ed39SKyle Evans 836*0495ed39SKyle Evans static unsigned int binsearch (const TValue *array, unsigned int i, 837*0495ed39SKyle Evans unsigned int j) { 838*0495ed39SKyle Evans while (j - i > 1u) { /* binary search */ 839*0495ed39SKyle Evans unsigned int m = (i + j) / 2; 840*0495ed39SKyle Evans if (isempty(&array[m - 1])) j = m; 8418e3e3a7aSWarner Losh else i = m; 8428e3e3a7aSWarner Losh } 8438e3e3a7aSWarner Losh return i; 8448e3e3a7aSWarner Losh } 8458e3e3a7aSWarner Losh 8468e3e3a7aSWarner Losh 8478e3e3a7aSWarner Losh /* 848*0495ed39SKyle Evans ** Try to find a boundary in table 't'. (A 'boundary' is an integer index 849*0495ed39SKyle Evans ** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent 850*0495ed39SKyle Evans ** and 'maxinteger' if t[maxinteger] is present.) 851*0495ed39SKyle Evans ** (In the next explanation, we use Lua indices, that is, with base 1. 852*0495ed39SKyle Evans ** The code itself uses base 0 when indexing the array part of the table.) 853*0495ed39SKyle Evans ** The code starts with 'limit = t->alimit', a position in the array 854*0495ed39SKyle Evans ** part that may be a boundary. 855*0495ed39SKyle Evans ** 856*0495ed39SKyle Evans ** (1) If 't[limit]' is empty, there must be a boundary before it. 857*0495ed39SKyle Evans ** As a common case (e.g., after 't[#t]=nil'), check whether 'limit-1' 858*0495ed39SKyle Evans ** is present. If so, it is a boundary. Otherwise, do a binary search 859*0495ed39SKyle Evans ** between 0 and limit to find a boundary. In both cases, try to 860*0495ed39SKyle Evans ** use this boundary as the new 'alimit', as a hint for the next call. 861*0495ed39SKyle Evans ** 862*0495ed39SKyle Evans ** (2) If 't[limit]' is not empty and the array has more elements 863*0495ed39SKyle Evans ** after 'limit', try to find a boundary there. Again, try first 864*0495ed39SKyle Evans ** the special case (which should be quite frequent) where 'limit+1' 865*0495ed39SKyle Evans ** is empty, so that 'limit' is a boundary. Otherwise, check the 866*0495ed39SKyle Evans ** last element of the array part. If it is empty, there must be a 867*0495ed39SKyle Evans ** boundary between the old limit (present) and the last element 868*0495ed39SKyle Evans ** (absent), which is found with a binary search. (This boundary always 869*0495ed39SKyle Evans ** can be a new limit.) 870*0495ed39SKyle Evans ** 871*0495ed39SKyle Evans ** (3) The last case is when there are no elements in the array part 872*0495ed39SKyle Evans ** (limit == 0) or its last element (the new limit) is present. 873*0495ed39SKyle Evans ** In this case, must check the hash part. If there is no hash part 874*0495ed39SKyle Evans ** or 'limit+1' is absent, 'limit' is a boundary. Otherwise, call 875*0495ed39SKyle Evans ** 'hash_search' to find a boundary in the hash part of the table. 876*0495ed39SKyle Evans ** (In those cases, the boundary is not inside the array part, and 877*0495ed39SKyle Evans ** therefore cannot be used as a new limit.) 8788e3e3a7aSWarner Losh */ 879e112e9d2SKyle Evans lua_Unsigned luaH_getn (Table *t) { 880*0495ed39SKyle Evans unsigned int limit = t->alimit; 881*0495ed39SKyle Evans if (limit > 0 && isempty(&t->array[limit - 1])) { /* (1)? */ 882*0495ed39SKyle Evans /* there must be a boundary before 'limit' */ 883*0495ed39SKyle Evans if (limit >= 2 && !isempty(&t->array[limit - 2])) { 884*0495ed39SKyle Evans /* 'limit - 1' is a boundary; can it be a new limit? */ 885*0495ed39SKyle Evans if (ispow2realasize(t) && !ispow2(limit - 1)) { 886*0495ed39SKyle Evans t->alimit = limit - 1; 887*0495ed39SKyle Evans setnorealasize(t); /* now 'alimit' is not the real size */ 8888e3e3a7aSWarner Losh } 889*0495ed39SKyle Evans return limit - 1; 8908e3e3a7aSWarner Losh } 891*0495ed39SKyle Evans else { /* must search for a boundary in [0, limit] */ 892*0495ed39SKyle Evans unsigned int boundary = binsearch(t->array, 0, limit); 893*0495ed39SKyle Evans /* can this boundary represent the real size of the array? */ 894*0495ed39SKyle Evans if (ispow2realasize(t) && boundary > luaH_realasize(t) / 2) { 895*0495ed39SKyle Evans t->alimit = boundary; /* use it as the new limit */ 896*0495ed39SKyle Evans setnorealasize(t); 897*0495ed39SKyle Evans } 898*0495ed39SKyle Evans return boundary; 899*0495ed39SKyle Evans } 900*0495ed39SKyle Evans } 901*0495ed39SKyle Evans /* 'limit' is zero or present in table */ 902*0495ed39SKyle Evans if (!limitequalsasize(t)) { /* (2)? */ 903*0495ed39SKyle Evans /* 'limit' > 0 and array has more elements after 'limit' */ 904*0495ed39SKyle Evans if (isempty(&t->array[limit])) /* 'limit + 1' is empty? */ 905*0495ed39SKyle Evans return limit; /* this is the boundary */ 906*0495ed39SKyle Evans /* else, try last element in the array */ 907*0495ed39SKyle Evans limit = luaH_realasize(t); 908*0495ed39SKyle Evans if (isempty(&t->array[limit - 1])) { /* empty? */ 909*0495ed39SKyle Evans /* there must be a boundary in the array after old limit, 910*0495ed39SKyle Evans and it must be a valid new limit */ 911*0495ed39SKyle Evans unsigned int boundary = binsearch(t->array, t->alimit, limit); 912*0495ed39SKyle Evans t->alimit = boundary; 913*0495ed39SKyle Evans return boundary; 914*0495ed39SKyle Evans } 915*0495ed39SKyle Evans /* else, new limit is present in the table; check the hash part */ 916*0495ed39SKyle Evans } 917*0495ed39SKyle Evans /* (3) 'limit' is the last element and either is zero or present in table */ 918*0495ed39SKyle Evans lua_assert(limit == luaH_realasize(t) && 919*0495ed39SKyle Evans (limit == 0 || !isempty(&t->array[limit - 1]))); 920*0495ed39SKyle Evans if (isdummy(t) || isempty(luaH_getint(t, cast(lua_Integer, limit + 1)))) 921*0495ed39SKyle Evans return limit; /* 'limit + 1' is absent */ 922*0495ed39SKyle Evans else /* 'limit + 1' is also present */ 923*0495ed39SKyle Evans return hash_search(t, limit); 9248e3e3a7aSWarner Losh } 9258e3e3a7aSWarner Losh 9268e3e3a7aSWarner Losh 9278e3e3a7aSWarner Losh 9288e3e3a7aSWarner Losh #if defined(LUA_DEBUG) 9298e3e3a7aSWarner Losh 930*0495ed39SKyle Evans /* export these functions for the test library */ 931*0495ed39SKyle Evans 9328e3e3a7aSWarner Losh Node *luaH_mainposition (const Table *t, const TValue *key) { 933*0495ed39SKyle Evans return mainpositionTV(t, key); 9348e3e3a7aSWarner Losh } 9358e3e3a7aSWarner Losh 9368e3e3a7aSWarner Losh int luaH_isdummy (const Table *t) { return isdummy(t); } 9378e3e3a7aSWarner Losh 9388e3e3a7aSWarner Losh #endif 939