rax
rax copied to clipboard
fix two cases in raxRemove which can be compressed but not
There are two minor problem in raxRemove which omit potential compressible cases:
case 1:
@@ -1081 +1081 @@ int raxRemove(rax *rax, unsigned char *s, size_t len, void **old) {
- } else if (h->size == 1) {
+ } else if (h->size == 1 || h->iscompr) {
/* If the node had just one child, after the removal of the key
* further compression with adjacent nodes is pontentially possible. */
trycompress = 1;
If h->iscompr missed here, the example in annotation will not work.
case 2:
given two nods, say A and B, there are only three cases in which they cannot be merged:
- B is key
- !A->iscompr && A->size > 1
- !B->iscompr && B->size > 1 whether A is a key doesn't matter.
As a example, we operates like this: insert three nil keys "FOOBAR", "FOOTBALL" and "FOO", then remove "FOOTBALL" In current code, we will get: "FOO" -> [B]=(nil) -> "AR" -> []=(nil) which can be merged to: "FOO" -> "BAR"=(nil) -> []=(nil)
So I changed the judgments:
@@ -1073,12 +1073,12 @@ int raxRemove(rax *rax, unsigned char *s, size_t len, void **old) {
/* If after the removal the node has just a single child
* and is not a key, we need to try to compress it. */
- if (new->size == 1 && new->iskey == 0) {
+ if (new->size == 1) {
trycompress = 1;
h = new;
}
and here:
@@ -1142,7 +1142,7 @@ int raxRemove(rax *rax, unsigned char *s, size_t len, void **old) {
raxNode *parent;
while(1) {
parent = raxStackPop(&ts);
- if (!parent || parent->iskey ||
+ if (!parent || h->iskey ||
(!parent->iscompr && parent->size != 1)) break;
h = parent;
and the key data restore code, not list.
Thank you, I'll check.