diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2023-11-03 15:26:13 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2023-11-03 15:26:13 -0300 |
commit | 08a077d673b25cf1fbfe21794f240f4ff4999667 (patch) | |
tree | 77ae945c9a2680af23d5fa11c156482b35c14e04 /ltable.c | |
parent | 43c8e5bded052801f54a7439d18933b83570eb82 (diff) | |
download | lua-08a077d673b25cf1fbfe21794f240f4ff4999667.tar.gz lua-08a077d673b25cf1fbfe21794f240f4ff4999667.tar.bz2 lua-08a077d673b25cf1fbfe21794f240f4ff4999667.zip |
Full implementation of new representation for arrays
Diffstat (limited to 'ltable.c')
-rw-r--r-- | ltable.c | 46 |
1 files changed, 37 insertions, 9 deletions
@@ -350,7 +350,7 @@ 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 | int tag = *getArrTag(t, i + 1); | 353 | int tag = *getArrTag(t, i); |
354 | if (!tagisempty(tag)) { /* a non-empty entry? */ | 354 | if (!tagisempty(tag)) { /* a non-empty entry? */ |
355 | setivalue(s2v(key), i + 1); | 355 | setivalue(s2v(key), i + 1); |
356 | farr2val(t, i + 1, tag, s2v(key + 1)); | 356 | farr2val(t, i + 1, tag, s2v(key + 1)); |
@@ -458,7 +458,7 @@ static int countint (lua_Integer key, unsigned int *nums) { | |||
458 | 458 | ||
459 | 459 | ||
460 | l_sinline int arraykeyisempty (const Table *t, lua_Integer key) { | 460 | l_sinline int arraykeyisempty (const Table *t, lua_Integer key) { |
461 | int tag = *getArrTag(t, key); | 461 | int tag = *getArrTag(t, key - 1); |
462 | return tagisempty(tag); | 462 | return tagisempty(tag); |
463 | } | 463 | } |
464 | 464 | ||
@@ -513,6 +513,33 @@ static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) { | |||
513 | 513 | ||
514 | 514 | ||
515 | /* | 515 | /* |
516 | ** Convert an "abstract size" (number of values in an array) to | ||
517 | ** "concrete size" (number of cell elements in the array). Cells | ||
518 | ** do not need to be full; we only must make sure it has the values | ||
519 | ** needed and its 'tag' element. So, we compute the concrete tag index | ||
520 | ** and the concrete value index of the last element, get their maximum | ||
521 | ** and adds 1. | ||
522 | */ | ||
523 | static unsigned int concretesize (unsigned int size) { | ||
524 | if (size == 0) return 0; | ||
525 | else { | ||
526 | unsigned int ts = TagIndex(size - 1); | ||
527 | unsigned int vs = ValueIndex(size - 1); | ||
528 | return ((ts >= vs) ? ts : vs) + 1; | ||
529 | } | ||
530 | } | ||
531 | |||
532 | |||
533 | static ArrayCell *resizearray (lua_State *L , Table *t, | ||
534 | unsigned int oldasize, | ||
535 | unsigned int newasize) { | ||
536 | oldasize = concretesize(oldasize); | ||
537 | newasize = concretesize(newasize); | ||
538 | return luaM_reallocvector(L, t->array, oldasize, newasize, ArrayCell); | ||
539 | } | ||
540 | |||
541 | |||
542 | /* | ||
516 | ** Creates an array for the hash part of a table with the given | 543 | ** Creates an array for the hash part of a table with the given |
517 | ** size, or reuses the dummy node if size is zero. | 544 | ** size, or reuses the dummy node if size is zero. |
518 | ** The computation for size overflow is in two steps: the first | 545 | ** The computation for size overflow is in two steps: the first |
@@ -605,7 +632,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize, | |||
605 | exchangehashpart(t, &newt); /* and new hash */ | 632 | exchangehashpart(t, &newt); /* and new hash */ |
606 | /* re-insert into the new hash the elements from vanishing slice */ | 633 | /* re-insert into the new hash the elements from vanishing slice */ |
607 | for (i = newasize; i < oldasize; i++) { | 634 | for (i = newasize; i < oldasize; i++) { |
608 | int tag = *getArrTag(t, i + 1); | 635 | int tag = *getArrTag(t, i); |
609 | if (!tagisempty(tag)) { /* a non-empty entry? */ | 636 | if (!tagisempty(tag)) { /* a non-empty entry? */ |
610 | TValue aux; | 637 | TValue aux; |
611 | farr2val(t, i + 1, tag, &aux); | 638 | farr2val(t, i + 1, tag, &aux); |
@@ -616,7 +643,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize, | |||
616 | exchangehashpart(t, &newt); /* and hash (in case of errors) */ | 643 | exchangehashpart(t, &newt); /* and hash (in case of errors) */ |
617 | } | 644 | } |
618 | /* allocate new array */ | 645 | /* allocate new array */ |
619 | newarray = luaM_reallocvector(L, t->array, oldasize, newasize, ArrayCell); | 646 | newarray = resizearray(L, t, oldasize, newasize); |
620 | if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ | 647 | if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ |
621 | freehash(L, &newt); /* release new hash part */ | 648 | freehash(L, &newt); /* release new hash part */ |
622 | luaM_error(L); /* raise error (with array unchanged) */ | 649 | luaM_error(L); /* raise error (with array unchanged) */ |
@@ -626,7 +653,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize, | |||
626 | t->array = newarray; /* set new array part */ | 653 | t->array = newarray; /* set new array part */ |
627 | t->alimit = newasize; | 654 | t->alimit = newasize; |
628 | for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ | 655 | for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ |
629 | *getArrTag(t, i + 1) = LUA_VEMPTY; | 656 | *getArrTag(t, i) = LUA_VEMPTY; |
630 | /* re-insert elements from old hash part into new parts */ | 657 | /* re-insert elements from old hash part into new parts */ |
631 | reinsert(L, &newt, t); /* 'newt' now has the old hash */ | 658 | reinsert(L, &newt, t); /* 'newt' now has the old hash */ |
632 | freehash(L, &newt); /* free old hash part */ | 659 | freehash(L, &newt); /* free old hash part */ |
@@ -682,8 +709,9 @@ Table *luaH_new (lua_State *L) { | |||
682 | 709 | ||
683 | 710 | ||
684 | void luaH_free (lua_State *L, Table *t) { | 711 | void luaH_free (lua_State *L, Table *t) { |
712 | unsigned ps = concretesize(luaH_realasize(t)); | ||
685 | freehash(L, t); | 713 | freehash(L, t); |
686 | luaM_freearray(L, t->array, luaH_realasize(t)); | 714 | luaM_freearray(L, t->array, ps); |
687 | luaM_free(L, t); | 715 | luaM_free(L, t); |
688 | } | 716 | } |
689 | 717 | ||
@@ -799,7 +827,7 @@ static int finishnodeget (const TValue *val, TValue *res) { | |||
799 | 827 | ||
800 | int luaH_getint (Table *t, lua_Integer key, TValue *res) { | 828 | int luaH_getint (Table *t, lua_Integer key, TValue *res) { |
801 | if (keyinarray(t, key)) { | 829 | if (keyinarray(t, key)) { |
802 | int tag = *getArrTag(t, key); | 830 | int tag = *getArrTag(t, key - 1); |
803 | if (!tagisempty(tag)) { | 831 | if (!tagisempty(tag)) { |
804 | farr2val(t, key, tag, res); | 832 | farr2val(t, key, tag, res); |
805 | return HOK; /* success */ | 833 | return HOK; /* success */ |
@@ -902,7 +930,7 @@ static int finishnodeset (Table *t, const TValue *slot, TValue *val) { | |||
902 | 930 | ||
903 | int luaH_psetint (Table *t, lua_Integer key, TValue *val) { | 931 | int luaH_psetint (Table *t, lua_Integer key, TValue *val) { |
904 | if (keyinarray(t, key)) { | 932 | if (keyinarray(t, key)) { |
905 | lu_byte *tag = getArrTag(t, key); | 933 | lu_byte *tag = getArrTag(t, key - 1); |
906 | if (!tagisempty(*tag)) { | 934 | if (!tagisempty(*tag)) { |
907 | fval2arr(t, key, tag, val); | 935 | fval2arr(t, key, tag, val); |
908 | return HOK; /* success */ | 936 | return HOK; /* success */ |
@@ -960,7 +988,7 @@ void luaH_finishset (lua_State *L, Table *t, const TValue *key, | |||
960 | } | 988 | } |
961 | else { /* array entry */ | 989 | else { /* array entry */ |
962 | hres = ~hres; /* real index */ | 990 | hres = ~hres; /* real index */ |
963 | fval2arr(t, hres, getArrTag(t, hres), value); | 991 | obj2arr(t, hres, value); |
964 | } | 992 | } |
965 | } | 993 | } |
966 | 994 | ||