aboutsummaryrefslogtreecommitdiff
path: root/src/lj_tab.c
diff options
context:
space:
mode:
authorMike Pall <mike>2021-09-19 17:38:49 +0200
committerMike Pall <mike>2021-09-19 17:38:49 +0200
commitc6f5ef649b645db9cf3d11d1b5c63602c49c6411 (patch)
tree4d299528ff4e77c2f9059b8e24c50755ff638d2d /src/lj_tab.c
parent4e0ea654a81e68b1bcd20ddc2026ff1bc9288b84 (diff)
downloadluajit-c6f5ef649b645db9cf3d11d1b5c63602c49c6411.tar.gz
luajit-c6f5ef649b645db9cf3d11d1b5c63602c49c6411.tar.bz2
luajit-c6f5ef649b645db9cf3d11d1b5c63602c49c6411.zip
Refactor table traversal.
Sponsored by OpenResty Inc.
Diffstat (limited to 'src/lj_tab.c')
-rw-r--r--src/lj_tab.c56
1 files changed, 33 insertions, 23 deletions
diff --git a/src/lj_tab.c b/src/lj_tab.c
index ed5fd2dd..4113839f 100644
--- a/src/lj_tab.c
+++ b/src/lj_tab.c
@@ -568,56 +568,66 @@ TValue *lj_tab_set(lua_State *L, GCtab *t, cTValue *key)
568 568
569/* -- Table traversal ----------------------------------------------------- */ 569/* -- Table traversal ----------------------------------------------------- */
570 570
571/* Get the traversal index of a key. */ 571/* Table traversal indexes:
572static uint32_t keyindex(lua_State *L, GCtab *t, cTValue *key) 572**
573** Array key index: [0 .. t->asize-1]
574** Hash key index: [t->asize .. t->asize+t->hmask]
575** Invalid key: ~0
576*/
577
578/* Get the successor traversal index of a key. */
579uint32_t LJ_FASTCALL lj_tab_keyindex(GCtab *t, cTValue *key)
573{ 580{
574 TValue tmp; 581 TValue tmp;
575 if (tvisint(key)) { 582 if (tvisint(key)) {
576 int32_t k = intV(key); 583 int32_t k = intV(key);
577 if ((uint32_t)k < t->asize) 584 if ((uint32_t)k < t->asize)
578 return (uint32_t)k; /* Array key indexes: [0..t->asize-1] */ 585 return (uint32_t)k + 1;
579 setnumV(&tmp, (lua_Number)k); 586 setnumV(&tmp, (lua_Number)k);
580 key = &tmp; 587 key = &tmp;
581 } else if (tvisnum(key)) { 588 } else if (tvisnum(key)) {
582 lua_Number nk = numV(key); 589 lua_Number nk = numV(key);
583 int32_t k = lj_num2int(nk); 590 int32_t k = lj_num2int(nk);
584 if ((uint32_t)k < t->asize && nk == (lua_Number)k) 591 if ((uint32_t)k < t->asize && nk == (lua_Number)k)
585 return (uint32_t)k; /* Array key indexes: [0..t->asize-1] */ 592 return (uint32_t)k + 1;
586 } 593 }
587 if (!tvisnil(key)) { 594 if (!tvisnil(key)) {
588 Node *n = hashkey(t, key); 595 Node *n = hashkey(t, key);
589 do { 596 do {
590 if (lj_obj_equal(&n->key, key)) 597 if (lj_obj_equal(&n->key, key))
591 return t->asize + (uint32_t)(n - noderef(t->node)); 598 return t->asize + (uint32_t)((n+1) - noderef(t->node));
592 /* Hash key indexes: [t->asize..t->asize+t->nmask] */
593 } while ((n = nextnode(n))); 599 } while ((n = nextnode(n)));
594 if (key->u32.hi == 0xfffe7fff) /* ITERN was despecialized while running. */ 600 if (key->u32.hi == LJ_KEYINDEX) /* Despecialized ITERN while running. */
595 return key->u32.lo - 1; 601 return key->u32.lo;
596 lj_err_msg(L, LJ_ERR_NEXTIDX); 602 return ~0u; /* Invalid key to next. */
597 return 0; /* unreachable */
598 } 603 }
599 return ~0u; /* A nil key starts the traversal. */ 604 return 0; /* A nil key starts the traversal. */
600} 605}
601 606
602/* Advance to the next step in a table traversal. */ 607/* Get the next key/value pair of a table traversal. */
603int lj_tab_next(lua_State *L, GCtab *t, TValue *key) 608int lj_tab_next(GCtab *t, cTValue *key, TValue *o)
604{ 609{
605 uint32_t i = keyindex(L, t, key); /* Find predecessor key index. */ 610 uint32_t idx = lj_tab_keyindex(t, key); /* Find successor index of key. */
606 for (i++; i < t->asize; i++) /* First traverse the array keys. */ 611 /* First traverse the array part. */
607 if (!tvisnil(arrayslot(t, i))) { 612 for (; idx < t->asize; idx++) {
608 setintV(key, i); 613 cTValue *a = arrayslot(t, idx);
609 copyTV(L, key+1, arrayslot(t, i)); 614 if (LJ_LIKELY(!tvisnil(a))) {
615 setintV(o, idx);
616 o[1] = *a;
610 return 1; 617 return 1;
611 } 618 }
612 for (i -= t->asize; i <= t->hmask; i++) { /* Then traverse the hash keys. */ 619 }
613 Node *n = &noderef(t->node)[i]; 620 idx -= t->asize;
621 /* Then traverse the hash part. */
622 for (; idx <= t->hmask; idx++) {
623 Node *n = &noderef(t->node)[idx];
614 if (!tvisnil(&n->val)) { 624 if (!tvisnil(&n->val)) {
615 copyTV(L, key, &n->key); 625 o[0] = n->key;
616 copyTV(L, key+1, &n->val); 626 o[1] = n->val;
617 return 1; 627 return 1;
618 } 628 }
619 } 629 }
620 return 0; /* End of traversal. */ 630 return (int32_t)idx < 0 ? -1 : 0; /* Invalid key or end of traversal. */
621} 631}
622 632
623/* -- Table length calculation -------------------------------------------- */ 633/* -- Table length calculation -------------------------------------------- */