1 /* 2 ** $Id: ltable.c $ 3 ** Lua tables (hash) 4 ** See Copyright Notice in lua.h 5 */ 6 7 #define ltable_c 8 #define LUA_CORE 9 10 #include "lprefix.h" 11 12 13 /* 14 ** Implementation of tables (aka arrays, objects, or hash tables). 15 ** Tables keep its elements in two parts: an array part and a hash part. 16 ** Non-negative integer keys are all candidates to be kept in the array 17 ** part. The actual size of the array is the largest 'n' such that 18 ** more than half the slots between 1 and n are in use. 19 ** Hash uses a mix of chained scatter table with Brent's variation. 20 ** A main invariant of these tables is that, if an element is not 21 ** in its main position (i.e. the 'original' position that its hash gives 22 ** to it), then the colliding element is in its own main position. 23 ** Hence even when the load factor reaches 100%, performance remains good. 24 */ 25 26 #include <math.h> 27 #include <limits.h> 28 29 #include "lua.h" 30 31 #include "ldebug.h" 32 #include "ldo.h" 33 #include "lgc.h" 34 #include "lmem.h" 35 #include "lobject.h" 36 #include "lstate.h" 37 #include "lstring.h" 38 #include "ltable.h" 39 #include "lvm.h" 40 41 42 /* 43 ** MAXABITS is the largest integer such that MAXASIZE fits in an 44 ** unsigned int. 45 */ 46 #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1) 47 48 49 /* 50 ** MAXASIZE is the maximum size of the array part. It is the minimum 51 ** between 2^MAXABITS and the maximum size that, measured in bytes, 52 ** fits in a 'size_t'. 53 */ 54 #define MAXASIZE luaM_limitN(1u << MAXABITS, TValue) 55 56 /* 57 ** MAXHBITS is the largest integer such that 2^MAXHBITS fits in a 58 ** signed int. 59 */ 60 #define MAXHBITS (MAXABITS - 1) 61 62 63 /* 64 ** MAXHSIZE is the maximum size of the hash part. It is the minimum 65 ** between 2^MAXHBITS and the maximum size such that, measured in bytes, 66 ** it fits in a 'size_t'. 67 */ 68 #define MAXHSIZE luaM_limitN(1u << MAXHBITS, Node) 69 70 71 /* 72 ** When the original hash value is good, hashing by a power of 2 73 ** avoids the cost of '%'. 74 */ 75 #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) 76 77 /* 78 ** for other types, it is better to avoid modulo by power of 2, as 79 ** they can have many 2 factors. 80 */ 81 #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) 82 83 84 #define hashstr(t,str) hashpow2(t, (str)->hash) 85 #define hashboolean(t,p) hashpow2(t, p) 86 87 88 #define hashpointer(t,p) hashmod(t, point2uint(p)) 89 90 91 #define dummynode (&dummynode_) 92 93 static const Node dummynode_ = { 94 {{NULL}, LUA_VEMPTY, /* value's value and type */ 95 LUA_VNIL, 0, {NULL}} /* key type, next, and key value */ 96 }; 97 98 99 static const TValue absentkey = {ABSTKEYCONSTANT}; 100 101 102 /* 103 ** Hash for integers. To allow a good hash, use the remainder operator 104 ** ('%'). If integer fits as a non-negative int, compute an int 105 ** remainder, which is faster. Otherwise, use an unsigned-integer 106 ** remainder, which uses all bits and ensures a non-negative result. 107 */ 108 static Node *hashint (const Table *t, lua_Integer i) { 109 lua_Unsigned ui = l_castS2U(i); 110 if (ui <= (unsigned int)INT_MAX) 111 return hashmod(t, cast_int(ui)); 112 else 113 return hashmod(t, ui); 114 } 115 116 117 /* 118 ** Hash for floating-point numbers. 119 ** The main computation should be just 120 ** n = frexp(n, &i); return (n * INT_MAX) + i 121 ** but there are some numerical subtleties. 122 ** In a two-complement representation, INT_MAX does not has an exact 123 ** representation as a float, but INT_MIN does; because the absolute 124 ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the 125 ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal 126 ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when 127 ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with 128 ** INT_MIN. 129 */ 130 #if !defined(l_hashfloat) 131 static int l_hashfloat (lua_Number n) { 132 int i; 133 lua_Integer ni; 134 n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN); 135 if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */ 136 lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL)); 137 return 0; 138 } 139 else { /* normal case */ 140 unsigned int u = cast_uint(i) + cast_uint(ni); 141 return cast_int(u <= cast_uint(INT_MAX) ? u : ~u); 142 } 143 } 144 #endif 145 146 147 /* 148 ** returns the 'main' position of an element in a table (that is, 149 ** the index of its hash value). 150 */ 151 static Node *mainpositionTV (const Table *t, const TValue *key) { 152 switch (ttypetag(key)) { 153 case LUA_VNUMINT: { 154 lua_Integer i = ivalue(key); 155 return hashint(t, i); 156 } 157 case LUA_VNUMFLT: { 158 lua_Number n = fltvalue(key); 159 return hashmod(t, l_hashfloat(n)); 160 } 161 case LUA_VSHRSTR: { 162 TString *ts = tsvalue(key); 163 return hashstr(t, ts); 164 } 165 case LUA_VLNGSTR: { 166 TString *ts = tsvalue(key); 167 return hashpow2(t, luaS_hashlongstr(ts)); 168 } 169 case LUA_VFALSE: 170 return hashboolean(t, 0); 171 case LUA_VTRUE: 172 return hashboolean(t, 1); 173 case LUA_VLIGHTUSERDATA: { 174 void *p = pvalue(key); 175 return hashpointer(t, p); 176 } 177 case LUA_VLCF: { 178 lua_CFunction f = fvalue(key); 179 return hashpointer(t, f); 180 } 181 default: { 182 GCObject *o = gcvalue(key); 183 return hashpointer(t, o); 184 } 185 } 186 } 187 188 189 l_sinline Node *mainpositionfromnode (const Table *t, Node *nd) { 190 TValue key; 191 getnodekey(cast(lua_State *, NULL), &key, nd); 192 return mainpositionTV(t, &key); 193 } 194 195 196 /* 197 ** Check whether key 'k1' is equal to the key in node 'n2'. This 198 ** equality is raw, so there are no metamethods. Floats with integer 199 ** values have been normalized, so integers cannot be equal to 200 ** floats. It is assumed that 'eqshrstr' is simply pointer equality, so 201 ** that short strings are handled in the default case. 202 ** A true 'deadok' means to accept dead keys as equal to their original 203 ** values. All dead keys are compared in the default case, by pointer 204 ** identity. (Only collectable objects can produce dead keys.) Note that 205 ** dead long strings are also compared by identity. 206 ** Once a key is dead, its corresponding value may be collected, and 207 ** then another value can be created with the same address. If this 208 ** other value is given to 'next', 'equalkey' will signal a false 209 ** positive. In a regular traversal, this situation should never happen, 210 ** as all keys given to 'next' came from the table itself, and therefore 211 ** could not have been collected. Outside a regular traversal, we 212 ** have garbage in, garbage out. What is relevant is that this false 213 ** positive does not break anything. (In particular, 'next' will return 214 ** some other valid item on the table or nil.) 215 */ 216 static int equalkey (const TValue *k1, const Node *n2, int deadok) { 217 if ((rawtt(k1) != keytt(n2)) && /* not the same variants? */ 218 !(deadok && keyisdead(n2) && iscollectable(k1))) 219 return 0; /* cannot be same key */ 220 switch (keytt(n2)) { 221 case LUA_VNIL: case LUA_VFALSE: case LUA_VTRUE: 222 return 1; 223 case LUA_VNUMINT: 224 return (ivalue(k1) == keyival(n2)); 225 case LUA_VNUMFLT: 226 return luai_numeq(fltvalue(k1), fltvalueraw(keyval(n2))); 227 case LUA_VLIGHTUSERDATA: 228 return pvalue(k1) == pvalueraw(keyval(n2)); 229 case LUA_VLCF: 230 return fvalue(k1) == fvalueraw(keyval(n2)); 231 case ctb(LUA_VLNGSTR): 232 return luaS_eqlngstr(tsvalue(k1), keystrval(n2)); 233 default: 234 return gcvalue(k1) == gcvalueraw(keyval(n2)); 235 } 236 } 237 238 239 /* 240 ** True if value of 'alimit' is equal to the real size of the array 241 ** part of table 't'. (Otherwise, the array part must be larger than 242 ** 'alimit'.) 243 */ 244 #define limitequalsasize(t) (isrealasize(t) || ispow2((t)->alimit)) 245 246 247 /* 248 ** Returns the real size of the 'array' array 249 */ 250 LUAI_FUNC unsigned int luaH_realasize (const Table *t) { 251 if (limitequalsasize(t)) 252 return t->alimit; /* this is the size */ 253 else { 254 unsigned int size = t->alimit; 255 /* compute the smallest power of 2 not smaller than 'n' */ 256 size |= (size >> 1); 257 size |= (size >> 2); 258 size |= (size >> 4); 259 size |= (size >> 8); 260 size |= (size >> 16); 261 #if (UINT_MAX >> 30) > 3 262 size |= (size >> 32); /* unsigned int has more than 32 bits */ 263 #endif 264 size++; 265 lua_assert(ispow2(size) && size/2 < t->alimit && t->alimit < size); 266 return size; 267 } 268 } 269 270 271 /* 272 ** Check whether real size of the array is a power of 2. 273 ** (If it is not, 'alimit' cannot be changed to any other value 274 ** without changing the real size.) 275 */ 276 static int ispow2realasize (const Table *t) { 277 return (!isrealasize(t) || ispow2(t->alimit)); 278 } 279 280 281 static unsigned int setlimittosize (Table *t) { 282 t->alimit = luaH_realasize(t); 283 setrealasize(t); 284 return t->alimit; 285 } 286 287 288 #define limitasasize(t) check_exp(isrealasize(t), t->alimit) 289 290 291 292 /* 293 ** "Generic" get version. (Not that generic: not valid for integers, 294 ** which may be in array part, nor for floats with integral values.) 295 ** See explanation about 'deadok' in function 'equalkey'. 296 */ 297 static const TValue *getgeneric (Table *t, const TValue *key, int deadok) { 298 Node *n = mainpositionTV(t, key); 299 for (;;) { /* check whether 'key' is somewhere in the chain */ 300 if (equalkey(key, n, deadok)) 301 return gval(n); /* that's it */ 302 else { 303 int nx = gnext(n); 304 if (nx == 0) 305 return &absentkey; /* not found */ 306 n += nx; 307 } 308 } 309 } 310 311 312 /* 313 ** returns the index for 'k' if 'k' is an appropriate key to live in 314 ** the array part of a table, 0 otherwise. 315 */ 316 static unsigned int arrayindex (lua_Integer k) { 317 if (l_castS2U(k) - 1u < MAXASIZE) /* 'k' in [1, MAXASIZE]? */ 318 return cast_uint(k); /* 'key' is an appropriate array index */ 319 else 320 return 0; 321 } 322 323 324 /* 325 ** returns the index of a 'key' for table traversals. First goes all 326 ** elements in the array part, then elements in the hash part. The 327 ** beginning of a traversal is signaled by 0. 328 */ 329 static unsigned int findindex (lua_State *L, Table *t, TValue *key, 330 unsigned int asize) { 331 unsigned int i; 332 if (ttisnil(key)) return 0; /* first iteration */ 333 i = ttisinteger(key) ? arrayindex(ivalue(key)) : 0; 334 if (i - 1u < asize) /* is 'key' inside array part? */ 335 return i; /* yes; that's the index */ 336 else { 337 const TValue *n = getgeneric(t, key, 1); 338 if (l_unlikely(isabstkey(n))) 339 luaG_runerror(L, "invalid key to 'next'"); /* key not found */ 340 i = cast_int(nodefromval(n) - gnode(t, 0)); /* key index in hash table */ 341 /* hash elements are numbered after array ones */ 342 return (i + 1) + asize; 343 } 344 } 345 346 347 int luaH_next (lua_State *L, Table *t, StkId key) { 348 unsigned int asize = luaH_realasize(t); 349 unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */ 350 for (; i < asize; i++) { /* try first array part */ 351 if (!isempty(&t->array[i])) { /* a non-empty entry? */ 352 setivalue(s2v(key), i + 1); 353 setobj2s(L, key + 1, &t->array[i]); 354 return 1; 355 } 356 } 357 for (i -= asize; cast_int(i) < sizenode(t); i++) { /* hash part */ 358 if (!isempty(gval(gnode(t, i)))) { /* a non-empty entry? */ 359 Node *n = gnode(t, i); 360 getnodekey(L, s2v(key), n); 361 setobj2s(L, key + 1, gval(n)); 362 return 1; 363 } 364 } 365 return 0; /* no more elements */ 366 } 367 368 369 static void freehash (lua_State *L, Table *t) { 370 if (!isdummy(t)) 371 luaM_freearray(L, t->node, cast_sizet(sizenode(t))); 372 } 373 374 375 /* 376 ** {============================================================= 377 ** Rehash 378 ** ============================================================== 379 */ 380 381 /* 382 ** Compute the optimal size for the array part of table 't'. 'nums' is a 383 ** "count array" where 'nums[i]' is the number of integers in the table 384 ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of 385 ** integer keys in the table and leaves with the number of keys that 386 ** will go to the array part; return the optimal size. (The condition 387 ** 'twotoi > 0' in the for loop stops the loop if 'twotoi' overflows.) 388 */ 389 static unsigned int computesizes (unsigned int nums[], unsigned int *pna) { 390 int i; 391 unsigned int twotoi; /* 2^i (candidate for optimal size) */ 392 unsigned int a = 0; /* number of elements smaller than 2^i */ 393 unsigned int na = 0; /* number of elements to go to array part */ 394 unsigned int optimal = 0; /* optimal size for array part */ 395 /* loop while keys can fill more than half of total size */ 396 for (i = 0, twotoi = 1; 397 twotoi > 0 && *pna > twotoi / 2; 398 i++, twotoi *= 2) { 399 a += nums[i]; 400 if (a > twotoi/2) { /* more than half elements present? */ 401 optimal = twotoi; /* optimal size (till now) */ 402 na = a; /* all elements up to 'optimal' will go to array part */ 403 } 404 } 405 lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal); 406 *pna = na; 407 return optimal; 408 } 409 410 411 static int countint (lua_Integer key, unsigned int *nums) { 412 unsigned int k = arrayindex(key); 413 if (k != 0) { /* is 'key' an appropriate array index? */ 414 nums[luaO_ceillog2(k)]++; /* count as such */ 415 return 1; 416 } 417 else 418 return 0; 419 } 420 421 422 /* 423 ** Count keys in array part of table 't': Fill 'nums[i]' with 424 ** number of keys that will go into corresponding slice and return 425 ** total number of non-nil keys. 426 */ 427 static unsigned int numusearray (const Table *t, unsigned int *nums) { 428 int lg; 429 unsigned int ttlg; /* 2^lg */ 430 unsigned int ause = 0; /* summation of 'nums' */ 431 unsigned int i = 1; /* count to traverse all array keys */ 432 unsigned int asize = limitasasize(t); /* real array size */ 433 /* traverse each slice */ 434 for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { 435 unsigned int lc = 0; /* counter */ 436 unsigned int lim = ttlg; 437 if (lim > asize) { 438 lim = asize; /* adjust upper limit */ 439 if (i > lim) 440 break; /* no more elements to count */ 441 } 442 /* count elements in range (2^(lg - 1), 2^lg] */ 443 for (; i <= lim; i++) { 444 if (!isempty(&t->array[i-1])) 445 lc++; 446 } 447 nums[lg] += lc; 448 ause += lc; 449 } 450 return ause; 451 } 452 453 454 static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) { 455 int totaluse = 0; /* total number of elements */ 456 int ause = 0; /* elements added to 'nums' (can go to array part) */ 457 int i = sizenode(t); 458 while (i--) { 459 Node *n = &t->node[i]; 460 if (!isempty(gval(n))) { 461 if (keyisinteger(n)) 462 ause += countint(keyival(n), nums); 463 totaluse++; 464 } 465 } 466 *pna += ause; 467 return totaluse; 468 } 469 470 471 /* 472 ** Creates an array for the hash part of a table with the given 473 ** size, or reuses the dummy node if size is zero. 474 ** The computation for size overflow is in two steps: the first 475 ** comparison ensures that the shift in the second one does not 476 ** overflow. 477 */ 478 static void setnodevector (lua_State *L, Table *t, unsigned int size) { 479 if (size == 0) { /* no elements to hash part? */ 480 t->node = cast(Node *, dummynode); /* use common 'dummynode' */ 481 t->lsizenode = 0; 482 t->lastfree = NULL; /* signal that it is using dummy node */ 483 } 484 else { 485 int i; 486 int lsize = luaO_ceillog2(size); 487 if (lsize > MAXHBITS || (1u << lsize) > MAXHSIZE) 488 luaG_runerror(L, "table overflow"); 489 size = twoto(lsize); 490 t->node = luaM_newvector(L, size, Node); 491 for (i = 0; i < (int)size; i++) { 492 Node *n = gnode(t, i); 493 gnext(n) = 0; 494 setnilkey(n); 495 setempty(gval(n)); 496 } 497 t->lsizenode = cast_byte(lsize); 498 t->lastfree = gnode(t, size); /* all positions are free */ 499 } 500 } 501 502 503 /* 504 ** (Re)insert all elements from the hash part of 'ot' into table 't'. 505 */ 506 static void reinsert (lua_State *L, Table *ot, Table *t) { 507 int j; 508 int size = sizenode(ot); 509 for (j = 0; j < size; j++) { 510 Node *old = gnode(ot, j); 511 if (!isempty(gval(old))) { 512 /* doesn't need barrier/invalidate cache, as entry was 513 already present in the table */ 514 TValue k; 515 getnodekey(L, &k, old); 516 luaH_set(L, t, &k, gval(old)); 517 } 518 } 519 } 520 521 522 /* 523 ** Exchange the hash part of 't1' and 't2'. 524 */ 525 static void exchangehashpart (Table *t1, Table *t2) { 526 lu_byte lsizenode = t1->lsizenode; 527 Node *node = t1->node; 528 Node *lastfree = t1->lastfree; 529 t1->lsizenode = t2->lsizenode; 530 t1->node = t2->node; 531 t1->lastfree = t2->lastfree; 532 t2->lsizenode = lsizenode; 533 t2->node = node; 534 t2->lastfree = lastfree; 535 } 536 537 538 /* 539 ** Resize table 't' for the new given sizes. Both allocations (for 540 ** the hash part and for the array part) can fail, which creates some 541 ** subtleties. If the first allocation, for the hash part, fails, an 542 ** error is raised and that is it. Otherwise, it copies the elements from 543 ** the shrinking part of the array (if it is shrinking) into the new 544 ** hash. Then it reallocates the array part. If that fails, the table 545 ** is in its original state; the function frees the new hash part and then 546 ** raises the allocation error. Otherwise, it sets the new hash part 547 ** into the table, initializes the new part of the array (if any) with 548 ** nils and reinserts the elements of the old hash back into the new 549 ** parts of the table. 550 */ 551 void luaH_resize (lua_State *L, Table *t, unsigned int newasize, 552 unsigned int nhsize) { 553 unsigned int i; 554 Table newt; /* to keep the new hash part */ 555 unsigned int oldasize = setlimittosize(t); 556 TValue *newarray; 557 /* create new hash part with appropriate size into 'newt' */ 558 setnodevector(L, &newt, nhsize); 559 if (newasize < oldasize) { /* will array shrink? */ 560 t->alimit = newasize; /* pretend array has new size... */ 561 exchangehashpart(t, &newt); /* and new hash */ 562 /* re-insert into the new hash the elements from vanishing slice */ 563 for (i = newasize; i < oldasize; i++) { 564 if (!isempty(&t->array[i])) 565 luaH_setint(L, t, i + 1, &t->array[i]); 566 } 567 t->alimit = oldasize; /* restore current size... */ 568 exchangehashpart(t, &newt); /* and hash (in case of errors) */ 569 } 570 /* allocate new array */ 571 newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue); 572 if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ 573 freehash(L, &newt); /* release new hash part */ 574 luaM_error(L); /* raise error (with array unchanged) */ 575 } 576 /* allocation ok; initialize new part of the array */ 577 exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */ 578 t->array = newarray; /* set new array part */ 579 t->alimit = newasize; 580 for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ 581 setempty(&t->array[i]); 582 /* re-insert elements from old hash part into new parts */ 583 reinsert(L, &newt, t); /* 'newt' now has the old hash */ 584 freehash(L, &newt); /* free old hash part */ 585 } 586 587 588 void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) { 589 int nsize = allocsizenode(t); 590 luaH_resize(L, t, nasize, nsize); 591 } 592 593 /* 594 ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i 595 */ 596 static void rehash (lua_State *L, Table *t, const TValue *ek) { 597 unsigned int asize; /* optimal size for array part */ 598 unsigned int na; /* number of keys in the array part */ 599 unsigned int nums[MAXABITS + 1]; 600 int i; 601 int totaluse; 602 for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */ 603 setlimittosize(t); 604 na = numusearray(t, nums); /* count keys in array part */ 605 totaluse = na; /* all those keys are integer keys */ 606 totaluse += numusehash(t, nums, &na); /* count keys in hash part */ 607 /* count extra key */ 608 if (ttisinteger(ek)) 609 na += countint(ivalue(ek), nums); 610 totaluse++; 611 /* compute new size for array part */ 612 asize = computesizes(nums, &na); 613 /* resize the table to new computed sizes */ 614 luaH_resize(L, t, asize, totaluse - na); 615 } 616 617 618 619 /* 620 ** }============================================================= 621 */ 622 623 624 Table *luaH_new (lua_State *L) { 625 GCObject *o = luaC_newobj(L, LUA_VTABLE, sizeof(Table)); 626 Table *t = gco2t(o); 627 t->metatable = NULL; 628 t->flags = cast_byte(maskflags); /* table has no metamethod fields */ 629 t->array = NULL; 630 t->alimit = 0; 631 setnodevector(L, t, 0); 632 return t; 633 } 634 635 636 void luaH_free (lua_State *L, Table *t) { 637 freehash(L, t); 638 luaM_freearray(L, t->array, luaH_realasize(t)); 639 luaM_free(L, t); 640 } 641 642 643 static Node *getfreepos (Table *t) { 644 if (!isdummy(t)) { 645 while (t->lastfree > t->node) { 646 t->lastfree--; 647 if (keyisnil(t->lastfree)) 648 return t->lastfree; 649 } 650 } 651 return NULL; /* could not find a free place */ 652 } 653 654 655 656 /* 657 ** inserts a new key into a hash table; first, check whether key's main 658 ** position is free. If not, check whether colliding node is in its main 659 ** position or not: if it is not, move colliding node to an empty place and 660 ** put new key in its main position; otherwise (colliding node is in its main 661 ** position), new key goes to an empty position. 662 */ 663 void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value) { 664 Node *mp; 665 TValue aux; 666 if (l_unlikely(ttisnil(key))) 667 luaG_runerror(L, "table index is nil"); 668 else if (ttisfloat(key)) { 669 lua_Number f = fltvalue(key); 670 lua_Integer k; 671 if (luaV_flttointeger(f, &k, F2Ieq)) { /* does key fit in an integer? */ 672 setivalue(&aux, k); 673 key = &aux; /* insert it as an integer */ 674 } 675 else if (l_unlikely(luai_numisnan(f))) 676 luaG_runerror(L, "table index is NaN"); 677 } 678 if (ttisnil(value)) 679 return; /* do not insert nil values */ 680 mp = mainpositionTV(t, key); 681 if (!isempty(gval(mp)) || isdummy(t)) { /* main position is taken? */ 682 Node *othern; 683 Node *f = getfreepos(t); /* get a free place */ 684 if (f == NULL) { /* cannot find a free place? */ 685 rehash(L, t, key); /* grow table */ 686 /* whatever called 'newkey' takes care of TM cache */ 687 luaH_set(L, t, key, value); /* insert key into grown table */ 688 return; 689 } 690 lua_assert(!isdummy(t)); 691 othern = mainpositionfromnode(t, mp); 692 if (othern != mp) { /* is colliding node out of its main position? */ 693 /* yes; move colliding node into free position */ 694 while (othern + gnext(othern) != mp) /* find previous */ 695 othern += gnext(othern); 696 gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */ 697 *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */ 698 if (gnext(mp) != 0) { 699 gnext(f) += cast_int(mp - f); /* correct 'next' */ 700 gnext(mp) = 0; /* now 'mp' is free */ 701 } 702 setempty(gval(mp)); 703 } 704 else { /* colliding node is in its own main position */ 705 /* new node will go into free position */ 706 if (gnext(mp) != 0) 707 gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */ 708 else lua_assert(gnext(f) == 0); 709 gnext(mp) = cast_int(f - mp); 710 mp = f; 711 } 712 } 713 setnodekey(L, mp, key); 714 luaC_barrierback(L, obj2gco(t), key); 715 lua_assert(isempty(gval(mp))); 716 setobj2t(L, gval(mp), value); 717 } 718 719 720 /* 721 ** Search function for integers. If integer is inside 'alimit', get it 722 ** directly from the array part. Otherwise, if 'alimit' is not equal to 723 ** the real size of the array, key still can be in the array part. In 724 ** this case, try to avoid a call to 'luaH_realasize' when key is just 725 ** one more than the limit (so that it can be incremented without 726 ** changing the real size of the array). 727 */ 728 const TValue *luaH_getint (Table *t, lua_Integer key) { 729 if (l_castS2U(key) - 1u < t->alimit) /* 'key' in [1, t->alimit]? */ 730 return &t->array[key - 1]; 731 else if (!limitequalsasize(t) && /* key still may be in the array part? */ 732 (l_castS2U(key) == t->alimit + 1 || 733 l_castS2U(key) - 1u < luaH_realasize(t))) { 734 t->alimit = cast_uint(key); /* probably '#t' is here now */ 735 return &t->array[key - 1]; 736 } 737 else { 738 Node *n = hashint(t, key); 739 for (;;) { /* check whether 'key' is somewhere in the chain */ 740 if (keyisinteger(n) && keyival(n) == key) 741 return gval(n); /* that's it */ 742 else { 743 int nx = gnext(n); 744 if (nx == 0) break; 745 n += nx; 746 } 747 } 748 return &absentkey; 749 } 750 } 751 752 753 /* 754 ** search function for short strings 755 */ 756 const TValue *luaH_getshortstr (Table *t, TString *key) { 757 Node *n = hashstr(t, key); 758 lua_assert(key->tt == LUA_VSHRSTR); 759 for (;;) { /* check whether 'key' is somewhere in the chain */ 760 if (keyisshrstr(n) && eqshrstr(keystrval(n), key)) 761 return gval(n); /* that's it */ 762 else { 763 int nx = gnext(n); 764 if (nx == 0) 765 return &absentkey; /* not found */ 766 n += nx; 767 } 768 } 769 } 770 771 772 const TValue *luaH_getstr (Table *t, TString *key) { 773 if (key->tt == LUA_VSHRSTR) 774 return luaH_getshortstr(t, key); 775 else { /* for long strings, use generic case */ 776 TValue ko; 777 setsvalue(cast(lua_State *, NULL), &ko, key); 778 return getgeneric(t, &ko, 0); 779 } 780 } 781 782 783 /* 784 ** main search function 785 */ 786 const TValue *luaH_get (Table *t, const TValue *key) { 787 switch (ttypetag(key)) { 788 case LUA_VSHRSTR: return luaH_getshortstr(t, tsvalue(key)); 789 case LUA_VNUMINT: return luaH_getint(t, ivalue(key)); 790 case LUA_VNIL: return &absentkey; 791 case LUA_VNUMFLT: { 792 lua_Integer k; 793 if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */ 794 return luaH_getint(t, k); /* use specialized version */ 795 /* else... */ 796 } /* FALLTHROUGH */ 797 default: 798 return getgeneric(t, key, 0); 799 } 800 } 801 802 803 /* 804 ** Finish a raw "set table" operation, where 'slot' is where the value 805 ** should have been (the result of a previous "get table"). 806 ** Beware: when using this function you probably need to check a GC 807 ** barrier and invalidate the TM cache. 808 */ 809 void luaH_finishset (lua_State *L, Table *t, const TValue *key, 810 const TValue *slot, TValue *value) { 811 if (isabstkey(slot)) 812 luaH_newkey(L, t, key, value); 813 else 814 setobj2t(L, cast(TValue *, slot), value); 815 } 816 817 818 /* 819 ** beware: when using this function you probably need to check a GC 820 ** barrier and invalidate the TM cache. 821 */ 822 void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) { 823 const TValue *slot = luaH_get(t, key); 824 luaH_finishset(L, t, key, slot, value); 825 } 826 827 828 void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { 829 const TValue *p = luaH_getint(t, key); 830 if (isabstkey(p)) { 831 TValue k; 832 setivalue(&k, key); 833 luaH_newkey(L, t, &k, value); 834 } 835 else 836 setobj2t(L, cast(TValue *, p), value); 837 } 838 839 840 /* 841 ** Try to find a boundary in the hash part of table 't'. From the 842 ** caller, we know that 'j' is zero or present and that 'j + 1' is 843 ** present. We want to find a larger key that is absent from the 844 ** table, so that we can do a binary search between the two keys to 845 ** find a boundary. We keep doubling 'j' until we get an absent index. 846 ** If the doubling would overflow, we try LUA_MAXINTEGER. If it is 847 ** absent, we are ready for the binary search. ('j', being max integer, 848 ** is larger or equal to 'i', but it cannot be equal because it is 849 ** absent while 'i' is present; so 'j > i'.) Otherwise, 'j' is a 850 ** boundary. ('j + 1' cannot be a present integer key because it is 851 ** not a valid integer in Lua.) 852 */ 853 static lua_Unsigned hash_search (Table *t, lua_Unsigned j) { 854 lua_Unsigned i; 855 if (j == 0) j++; /* the caller ensures 'j + 1' is present */ 856 do { 857 i = j; /* 'i' is a present index */ 858 if (j <= l_castS2U(LUA_MAXINTEGER) / 2) 859 j *= 2; 860 else { 861 j = LUA_MAXINTEGER; 862 if (isempty(luaH_getint(t, j))) /* t[j] not present? */ 863 break; /* 'j' now is an absent index */ 864 else /* weird case */ 865 return j; /* well, max integer is a boundary... */ 866 } 867 } while (!isempty(luaH_getint(t, j))); /* repeat until an absent t[j] */ 868 /* i < j && t[i] present && t[j] absent */ 869 while (j - i > 1u) { /* do a binary search between them */ 870 lua_Unsigned m = (i + j) / 2; 871 if (isempty(luaH_getint(t, m))) j = m; 872 else i = m; 873 } 874 return i; 875 } 876 877 878 static unsigned int binsearch (const TValue *array, unsigned int i, 879 unsigned int j) { 880 while (j - i > 1u) { /* binary search */ 881 unsigned int m = (i + j) / 2; 882 if (isempty(&array[m - 1])) j = m; 883 else i = m; 884 } 885 return i; 886 } 887 888 889 /* 890 ** Try to find a boundary in table 't'. (A 'boundary' is an integer index 891 ** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent 892 ** and 'maxinteger' if t[maxinteger] is present.) 893 ** (In the next explanation, we use Lua indices, that is, with base 1. 894 ** The code itself uses base 0 when indexing the array part of the table.) 895 ** The code starts with 'limit = t->alimit', a position in the array 896 ** part that may be a boundary. 897 ** 898 ** (1) If 't[limit]' is empty, there must be a boundary before it. 899 ** As a common case (e.g., after 't[#t]=nil'), check whether 'limit-1' 900 ** is present. If so, it is a boundary. Otherwise, do a binary search 901 ** between 0 and limit to find a boundary. In both cases, try to 902 ** use this boundary as the new 'alimit', as a hint for the next call. 903 ** 904 ** (2) If 't[limit]' is not empty and the array has more elements 905 ** after 'limit', try to find a boundary there. Again, try first 906 ** the special case (which should be quite frequent) where 'limit+1' 907 ** is empty, so that 'limit' is a boundary. Otherwise, check the 908 ** last element of the array part. If it is empty, there must be a 909 ** boundary between the old limit (present) and the last element 910 ** (absent), which is found with a binary search. (This boundary always 911 ** can be a new limit.) 912 ** 913 ** (3) The last case is when there are no elements in the array part 914 ** (limit == 0) or its last element (the new limit) is present. 915 ** In this case, must check the hash part. If there is no hash part 916 ** or 'limit+1' is absent, 'limit' is a boundary. Otherwise, call 917 ** 'hash_search' to find a boundary in the hash part of the table. 918 ** (In those cases, the boundary is not inside the array part, and 919 ** therefore cannot be used as a new limit.) 920 */ 921 lua_Unsigned luaH_getn (Table *t) { 922 unsigned int limit = t->alimit; 923 if (limit > 0 && isempty(&t->array[limit - 1])) { /* (1)? */ 924 /* there must be a boundary before 'limit' */ 925 if (limit >= 2 && !isempty(&t->array[limit - 2])) { 926 /* 'limit - 1' is a boundary; can it be a new limit? */ 927 if (ispow2realasize(t) && !ispow2(limit - 1)) { 928 t->alimit = limit - 1; 929 setnorealasize(t); /* now 'alimit' is not the real size */ 930 } 931 return limit - 1; 932 } 933 else { /* must search for a boundary in [0, limit] */ 934 unsigned int boundary = binsearch(t->array, 0, limit); 935 /* can this boundary represent the real size of the array? */ 936 if (ispow2realasize(t) && boundary > luaH_realasize(t) / 2) { 937 t->alimit = boundary; /* use it as the new limit */ 938 setnorealasize(t); 939 } 940 return boundary; 941 } 942 } 943 /* 'limit' is zero or present in table */ 944 if (!limitequalsasize(t)) { /* (2)? */ 945 /* 'limit' > 0 and array has more elements after 'limit' */ 946 if (isempty(&t->array[limit])) /* 'limit + 1' is empty? */ 947 return limit; /* this is the boundary */ 948 /* else, try last element in the array */ 949 limit = luaH_realasize(t); 950 if (isempty(&t->array[limit - 1])) { /* empty? */ 951 /* there must be a boundary in the array after old limit, 952 and it must be a valid new limit */ 953 unsigned int boundary = binsearch(t->array, t->alimit, limit); 954 t->alimit = boundary; 955 return boundary; 956 } 957 /* else, new limit is present in the table; check the hash part */ 958 } 959 /* (3) 'limit' is the last element and either is zero or present in table */ 960 lua_assert(limit == luaH_realasize(t) && 961 (limit == 0 || !isempty(&t->array[limit - 1]))); 962 if (isdummy(t) || isempty(luaH_getint(t, cast(lua_Integer, limit + 1)))) 963 return limit; /* 'limit + 1' is absent */ 964 else /* 'limit + 1' is also present */ 965 return hash_search(t, limit); 966 } 967 968 969 970 #if defined(LUA_DEBUG) 971 972 /* export these functions for the test library */ 973 974 Node *luaH_mainposition (const Table *t, const TValue *key) { 975 return mainpositionTV(t, key); 976 } 977 978 int luaH_isdummy (const Table *t) { return isdummy(t); } 979 980 #endif 981