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 | |
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.
-rw-r--r-- | lgc.c | 8 | ||||
-rw-r--r-- | lobject.h | 16 | ||||
-rw-r--r-- | ltable.c | 298 | ||||
-rw-r--r-- | ltable.h | 36 | ||||
-rw-r--r-- | ltests.c | 6 | ||||
-rw-r--r-- | lvm.c | 2 | ||||
-rw-r--r-- | testes/nextvar.lua | 29 |
7 files changed, 146 insertions, 249 deletions
@@ -486,7 +486,7 @@ static void traverseweakvalue (global_State *g, Table *h) { | |||
486 | Node *n, *limit = gnodelast(h); | 486 | Node *n, *limit = gnodelast(h); |
487 | /* if there is array part, assume it may have white values (it is not | 487 | /* if there is array part, assume it may have white values (it is not |
488 | worth traversing it now just to check) */ | 488 | worth traversing it now just to check) */ |
489 | int hasclears = (h->alimit > 0); | 489 | int hasclears = (h->asize > 0); |
490 | for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */ | 490 | for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */ |
491 | if (isempty(gval(n))) /* entry is empty? */ | 491 | if (isempty(gval(n))) /* entry is empty? */ |
492 | clearkey(n); /* clear its key */ | 492 | clearkey(n); /* clear its key */ |
@@ -508,7 +508,7 @@ static void traverseweakvalue (global_State *g, Table *h) { | |||
508 | ** Traverse the array part of a table. | 508 | ** Traverse the array part of a table. |
509 | */ | 509 | */ |
510 | static int traversearray (global_State *g, Table *h) { | 510 | static int traversearray (global_State *g, Table *h) { |
511 | unsigned asize = luaH_realasize(h); | 511 | unsigned asize = h->asize; |
512 | int marked = 0; /* true if some object is marked in this traversal */ | 512 | int marked = 0; /* true if some object is marked in this traversal */ |
513 | unsigned i; | 513 | unsigned i; |
514 | for (i = 0; i < asize; i++) { | 514 | for (i = 0; i < asize; i++) { |
@@ -604,7 +604,7 @@ static l_mem traversetable (global_State *g, Table *h) { | |||
604 | } | 604 | } |
605 | else /* not weak */ | 605 | else /* not weak */ |
606 | traversestrongtable(g, h); | 606 | traversestrongtable(g, h); |
607 | return 1 + 2*sizenode(h) + h->alimit; | 607 | return 1 + 2*sizenode(h) + h->asize; |
608 | } | 608 | } |
609 | 609 | ||
610 | 610 | ||
@@ -790,7 +790,7 @@ static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) { | |||
790 | Table *h = gco2t(l); | 790 | Table *h = gco2t(l); |
791 | Node *n, *limit = gnodelast(h); | 791 | Node *n, *limit = gnodelast(h); |
792 | unsigned int i; | 792 | unsigned int i; |
793 | unsigned int asize = luaH_realasize(h); | 793 | unsigned int asize = h->asize; |
794 | for (i = 0; i < asize; i++) { | 794 | for (i = 0; i < asize; i++) { |
795 | GCObject *o = gcvalarr(h, i); | 795 | GCObject *o = gcvalarr(h, i); |
796 | if (iscleared(g, o)) /* value was collected? */ | 796 | if (iscleared(g, o)) /* value was collected? */ |
@@ -763,24 +763,12 @@ typedef union Node { | |||
763 | checkliveness(L,io_); } | 763 | checkliveness(L,io_); } |
764 | 764 | ||
765 | 765 | ||
766 | /* | ||
767 | ** About 'alimit': if 'isrealasize(t)' is true, then 'alimit' is the | ||
768 | ** real size of 'array'. Otherwise, the real size of 'array' is the | ||
769 | ** smallest power of two not smaller than 'alimit' (or zero iff 'alimit' | ||
770 | ** is zero); 'alimit' is then used as a hint for #t. | ||
771 | */ | ||
772 | |||
773 | #define BITRAS (1 << 7) | ||
774 | #define isrealasize(t) (!((t)->flags & BITRAS)) | ||
775 | #define setrealasize(t) ((t)->flags &= cast_byte(~BITRAS)) | ||
776 | #define setnorealasize(t) ((t)->flags |= BITRAS) | ||
777 | |||
778 | 766 | ||
779 | typedef struct Table { | 767 | typedef struct Table { |
780 | CommonHeader; | 768 | CommonHeader; |
781 | lu_byte flags; /* 1<<p means tagmethod(p) is not present */ | 769 | lu_byte flags; /* 1<<p means tagmethod(p) is not present */ |
782 | lu_byte lsizenode; /* log2 of size of 'node' array */ | 770 | lu_byte lsizenode; /* log2 of number of slots of 'node' array */ |
783 | unsigned int alimit; /* "limit" of 'array' array */ | 771 | unsigned int asize; /* number of slots in 'array' array */ |
784 | Value *array; /* array part */ | 772 | Value *array; /* array part */ |
785 | Node *node; | 773 | Node *node; |
786 | struct Table *metatable; | 774 | struct Table *metatable; |
@@ -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); |
@@ -48,7 +48,7 @@ | |||
48 | 48 | ||
49 | #define luaH_fastgeti(t,k,res,tag) \ | 49 | #define luaH_fastgeti(t,k,res,tag) \ |
50 | { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \ | 50 | { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \ |
51 | if ((u < h->alimit)) { \ | 51 | if ((u < h->asize)) { \ |
52 | tag = *getArrTag(h, u); \ | 52 | tag = *getArrTag(h, u); \ |
53 | if (!tagisempty(tag)) { farr2val(h, u, tag, res); }} \ | 53 | if (!tagisempty(tag)) { farr2val(h, u, tag, res); }} \ |
54 | else { tag = luaH_getint(h, (k), res); }} | 54 | else { tag = luaH_getint(h, (k), res); }} |
@@ -56,10 +56,11 @@ | |||
56 | 56 | ||
57 | #define luaH_fastseti(t,k,val,hres) \ | 57 | #define luaH_fastseti(t,k,val,hres) \ |
58 | { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \ | 58 | { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \ |
59 | if ((u < h->alimit)) { \ | 59 | if ((u < h->asize)) { \ |
60 | lu_byte *tag = getArrTag(h, u); \ | 60 | lu_byte *tag = getArrTag(h, u); \ |
61 | if (tagisempty(*tag)) hres = ~cast_int(u); \ | 61 | if (h->metatable == NULL || !tagisempty(*tag)) \ |
62 | else { fval2arr(h, u, tag, val); hres = HOK; }} \ | 62 | { fval2arr(h, u, tag, val); hres = HOK; } \ |
63 | else hres = ~cast_int(u); } \ | ||
63 | else { hres = luaH_psetint(h, k, val); }} | 64 | else { hres = luaH_psetint(h, k, val); }} |
64 | 65 | ||
65 | 66 | ||
@@ -94,28 +95,36 @@ | |||
94 | /* | 95 | /* |
95 | ** The array part of a table is represented by an inverted array of | 96 | ** The array part of a table is represented by an inverted array of |
96 | ** values followed by an array of tags, to avoid wasting space with | 97 | ** values followed by an array of tags, to avoid wasting space with |
97 | ** padding. The 'array' pointer points to the junction of the two | 98 | ** padding. In between them there is an unsigned int, explained later. |
98 | ** arrays, so that values are indexed with negative indices and tags | 99 | ** The 'array' pointer points between the two arrays, so that values are |
99 | ** with non-negative indices. | 100 | ** indexed with negative indices and tags with non-negative indices. |
100 | 101 | ||
101 | Values Tags | 102 | Values Tags |
102 | -------------------------------------------------------- | 103 | -------------------------------------------------------- |
103 | ... | Value 1 | Value 0 |0|1|... | 104 | ... | Value 1 | Value 0 |unsigned|0|1|... |
104 | -------------------------------------------------------- | 105 | -------------------------------------------------------- |
105 | ^ t->array | 106 | ^ t->array |
106 | 107 | ||
107 | ** All accesses to 't->array' should be through the macros 'getArrTag' | 108 | ** All accesses to 't->array' should be through the macros 'getArrTag' |
108 | ** and 'getArrVal'. | 109 | ** and 'getArrVal'. |
109 | */ | 110 | */ |
110 | 111 | ||
111 | /* Computes the address of the tag for the abstract C-index 'k' */ | 112 | /* Computes the address of the tag for the abstract C-index 'k' */ |
112 | #define getArrTag(t,k) (cast(lu_byte*, (t)->array) + (k)) | 113 | #define getArrTag(t,k) (cast(lu_byte*, (t)->array) + sizeof(unsigned) + (k)) |
113 | 114 | ||
114 | /* Computes the address of the value for the abstract C-index 'k' */ | 115 | /* Computes the address of the value for the abstract C-index 'k' */ |
115 | #define getArrVal(t,k) ((t)->array - 1 - (k)) | 116 | #define getArrVal(t,k) ((t)->array - 1 - (k)) |
116 | 117 | ||
117 | 118 | ||
118 | /* | 119 | /* |
120 | ** The unsigned between the two arrays is used as a hint for #t; | ||
121 | ** see luaH_getn. It is stored there to avoid wasting space in | ||
122 | ** the structure Table for tables with no array part. | ||
123 | */ | ||
124 | #define lenhint(t) cast(unsigned*, (t)->array) | ||
125 | |||
126 | |||
127 | /* | ||
119 | ** Move TValues to/from arrays, using C indices | 128 | ** Move TValues to/from arrays, using C indices |
120 | */ | 129 | */ |
121 | #define arr2obj(h,k,val) \ | 130 | #define arr2obj(h,k,val) \ |
@@ -167,7 +176,6 @@ LUAI_FUNC lu_mem luaH_size (Table *t); | |||
167 | LUAI_FUNC void luaH_free (lua_State *L, Table *t); | 176 | LUAI_FUNC void luaH_free (lua_State *L, Table *t); |
168 | LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key); | 177 | LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key); |
169 | LUAI_FUNC lua_Unsigned luaH_getn (Table *t); | 178 | LUAI_FUNC lua_Unsigned luaH_getn (Table *t); |
170 | LUAI_FUNC unsigned luaH_realasize (const Table *t); | ||
171 | 179 | ||
172 | 180 | ||
173 | #if defined(LUA_DEBUG) | 181 | #if defined(LUA_DEBUG) |
@@ -359,7 +359,7 @@ static void checkvalref (global_State *g, GCObject *f, const TValue *t) { | |||
359 | 359 | ||
360 | static void checktable (global_State *g, Table *h) { | 360 | static void checktable (global_State *g, Table *h) { |
361 | unsigned int i; | 361 | unsigned int i; |
362 | unsigned int asize = luaH_realasize(h); | 362 | unsigned int asize = h->asize; |
363 | Node *n, *limit = gnode(h, sizenode(h)); | 363 | Node *n, *limit = gnode(h, sizenode(h)); |
364 | GCObject *hgc = obj2gco(h); | 364 | GCObject *hgc = obj2gco(h); |
365 | checkobjrefN(g, hgc, h->metatable); | 365 | checkobjrefN(g, hgc, h->metatable); |
@@ -1034,11 +1034,11 @@ static int table_query (lua_State *L) { | |||
1034 | unsigned int asize; | 1034 | unsigned int asize; |
1035 | luaL_checktype(L, 1, LUA_TTABLE); | 1035 | luaL_checktype(L, 1, LUA_TTABLE); |
1036 | t = hvalue(obj_at(L, 1)); | 1036 | t = hvalue(obj_at(L, 1)); |
1037 | asize = luaH_realasize(t); | 1037 | asize = t->asize; |
1038 | if (i == -1) { | 1038 | if (i == -1) { |
1039 | lua_pushinteger(L, cast(lua_Integer, asize)); | 1039 | lua_pushinteger(L, cast(lua_Integer, asize)); |
1040 | lua_pushinteger(L, cast(lua_Integer, allocsizenode(t))); | 1040 | lua_pushinteger(L, cast(lua_Integer, allocsizenode(t))); |
1041 | lua_pushinteger(L, cast(lua_Integer, t->alimit)); | 1041 | lua_pushinteger(L, cast(lua_Integer, asize > 0 ? *lenhint(t) : 0)); |
1042 | return 3; | 1042 | return 3; |
1043 | } | 1043 | } |
1044 | else if (cast_uint(i) < asize) { | 1044 | else if (cast_uint(i) < asize) { |
@@ -1865,7 +1865,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) { | |||
1865 | pc++; | 1865 | pc++; |
1866 | } | 1866 | } |
1867 | /* when 'n' is known, table should have proper size */ | 1867 | /* when 'n' is known, table should have proper size */ |
1868 | if (last > luaH_realasize(h)) { /* needs more space? */ | 1868 | if (last > h->asize) { /* needs more space? */ |
1869 | /* fixed-size sets should have space preallocated */ | 1869 | /* fixed-size sets should have space preallocated */ |
1870 | lua_assert(GETARG_vB(i) == 0); | 1870 | lua_assert(GETARG_vB(i) == 0); |
1871 | luaH_resizearray(L, h, last); /* preallocate it at once */ | 1871 | luaH_resizearray(L, h, last); /* preallocate it at once */ |
diff --git a/testes/nextvar.lua b/testes/nextvar.lua index 00e509f8..d1da3cee 100644 --- a/testes/nextvar.lua +++ b/testes/nextvar.lua | |||
@@ -316,21 +316,6 @@ end | |||
316 | local a = {} | 316 | local a = {} |
317 | for i=1,lim do a[i] = true; foo(i, table.unpack(a)) end | 317 | for i=1,lim do a[i] = true; foo(i, table.unpack(a)) end |
318 | 318 | ||
319 | |||
320 | -- Table length with limit smaller than maximum value at array | ||
321 | local a = {} | ||
322 | for i = 1,64 do a[i] = true end -- make its array size 64 | ||
323 | for i = 1,64 do a[i] = nil end -- erase all elements | ||
324 | assert(T.querytab(a) == 64) -- array part has 64 elements | ||
325 | a[32] = true; a[48] = true; -- binary search will find these ones | ||
326 | a[51] = true -- binary search will miss this one | ||
327 | assert(#a == 48) -- this will set the limit | ||
328 | assert(select(3, T.querytab(a)) == 48) -- this is the limit now | ||
329 | a[50] = true -- this will set a new limit | ||
330 | assert(select(3, T.querytab(a)) == 50) -- this is the limit now | ||
331 | -- but the size is larger (and still inside the array part) | ||
332 | assert(#a == 51) | ||
333 | |||
334 | end --] | 319 | end --] |
335 | 320 | ||
336 | 321 | ||
@@ -344,6 +329,20 @@ assert(#{1, 2, 3, nil, nil} == 3) | |||
344 | print'+' | 329 | print'+' |
345 | 330 | ||
346 | 331 | ||
332 | do | ||
333 | local s1, s2 = math.randomseed() | ||
334 | print(string.format( | ||
335 | "testing length for some random tables (seeds 0X%x:%x)", s1, s2)) | ||
336 | local N = 130 | ||
337 | for i = 1, 1e3 do -- create that many random tables | ||
338 | local a = table.create(math.random(N)) -- initiate with random size | ||
339 | for j = 1, math.random(N) do -- add random number of random entries | ||
340 | a[math.random(N)] = true | ||
341 | end | ||
342 | assert(#a == 0 or a[#a] and not a[#a + 1]) | ||
343 | end | ||
344 | end | ||
345 | |||
347 | local nofind = {} | 346 | local nofind = {} |
348 | 347 | ||
349 | a,b,c = 1,2,3 | 348 | a,b,c = 1,2,3 |