aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2023-11-07 17:26:15 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2023-11-07 17:26:15 -0300
commit37c215b43f27a1c41e8a920987e1c3bd7b34330d (patch)
treef14f4417384cffb9d2e5ef3c09621555a5d1e9a2 /ltable.c
parent9e99f3071d07767f9e882c4abf3537f75ce2d161 (diff)
parentfa075b79530af1cbc977349f2e467d69ce01202c (diff)
downloadlua-37c215b43f27a1c41e8a920987e1c3bd7b34330d.tar.gz
lua-37c215b43f27a1c41e8a920987e1c3bd7b34330d.tar.bz2
lua-37c215b43f27a1c41e8a920987e1c3bd7b34330d.zip
Merge branch 'newarray' into nextversion
Diffstat (limited to 'ltable.c')
-rw-r--r--ltable.c328
1 files changed, 244 insertions, 84 deletions
diff --git a/ltable.c b/ltable.c
index 103478fb..c9f66b3c 100644
--- a/ltable.c
+++ b/ltable.c
@@ -371,9 +371,10 @@ int luaH_next (lua_State *L, Table *t, StkId key) {
371 unsigned int asize = luaH_realasize(t); 371 unsigned int asize = luaH_realasize(t);
372 unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */ 372 unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */
373 for (; i < asize; i++) { /* try first array part */ 373 for (; i < asize; i++) { /* try first array part */
374 if (!isempty(&t->array[i])) { /* a non-empty entry? */ 374 int tag = *getArrTag(t, i);
375 if (!tagisempty(tag)) { /* a non-empty entry? */
375 setivalue(s2v(key), i + 1); 376 setivalue(s2v(key), i + 1);
376 setobj2s(L, key + 1, &t->array[i]); 377 farr2val(t, i + 1, tag, s2v(key + 1));
377 return 1; 378 return 1;
378 } 379 }
379 } 380 }
@@ -403,6 +404,41 @@ static void freehash (lua_State *L, Table *t) {
403 404
404 405
405/* 406/*
407** Check whether an integer key is in the array part. If 'alimit' is
408** not the real size of the array, the key still can be in the array
409** part. In this case, do the "Xmilia trick" to check whether 'key-1'
410** is smaller than the real size.
411** The trick works as follow: let 'p' be an integer such that
412** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'.
413** That is, 2^(p+1) is the real size of the array, and 'p' is the highest
414** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'.
415** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will
416** have the 'p' bit cleared. If the key is outside the array, that is,
417** 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than 'p',
418** therefore it will be larger or equal to 'alimit', and the check
419** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than
420** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
421** than 2^p, therefore smaller than 'alimit', and the check succeeds.
422** As special cases, when 'alimit' is 0 the condition is trivially false,
423** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
424** If key is 0 or negative, 'res' will have its higher bit on, so that
425** if cannot be smaller than alimit.
426*/
427static int keyinarray (Table *t, lua_Integer key) {
428 lua_Unsigned alimit = t->alimit;
429 if (l_castS2U(key) - 1u < alimit) /* 'key' in [1, t->alimit]? */
430 return 1;
431 else if (!isrealasize(t) && /* key still may be in the array part? */
432 (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
433 t->alimit = cast_uint(key); /* probably '#t' is here now */
434 return 1;
435 }
436 else
437 return 0;
438}
439
440
441/*
406** {============================================================= 442** {=============================================================
407** Rehash 443** Rehash
408** ============================================================== 444** ==============================================================
@@ -449,6 +485,12 @@ static int countint (lua_Integer key, unsigned int *nums) {
449} 485}
450 486
451 487
488l_sinline int arraykeyisempty (const Table *t, lua_Integer key) {
489 int tag = *getArrTag(t, key - 1);
490 return tagisempty(tag);
491}
492
493
452/* 494/*
453** Count keys in array part of table 't': Fill 'nums[i]' with 495** Count keys in array part of table 't': Fill 'nums[i]' with
454** number of keys that will go into corresponding slice and return 496** number of keys that will go into corresponding slice and return
@@ -471,7 +513,7 @@ static unsigned int numusearray (const Table *t, unsigned int *nums) {
471 } 513 }
472 /* count elements in range (2^(lg - 1), 2^lg] */ 514 /* count elements in range (2^(lg - 1), 2^lg] */
473 for (; i <= lim; i++) { 515 for (; i <= lim; i++) {
474 if (!isempty(&t->array[i-1])) 516 if (!arraykeyisempty(t, i))
475 lc++; 517 lc++;
476 } 518 }
477 nums[lg] += lc; 519 nums[lg] += lc;
@@ -499,6 +541,33 @@ static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
499 541
500 542
501/* 543/*
544** Convert an "abstract size" (number of values in an array) to
545** "concrete size" (number of cell elements in the array). Cells
546** do not need to be full; we only must make sure it has the values
547** needed and its 'tag' element. So, we compute the concrete tag index
548** and the concrete value index of the last element, get their maximum
549** and adds 1.
550*/
551static unsigned int concretesize (unsigned int size) {
552 if (size == 0) return 0;
553 else {
554 unsigned int ts = TagIndex(size - 1);
555 unsigned int vs = ValueIndex(size - 1);
556 return ((ts >= vs) ? ts : vs) + 1;
557 }
558}
559
560
561static ArrayCell *resizearray (lua_State *L , Table *t,
562 unsigned int oldasize,
563 unsigned int newasize) {
564 oldasize = concretesize(oldasize);
565 newasize = concretesize(newasize);
566 return luaM_reallocvector(L, t->array, oldasize, newasize, ArrayCell);
567}
568
569
570/*
502** Creates an array for the hash part of a table with the given 571** Creates an array for the hash part of a table with the given
503** size, or reuses the dummy node if size is zero. 572** size, or reuses the dummy node if size is zero.
504** The computation for size overflow is in two steps: the first 573** The computation for size overflow is in two steps: the first
@@ -593,7 +662,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
593 unsigned int i; 662 unsigned int i;
594 Table newt; /* to keep the new hash part */ 663 Table newt; /* to keep the new hash part */
595 unsigned int oldasize = setlimittosize(t); 664 unsigned int oldasize = setlimittosize(t);
596 TValue *newarray; 665 ArrayCell *newarray;
597 /* create new hash part with appropriate size into 'newt' */ 666 /* create new hash part with appropriate size into 'newt' */
598 newt.flags = 0; 667 newt.flags = 0;
599 setnodevector(L, &newt, nhsize); 668 setnodevector(L, &newt, nhsize);
@@ -602,14 +671,18 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
602 exchangehashpart(t, &newt); /* and new hash */ 671 exchangehashpart(t, &newt); /* and new hash */
603 /* re-insert into the new hash the elements from vanishing slice */ 672 /* re-insert into the new hash the elements from vanishing slice */
604 for (i = newasize; i < oldasize; i++) { 673 for (i = newasize; i < oldasize; i++) {
605 if (!isempty(&t->array[i])) 674 int tag = *getArrTag(t, i);
606 luaH_setint(L, t, i + 1, &t->array[i]); 675 if (!tagisempty(tag)) { /* a non-empty entry? */
676 TValue aux;
677 farr2val(t, i + 1, tag, &aux);
678 luaH_setint(L, t, i + 1, &aux);
679 }
607 } 680 }
608 t->alimit = oldasize; /* restore current size... */ 681 t->alimit = oldasize; /* restore current size... */
609 exchangehashpart(t, &newt); /* and hash (in case of errors) */ 682 exchangehashpart(t, &newt); /* and hash (in case of errors) */
610 } 683 }
611 /* allocate new array */ 684 /* allocate new array */
612 newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue); 685 newarray = resizearray(L, t, oldasize, newasize);
613 if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ 686 if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */
614 freehash(L, &newt); /* release new hash part */ 687 freehash(L, &newt); /* release new hash part */
615 luaM_error(L); /* raise error (with array unchanged) */ 688 luaM_error(L); /* raise error (with array unchanged) */
@@ -619,7 +692,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
619 t->array = newarray; /* set new array part */ 692 t->array = newarray; /* set new array part */
620 t->alimit = newasize; 693 t->alimit = newasize;
621 for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ 694 for (i = oldasize; i < newasize; i++) /* clear new slice of the array */
622 setempty(&t->array[i]); 695 *getArrTag(t, i) = LUA_VEMPTY;
623 /* re-insert elements from old hash part into new parts */ 696 /* re-insert elements from old hash part into new parts */
624 reinsert(L, &newt, t); /* 'newt' now has the old hash */ 697 reinsert(L, &newt, t); /* 'newt' now has the old hash */
625 freehash(L, &newt); /* free old hash part */ 698 freehash(L, &newt); /* free old hash part */
@@ -675,8 +748,9 @@ Table *luaH_new (lua_State *L) {
675 748
676 749
677void luaH_free (lua_State *L, Table *t) { 750void luaH_free (lua_State *L, Table *t) {
751 unsigned ps = concretesize(luaH_realasize(t));
678 freehash(L, t); 752 freehash(L, t);
679 luaM_freearray(L, t->array, luaH_realasize(t)); 753 luaM_freearray(L, t->array, ps);
680 luaM_free(L, t); 754 luaM_free(L, t);
681} 755}
682 756
@@ -770,57 +844,57 @@ static void luaH_newkey (lua_State *L, Table *t, const TValue *key,
770} 844}
771 845
772 846
773/* 847static const TValue *getintfromhash (Table *t, lua_Integer key) {
774** Search function for integers. If integer is inside 'alimit', get it 848 Node *n = hashint(t, key);
775** directly from the array part. Otherwise, if 'alimit' is not 849 lua_assert(l_castS2U(key) - 1u >= luaH_realasize(t));
776** the real size of the array, the key still can be in the array part. 850 for (;;) { /* check whether 'key' is somewhere in the chain */
777** In this case, do the "Xmilia trick" to check whether 'key-1' is 851 if (keyisinteger(n) && keyival(n) == key)
778** smaller than the real size. 852 return gval(n); /* that's it */
779** The trick works as follow: let 'p' be an integer such that 853 else {
780** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'. 854 int nx = gnext(n);
781** That is, 2^(p+1) is the real size of the array, and 'p' is the highest 855 if (nx == 0) break;
782** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'. 856 n += nx;
783** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will 857 }
784** have the 'p' bit cleared. If the key is outside the array, that is,
785** 'key-1 >= 2^(p+1)', then 'res' will have some bit on higher than 'p',
786** therefore it will be larger or equal to 'alimit', and the check
787** will fail. If 'key-1 < 2^(p+1)', then 'res' has no bit on higher than
788** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
789** than 2^p, therefore smaller than 'alimit', and the check succeeds.
790** As special cases, when 'alimit' is 0 the condition is trivially false,
791** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
792** If key is 0 or negative, 'res' will have its higher bit on, so that
793** if cannot be smaller than alimit.
794*/
795const TValue *luaH_getint (Table *t, lua_Integer key) {
796 lua_Unsigned alimit = t->alimit;
797 if (l_castS2U(key) - 1u < alimit) /* 'key' in [1, t->alimit]? */
798 return &t->array[key - 1];
799 else if (!isrealasize(t) && /* key still may be in the array part? */
800 (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
801 t->alimit = cast_uint(key); /* probably '#t' is here now */
802 return &t->array[key - 1];
803 } 858 }
804 else { /* key is not in the array part; check the hash */ 859 return &absentkey;
805 Node *n = hashint(t, key); 860}
806 for (;;) { /* check whether 'key' is somewhere in the chain */ 861
807 if (keyisinteger(n) && keyival(n) == key) 862
808 return gval(n); /* that's it */ 863static int hashkeyisempty (Table *t, lua_Integer key) {
809 else { 864 const TValue *val = getintfromhash(t, key);
810 int nx = gnext(n); 865 return isempty(val);
811 if (nx == 0) break; 866}
812 n += nx; 867
813 } 868
869static int finishnodeget (const TValue *val, TValue *res) {
870 if (!ttisnil(val)) {
871 setobj(((lua_State*)NULL), res, val);
872 return HOK; /* success */
873 }
874 else
875 return HNOTFOUND; /* could not get value */
876}
877
878
879int luaH_getint (Table *t, lua_Integer key, TValue *res) {
880 if (keyinarray(t, key)) {
881 int tag = *getArrTag(t, key - 1);
882 if (!tagisempty(tag)) {
883 farr2val(t, key, tag, res);
884 return HOK; /* success */
814 } 885 }
815 return &absentkey; 886 else
887 return ~cast_int(key); /* empty slot in the array part */
816 } 888 }
889 else
890 return finishnodeget(getintfromhash(t, key), res);
817} 891}
818 892
819 893
820/* 894/*
821** search function for short strings 895** search function for short strings
822*/ 896*/
823const TValue *luaH_getshortstr (Table *t, TString *key) { 897const TValue *luaH_Hgetshortstr (Table *t, TString *key) {
824 Node *n = hashstr(t, key); 898 Node *n = hashstr(t, key);
825 lua_assert(key->tt == LUA_VSHRSTR); 899 lua_assert(key->tt == LUA_VSHRSTR);
826 for (;;) { /* check whether 'key' is somewhere in the chain */ 900 for (;;) { /* check whether 'key' is somewhere in the chain */
@@ -836,9 +910,14 @@ const TValue *luaH_getshortstr (Table *t, TString *key) {
836} 910}
837 911
838 912
839const TValue *luaH_getstr (Table *t, TString *key) { 913int luaH_getshortstr (Table *t, TString *key, TValue *res) {
914 return finishnodeget(luaH_Hgetshortstr(t, key), res);
915}
916
917
918static const TValue *Hgetstr (Table *t, TString *key) {
840 if (key->tt == LUA_VSHRSTR) 919 if (key->tt == LUA_VSHRSTR)
841 return luaH_getshortstr(t, key); 920 return luaH_Hgetshortstr(t, key);
842 else { /* for long strings, use generic case */ 921 else { /* for long strings, use generic case */
843 TValue ko; 922 TValue ko;
844 setsvalue(cast(lua_State *, NULL), &ko, key); 923 setsvalue(cast(lua_State *, NULL), &ko, key);
@@ -847,38 +926,121 @@ const TValue *luaH_getstr (Table *t, TString *key) {
847} 926}
848 927
849 928
929int luaH_getstr (Table *t, TString *key, TValue *res) {
930 return finishnodeget(Hgetstr(t, key), res);
931}
932
933
934TString *luaH_getstrkey (Table *t, TString *key) {
935 const TValue *o = Hgetstr(t, key);
936 if (!isabstkey(o)) /* string already present? */
937 return keystrval(nodefromval(o)); /* get saved copy */
938 else
939 return NULL;
940}
941
942
850/* 943/*
851** main search function 944** main search function
852*/ 945*/
853const TValue *luaH_get (Table *t, const TValue *key) { 946int luaH_get (Table *t, const TValue *key, TValue *res) {
947 const TValue *slot;
854 switch (ttypetag(key)) { 948 switch (ttypetag(key)) {
855 case LUA_VSHRSTR: return luaH_getshortstr(t, tsvalue(key)); 949 case LUA_VSHRSTR:
856 case LUA_VNUMINT: return luaH_getint(t, ivalue(key)); 950 slot = luaH_Hgetshortstr(t, tsvalue(key));
857 case LUA_VNIL: return &absentkey; 951 break;
952 case LUA_VNUMINT:
953 return luaH_getint(t, ivalue(key), res);
954 case LUA_VNIL:
955 slot = &absentkey;
956 break;
858 case LUA_VNUMFLT: { 957 case LUA_VNUMFLT: {
859 lua_Integer k; 958 lua_Integer k;
860 if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */ 959 if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */
861 return luaH_getint(t, k); /* use specialized version */ 960 return luaH_getint(t, k, res); /* use specialized version */
862 /* else... */ 961 /* else... */
863 } /* FALLTHROUGH */ 962 } /* FALLTHROUGH */
864 default: 963 default:
865 return getgeneric(t, key, 0); 964 slot = getgeneric(t, key, 0);
965 break;
866 } 966 }
967 return finishnodeget(slot, res);
867} 968}
868 969
869 970
971static int finishnodeset (Table *t, const TValue *slot, TValue *val) {
972 if (!ttisnil(slot)) {
973 setobj(((lua_State*)NULL), cast(TValue*, slot), val);
974 return HOK; /* success */
975 }
976 else if (isabstkey(slot))
977 return HNOTFOUND; /* no slot with that key */
978 else return (cast(Node*, slot) - t->node) + HFIRSTNODE; /* node encoded */
979}
980
981
982int luaH_psetint (Table *t, lua_Integer key, TValue *val) {
983 if (keyinarray(t, key)) {
984 lu_byte *tag = getArrTag(t, key - 1);
985 if (!tagisempty(*tag)) {
986 fval2arr(t, key, tag, val);
987 return HOK; /* success */
988 }
989 else
990 return ~cast_int(key); /* empty slot in the array part */
991 }
992 else
993 return finishnodeset(t, getintfromhash(t, key), val);
994}
995
996
997int luaH_psetshortstr (Table *t, TString *key, TValue *val) {
998 return finishnodeset(t, luaH_Hgetshortstr(t, key), val);
999}
1000
1001
1002int luaH_psetstr (Table *t, TString *key, TValue *val) {
1003 return finishnodeset(t, Hgetstr(t, key), val);
1004}
1005
1006
1007int luaH_pset (Table *t, const TValue *key, TValue *val) {
1008 switch (ttypetag(key)) {
1009 case LUA_VSHRSTR: return luaH_psetshortstr(t, tsvalue(key), val);
1010 case LUA_VNUMINT: return luaH_psetint(t, ivalue(key), val);
1011 case LUA_VNIL: return HNOTFOUND;
1012 case LUA_VNUMFLT: {
1013 lua_Integer k;
1014 if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */
1015 return luaH_psetint(t, k, val); /* use specialized version */
1016 /* else... */
1017 } /* FALLTHROUGH */
1018 default:
1019 return finishnodeset(t, getgeneric(t, key, 0), val);
1020 }
1021}
1022
870/* 1023/*
871** Finish a raw "set table" operation, where 'slot' is where the value 1024** Finish a raw "set table" operation, where 'slot' is where the value
872** should have been (the result of a previous "get table"). 1025** should have been (the result of a previous "get table").
873** Beware: when using this function you probably need to check a GC 1026** Beware: when using this function you probably need to check a GC
874** barrier and invalidate the TM cache. 1027** barrier and invalidate the TM cache.
875*/ 1028*/
1029
1030
876void luaH_finishset (lua_State *L, Table *t, const TValue *key, 1031void luaH_finishset (lua_State *L, Table *t, const TValue *key,
877 const TValue *slot, TValue *value) { 1032 TValue *value, int hres) {
878 if (isabstkey(slot)) 1033 lua_assert(hres != HOK);
1034 if (hres == HNOTFOUND) {
879 luaH_newkey(L, t, key, value); 1035 luaH_newkey(L, t, key, value);
880 else 1036 }
881 setobj2t(L, cast(TValue *, slot), value); 1037 else if (hres > 0) { /* regular Node? */
1038 setobj2t(L, gval(gnode(t, hres - HFIRSTNODE)), value);
1039 }
1040 else { /* array entry */
1041 hres = ~hres; /* real index */
1042 obj2arr(t, hres, value);
1043 }
882} 1044}
883 1045
884 1046
@@ -887,20 +1049,19 @@ void luaH_finishset (lua_State *L, Table *t, const TValue *key,
887** barrier and invalidate the TM cache. 1049** barrier and invalidate the TM cache.
888*/ 1050*/
889void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) { 1051void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) {
890 const TValue *slot = luaH_get(t, key); 1052 int hres = luaH_pset(t, key, value);
891 luaH_finishset(L, t, key, slot, value); 1053 if (hres != HOK)
1054 luaH_finishset(L, t, key, value, hres);
892} 1055}
893 1056
894 1057
895void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { 1058void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
896 const TValue *p = luaH_getint(t, key); 1059 int hres = luaH_psetint(t, key, value);
897 if (isabstkey(p)) { 1060 if (hres != HOK) {
898 TValue k; 1061 TValue k;
899 setivalue(&k, key); 1062 setivalue(&k, key);
900 luaH_newkey(L, t, &k, value); 1063 luaH_finishset(L, t, &k, value, hres);
901 } 1064 }
902 else
903 setobj2t(L, cast(TValue *, p), value);
904} 1065}
905 1066
906 1067
@@ -926,27 +1087,26 @@ static lua_Unsigned hash_search (Table *t, lua_Unsigned j) {
926 j *= 2; 1087 j *= 2;
927 else { 1088 else {
928 j = LUA_MAXINTEGER; 1089 j = LUA_MAXINTEGER;
929 if (isempty(luaH_getint(t, j))) /* t[j] not present? */ 1090 if (hashkeyisempty(t, j)) /* t[j] not present? */
930 break; /* 'j' now is an absent index */ 1091 break; /* 'j' now is an absent index */
931 else /* weird case */ 1092 else /* weird case */
932 return j; /* well, max integer is a boundary... */ 1093 return j; /* well, max integer is a boundary... */
933 } 1094 }
934 } while (!isempty(luaH_getint(t, j))); /* repeat until an absent t[j] */ 1095 } while (!hashkeyisempty(t, j)); /* repeat until an absent t[j] */
935 /* i < j && t[i] present && t[j] absent */ 1096 /* i < j && t[i] present && t[j] absent */
936 while (j - i > 1u) { /* do a binary search between them */ 1097 while (j - i > 1u) { /* do a binary search between them */
937 lua_Unsigned m = (i + j) / 2; 1098 lua_Unsigned m = (i + j) / 2;
938 if (isempty(luaH_getint(t, m))) j = m; 1099 if (hashkeyisempty(t, m)) j = m;
939 else i = m; 1100 else i = m;
940 } 1101 }
941 return i; 1102 return i;
942} 1103}
943 1104
944 1105
945static unsigned int binsearch (const TValue *array, unsigned int i, 1106static unsigned int binsearch (Table *array, unsigned int i, unsigned int j) {
946 unsigned int j) {
947 while (j - i > 1u) { /* binary search */ 1107 while (j - i > 1u) { /* binary search */
948 unsigned int m = (i + j) / 2; 1108 unsigned int m = (i + j) / 2;
949 if (isempty(&array[m - 1])) j = m; 1109 if (arraykeyisempty(array, m)) j = m;
950 else i = m; 1110 else i = m;
951 } 1111 }
952 return i; 1112 return i;
@@ -987,9 +1147,9 @@ static unsigned int binsearch (const TValue *array, unsigned int i,
987*/ 1147*/
988lua_Unsigned luaH_getn (Table *t) { 1148lua_Unsigned luaH_getn (Table *t) {
989 unsigned int limit = t->alimit; 1149 unsigned int limit = t->alimit;
990 if (limit > 0 && isempty(&t->array[limit - 1])) { /* (1)? */ 1150 if (limit > 0 && arraykeyisempty(t, limit)) { /* (1)? */
991 /* there must be a boundary before 'limit' */ 1151 /* there must be a boundary before 'limit' */
992 if (limit >= 2 && !isempty(&t->array[limit - 2])) { 1152 if (limit >= 2 && !arraykeyisempty(t, limit - 1)) {
993 /* 'limit - 1' is a boundary; can it be a new limit? */ 1153 /* 'limit - 1' is a boundary; can it be a new limit? */
994 if (ispow2realasize(t) && !ispow2(limit - 1)) { 1154 if (ispow2realasize(t) && !ispow2(limit - 1)) {
995 t->alimit = limit - 1; 1155 t->alimit = limit - 1;
@@ -998,7 +1158,7 @@ lua_Unsigned luaH_getn (Table *t) {
998 return limit - 1; 1158 return limit - 1;
999 } 1159 }
1000 else { /* must search for a boundary in [0, limit] */ 1160 else { /* must search for a boundary in [0, limit] */
1001 unsigned int boundary = binsearch(t->array, 0, limit); 1161 unsigned int boundary = binsearch(t, 0, limit);
1002 /* can this boundary represent the real size of the array? */ 1162 /* can this boundary represent the real size of the array? */
1003 if (ispow2realasize(t) && boundary > luaH_realasize(t) / 2) { 1163 if (ispow2realasize(t) && boundary > luaH_realasize(t) / 2) {
1004 t->alimit = boundary; /* use it as the new limit */ 1164 t->alimit = boundary; /* use it as the new limit */
@@ -1010,14 +1170,14 @@ lua_Unsigned luaH_getn (Table *t) {
1010 /* 'limit' is zero or present in table */ 1170 /* 'limit' is zero or present in table */
1011 if (!limitequalsasize(t)) { /* (2)? */ 1171 if (!limitequalsasize(t)) { /* (2)? */
1012 /* 'limit' > 0 and array has more elements after 'limit' */ 1172 /* 'limit' > 0 and array has more elements after 'limit' */
1013 if (isempty(&t->array[limit])) /* 'limit + 1' is empty? */ 1173 if (arraykeyisempty(t, limit + 1)) /* 'limit + 1' is empty? */
1014 return limit; /* this is the boundary */ 1174 return limit; /* this is the boundary */
1015 /* else, try last element in the array */ 1175 /* else, try last element in the array */
1016 limit = luaH_realasize(t); 1176 limit = luaH_realasize(t);
1017 if (isempty(&t->array[limit - 1])) { /* empty? */ 1177 if (arraykeyisempty(t, limit)) { /* empty? */
1018 /* there must be a boundary in the array after old limit, 1178 /* there must be a boundary in the array after old limit,
1019 and it must be a valid new limit */ 1179 and it must be a valid new limit */
1020 unsigned int boundary = binsearch(t->array, t->alimit, limit); 1180 unsigned int boundary = binsearch(t, t->alimit, limit);
1021 t->alimit = boundary; 1181 t->alimit = boundary;
1022 return boundary; 1182 return boundary;
1023 } 1183 }
@@ -1025,8 +1185,8 @@ lua_Unsigned luaH_getn (Table *t) {
1025 } 1185 }
1026 /* (3) 'limit' is the last element and either is zero or present in table */ 1186 /* (3) 'limit' is the last element and either is zero or present in table */
1027 lua_assert(limit == luaH_realasize(t) && 1187 lua_assert(limit == luaH_realasize(t) &&
1028 (limit == 0 || !isempty(&t->array[limit - 1]))); 1188 (limit == 0 || !arraykeyisempty(t, limit)));
1029 if (isdummy(t) || isempty(luaH_getint(t, cast(lua_Integer, limit + 1)))) 1189 if (isdummy(t) || hashkeyisempty(t, cast(lua_Integer, limit + 1)))
1030 return limit; /* 'limit + 1' is absent */ 1190 return limit; /* 'limit + 1' is absent */
1031 else /* 'limit + 1' is also present */ 1191 else /* 'limit + 1' is also present */
1032 return hash_search(t, limit); 1192 return hash_search(t, limit);