diff options
author | Mike Pall <mike> | 2021-09-19 17:38:49 +0200 |
---|---|---|
committer | Mike Pall <mike> | 2021-09-19 17:38:49 +0200 |
commit | c6f5ef649b645db9cf3d11d1b5c63602c49c6411 (patch) | |
tree | 4d299528ff4e77c2f9059b8e24c50755ff638d2d /src/lj_tab.c | |
parent | 4e0ea654a81e68b1bcd20ddc2026ff1bc9288b84 (diff) | |
download | luajit-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.c | 56 |
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: |
572 | static 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. */ | ||
579 | uint32_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. */ |
603 | int lj_tab_next(lua_State *L, GCtab *t, TValue *key) | 608 | int 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 -------------------------------------------- */ |