aboutsummaryrefslogtreecommitdiff
path: root/src/lj_tab.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lj_tab.c')
-rw-r--r--src/lj_tab.c157
1 files changed, 103 insertions, 54 deletions
diff --git a/src/lj_tab.c b/src/lj_tab.c
index a45ddaca..982b0763 100644
--- a/src/lj_tab.c
+++ b/src/lj_tab.c
@@ -23,18 +23,22 @@ static LJ_AINLINE Node *hashmask(const GCtab *t, uint32_t hash)
23 return &n[hash & t->hmask]; 23 return &n[hash & t->hmask];
24} 24}
25 25
26/* String hashes are precomputed when they are interned. */ 26/* String IDs are generated when a string is interned. */
27#define hashstr(t, s) hashmask(t, (s)->hash) 27#define hashstr(t, s) hashmask(t, (s)->sid)
28 28
29#define hashlohi(t, lo, hi) hashmask((t), hashrot((lo), (hi))) 29#define hashlohi(t, lo, hi) hashmask((t), hashrot((lo), (hi)))
30#define hashnum(t, o) hashlohi((t), (o)->u32.lo, ((o)->u32.hi << 1)) 30#define hashnum(t, o) hashlohi((t), (o)->u32.lo, ((o)->u32.hi << 1))
31#define hashptr(t, p) hashlohi((t), u32ptr(p), u32ptr(p) + HASH_BIAS) 31#if LJ_GC64
32#define hashgcref(t, r) \
33 hashlohi((t), (uint32_t)gcrefu(r), (uint32_t)(gcrefu(r) >> 32))
34#else
32#define hashgcref(t, r) hashlohi((t), gcrefu(r), gcrefu(r) + HASH_BIAS) 35#define hashgcref(t, r) hashlohi((t), gcrefu(r), gcrefu(r) + HASH_BIAS)
36#endif
33 37
34/* Hash an arbitrary key and return its anchor position in the hash table. */ 38/* Hash an arbitrary key and return its anchor position in the hash table. */
35static Node *hashkey(const GCtab *t, cTValue *key) 39static Node *hashkey(const GCtab *t, cTValue *key)
36{ 40{
37 lua_assert(!tvisint(key)); 41 lj_assertX(!tvisint(key), "attempt to hash integer");
38 if (tvisstr(key)) 42 if (tvisstr(key))
39 return hashstr(t, strV(key)); 43 return hashstr(t, strV(key));
40 else if (tvisnum(key)) 44 else if (tvisnum(key))
@@ -53,13 +57,13 @@ static LJ_AINLINE void newhpart(lua_State *L, GCtab *t, uint32_t hbits)
53{ 57{
54 uint32_t hsize; 58 uint32_t hsize;
55 Node *node; 59 Node *node;
56 lua_assert(hbits != 0); 60 lj_assertL(hbits != 0, "zero hash size");
57 if (hbits > LJ_MAX_HBITS) 61 if (hbits > LJ_MAX_HBITS)
58 lj_err_msg(L, LJ_ERR_TABOV); 62 lj_err_msg(L, LJ_ERR_TABOV);
59 hsize = 1u << hbits; 63 hsize = 1u << hbits;
60 node = lj_mem_newvec(L, hsize, Node); 64 node = lj_mem_newvec(L, hsize, Node);
61 setmref(node->freetop, &node[hsize]);
62 setmref(t->node, node); 65 setmref(t->node, node);
66 setfreetop(t, node, &node[hsize]);
63 t->hmask = hsize-1; 67 t->hmask = hsize-1;
64} 68}
65 69
@@ -74,7 +78,7 @@ static LJ_AINLINE void clearhpart(GCtab *t)
74{ 78{
75 uint32_t i, hmask = t->hmask; 79 uint32_t i, hmask = t->hmask;
76 Node *node = noderef(t->node); 80 Node *node = noderef(t->node);
77 lua_assert(t->hmask != 0); 81 lj_assertX(t->hmask != 0, "empty hash part");
78 for (i = 0; i <= hmask; i++) { 82 for (i = 0; i <= hmask; i++) {
79 Node *n = &node[i]; 83 Node *n = &node[i];
80 setmref(n->next, NULL); 84 setmref(n->next, NULL);
@@ -98,7 +102,8 @@ static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
98 GCtab *t; 102 GCtab *t;
99 /* First try to colocate the array part. */ 103 /* First try to colocate the array part. */
100 if (LJ_MAX_COLOSIZE != 0 && asize > 0 && asize <= LJ_MAX_COLOSIZE) { 104 if (LJ_MAX_COLOSIZE != 0 && asize > 0 && asize <= LJ_MAX_COLOSIZE) {
101 lua_assert((sizeof(GCtab) & 7) == 0); 105 Node *nilnode;
106 lj_assertL((sizeof(GCtab) & 7) == 0, "bad GCtab size");
102 t = (GCtab *)lj_mem_newgco(L, sizetabcolo(asize)); 107 t = (GCtab *)lj_mem_newgco(L, sizetabcolo(asize));
103 t->gct = ~LJ_TTAB; 108 t->gct = ~LJ_TTAB;
104 t->nomm = (uint8_t)~0; 109 t->nomm = (uint8_t)~0;
@@ -107,8 +112,13 @@ static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
107 setgcrefnull(t->metatable); 112 setgcrefnull(t->metatable);
108 t->asize = asize; 113 t->asize = asize;
109 t->hmask = 0; 114 t->hmask = 0;
110 setmref(t->node, &G(L)->nilnode); 115 nilnode = &G(L)->nilnode;
116 setmref(t->node, nilnode);
117#if LJ_GC64
118 setmref(t->freetop, nilnode);
119#endif
111 } else { /* Otherwise separately allocate the array part. */ 120 } else { /* Otherwise separately allocate the array part. */
121 Node *nilnode;
112 t = lj_mem_newobj(L, GCtab); 122 t = lj_mem_newobj(L, GCtab);
113 t->gct = ~LJ_TTAB; 123 t->gct = ~LJ_TTAB;
114 t->nomm = (uint8_t)~0; 124 t->nomm = (uint8_t)~0;
@@ -117,7 +127,11 @@ static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
117 setgcrefnull(t->metatable); 127 setgcrefnull(t->metatable);
118 t->asize = 0; /* In case the array allocation fails. */ 128 t->asize = 0; /* In case the array allocation fails. */
119 t->hmask = 0; 129 t->hmask = 0;
120 setmref(t->node, &G(L)->nilnode); 130 nilnode = &G(L)->nilnode;
131 setmref(t->node, nilnode);
132#if LJ_GC64
133 setmref(t->freetop, nilnode);
134#endif
121 if (asize > 0) { 135 if (asize > 0) {
122 if (asize > LJ_MAX_ASIZE) 136 if (asize > LJ_MAX_ASIZE)
123 lj_err_msg(L, LJ_ERR_TABOV); 137 lj_err_msg(L, LJ_ERR_TABOV);
@@ -149,6 +163,12 @@ GCtab *lj_tab_new(lua_State *L, uint32_t asize, uint32_t hbits)
149 return t; 163 return t;
150} 164}
151 165
166/* The API of this function conforms to lua_createtable(). */
167GCtab *lj_tab_new_ah(lua_State *L, int32_t a, int32_t h)
168{
169 return lj_tab_new(L, (uint32_t)(a > 0 ? a+1 : 0), hsize2hbits(h));
170}
171
152#if LJ_HASJIT 172#if LJ_HASJIT
153GCtab * LJ_FASTCALL lj_tab_new1(lua_State *L, uint32_t ahsize) 173GCtab * LJ_FASTCALL lj_tab_new1(lua_State *L, uint32_t ahsize)
154{ 174{
@@ -165,7 +185,8 @@ GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
165 GCtab *t; 185 GCtab *t;
166 uint32_t asize, hmask; 186 uint32_t asize, hmask;
167 t = newtab(L, kt->asize, kt->hmask > 0 ? lj_fls(kt->hmask)+1 : 0); 187 t = newtab(L, kt->asize, kt->hmask > 0 ? lj_fls(kt->hmask)+1 : 0);
168 lua_assert(kt->asize == t->asize && kt->hmask == t->hmask); 188 lj_assertL(kt->asize == t->asize && kt->hmask == t->hmask,
189 "mismatched size of table and template");
169 t->nomm = 0; /* Keys with metamethod names may be present. */ 190 t->nomm = 0; /* Keys with metamethod names may be present. */
170 asize = kt->asize; 191 asize = kt->asize;
171 if (asize > 0) { 192 if (asize > 0) {
@@ -185,7 +206,7 @@ GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
185 Node *node = noderef(t->node); 206 Node *node = noderef(t->node);
186 Node *knode = noderef(kt->node); 207 Node *knode = noderef(kt->node);
187 ptrdiff_t d = (char *)node - (char *)knode; 208 ptrdiff_t d = (char *)node - (char *)knode;
188 setmref(node->freetop, (Node *)((char *)noderef(knode->freetop) + d)); 209 setfreetop(t, node, (Node *)((char *)getfreetop(kt, knode) + d));
189 for (i = 0; i <= hmask; i++) { 210 for (i = 0; i <= hmask; i++) {
190 Node *kn = &knode[i]; 211 Node *kn = &knode[i];
191 Node *n = &node[i]; 212 Node *n = &node[i];
@@ -198,6 +219,17 @@ GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
198 return t; 219 return t;
199} 220}
200 221
222/* Clear a table. */
223void LJ_FASTCALL lj_tab_clear(GCtab *t)
224{
225 clearapart(t);
226 if (t->hmask > 0) {
227 Node *node = noderef(t->node);
228 setfreetop(t, node, &node[t->hmask+1]);
229 clearhpart(t);
230 }
231}
232
201/* Free a table. */ 233/* Free a table. */
202void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t) 234void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
203{ 235{
@@ -214,7 +246,7 @@ void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
214/* -- Table resizing ------------------------------------------------------ */ 246/* -- Table resizing ------------------------------------------------------ */
215 247
216/* Resize a table to fit the new array/hash part sizes. */ 248/* Resize a table to fit the new array/hash part sizes. */
217static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits) 249void lj_tab_resize(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
218{ 250{
219 Node *oldnode = noderef(t->node); 251 Node *oldnode = noderef(t->node);
220 uint32_t oldasize = t->asize; 252 uint32_t oldasize = t->asize;
@@ -247,6 +279,9 @@ static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
247 } else { 279 } else {
248 global_State *g = G(L); 280 global_State *g = G(L);
249 setmref(t->node, &g->nilnode); 281 setmref(t->node, &g->nilnode);
282#if LJ_GC64
283 setmref(t->freetop, &g->nilnode);
284#endif
250 t->hmask = 0; 285 t->hmask = 0;
251 } 286 }
252 if (asize < oldasize) { /* Array part shrinks? */ 287 if (asize < oldasize) { /* Array part shrinks? */
@@ -276,7 +311,7 @@ static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
276 311
277static uint32_t countint(cTValue *key, uint32_t *bins) 312static uint32_t countint(cTValue *key, uint32_t *bins)
278{ 313{
279 lua_assert(!tvisint(key)); 314 lj_assertX(!tvisint(key), "bad integer key");
280 if (tvisnum(key)) { 315 if (tvisnum(key)) {
281 lua_Number nk = numV(key); 316 lua_Number nk = numV(key);
282 int32_t k = lj_num2int(nk); 317 int32_t k = lj_num2int(nk);
@@ -348,7 +383,7 @@ static void rehashtab(lua_State *L, GCtab *t, cTValue *ek)
348 asize += countint(ek, bins); 383 asize += countint(ek, bins);
349 na = bestasize(bins, &asize); 384 na = bestasize(bins, &asize);
350 total -= na; 385 total -= na;
351 resizetab(L, t, asize, hsize2hbits(total)); 386 lj_tab_resize(L, t, asize, hsize2hbits(total));
352} 387}
353 388
354#if LJ_HASFFI 389#if LJ_HASFFI
@@ -360,7 +395,7 @@ void lj_tab_rehash(lua_State *L, GCtab *t)
360 395
361void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize) 396void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize)
362{ 397{
363 resizetab(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0); 398 lj_tab_resize(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0);
364} 399}
365 400
366/* -- Table getters ------------------------------------------------------- */ 401/* -- Table getters ------------------------------------------------------- */
@@ -428,16 +463,17 @@ TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
428 Node *n = hashkey(t, key); 463 Node *n = hashkey(t, key);
429 if (!tvisnil(&n->val) || t->hmask == 0) { 464 if (!tvisnil(&n->val) || t->hmask == 0) {
430 Node *nodebase = noderef(t->node); 465 Node *nodebase = noderef(t->node);
431 Node *collide, *freenode = noderef(nodebase->freetop); 466 Node *collide, *freenode = getfreetop(t, nodebase);
432 lua_assert(freenode >= nodebase && freenode <= nodebase+t->hmask+1); 467 lj_assertL(freenode >= nodebase && freenode <= nodebase+t->hmask+1,
468 "bad freenode");
433 do { 469 do {
434 if (freenode == nodebase) { /* No free node found? */ 470 if (freenode == nodebase) { /* No free node found? */
435 rehashtab(L, t, key); /* Rehash table. */ 471 rehashtab(L, t, key); /* Rehash table. */
436 return lj_tab_set(L, t, key); /* Retry key insertion. */ 472 return lj_tab_set(L, t, key); /* Retry key insertion. */
437 } 473 }
438 } while (!tvisnil(&(--freenode)->key)); 474 } while (!tvisnil(&(--freenode)->key));
439 setmref(nodebase->freetop, freenode); 475 setfreetop(t, nodebase, freenode);
440 lua_assert(freenode != &G(L)->nilnode); 476 lj_assertL(freenode != &G(L)->nilnode, "store to fallback hash");
441 collide = hashkey(t, &n->key); 477 collide = hashkey(t, &n->key);
442 if (collide != n) { /* Colliding node not the main node? */ 478 if (collide != n) { /* Colliding node not the main node? */
443 while (noderef(collide->next) != n) /* Find predecessor. */ 479 while (noderef(collide->next) != n) /* Find predecessor. */
@@ -493,7 +529,7 @@ TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
493 if (LJ_UNLIKELY(tvismzero(&n->key))) 529 if (LJ_UNLIKELY(tvismzero(&n->key)))
494 n->key.u64 = 0; 530 n->key.u64 = 0;
495 lj_gc_anybarriert(L, t); 531 lj_gc_anybarriert(L, t);
496 lua_assert(tvisnil(&n->val)); 532 lj_assertL(tvisnil(&n->val), "new hash slot is not empty");
497 return &n->val; 533 return &n->val;
498} 534}
499 535
@@ -605,49 +641,62 @@ int lj_tab_next(lua_State *L, GCtab *t, TValue *key)
605 641
606/* -- Table length calculation -------------------------------------------- */ 642/* -- Table length calculation -------------------------------------------- */
607 643
608static MSize unbound_search(GCtab *t, MSize j) 644/* Compute table length. Slow path with mixed array/hash lookups. */
645LJ_NOINLINE static MSize tab_len_slow(GCtab *t, size_t hi)
609{ 646{
610 cTValue *tv; 647 cTValue *tv;
611 MSize i = j; /* i is zero or a present index */ 648 size_t lo = hi;
612 j++; 649 hi++;
613 /* find `i' and `j' such that i is present and j is not */ 650 /* Widening search for an upper bound. */
614 while ((tv = lj_tab_getint(t, (int32_t)j)) && !tvisnil(tv)) { 651 while ((tv = lj_tab_getint(t, (int32_t)hi)) && !tvisnil(tv)) {
615 i = j; 652 lo = hi;
616 j *= 2; 653 hi += hi;
617 if (j > (MSize)(INT_MAX-2)) { /* overflow? */ 654 if (hi > (size_t)(INT_MAX-2)) { /* Punt and do a linear search. */
618 /* table was built with bad purposes: resort to linear search */ 655 lo = 1;
619 i = 1; 656 while ((tv = lj_tab_getint(t, (int32_t)lo)) && !tvisnil(tv)) lo++;
620 while ((tv = lj_tab_getint(t, (int32_t)i)) && !tvisnil(tv)) i++; 657 return (MSize)(lo - 1);
621 return i - 1;
622 } 658 }
623 } 659 }
624 /* now do a binary search between them */ 660 /* Binary search to find a non-nil to nil transition. */
625 while (j - i > 1) { 661 while (hi - lo > 1) {
626 MSize m = (i+j)/2; 662 size_t mid = (lo+hi) >> 1;
627 cTValue *tvb = lj_tab_getint(t, (int32_t)m); 663 cTValue *tvb = lj_tab_getint(t, (int32_t)mid);
628 if (tvb && !tvisnil(tvb)) i = m; else j = m; 664 if (tvb && !tvisnil(tvb)) lo = mid; else hi = mid;
629 } 665 }
630 return i; 666 return (MSize)lo;
631} 667}
632 668
633/* 669/* Compute table length. Fast path. */
634** Try to find a boundary in table `t'. A `boundary' is an integer index
635** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
636*/
637MSize LJ_FASTCALL lj_tab_len(GCtab *t) 670MSize LJ_FASTCALL lj_tab_len(GCtab *t)
638{ 671{
639 MSize j = (MSize)t->asize; 672 size_t hi = (size_t)t->asize;
640 if (j > 1 && tvisnil(arrayslot(t, j-1))) { 673 if (hi) hi--;
641 MSize i = 1; 674 /* In a growing array the last array element is very likely nil. */
642 while (j - i > 1) { 675 if (hi > 0 && LJ_LIKELY(tvisnil(arrayslot(t, hi)))) {
643 MSize m = (i+j)/2; 676 /* Binary search to find a non-nil to nil transition in the array. */
644 if (tvisnil(arrayslot(t, m-1))) j = m; else i = m; 677 size_t lo = 0;
678 while (hi - lo > 1) {
679 size_t mid = (lo+hi) >> 1;
680 if (tvisnil(arrayslot(t, mid))) hi = mid; else lo = mid;
645 } 681 }
646 return i-1; 682 return (MSize)lo;
647 } 683 }
648 if (j) j--; 684 /* Without a hash part, there's an implicit nil after the last element. */
649 if (t->hmask <= 0) 685 return t->hmask ? tab_len_slow(t, hi) : (MSize)hi;
650 return j;
651 return unbound_search(t, j);
652} 686}
653 687
688#if LJ_HASJIT
689/* Verify hinted table length or compute it. */
690MSize LJ_FASTCALL lj_tab_len_hint(GCtab *t, size_t hint)
691{
692 size_t asize = (size_t)t->asize;
693 cTValue *tv = arrayslot(t, hint);
694 if (LJ_LIKELY(hint+1 < asize)) {
695 if (LJ_LIKELY(!tvisnil(tv) && tvisnil(tv+1))) return (MSize)hint;
696 } else if (hint+1 <= asize && LJ_LIKELY(t->hmask == 0) && !tvisnil(tv)) {
697 return (MSize)hint;
698 }
699 return lj_tab_len(t);
700}
701#endif
702