diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2023-11-07 17:26:15 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2023-11-07 17:26:15 -0300 |
commit | 37c215b43f27a1c41e8a920987e1c3bd7b34330d (patch) | |
tree | f14f4417384cffb9d2e5ef3c09621555a5d1e9a2 /ltable.c | |
parent | 9e99f3071d07767f9e882c4abf3537f75ce2d161 (diff) | |
parent | fa075b79530af1cbc977349f2e467d69ce01202c (diff) | |
download | lua-37c215b43f27a1c41e8a920987e1c3bd7b34330d.tar.gz lua-37c215b43f27a1c41e8a920987e1c3bd7b34330d.tar.bz2 lua-37c215b43f27a1c41e8a920987e1c3bd7b34330d.zip |
Merge branch 'newarray' into nextversion
Diffstat (limited to 'ltable.c')
-rw-r--r-- | ltable.c | 328 |
1 files changed, 244 insertions, 84 deletions
@@ -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 | */ | ||
427 | static 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 | ||
488 | l_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 | */ | ||
551 | static 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 | |||
561 | static 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 | ||
677 | void luaH_free (lua_State *L, Table *t) { | 750 | void 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 | /* | 847 | static 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 | */ | ||
795 | const 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 */ | 863 | static 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 | |
869 | static 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 | |||
879 | int 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 | */ |
823 | const TValue *luaH_getshortstr (Table *t, TString *key) { | 897 | const 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 | ||
839 | const TValue *luaH_getstr (Table *t, TString *key) { | 913 | int luaH_getshortstr (Table *t, TString *key, TValue *res) { |
914 | return finishnodeget(luaH_Hgetshortstr(t, key), res); | ||
915 | } | ||
916 | |||
917 | |||
918 | static 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 | ||
929 | int luaH_getstr (Table *t, TString *key, TValue *res) { | ||
930 | return finishnodeget(Hgetstr(t, key), res); | ||
931 | } | ||
932 | |||
933 | |||
934 | TString *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 | */ |
853 | const TValue *luaH_get (Table *t, const TValue *key) { | 946 | int 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 | ||
971 | static 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 | |||
982 | int 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 | |||
997 | int luaH_psetshortstr (Table *t, TString *key, TValue *val) { | ||
998 | return finishnodeset(t, luaH_Hgetshortstr(t, key), val); | ||
999 | } | ||
1000 | |||
1001 | |||
1002 | int luaH_psetstr (Table *t, TString *key, TValue *val) { | ||
1003 | return finishnodeset(t, Hgetstr(t, key), val); | ||
1004 | } | ||
1005 | |||
1006 | |||
1007 | int 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 | |||
876 | void luaH_finishset (lua_State *L, Table *t, const TValue *key, | 1031 | void 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 | */ |
889 | void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) { | 1051 | void 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 | ||
895 | void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { | 1058 | void 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 | ||
945 | static unsigned int binsearch (const TValue *array, unsigned int i, | 1106 | static 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 | */ |
988 | lua_Unsigned luaH_getn (Table *t) { | 1148 | lua_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); |