aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-29 17:26:20 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-29 17:26:20 -0300
commit002beeebe79065e03dd9f531bee367e8459e3f64 (patch)
tree5b066d30e08950c923c253ce85f702b39fbe9c31 /ltable.c
parent9329eeac3b7035c223d7a8b63dbde1f6db371bf5 (diff)
downloadlua-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.c298
1 files changed, 100 insertions, 198 deletions
diff --git a/ltable.c b/ltable.c
index 71a6f30d..6ea382a1 100644
--- a/ltable.c
+++ b/ltable.c
@@ -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*/
287unsigned 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*/
315static int ispow2realasize (const Table *t) {
316 return (!isrealasize(t) || ispow2(t->alimit));
317}
318
319
320static 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
386int luaH_next (lua_State *L, Table *t, StkId key) { 331int 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*/
449static int keyinarray (Table *t, lua_Integer key) { 375l_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
537l_sinline int arraykeyisempty (const Table *t, lua_Unsigned key) { 453l_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*/
602static size_t concretesize (unsigned int size) { 518static 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) {
730static void reinsertOldSlice (lua_State *L, Table *t, unsigned oldasize, 650static 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) {
772void luaH_resize (lua_State *L, Table *t, unsigned newasize, 692void 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
866lu_mem luaH_size (Table *t) { 787lu_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*/
878void luaH_free (lua_State *L, Table *t) { 798void 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
973static const TValue *getintfromhash (Table *t, lua_Integer key) { 892static 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
1114int luaH_psetint (Table *t, lua_Integer key, TValue *val) { 1033int 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 } 1039static 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) {
1139int luaH_pset (Table *t, const TValue *key, TValue *val) { 1056int 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
1246static unsigned int binsearch (Table *array, unsigned int i, unsigned int j) { 1163static 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 */
1175static 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*/
1288lua_Unsigned luaH_getn (Table *t) { 1193lua_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
1341Node *luaH_mainposition (const Table *t, const TValue *key) { 1243Node *luaH_mainposition (const Table *t, const TValue *key) {
1342 return mainpositionTV(t, key); 1244 return mainpositionTV(t, key);