diff options
Diffstat (limited to 'src/lj_tab.c')
-rw-r--r-- | src/lj_tab.c | 157 |
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. */ |
35 | static Node *hashkey(const GCtab *t, cTValue *key) | 39 | static 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(). */ | ||
167 | GCtab *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 |
153 | GCtab * LJ_FASTCALL lj_tab_new1(lua_State *L, uint32_t ahsize) | 173 | GCtab * 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. */ | ||
223 | void 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. */ |
202 | void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t) | 234 | void 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. */ |
217 | static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits) | 249 | void 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 | ||
277 | static uint32_t countint(cTValue *key, uint32_t *bins) | 312 | static 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 | ||
361 | void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize) | 396 | void 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 | ||
608 | static MSize unbound_search(GCtab *t, MSize j) | 644 | /* Compute table length. Slow path with mixed array/hash lookups. */ |
645 | LJ_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 | */ | ||
637 | MSize LJ_FASTCALL lj_tab_len(GCtab *t) | 670 | MSize 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. */ | ||
690 | MSize 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 | |||