diff options
| author | Sverker Eriksson <[email protected]> | 2018-10-17 21:31:19 +0200 |
|---|---|---|
| committer | Sverker Eriksson <[email protected]> | 2018-10-23 12:36:28 +0200 |
| commit | 8cd07dae15569deea3a0b539057299a238c8ddc1 (patch) | |
| tree | 8cbc7077ff08e5a9c9987552079cd752acf957c4 /erts | |
| parent | 32fc84630bdb499ca0eabb6b1de8a03b1d9aa321 (diff) | |
| download | otp-8cd07dae15569deea3a0b539057299a238c8ddc1.tar.gz otp-8cd07dae15569deea3a0b539057299a238c8ddc1.tar.bz2 otp-8cd07dae15569deea3a0b539057299a238c8ddc1.zip | |
erts: Optimize find_next/prev_from_pb_key
to not have to backtrack up on the stack.
Diffstat (limited to 'erts')
| -rw-r--r-- | erts/emulator/beam/erl_db_tree.c | 38 |
1 files changed, 14 insertions, 24 deletions
diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index a3147e0f68..250d90e189 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -2947,7 +2947,7 @@ static TreeDbTerm *find_next_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, { TreeDbTerm* root; TreeDbTerm *this; - TreeDbTerm *tmp; + Uint candidate = 0; Sint c; if (iter) { @@ -2967,20 +2967,15 @@ static TreeDbTerm *find_next_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, PUSH_NODE(stack, this); if (( c = cmp_partly_bound(key,GETKEY(tbl, this->dbterm.tpl))) >= 0) { if (this->right == NULL) { - do { - tmp = POP_NODE(stack); - if (( this = TOP_NODE(stack)) == NULL) { - return NULL; - } - } while (this->right == tmp); - return this; - } else - this = this->right; + stack->pos = candidate; + return TOP_NODE(stack); + } + this = this->right; } else /*if (c < 0)*/ { if (this->left == NULL) /* Done */ return this; - else - this = this->left; + candidate = stack->pos; + this = this->left; } } } @@ -2991,7 +2986,7 @@ static TreeDbTerm *find_prev_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, { TreeDbTerm* root; TreeDbTerm *this; - TreeDbTerm *tmp; + Uint candidate = 0; Sint c; if (iter) { @@ -3011,20 +3006,15 @@ static TreeDbTerm *find_prev_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, PUSH_NODE(stack, this); if (( c = cmp_partly_bound(key,GETKEY(tbl, this->dbterm.tpl))) <= 0) { if (this->left == NULL) { - do { - tmp = POP_NODE(stack); - if (( this = TOP_NODE(stack)) == NULL) { - return NULL; - } - } while (this->left == tmp); - return this; - } else - this = this->left; + stack->pos = candidate; + return TOP_NODE(stack); + } + this = this->left; } else /*if (c > 0)*/ { if (this->right == NULL) /* Done */ return this; - else - this = this->right; + candidate = stack->pos; + this = this->right; } } } |