rax icon indicating copy to clipboard operation
rax copied to clipboard

fix two cases in raxRemove which can be compressed but not

Open zhuer91 opened this issue 6 years ago • 1 comments

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:

  1. B is key
  2. !A->iscompr && A->size > 1
  3. !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.

zhuer91 avatar Aug 16 '19 04:08 zhuer91

Thank you, I'll check.

antirez avatar Oct 30 '19 18:10 antirez