diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-11-29 17:26:20 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-11-29 17:26:20 -0300 |
commit | 002beeebe79065e03dd9f531bee367e8459e3f64 (patch) | |
tree | 5b066d30e08950c923c253ce85f702b39fbe9c31 /ltable.c | |
parent | 9329eeac3b7035c223d7a8b63dbde1f6db371bf5 (diff) | |
download | lua-002beeebe79065e03dd9f531bee367e8459e3f64.tar.gz lua-002beeebe79065e03dd9f531bee367e8459e3f64.tar.bz2 lua-002beeebe79065e03dd9f531bee367e8459e3f64.zip |
New way to keep hints for table length
Instead of using 'alimit' for keeping the size of the array and at
the same time being a hint for '#t', a table now keeps these two
values separate. The Table structure has a field 'asize' with the
size of the array, while the length hint is kept in the array itself.
That way, tables with no array part waste no space with that field.
Moreover, the space for the hint may have zero cost for small arrays,
if the array of tags plus the hint still fits in a single word.
Diffstat (limited to 'ltable.c')
-rw-r--r-- | ltable.c | 298 |
1 files changed, 100 insertions, 198 deletions
@@ -41,12 +41,12 @@ | |||
41 | 41 | ||
42 | 42 | ||
43 | /* | 43 | /* |
44 | ** Only tables with hash parts larger than 2^LIMFORLAST has a 'lastfree' | 44 | ** Only hash parts with at least 2^LIMFORLAST have a 'lastfree' field |
45 | ** field that optimizes finding a free slot. That field is stored just | 45 | ** that optimizes finding a free slot. That field is stored just before |
46 | ** before the array of nodes, in the same block. Smaller tables do a | 46 | ** the array of nodes, in the same block. Smaller tables do a complete |
47 | ** complete search when looking for a free slot. | 47 | ** search when looking for a free slot. |
48 | */ | 48 | */ |
49 | #define LIMFORLAST 2 /* log2 of real limit */ | 49 | #define LIMFORLAST 3 /* log2 of real limit (8) */ |
50 | 50 | ||
51 | /* | 51 | /* |
52 | ** The union 'Limbox' stores 'lastfree' and ensures that what follows it | 52 | ** The union 'Limbox' stores 'lastfree' and ensures that what follows it |
@@ -59,7 +59,7 @@ typedef union { | |||
59 | char padding[offsetof(Limbox_aux, follows_pNode)]; | 59 | char padding[offsetof(Limbox_aux, follows_pNode)]; |
60 | } Limbox; | 60 | } Limbox; |
61 | 61 | ||
62 | #define haslastfree(t) ((t)->lsizenode > LIMFORLAST) | 62 | #define haslastfree(t) ((t)->lsizenode >= LIMFORLAST) |
63 | #define getlastfree(t) ((cast(Limbox *, (t)->node) - 1)->lastfree) | 63 | #define getlastfree(t) ((cast(Limbox *, (t)->node) - 1)->lastfree) |
64 | 64 | ||
65 | 65 | ||
@@ -274,61 +274,6 @@ static int equalkey (const TValue *k1, const Node *n2, int deadok) { | |||
274 | 274 | ||
275 | 275 | ||
276 | /* | 276 | /* |
277 | ** True if value of 'alimit' is equal to the real size of the array | ||
278 | ** part of table 't'. (Otherwise, the array part must be larger than | ||
279 | ** 'alimit'.) | ||
280 | */ | ||
281 | #define limitequalsasize(t) (isrealasize(t) || ispow2((t)->alimit)) | ||
282 | |||
283 | |||
284 | /* | ||
285 | ** Returns the real size of the 'array' array | ||
286 | */ | ||
287 | unsigned int luaH_realasize (const Table *t) { | ||
288 | if (limitequalsasize(t)) | ||
289 | return t->alimit; /* this is the size */ | ||
290 | else { | ||
291 | unsigned int size = t->alimit; | ||
292 | /* compute the smallest power of 2 not smaller than 'size' */ | ||
293 | size |= (size >> 1); | ||
294 | size |= (size >> 2); | ||
295 | size |= (size >> 4); | ||
296 | size |= (size >> 8); | ||
297 | #if (UINT_MAX >> 14) > 3 /* unsigned int has more than 16 bits */ | ||
298 | size |= (size >> 16); | ||
299 | #if (UINT_MAX >> 30) > 3 | ||
300 | size |= (size >> 32); /* unsigned int has more than 32 bits */ | ||
301 | #endif | ||
302 | #endif | ||
303 | size++; | ||
304 | lua_assert(ispow2(size) && size/2 < t->alimit && t->alimit < size); | ||
305 | return size; | ||
306 | } | ||
307 | } | ||
308 | |||
309 | |||
310 | /* | ||
311 | ** Check whether real size of the array is a power of 2. | ||
312 | ** (If it is not, 'alimit' cannot be changed to any other value | ||
313 | ** without changing the real size.) | ||
314 | */ | ||
315 | static int ispow2realasize (const Table *t) { | ||
316 | return (!isrealasize(t) || ispow2(t->alimit)); | ||
317 | } | ||
318 | |||
319 | |||
320 | static unsigned int setlimittosize (Table *t) { | ||
321 | t->alimit = luaH_realasize(t); | ||
322 | setrealasize(t); | ||
323 | return t->alimit; | ||
324 | } | ||
325 | |||
326 | |||
327 | #define limitasasize(t) check_exp(isrealasize(t), t->alimit) | ||
328 | |||
329 | |||
330 | |||
331 | /* | ||
332 | ** "Generic" get version. (Not that generic: not valid for integers, | 277 | ** "Generic" get version. (Not that generic: not valid for integers, |
333 | ** which may be in array part, nor for floats with integral values.) | 278 | ** which may be in array part, nor for floats with integral values.) |
334 | ** See explanation about 'deadok' in function 'equalkey'. | 279 | ** See explanation about 'deadok' in function 'equalkey'. |
@@ -384,7 +329,7 @@ static unsigned findindex (lua_State *L, Table *t, TValue *key, | |||
384 | 329 | ||
385 | 330 | ||
386 | int luaH_next (lua_State *L, Table *t, StkId key) { | 331 | int luaH_next (lua_State *L, Table *t, StkId key) { |
387 | unsigned int asize = luaH_realasize(t); | 332 | unsigned int asize = t->asize; |
388 | unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */ | 333 | unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */ |
389 | for (; i < asize; i++) { /* try first array part */ | 334 | for (; i < asize; i++) { /* try first array part */ |
390 | lu_byte tag = *getArrTag(t, i); | 335 | lu_byte tag = *getArrTag(t, i); |
@@ -425,38 +370,10 @@ static void freehash (lua_State *L, Table *t) { | |||
425 | 370 | ||
426 | 371 | ||
427 | /* | 372 | /* |
428 | ** Check whether an integer key is in the array part. If 'alimit' is | 373 | ** Check whether an integer key is in the array part of a table. |
429 | ** not the real size of the array, the key still can be in the array | ||
430 | ** part. In this case, do the "Xmilia trick" to check whether 'key-1' | ||
431 | ** is smaller than the real size. | ||
432 | ** The trick works as follow: let 'p' be the integer such that | ||
433 | ** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'. That is, | ||
434 | ** 'p' is the highest 1-bit in 'alimit-1', and 2^(p+1) is the real size | ||
435 | ** of the array. What we have to check becomes 'key-1 < 2^(p+1)'. We | ||
436 | ** compute '(key-1) & ~(alimit-1)', which we call 'res'; it will have | ||
437 | ** the 'p' bit cleared. (It may also clear other bits smaller than 'p', | ||
438 | ** but no bit higher than 'p'.) If the key is outside the array, that | ||
439 | ** is, 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than | ||
440 | ** 'p', therefore it will be larger or equal to 'alimit', and the check | ||
441 | ** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than | ||
442 | ** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller | ||
443 | ** than 2^p, therefore smaller than 'alimit', and the check succeeds. | ||
444 | ** As special cases, when 'alimit' is 0 the condition is trivially false, | ||
445 | ** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'. | ||
446 | ** If key is 0 or negative, 'res' will have its higher bit on, so that | ||
447 | ** it cannot be smaller than 'alimit'. | ||
448 | */ | 374 | */ |
449 | static int keyinarray (Table *t, lua_Integer key) { | 375 | l_sinline int keyinarray (Table *t, lua_Integer key) { |
450 | lua_Unsigned alimit = t->alimit; | 376 | return (l_castS2U(key) - 1u < t->asize); /* 'key' in [1, t->asize]? */ |
451 | if (l_castS2U(key) - 1u < alimit) /* 'key' in [1, t->alimit]? */ | ||
452 | return 1; | ||
453 | else if (!isrealasize(t) && /* key still may be in the array part? */ | ||
454 | (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) { | ||
455 | t->alimit = cast_uint(key); /* probably '#t' is here now */ | ||
456 | return 1; | ||
457 | } | ||
458 | else | ||
459 | return 0; | ||
460 | } | 377 | } |
461 | 378 | ||
462 | 379 | ||
@@ -466,7 +383,6 @@ static int keyinarray (Table *t, lua_Integer key) { | |||
466 | ** ============================================================== | 383 | ** ============================================================== |
467 | */ | 384 | */ |
468 | 385 | ||
469 | |||
470 | /* | 386 | /* |
471 | ** Structure to count the keys in a table. | 387 | ** Structure to count the keys in a table. |
472 | ** 'total' is the total number of keys in the table. | 388 | ** 'total' is the total number of keys in the table. |
@@ -534,7 +450,7 @@ static void countint (lua_Integer key, Counters *ct) { | |||
534 | } | 450 | } |
535 | 451 | ||
536 | 452 | ||
537 | l_sinline int arraykeyisempty (const Table *t, lua_Unsigned key) { | 453 | l_sinline int arraykeyisempty (const Table *t, unsigned key) { |
538 | int tag = *getArrTag(t, key - 1); | 454 | int tag = *getArrTag(t, key - 1); |
539 | return tagisempty(tag); | 455 | return tagisempty(tag); |
540 | } | 456 | } |
@@ -548,7 +464,7 @@ static void numusearray (const Table *t, Counters *ct) { | |||
548 | unsigned int ttlg; /* 2^lg */ | 464 | unsigned int ttlg; /* 2^lg */ |
549 | unsigned int ause = 0; /* summation of 'nums' */ | 465 | unsigned int ause = 0; /* summation of 'nums' */ |
550 | unsigned int i = 1; /* index to traverse all array keys */ | 466 | unsigned int i = 1; /* index to traverse all array keys */ |
551 | unsigned int asize = limitasasize(t); /* real array size */ | 467 | unsigned int asize = t->asize; |
552 | /* traverse each slice */ | 468 | /* traverse each slice */ |
553 | for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { | 469 | for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { |
554 | unsigned int lc = 0; /* counter */ | 470 | unsigned int lc = 0; /* counter */ |
@@ -600,7 +516,10 @@ static void numusehash (const Table *t, Counters *ct) { | |||
600 | ** "concrete size" (number of bytes in the array). | 516 | ** "concrete size" (number of bytes in the array). |
601 | */ | 517 | */ |
602 | static size_t concretesize (unsigned int size) { | 518 | static size_t concretesize (unsigned int size) { |
603 | return size * sizeof(Value) + size; /* space for the two arrays */ | 519 | if (size == 0) |
520 | return 0; | ||
521 | else /* space for the two arrays plus an unsigned in between */ | ||
522 | return size * (sizeof(Value) + 1) + sizeof(unsigned); | ||
604 | } | 523 | } |
605 | 524 | ||
606 | 525 | ||
@@ -631,17 +550,18 @@ static Value *resizearray (lua_State *L , Table *t, | |||
631 | luaM_reallocvector(L, NULL, 0, newasizeb, lu_byte)); | 550 | luaM_reallocvector(L, NULL, 0, newasizeb, lu_byte)); |
632 | if (np == NULL) /* allocation error? */ | 551 | if (np == NULL) /* allocation error? */ |
633 | return NULL; | 552 | return NULL; |
553 | np += newasize; /* shift pointer to the end of value segment */ | ||
634 | if (oldasize > 0) { | 554 | if (oldasize > 0) { |
635 | size_t oldasizeb = concretesize(oldasize); | ||
636 | /* move common elements to new position */ | 555 | /* move common elements to new position */ |
637 | Value *op = t->array - oldasize; /* real original array */ | 556 | size_t oldasizeb = concretesize(oldasize); |
557 | Value *op = t->array; /* original array */ | ||
638 | unsigned tomove = (oldasize < newasize) ? oldasize : newasize; | 558 | unsigned tomove = (oldasize < newasize) ? oldasize : newasize; |
639 | size_t tomoveb = (oldasize < newasize) ? oldasizeb : newasizeb; | 559 | size_t tomoveb = (oldasize < newasize) ? oldasizeb : newasizeb; |
640 | lua_assert(tomoveb > 0); | 560 | lua_assert(tomoveb > 0); |
641 | memcpy(np + newasize - tomove, op + oldasize - tomove, tomoveb); | 561 | memcpy(np - tomove, op - tomove, tomoveb); |
642 | luaM_freemem(L, op, oldasizeb); | 562 | luaM_freemem(L, op - oldasize, oldasizeb); /* free old block */ |
643 | } | 563 | } |
644 | return np + newasize; /* shift pointer to the end of value segment */ | 564 | return np; |
645 | } | 565 | } |
646 | } | 566 | } |
647 | 567 | ||
@@ -665,7 +585,7 @@ static void setnodevector (lua_State *L, Table *t, unsigned size) { | |||
665 | if (lsize > MAXHBITS || (1u << lsize) > MAXHSIZE) | 585 | if (lsize > MAXHBITS || (1u << lsize) > MAXHSIZE) |
666 | luaG_runerror(L, "table overflow"); | 586 | luaG_runerror(L, "table overflow"); |
667 | size = twoto(lsize); | 587 | size = twoto(lsize); |
668 | if (lsize <= LIMFORLAST) /* no 'lastfree' field? */ | 588 | if (lsize < LIMFORLAST) /* no 'lastfree' field? */ |
669 | t->node = luaM_newvector(L, size, Node); | 589 | t->node = luaM_newvector(L, size, Node); |
670 | else { | 590 | else { |
671 | size_t bsize = size * sizeof(Node) + sizeof(Limbox); | 591 | size_t bsize = size * sizeof(Node) + sizeof(Limbox); |
@@ -730,7 +650,7 @@ static void exchangehashpart (Table *t1, Table *t2) { | |||
730 | static void reinsertOldSlice (lua_State *L, Table *t, unsigned oldasize, | 650 | static void reinsertOldSlice (lua_State *L, Table *t, unsigned oldasize, |
731 | unsigned newasize) { | 651 | unsigned newasize) { |
732 | unsigned i; | 652 | unsigned i; |
733 | t->alimit = newasize; /* pretend array has new size... */ | 653 | t->asize = newasize; /* pretend array has new size... */ |
734 | for (i = newasize; i < oldasize; i++) { /* traverse vanishing slice */ | 654 | for (i = newasize; i < oldasize; i++) { /* traverse vanishing slice */ |
735 | lu_byte tag = *getArrTag(t, i); | 655 | lu_byte tag = *getArrTag(t, i); |
736 | if (!tagisempty(tag)) { /* a non-empty entry? */ | 656 | if (!tagisempty(tag)) { /* a non-empty entry? */ |
@@ -740,7 +660,7 @@ static void reinsertOldSlice (lua_State *L, Table *t, unsigned oldasize, | |||
740 | luaH_setint(L, t, cast_int(i) + 1, &aux); | 660 | luaH_setint(L, t, cast_int(i) + 1, &aux); |
741 | } | 661 | } |
742 | } | 662 | } |
743 | t->alimit = oldasize; /* restore current size... */ | 663 | t->asize = oldasize; /* restore current size... */ |
744 | } | 664 | } |
745 | 665 | ||
746 | 666 | ||
@@ -772,7 +692,7 @@ static void clearNewSlice (Table *t, unsigned oldasize, unsigned newasize) { | |||
772 | void luaH_resize (lua_State *L, Table *t, unsigned newasize, | 692 | void luaH_resize (lua_State *L, Table *t, unsigned newasize, |
773 | unsigned nhsize) { | 693 | unsigned nhsize) { |
774 | Table newt; /* to keep the new hash part */ | 694 | Table newt; /* to keep the new hash part */ |
775 | unsigned int oldasize = setlimittosize(t); | 695 | unsigned oldasize = t->asize; |
776 | Value *newarray; | 696 | Value *newarray; |
777 | if (newasize > MAXASIZE) | 697 | if (newasize > MAXASIZE) |
778 | luaG_runerror(L, "table overflow"); | 698 | luaG_runerror(L, "table overflow"); |
@@ -794,7 +714,9 @@ void luaH_resize (lua_State *L, Table *t, unsigned newasize, | |||
794 | /* allocation ok; initialize new part of the array */ | 714 | /* allocation ok; initialize new part of the array */ |
795 | exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */ | 715 | exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */ |
796 | t->array = newarray; /* set new array part */ | 716 | t->array = newarray; /* set new array part */ |
797 | t->alimit = newasize; | 717 | t->asize = newasize; |
718 | if (newarray != NULL) | ||
719 | *lenhint(t) = newasize / 2u; /* set an initial hint */ | ||
798 | clearNewSlice(t, oldasize, newasize); | 720 | clearNewSlice(t, oldasize, newasize); |
799 | /* re-insert elements from old hash part into new parts */ | 721 | /* re-insert elements from old hash part into new parts */ |
800 | reinsert(L, &newt, t); /* 'newt' now has the old hash */ | 722 | reinsert(L, &newt, t); /* 'newt' now has the old hash */ |
@@ -818,7 +740,6 @@ static void rehash (lua_State *L, Table *t, const TValue *ek) { | |||
818 | Counters ct; | 740 | Counters ct; |
819 | unsigned i; | 741 | unsigned i; |
820 | unsigned nsize; /* size for the hash part */ | 742 | unsigned nsize; /* size for the hash part */ |
821 | setlimittosize(t); | ||
822 | /* reset counts */ | 743 | /* reset counts */ |
823 | for (i = 0; i <= MAXABITS; i++) ct.nums[i] = 0; | 744 | for (i = 0; i <= MAXABITS; i++) ct.nums[i] = 0; |
824 | ct.na = 0; | 745 | ct.na = 0; |
@@ -829,7 +750,7 @@ static void rehash (lua_State *L, Table *t, const TValue *ek) { | |||
829 | numusehash(t, &ct); /* count keys in hash part */ | 750 | numusehash(t, &ct); /* count keys in hash part */ |
830 | if (ct.na == 0) { | 751 | if (ct.na == 0) { |
831 | /* no new keys to enter array part; keep it with the same size */ | 752 | /* no new keys to enter array part; keep it with the same size */ |
832 | asize = luaH_realasize(t); | 753 | asize = t->asize; |
833 | } | 754 | } |
834 | else { /* compute best size for array part */ | 755 | else { /* compute best size for array part */ |
835 | numusearray(t, &ct); /* count keys in array part */ | 756 | numusearray(t, &ct); /* count keys in array part */ |
@@ -857,15 +778,14 @@ Table *luaH_new (lua_State *L) { | |||
857 | t->metatable = NULL; | 778 | t->metatable = NULL; |
858 | t->flags = maskflags; /* table has no metamethod fields */ | 779 | t->flags = maskflags; /* table has no metamethod fields */ |
859 | t->array = NULL; | 780 | t->array = NULL; |
860 | t->alimit = 0; | 781 | t->asize = 0; |
861 | setnodevector(L, t, 0); | 782 | setnodevector(L, t, 0); |
862 | return t; | 783 | return t; |
863 | } | 784 | } |
864 | 785 | ||
865 | 786 | ||
866 | lu_mem luaH_size (Table *t) { | 787 | lu_mem luaH_size (Table *t) { |
867 | lu_mem sz = cast(lu_mem, sizeof(Table)) | 788 | lu_mem sz = cast(lu_mem, sizeof(Table)) + concretesize(t->asize); |
868 | + luaH_realasize(t) * (sizeof(Value) + 1); | ||
869 | if (!isdummy(t)) | 789 | if (!isdummy(t)) |
870 | sz += sizehash(t); | 790 | sz += sizehash(t); |
871 | return sz; | 791 | return sz; |
@@ -876,9 +796,8 @@ lu_mem luaH_size (Table *t) { | |||
876 | ** Frees a table. | 796 | ** Frees a table. |
877 | */ | 797 | */ |
878 | void luaH_free (lua_State *L, Table *t) { | 798 | void luaH_free (lua_State *L, Table *t) { |
879 | unsigned int realsize = luaH_realasize(t); | ||
880 | freehash(L, t); | 799 | freehash(L, t); |
881 | resizearray(L, t, realsize, 0); | 800 | resizearray(L, t, t->asize, 0); |
882 | luaM_free(L, t); | 801 | luaM_free(L, t); |
883 | } | 802 | } |
884 | 803 | ||
@@ -972,7 +891,7 @@ static void luaH_newkey (lua_State *L, Table *t, const TValue *key, | |||
972 | 891 | ||
973 | static const TValue *getintfromhash (Table *t, lua_Integer key) { | 892 | static const TValue *getintfromhash (Table *t, lua_Integer key) { |
974 | Node *n = hashint(t, key); | 893 | Node *n = hashint(t, key); |
975 | lua_assert(l_castS2U(key) - 1u >= luaH_realasize(t)); | 894 | lua_assert(!keyinarray(t, key)); |
976 | for (;;) { /* check whether 'key' is somewhere in the chain */ | 895 | for (;;) { /* check whether 'key' is somewhere in the chain */ |
977 | if (keyisinteger(n) && keyival(n) == key) | 896 | if (keyisinteger(n) && keyival(n) == key) |
978 | return gval(n); /* that's it */ | 897 | return gval(n); /* that's it */ |
@@ -1112,17 +1031,15 @@ static int rawfinishnodeset (const TValue *slot, TValue *val) { | |||
1112 | 1031 | ||
1113 | 1032 | ||
1114 | int luaH_psetint (Table *t, lua_Integer key, TValue *val) { | 1033 | int luaH_psetint (Table *t, lua_Integer key, TValue *val) { |
1115 | if (keyinarray(t, key)) { | 1034 | lua_assert(!keyinarray(t, key)); |
1116 | lu_byte *tag = getArrTag(t, key - 1); | 1035 | return finishnodeset(t, getintfromhash(t, key), val); |
1117 | if (!tagisempty(*tag) || checknoTM(t->metatable, TM_NEWINDEX)) { | 1036 | } |
1118 | fval2arr(t, cast_uint(key) - 1, tag, val); | 1037 | |
1119 | return HOK; /* success */ | 1038 | |
1120 | } | 1039 | static int psetint (Table *t, lua_Integer key, TValue *val) { |
1121 | else | 1040 | int hres; |
1122 | return ~cast_int(key - 1); /* empty slot in the array part */ | 1041 | luaH_fastseti(t, key, val, hres); |
1123 | } | 1042 | return hres; |
1124 | else | ||
1125 | return finishnodeset(t, getintfromhash(t, key), val); | ||
1126 | } | 1043 | } |
1127 | 1044 | ||
1128 | 1045 | ||
@@ -1139,12 +1056,12 @@ int luaH_psetstr (Table *t, TString *key, TValue *val) { | |||
1139 | int luaH_pset (Table *t, const TValue *key, TValue *val) { | 1056 | int luaH_pset (Table *t, const TValue *key, TValue *val) { |
1140 | switch (ttypetag(key)) { | 1057 | switch (ttypetag(key)) { |
1141 | case LUA_VSHRSTR: return luaH_psetshortstr(t, tsvalue(key), val); | 1058 | case LUA_VSHRSTR: return luaH_psetshortstr(t, tsvalue(key), val); |
1142 | case LUA_VNUMINT: return luaH_psetint(t, ivalue(key), val); | 1059 | case LUA_VNUMINT: return psetint(t, ivalue(key), val); |
1143 | case LUA_VNIL: return HNOTFOUND; | 1060 | case LUA_VNIL: return HNOTFOUND; |
1144 | case LUA_VNUMFLT: { | 1061 | case LUA_VNUMFLT: { |
1145 | lua_Integer k; | 1062 | lua_Integer k; |
1146 | if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */ | 1063 | if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */ |
1147 | return luaH_psetint(t, k, val); /* use specialized version */ | 1064 | return psetint(t, k, val); /* use specialized version */ |
1148 | /* else... */ | 1065 | /* else... */ |
1149 | } /* FALLTHROUGH */ | 1066 | } /* FALLTHROUGH */ |
1150 | default: | 1067 | default: |
@@ -1244,6 +1161,7 @@ static lua_Unsigned hash_search (Table *t, lua_Unsigned j) { | |||
1244 | 1161 | ||
1245 | 1162 | ||
1246 | static unsigned int binsearch (Table *array, unsigned int i, unsigned int j) { | 1163 | static unsigned int binsearch (Table *array, unsigned int i, unsigned int j) { |
1164 | lua_assert(i <= j); | ||
1247 | while (j - i > 1u) { /* binary search */ | 1165 | while (j - i > 1u) { /* binary search */ |
1248 | unsigned int m = (i + j) / 2; | 1166 | unsigned int m = (i + j) / 2; |
1249 | if (arraykeyisempty(array, m)) j = m; | 1167 | if (arraykeyisempty(array, m)) j = m; |
@@ -1253,90 +1171,74 @@ static unsigned int binsearch (Table *array, unsigned int i, unsigned int j) { | |||
1253 | } | 1171 | } |
1254 | 1172 | ||
1255 | 1173 | ||
1174 | /* return a border, saving it as a hint for next call */ | ||
1175 | static lua_Unsigned newhint (Table *t, unsigned hint) { | ||
1176 | lua_assert(hint <= t->asize); | ||
1177 | *lenhint(t) = hint; | ||
1178 | return hint; | ||
1179 | } | ||
1180 | |||
1181 | |||
1256 | /* | 1182 | /* |
1257 | ** Try to find a boundary in table 't'. (A 'boundary' is an integer index | 1183 | ** Try to find a border in table 't'. (A 'border' is an integer index |
1258 | ** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent | 1184 | ** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent, |
1259 | ** and 'maxinteger' if t[maxinteger] is present.) | 1185 | ** or 'maxinteger' if t[maxinteger] is present.) |
1260 | ** (In the next explanation, we use Lua indices, that is, with base 1. | 1186 | ** If there is an array part, try to find a border there. First try |
1261 | ** The code itself uses base 0 when indexing the array part of the table.) | 1187 | ** to find it in the vicinity of the previous result (hint), to handle |
1262 | ** The code starts with 'limit = t->alimit', a position in the array | 1188 | ** cases like 't[#t + 1] = val' or 't[#t] = nil', that move the border |
1263 | ** part that may be a boundary. | 1189 | ** by one entry. Otherwise, do a binary search to find the border. |
1264 | ** | 1190 | ** If there is no array part, or its last element is non empty, the |
1265 | ** (1) If 't[limit]' is empty, there must be a boundary before it. | 1191 | ** border may be in the hash part. |
1266 | ** As a common case (e.g., after 't[#t]=nil'), check whether 'limit-1' | ||
1267 | ** is present. If so, it is a boundary. Otherwise, do a binary search | ||
1268 | ** between 0 and limit to find a boundary. In both cases, try to | ||
1269 | ** use this boundary as the new 'alimit', as a hint for the next call. | ||
1270 | ** | ||
1271 | ** (2) If 't[limit]' is not empty and the array has more elements | ||
1272 | ** after 'limit', try to find a boundary there. Again, try first | ||
1273 | ** the special case (which should be quite frequent) where 'limit+1' | ||
1274 | ** is empty, so that 'limit' is a boundary. Otherwise, check the | ||
1275 | ** last element of the array part. If it is empty, there must be a | ||
1276 | ** boundary between the old limit (present) and the last element | ||
1277 | ** (absent), which is found with a binary search. (This boundary always | ||
1278 | ** can be a new limit.) | ||
1279 | ** | ||
1280 | ** (3) The last case is when there are no elements in the array part | ||
1281 | ** (limit == 0) or its last element (the new limit) is present. | ||
1282 | ** In this case, must check the hash part. If there is no hash part | ||
1283 | ** or 'limit+1' is absent, 'limit' is a boundary. Otherwise, call | ||
1284 | ** 'hash_search' to find a boundary in the hash part of the table. | ||
1285 | ** (In those cases, the boundary is not inside the array part, and | ||
1286 | ** therefore cannot be used as a new limit.) | ||
1287 | */ | 1192 | */ |
1288 | lua_Unsigned luaH_getn (Table *t) { | 1193 | lua_Unsigned luaH_getn (Table *t) { |
1289 | unsigned int limit = t->alimit; | 1194 | unsigned asize = t->asize; |
1290 | if (limit > 0 && arraykeyisempty(t, limit)) { /* (1)? */ | 1195 | if (asize > 0) { /* is there an array part? */ |
1291 | /* there must be a boundary before 'limit' */ | 1196 | const unsigned maxvicinity = 4; |
1292 | if (limit >= 2 && !arraykeyisempty(t, limit - 1)) { | 1197 | unsigned limit = *lenhint(t); /* start with the hint */ |
1293 | /* 'limit - 1' is a boundary; can it be a new limit? */ | 1198 | if (limit == 0) |
1294 | if (ispow2realasize(t) && !ispow2(limit - 1)) { | 1199 | limit = 1; /* make limit a valid index in the array */ |
1295 | t->alimit = limit - 1; | 1200 | if (arraykeyisempty(t, limit)) { /* t[limit] empty? */ |
1296 | setnorealasize(t); /* now 'alimit' is not the real size */ | 1201 | /* there must be a border before 'limit' */ |
1202 | unsigned i; | ||
1203 | /* look for a border in the vicinity of the hint */ | ||
1204 | for (i = 0; i < maxvicinity && limit > 1; i++) { | ||
1205 | limit--; | ||
1206 | if (!arraykeyisempty(t, limit)) | ||
1207 | return newhint(t, limit); /* 'limit' is a border */ | ||
1297 | } | 1208 | } |
1298 | return limit - 1; | 1209 | /* t[limit] still empty; search for a border in [0, limit) */ |
1210 | return newhint(t, binsearch(t, 0, limit)); | ||
1299 | } | 1211 | } |
1300 | else { /* must search for a boundary in [0, limit] */ | 1212 | else { /* 'limit' is present in table; look for a border after it */ |
1301 | unsigned int boundary = binsearch(t, 0, limit); | 1213 | unsigned i; |
1302 | /* can this boundary represent the real size of the array? */ | 1214 | /* look for a border in the vicinity of the hint */ |
1303 | if (ispow2realasize(t) && boundary > luaH_realasize(t) / 2) { | 1215 | for (i = 0; i < maxvicinity && limit < asize; i++) { |
1304 | t->alimit = boundary; /* use it as the new limit */ | 1216 | limit++; |
1305 | setnorealasize(t); | 1217 | if (arraykeyisempty(t, limit)) |
1218 | return newhint(t, limit - 1); /* 'limit - 1' is a border */ | ||
1219 | } | ||
1220 | if (arraykeyisempty(t, asize)) { /* last element empty? */ | ||
1221 | /* t[limit] not empty; search for a border in [limit, asize) */ | ||
1222 | return newhint(t, binsearch(t, limit, asize)); | ||
1306 | } | 1223 | } |
1307 | return boundary; | ||
1308 | } | ||
1309 | } | ||
1310 | /* 'limit' is zero or present in table */ | ||
1311 | if (!limitequalsasize(t)) { /* (2)? */ | ||
1312 | /* 'limit' > 0 and array has more elements after 'limit' */ | ||
1313 | if (arraykeyisempty(t, limit + 1)) /* 'limit + 1' is empty? */ | ||
1314 | return limit; /* this is the boundary */ | ||
1315 | /* else, try last element in the array */ | ||
1316 | limit = luaH_realasize(t); | ||
1317 | if (arraykeyisempty(t, limit)) { /* empty? */ | ||
1318 | /* there must be a boundary in the array after old limit, | ||
1319 | and it must be a valid new limit */ | ||
1320 | unsigned int boundary = binsearch(t, t->alimit, limit); | ||
1321 | t->alimit = boundary; | ||
1322 | return boundary; | ||
1323 | } | 1224 | } |
1324 | /* else, new limit is present in the table; check the hash part */ | 1225 | /* last element non empty; set a hint to speed up findind that again */ |
1226 | /* (keys in the hash part cannot be hints) */ | ||
1227 | *lenhint(t) = asize; | ||
1325 | } | 1228 | } |
1326 | /* (3) 'limit' is the last element and either is zero or present in table */ | 1229 | /* no array part or t[asize] is not empty; check the hash part */ |
1327 | lua_assert(limit == luaH_realasize(t) && | 1230 | lua_assert(asize == 0 || !arraykeyisempty(t, asize)); |
1328 | (limit == 0 || !arraykeyisempty(t, limit))); | 1231 | if (isdummy(t) || hashkeyisempty(t, asize + 1)) |
1329 | if (isdummy(t) || hashkeyisempty(t, limit + 1)) | 1232 | return asize; /* 'asize + 1' is empty */ |
1330 | return limit; /* 'limit + 1' is absent */ | 1233 | else /* 'asize + 1' is also non empty */ |
1331 | else /* 'limit + 1' is also present */ | 1234 | return hash_search(t, asize); |
1332 | return hash_search(t, limit); | ||
1333 | } | 1235 | } |
1334 | 1236 | ||
1335 | 1237 | ||
1336 | 1238 | ||
1337 | #if defined(LUA_DEBUG) | 1239 | #if defined(LUA_DEBUG) |
1338 | 1240 | ||
1339 | /* export these functions for the test library */ | 1241 | /* export this function for the test library */ |
1340 | 1242 | ||
1341 | Node *luaH_mainposition (const Table *t, const TValue *key) { | 1243 | Node *luaH_mainposition (const Table *t, const TValue *key) { |
1342 | return mainpositionTV(t, key); | 1244 | return mainpositionTV(t, key); |