aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2023-10-30 14:25:59 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2023-10-30 14:25:59 -0300
commit43c8e5bded052801f54a7439d18933b83570eb82 (patch)
tree97f6d1e020110e14c798537c7bbb1f90feed4044 /ltable.c
parentb8b709b6d40c5c18d9b8ef33bb50afc55f048ab8 (diff)
downloadlua-43c8e5bded052801f54a7439d18933b83570eb82.tar.gz
lua-43c8e5bded052801f54a7439d18933b83570eb82.tar.bz2
lua-43c8e5bded052801f54a7439d18933b83570eb82.zip
Full abstraction for representation of array values
Diffstat (limited to 'ltable.c')
-rw-r--r--ltable.c116
1 files changed, 60 insertions, 56 deletions
diff --git a/ltable.c b/ltable.c
index d436cf6e..ddda9a44 100644
--- a/ltable.c
+++ b/ltable.c
@@ -350,9 +350,10 @@ int luaH_next (lua_State *L, Table *t, StkId key) {
350 unsigned int asize = luaH_realasize(t); 350 unsigned int asize = luaH_realasize(t);
351 unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */ 351 unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */
352 for (; i < asize; i++) { /* try first array part */ 352 for (; i < asize; i++) { /* try first array part */
353 if (!isempty(&t->array[i])) { /* a non-empty entry? */ 353 int tag = *getArrTag(t, i + 1);
354 if (!tagisempty(tag)) { /* a non-empty entry? */
354 setivalue(s2v(key), i + 1); 355 setivalue(s2v(key), i + 1);
355 setobj2s(L, key + 1, &t->array[i]); 356 farr2val(t, i + 1, tag, s2v(key + 1));
356 return 1; 357 return 1;
357 } 358 }
358 } 359 }
@@ -375,6 +376,41 @@ static void freehash (lua_State *L, Table *t) {
375 376
376 377
377/* 378/*
379** Check whether an integer key is in the array part. If 'alimit' is
380** not the real size of the array, the key still can be in the array
381** part. In this case, do the "Xmilia trick" to check whether 'key-1'
382** is smaller than the real size.
383** The trick works as follow: let 'p' be an integer such that
384** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'.
385** That is, 2^(p+1) is the real size of the array, and 'p' is the highest
386** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'.
387** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will
388** have the 'p' bit cleared. If the key is outside the array, that is,
389** 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than 'p',
390** therefore it will be larger or equal to 'alimit', and the check
391** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than
392** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
393** than 2^p, therefore smaller than 'alimit', and the check succeeds.
394** As special cases, when 'alimit' is 0 the condition is trivially false,
395** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
396** If key is 0 or negative, 'res' will have its higher bit on, so that
397** if cannot be smaller than alimit.
398*/
399static int keyinarray (Table *t, lua_Integer key) {
400 lua_Unsigned alimit = t->alimit;
401 if (l_castS2U(key) - 1u < alimit) /* 'key' in [1, t->alimit]? */
402 return 1;
403 else if (!isrealasize(t) && /* key still may be in the array part? */
404 (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
405 t->alimit = cast_uint(key); /* probably '#t' is here now */
406 return 1;
407 }
408 else
409 return 0;
410}
411
412
413/*
378** {============================================================= 414** {=============================================================
379** Rehash 415** Rehash
380** ============================================================== 416** ==============================================================
@@ -421,6 +457,12 @@ static int countint (lua_Integer key, unsigned int *nums) {
421} 457}
422 458
423 459
460l_sinline int arraykeyisempty (const Table *t, lua_Integer key) {
461 int tag = *getArrTag(t, key);
462 return tagisempty(tag);
463}
464
465
424/* 466/*
425** Count keys in array part of table 't': Fill 'nums[i]' with 467** Count keys in array part of table 't': Fill 'nums[i]' with
426** number of keys that will go into corresponding slice and return 468** number of keys that will go into corresponding slice and return
@@ -443,7 +485,7 @@ static unsigned int numusearray (const Table *t, unsigned int *nums) {
443 } 485 }
444 /* count elements in range (2^(lg - 1), 2^lg] */ 486 /* count elements in range (2^(lg - 1), 2^lg] */
445 for (; i <= lim; i++) { 487 for (; i <= lim; i++) {
446 if (!isempty(&t->array[i-1])) 488 if (!arraykeyisempty(t, i))
447 lc++; 489 lc++;
448 } 490 }
449 nums[lg] += lc; 491 nums[lg] += lc;
@@ -555,7 +597,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
555 unsigned int i; 597 unsigned int i;
556 Table newt; /* to keep the new hash part */ 598 Table newt; /* to keep the new hash part */
557 unsigned int oldasize = setlimittosize(t); 599 unsigned int oldasize = setlimittosize(t);
558 TValue *newarray; 600 ArrayCell *newarray;
559 /* create new hash part with appropriate size into 'newt' */ 601 /* create new hash part with appropriate size into 'newt' */
560 setnodevector(L, &newt, nhsize); 602 setnodevector(L, &newt, nhsize);
561 if (newasize < oldasize) { /* will array shrink? */ 603 if (newasize < oldasize) { /* will array shrink? */
@@ -563,14 +605,18 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
563 exchangehashpart(t, &newt); /* and new hash */ 605 exchangehashpart(t, &newt); /* and new hash */
564 /* re-insert into the new hash the elements from vanishing slice */ 606 /* re-insert into the new hash the elements from vanishing slice */
565 for (i = newasize; i < oldasize; i++) { 607 for (i = newasize; i < oldasize; i++) {
566 if (!isempty(&t->array[i])) 608 int tag = *getArrTag(t, i + 1);
567 luaH_setint(L, t, i + 1, &t->array[i]); 609 if (!tagisempty(tag)) { /* a non-empty entry? */
610 TValue aux;
611 farr2val(t, i + 1, tag, &aux);
612 luaH_setint(L, t, i + 1, &aux);
613 }
568 } 614 }
569 t->alimit = oldasize; /* restore current size... */ 615 t->alimit = oldasize; /* restore current size... */
570 exchangehashpart(t, &newt); /* and hash (in case of errors) */ 616 exchangehashpart(t, &newt); /* and hash (in case of errors) */
571 } 617 }
572 /* allocate new array */ 618 /* allocate new array */
573 newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue); 619 newarray = luaM_reallocvector(L, t->array, oldasize, newasize, ArrayCell);
574 if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ 620 if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */
575 freehash(L, &newt); /* release new hash part */ 621 freehash(L, &newt); /* release new hash part */
576 luaM_error(L); /* raise error (with array unchanged) */ 622 luaM_error(L); /* raise error (with array unchanged) */
@@ -580,7 +626,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
580 t->array = newarray; /* set new array part */ 626 t->array = newarray; /* set new array part */
581 t->alimit = newasize; 627 t->alimit = newasize;
582 for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ 628 for (i = oldasize; i < newasize; i++) /* clear new slice of the array */
583 setempty(&t->array[i]); 629 *getArrTag(t, i + 1) = LUA_VEMPTY;
584 /* re-insert elements from old hash part into new parts */ 630 /* re-insert elements from old hash part into new parts */
585 reinsert(L, &newt, t); /* 'newt' now has the old hash */ 631 reinsert(L, &newt, t); /* 'newt' now has the old hash */
586 freehash(L, &newt); /* free old hash part */ 632 freehash(L, &newt); /* free old hash part */
@@ -719,41 +765,6 @@ void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value) {
719} 765}
720 766
721 767
722/*
723** Check whether key is in the array part. If 'alimit' is not the real
724** size of the array, the key still can be in the array part. In this
725** case, do the "Xmilia trick" to check whether 'key-1' is smaller than
726** the real size.
727** The trick works as follow: let 'p' be an integer such that
728** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'.
729** That is, 2^(p+1) is the real size of the array, and 'p' is the highest
730** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'.
731** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will
732** have the 'p' bit cleared. If the key is outside the array, that is,
733** 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than 'p',
734** therefore it will be larger or equal to 'alimit', and the check
735** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than
736** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
737** than 2^p, therefore smaller than 'alimit', and the check succeeds.
738** As special cases, when 'alimit' is 0 the condition is trivially false,
739** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
740** If key is 0 or negative, 'res' will have its higher bit on, so that
741** if cannot be smaller than alimit.
742*/
743static int keyinarray (Table *t, lua_Integer key) {
744 lua_Unsigned alimit = t->alimit;
745 if (l_castS2U(key) - 1u < alimit) /* 'key' in [1, t->alimit]? */
746 return 1;
747 else if (!isrealasize(t) && /* key still may be in the array part? */
748 (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
749 t->alimit = cast_uint(key); /* probably '#t' is here now */
750 return 1;
751 }
752 else
753 return 0;
754}
755
756
757static const TValue *getintfromhash (Table *t, lua_Integer key) { 768static const TValue *getintfromhash (Table *t, lua_Integer key) {
758 Node *n = hashint(t, key); 769 Node *n = hashint(t, key);
759 lua_assert(l_castS2U(key) - 1u >= luaH_realasize(t)); 770 lua_assert(l_castS2U(key) - 1u >= luaH_realasize(t));
@@ -770,15 +781,8 @@ static const TValue *getintfromhash (Table *t, lua_Integer key) {
770} 781}
771 782
772 783
773l_sinline int arraykeyisempty (Table *t, lua_Integer key) {
774 int tag = *getArrTag(t, key);
775 return tagisempty(tag);
776}
777
778
779static int hashkeyisempty (Table *t, lua_Integer key) { 784static int hashkeyisempty (Table *t, lua_Integer key) {
780 const TValue *val = getintfromhash(t, key); 785 const TValue *val = getintfromhash(t, key);
781 lua_assert(!keyinarray(t, key));
782 return isempty(val); 786 return isempty(val);
783} 787}
784 788
@@ -797,7 +801,7 @@ int luaH_getint (Table *t, lua_Integer key, TValue *res) {
797 if (keyinarray(t, key)) { 801 if (keyinarray(t, key)) {
798 int tag = *getArrTag(t, key); 802 int tag = *getArrTag(t, key);
799 if (!tagisempty(tag)) { 803 if (!tagisempty(tag)) {
800 arr2val(t, key, tag, res); 804 farr2val(t, key, tag, res);
801 return HOK; /* success */ 805 return HOK; /* success */
802 } 806 }
803 else 807 else
@@ -900,7 +904,7 @@ int luaH_psetint (Table *t, lua_Integer key, TValue *val) {
900 if (keyinarray(t, key)) { 904 if (keyinarray(t, key)) {
901 lu_byte *tag = getArrTag(t, key); 905 lu_byte *tag = getArrTag(t, key);
902 if (!tagisempty(*tag)) { 906 if (!tagisempty(*tag)) {
903 val2arr(t, key, tag, val); 907 fval2arr(t, key, tag, val);
904 return HOK; /* success */ 908 return HOK; /* success */
905 } 909 }
906 else 910 else
@@ -956,7 +960,7 @@ void luaH_finishset (lua_State *L, Table *t, const TValue *key,
956 } 960 }
957 else { /* array entry */ 961 else { /* array entry */
958 hres = ~hres; /* real index */ 962 hres = ~hres; /* real index */
959 val2arr(t, hres, getArrTag(t, hres), value); 963 fval2arr(t, hres, getArrTag(t, hres), value);
960 } 964 }
961} 965}
962 966
@@ -1087,11 +1091,11 @@ lua_Unsigned luaH_getn (Table *t) {
1087 /* 'limit' is zero or present in table */ 1091 /* 'limit' is zero or present in table */
1088 if (!limitequalsasize(t)) { /* (2)? */ 1092 if (!limitequalsasize(t)) { /* (2)? */
1089 /* 'limit' > 0 and array has more elements after 'limit' */ 1093 /* 'limit' > 0 and array has more elements after 'limit' */
1090 if (isempty(&t->array[limit])) /* 'limit + 1' is empty? */ 1094 if (arraykeyisempty(t, limit + 1)) /* 'limit + 1' is empty? */
1091 return limit; /* this is the boundary */ 1095 return limit; /* this is the boundary */
1092 /* else, try last element in the array */ 1096 /* else, try last element in the array */
1093 limit = luaH_realasize(t); 1097 limit = luaH_realasize(t);
1094 if (isempty(&t->array[limit - 1])) { /* empty? */ 1098 if (arraykeyisempty(t, limit)) { /* empty? */
1095 /* there must be a boundary in the array after old limit, 1099 /* there must be a boundary in the array after old limit,
1096 and it must be a valid new limit */ 1100 and it must be a valid new limit */
1097 unsigned int boundary = binsearch(t, t->alimit, limit); 1101 unsigned int boundary = binsearch(t, t->alimit, limit);
@@ -1102,7 +1106,7 @@ lua_Unsigned luaH_getn (Table *t) {
1102 } 1106 }
1103 /* (3) 'limit' is the last element and either is zero or present in table */ 1107 /* (3) 'limit' is the last element and either is zero or present in table */
1104 lua_assert(limit == luaH_realasize(t) && 1108 lua_assert(limit == luaH_realasize(t) &&
1105 (limit == 0 || !isempty(&t->array[limit - 1]))); 1109 (limit == 0 || !arraykeyisempty(t, limit)));
1106 if (isdummy(t) || hashkeyisempty(t, cast(lua_Integer, limit + 1))) 1110 if (isdummy(t) || hashkeyisempty(t, cast(lua_Integer, limit + 1)))
1107 return limit; /* 'limit + 1' is absent */ 1111 return limit; /* 'limit + 1' is absent */
1108 else /* 'limit + 1' is also present */ 1112 else /* 'limit + 1' is also present */