aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-04-05 15:35:11 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-04-05 15:35:11 -0300
commit5edacafcfa36a1fa86a7b5316bacf8c6a2c47227 (patch)
tree31538a57a5c724af2cd758938ab06b8674edb7a8 /ltable.c
parent3507c3380f5251a49c63f87c81c027b2664795c7 (diff)
downloadlua-5edacafcfa36a1fa86a7b5316bacf8c6a2c47227.tar.gz
lua-5edacafcfa36a1fa86a7b5316bacf8c6a2c47227.tar.bz2
lua-5edacafcfa36a1fa86a7b5316bacf8c6a2c47227.zip
Yet another representation for arrays
This "linear" representation (see ltable.h for details) has worse locality than cells, but the simpler access code seems to compensate that.
Diffstat (limited to 'ltable.c')
-rw-r--r--ltable.c67
1 files changed, 44 insertions, 23 deletions
diff --git a/ltable.c b/ltable.c
index ef19a5c5..e969adef 100644
--- a/ltable.c
+++ b/ltable.c
@@ -25,6 +25,7 @@
25 25
26#include <math.h> 26#include <math.h>
27#include <limits.h> 27#include <limits.h>
28#include <string.h>
28 29
29#include "lua.h" 30#include "lua.h"
30 31
@@ -73,7 +74,7 @@ typedef union {
73** MAXASIZEB is the maximum number of elements in the array part such 74** MAXASIZEB is the maximum number of elements in the array part such
74** that the size of the array fits in 'size_t'. 75** that the size of the array fits in 'size_t'.
75*/ 76*/
76#define MAXASIZEB ((MAX_SIZET/sizeof(ArrayCell)) * NM) 77#define MAXASIZEB (MAX_SIZET/(sizeof(Value) + 1))
77 78
78 79
79/* 80/*
@@ -553,26 +554,52 @@ static int numusehash (const Table *t, unsigned *nums, unsigned *pna) {
553/* 554/*
554** Convert an "abstract size" (number of slots in an array) to 555** Convert an "abstract size" (number of slots in an array) to
555** "concrete size" (number of bytes in the array). 556** "concrete size" (number of bytes in the array).
556** If the abstract size is not a multiple of NM, the last cell is
557** incomplete, so we don't need to allocate memory for the whole cell.
558** 'extra' computes how many values are not needed in that last cell.
559** It will be zero when 'size' is a multiple of NM, and from there it
560** increases as 'size' decreases, up to (NM - 1).
561*/ 557*/
562static size_t concretesize (unsigned int size) { 558static size_t concretesize (unsigned int size) {
563 unsigned int numcells = (size + NM - 1) / NM; /* (size / NM) rounded up */ 559 return size * sizeof(Value) + size; /* space for the two arrays */
564 unsigned int extra = NM - 1 - ((size + NM - 1) % NM);
565 return numcells * sizeof(ArrayCell) - extra * sizeof(Value);
566} 560}
567 561
568 562
569static ArrayCell *resizearray (lua_State *L , Table *t, 563/*
564** Resize the array part of a table. If new size is equal to the old,
565** do nothing. Else, if new size is zero, free the old array. (It must
566** be present, as the sizes are different.) Otherwise, allocate a new
567** array, move the common elements to new proper position, and then
568** frees old array.
569** When array grows, we could reallocate it, but we still would need
570** to move the elements to their new position, so the copy implicit
571** in realloc is a waste. When array shrinks, it always erases some
572** elements that should still be in the array, so we must reallocate in
573** two steps anyway. It is simpler to always reallocate in two steps.
574*/
575static Value *resizearray (lua_State *L , Table *t,
570 unsigned oldasize, 576 unsigned oldasize,
571 unsigned newasize) { 577 unsigned newasize) {
572 size_t oldasizeb = concretesize(oldasize); 578 if (oldasize == newasize)
573 size_t newasizeb = concretesize(newasize); 579 return t->array; /* nothing to be done */
574 void *a = luaM_reallocvector(L, t->array, oldasizeb, newasizeb, lu_byte); 580 else if (newasize == 0) { /* erasing array? */
575 return cast(ArrayCell*, a); 581 Value *op = t->array - oldasize; /* original array's real address */
582 luaM_freemem(L, op, concretesize(oldasize)); /* free it */
583 return NULL;
584 }
585 else {
586 size_t newasizeb = concretesize(newasize);
587 Value *np = cast(Value *,
588 luaM_reallocvector(L, NULL, 0, newasizeb, lu_byte));
589 if (np == NULL) /* allocation error? */
590 return NULL;
591 if (oldasize > 0) {
592 Value *op = t->array - oldasize; /* real original array */
593 unsigned tomove = (oldasize < newasize) ? oldasize : newasize;
594 lua_assert(tomove > 0);
595 /* move common elements to new position */
596 memcpy(np + newasize - tomove,
597 op + oldasize - tomove,
598 concretesize(tomove));
599 luaM_freemem(L, op, concretesize(oldasize));
600 }
601 return np + newasize; /* shift pointer to the end of value segment */
602 }
576} 603}
577 604
578 605
@@ -699,7 +726,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned newasize,
699 unsigned nhsize) { 726 unsigned nhsize) {
700 Table newt; /* to keep the new hash part */ 727 Table newt; /* to keep the new hash part */
701 unsigned int oldasize = setlimittosize(t); 728 unsigned int oldasize = setlimittosize(t);
702 ArrayCell *newarray; 729 Value *newarray;
703 if (newasize > MAXASIZE) 730 if (newasize > MAXASIZE)
704 luaG_runerror(L, "table overflow"); 731 luaG_runerror(L, "table overflow");
705 /* create new hash part with appropriate size into 'newt' */ 732 /* create new hash part with appropriate size into 'newt' */
@@ -777,18 +804,12 @@ Table *luaH_new (lua_State *L) {
777 804
778 805
779/* 806/*
780** Frees a table. The assert ensures the correctness of 'concretesize', 807** Frees a table.
781** checking its result against the address of the last element in the
782** array part of the table, computed abstractly.
783*/ 808*/
784void luaH_free (lua_State *L, Table *t) { 809void luaH_free (lua_State *L, Table *t) {
785 unsigned int realsize = luaH_realasize(t); 810 unsigned int realsize = luaH_realasize(t);
786 size_t sizeb = concretesize(realsize);
787 lua_assert((sizeb == 0 && realsize == 0) ||
788 cast_charp(t->array) + sizeb - sizeof(Value) ==
789 cast_charp(getArrVal(t, realsize - 1)));
790 freehash(L, t); 811 freehash(L, t);
791 luaM_freemem(L, t->array, sizeb); 812 resizearray(L, t, realsize, 0);
792 luaM_free(L, t); 813 luaM_free(L, t);
793} 814}
794 815