preface

The previous article introduced rax tree insertion. This article looks at the delete code. Insertion involves the splitting of compressed nodes, while deletion leads to the merging of nodes.

The body of the

Imagine the following deletion process in mind before looking at the source code. First, the condition for deletion is to match the string exactly, and there are only two cases of matching: either an exact match to a compressed node, or a normal node. Take a look at the source code is how to deal with

int raxRemove(rax *rax, unsigned char *s, size_t len, void **old) {
    raxNode *h;
    raxStack ts;

    debugf("### Delete: %.*s\n", (int)len, s);
    // Use a stack to keep track of nodes visited
    raxStackInit(&ts);
    int splitpos = 0;
    size_t i = raxLowWalk(rax,s,len,&h,NULL,&splitpos,&ts);
    // Indicates that no node is matched
    if(i ! = len || (h->iscompr && splitpos ! =0) | |! h->iskey) { raxStackFree(&ts);return 0;
    }
    if (old) *old = raxGetData(h);
    h->iskey = 0;
    rax->numele--;
Copy the code

Again, the raxLowWalk code is used to match the nodes and get the information, but one step beyond Insert is to create a Stack that logs the nodes visited during the lookup

if (ts) raxStackPush(ts,h);
Copy the code

RaxLowWalk to record the stack code

If the deletion condition can be reached, the node must be a real node from the previous Insert, which has the following three conditions:

• It has to be a key
• If it is a compression node, then the match to the split position must be 0
• The string has to be matched exactly

And then go ahead

int trycompress = 0;

    if (h->size == 0) {
        debugf("Key deleted in node without children. Cleanup needed.\n");
        raxNode *child = NULL;
        while(h ! = rax->head) { child = h; debugf("Freeing child %p [%.*s] key:%d\n", (void*)child,
                (int)child->size, (char*)child->data, child->iskey);
            rax_free(child);
            rax->numnodes--;
            h = raxStackPop(&ts);
            /* Retrieve visited nodes * until a key node or non-compressed node has children greater than 1 */
            if(h->iskey || (! h->iscompr && h->size ! =1)) break;
        }
Copy the code

Trycompress indicates whether the node can be compressed

The first step is to traverse up from the matched node, accessed through the Stack. Because a string is scattered among nodes, it is deleted continuously until the condition is not satisfied. Ordinary nodes with a key node or multiple child nodes cannot be deleted directly.

if (child) {
            debugf("Unlinking child %p from parent %p\n",
                (void*)child, (void*)h);
            // Return h after breaking the child
            raxNode *new = raxRemoveChild(h,child);
            if (new! = h) { raxNode *parent = raxStackPeek(&ts); raxNode **parentlink;if (parent == NULL) {
                    parentlink = &rax->head;
                } else {
                    parentlink = raxFindParentLink(parent,h);
                }
                memcpy(parentlink,&new.sizeof(new));
            }

            // If the deleted node has only one child and is not a key, it can become a compressed node
            if (new->size == 1 && new->iskey == 0) {
                trycompress = 1;
                h = new; }}}else if (h->size == 1) {
        // If this node has child, it may be compressed
        trycompress = 1;
    }

    // Do not compress after OOM
    if (trycompress && ts.oom) trycompress = 0;

Copy the code

RaxRemoveChild disconnects the parent node from the parent node and saves the pointer to the parent node at the same time. The next step is to remove the parent node and replace it with a new node

raxNode *raxRemoveChild(raxNode *parent, raxNode *child) {
    debugnode("raxRemoveChild before", parent);

    // If the paren node is compressed, the child node can be deleted directly
    if (parent->iscompr) {
        void *data = NULL;
        if (parent->iskey) data = raxGetData(parent);
        parent->isnull = 0;
        parent->iscompr = 0;
        parent->size = 0;
        if (parent->iskey) raxSetData(parent,data);
        debugnode("raxRemoveChild after", parent);
        return parent;
    }

    // Get the first byte pointer and loop to the point equal to the child node to get the count
    raxNode **cp = raxNodeFirstChildPtr(parent);
    raxNode **c = cp;
    unsigned char *e = parent->data;
    
    while(1) {
        raxNode *aux;
        memcpy(&aux,c,sizeof(aux));
        if (aux == child) break;
        c++;
        e++;
    }

    // Copy the rest of the data after e+1 to e
    int taillen = parent->size - (e - parent->data) - 1;
    debugf("raxRemoveChild tail len: %d\n", taillen);
    memmove(e,e+1,taillen);

    // This is a realignment
    size_t shift = ((parent->size+4) % sizeof(void*)) = =1 ? sizeof(void*) : 0;

    if (shift)
        memmove(((char*)cp)-shift,cp,(parent->size-taillen- 1) *sizeof(raxNode**));

    /* Move the remaining "tail" pointers at the right position as well. */
    size_tvaluelen = (parent->iskey && ! parent->isnull) ?sizeof(void*) : 0;
    memmove(((char*)c)-shift,c+1,taillen*sizeof(raxNode**)+valuelen);

    // Reduce the count
    parent->size--;


    raxNode *newnode = rax_realloc(parent,raxNodeCurrentLength(parent));
    if (newnode) {
        debugnode("raxRemoveChild after", newnode);
    }
    return newnode ? newnode : parent;
}

Copy the code

See the comments

     * "FOO" -> "BAR"- > [] (2) * Delete FOO *"FOOBAR"- > [] (2)


     *          |B| -> "AR"- > [] (1)
     * "FOO" -> |-|
     *          |T| -> "ER"- > [] (2* * Delete FOOTER * *"FOO" -> |B| -> "AR"- > [] (1* * compress * *"FOOBAR"- > [] (1)
Copy the code

The Redis comment gives two cases, meaning that multiple non-key compressed nodes can be merged into a single node after the node is removed.

if (trycompress) {
        debugf("After removing %.*s:\n", (int)len, s);
        debugnode("Compression may be needed",h);
        debugf("Seek start node\n");

        /* Try to reach the upper node that is compressible. * At the end of the loop 'h' will point to the first node we * can try to compress and 'parent' to its parent. */
        raxNode *parent;
        // Get nodes from stack until the following conditions are met
        while(1) {
            parent = raxStackPop(&ts);
            // The compression condition is non-key node or size 1 compression node
            if(! parent || parent->iskey || (! parent->iscompr && parent->size ! =1)) break;
            h = parent;
            debugnode("Going up to",h);
        }

        raxNode *start = h;

        /* Scan chain of nodes we can compress. */
        size_t comprsize = h->size;
        int nodes = 1;
        // Count the number of nodes that can be merged starting from h
        while(h->size ! =0) {
            // Keep fetching child until the merge condition is not met
            raxNode **cp = raxNodeLastChildPtr(h);
            memcpy(&h,cp,sizeof(h));
            if(h->iskey || (! h->iscompr && h->size ! =1)) break;
            if (comprsize + h->size > RAX_NODE_MAX_SIZE) break;
            nodes++;
            comprsize += h->size;
        }
        if (nodes > 1) {
            // You can compress nodes to create new nodes to save
            size_t nodesize =
                sizeof(raxNode)+comprsize+raxPadding(comprsize)+sizeof(raxNode*);
            raxNode *new = rax_malloc(nodesize);
            // Can not create a node can not adjust the tree but preserve the tree for later query
            if (new= =NULL) {
                raxStackFree(&ts);
                return 1;
            }
            new->iskey = 0;
            new->isnull = 0;
            new->iscompr = 1;
            new->size = comprsize;
            rax->numnodes++;

            // Go through it again
            comprsize = 0;
            h = start;
            while(h->size ! =0) {
                // Copy node data
                memcpy(new->data+comprsize,h->data,h->size);
                comprsize += h->size;
                raxNode **cp = raxNodeLastChildPtr(h);
                raxNode *tofree = h;
                memcpy(&h,cp,sizeof(h));
                // Release the memory of the original node
                rax_free(tofree); rax->numnodes--;
                if(h->iskey || (! h->iscompr && h->size ! =1)) break;
            }
            debugnode("New node".new);

            // Modify the pointer to the new node
            raxNode **cp = raxNodeLastChildPtr(new);
            memcpy(cp,&h,sizeof(h));

            // Modify the parent node
            if (parent) {
                raxNode **parentlink = raxFindParentLink(parent,start);
                memcpy(parentlink,&new.sizeof(new));
            } else {
                rax->head = new;
            }

            debugf("Compressed %d nodes, %d total bytes\n",
                nodes, (int)comprsize);
        }
    }

 raxStackFree(&ts);
    return 1;
Copy the code

The steps are as follows:

1. Take nodes out of the Stack and keep going up until the compression condition is not satisfied
2. Get down from this node and count the number of nodes that can be compressed
3. Create a new node, traverse down again to add node data to the new node, and release the old node
4. The new node joins into the RAX tree

Through the above steps, multiple compression nodes can be merged into one compression node, and the tree is clipped to complete the node deletion.

Traverse the nodes

Since the keys inside raX are sorted lexicographically, a node is a key node, and the left and right sides are sorted lexicographically. The traversal method is as follows:

void raxStart(raxIterator *it, rax *rt);
int raxSeek(raxIterator *it, const char *op, unsigned char *ele, size_t len);
int raxNext(raxIterator *it);
int raxPrev(raxIterator *it);
Copy the code

The iterator is created by raxStart, and then raxSeek is called to initialize the iterator position

int raxSeek(raxIterator *it, const char *op, unsigned char *ele, size_t len) {
    int eq = 0, lt = 0, gt = 0, first = 0, last = 0;

    it->stack.items = 0; 
    it->flags |= RAX_ITER_JUST_SEEKED;
    it->flags &= ~RAX_ITER_EOF;
    it->key_len = 0;
    it->node = NULL;

    /* Set flags according to the operator used to perform the seek. */
    if (op[0] = ='>') {
        gt = 1;
        if (op[1] = ='=') eq = 1;
    } else if (op[0] = ='<') {
        lt = 1;
        if (op[1] = ='=') eq = 1;
    } else if (op[0] = ='=') {
        eq = 1;
    } else if (op[0] = =A '^') {
        first = 1;
    } else if (op[0] = ='$') {
        last = 1;
    } else {
        errno = 0;
        return 0; /* Error. */
    }

Copy the code

Ele represents the element, op is the search operation, support: >, >=, <, <=, =, ^(to find the first element), $(to find the tail element)

The code above parses the op command and creates the identifier

if (it->rt->numele == 0) {
        it->flags |= RAX_ITER_EOF;
        return 1;
    }

    if (first) {
        return raxSeek(it,"> =".NULL.0);
    }
Copy the code

If numele is 0, there are no elements and EOF is set to return. If the first element is found, override to an element greater than or equal to NULL

 if (last) {
        it->node = it->rt->head;
        if(! raxSeekGreatest(it))return 0;
        assert(it->node->iskey);
        it->data = raxGetData(it->node);
        return 1;
    }
int raxSeekGreatest(raxIterator *it) {
    while(it->node->size) {
        if (it->node->iscompr) {
            if(! raxIteratorAddChars(it,it->node->data, it->node->size))return 0;
        } else {
            if(! raxIteratorAddChars(it,it->node->data+it->node->size- 1.1))
                return 0;
        }
        raxNode **cp = raxNodeLastChildPtr(it->node);
        if(! raxStackPush(&it->stack,it->node)) return 0;
        memcpy(&it->node,cp,sizeof(it->node));
    }
    return 1;
}
Copy the code

If last fetches the last element, you simply iterate through the rightmost node of each element.

int splitpos = 0;
    size_t i = raxLowWalk(it->rt,ele,len,&it->node,NULL,&splitpos,&it->stack);

    /* Return OOM on incomplete stack info. */
    if (it->stack.oom) return 0;

    // Set the condition after the "=" symbol to indicate that the corresponding value can be obtained
    if(eq && i == len && (! it->node->iscompr || splitpos ==0) &&
        it->node->iskey)
    {
        if(! raxIteratorAddChars(it,ele,len))return 0;
        it->data = raxGetData(it->node);
     
Copy the code

If no node is found, but < or > is set, stack is used to assist. The core is to use raxIteratorPrevStep and raxIteratorNextStep functions. The raxNext and raxPrev methods also use these two.

int raxIteratorNextStep(raxIterator *it, int noup) {
    if (it->flags & RAX_ITER_EOF) {
        return 1;
    } else if (it->flags & RAX_ITER_JUST_SEEKED) {
        it->flags &= ~RAX_ITER_JUST_SEEKED;
        return 1;
    }
    
    size_t orig_key_len = it->key_len;
    size_t orig_stack_items = it->stack.items;
    raxNode *orig_node = it->node;
Copy the code

RaxIteratorNextStep first handles flag cases such as end, and then saves the original key_len and item

while(1) {
        int children = it->node->iscompr ? 1 : it->node->size;
        // The current node has bytes returned
        if(! noup && children) { debugf("GO DEEPER\n");
            if(! raxStackPush(&it->stack,it->node)) return 0;
            raxNode **cp = raxNodeFirstChildPtr(it->node);
            if(! raxIteratorAddChars(it,it->node->data, it->node->iscompr ? it->node->size :1)) return 0;
            memcpy(&it->node,cp,sizeof(it->node));
            if (it->node_cb && it->node_cb(&it->node))
                memcpy(cp,&it->node,sizeof(it->node));
            
            if (it->node->iskey) {
                it->data = raxGetData(it->node);
                return 1; }}else {
            // Find the parent node
            while(1) {
                int old_noup = noup;

                // The loop has reached the head and cannot be found
                if(! noup && it->node == it->rt->head) { it->flags |= RAX_ITER_EOF; it->stack.items = orig_stack_items;
                    it->key_len = orig_key_len;
                    it->node = orig_node;
                    return 1;
                }
                // Find the next child of the parent node if the current node has no byte points
                unsigned char prevchild = it->key[it->key_len- 1];
                if(! noup) { it->node = raxStackPop(&it->stack);
                } else {
                    noup = 0;
                }
                /* Adjust the current key to represent the node we are * at. */
                int todel = it->node->iscompr ? it->node->size : 1;
                raxIteratorDelChars(it,todel);

                // At least one additional child node is attempted
                if(! it->node->iscompr && it->node->size > (old_noup ?0 : 1)) {
                    raxNode **cp = raxNodeFirstChildPtr(it->node);
                    int i = 0;
                    while (i < it->node->size) {
                        // Iterate through all child nodes to find the first one that is larger than the current key
                        debugf("SCAN NEXT %c\n", it->node->data[i]);
                        if (it->node->data[i] > prevchild) break;
                        i++;
                        cp++;
                    }
                    // If the child node is found to be larger than the current one
                    if(i ! = it->node->size) { debugf("SCAN found a new node\n");
                        raxIteratorAddChars(it,it->node->data+i,1);
                        if(! raxStackPush(&it->stack,it->node)) return 0;
                        memcpy(&it->node,cp,sizeof(it->node));
                        if (it->node_cb && it->node_cb(&it->node))
                            memcpy(cp,&it->node,sizeof(it->node));
                        // If the current node is a key node, the value can be returned or the inner loop is terminated
                        if (it->node->iskey) {
                            it->data = raxGetData(it->node);
                            return 1;
                        }
                        break;
                    }
                }
            }
        }
    }
Copy the code

See the notes for details

Since raxIteratorPrevStep is the opposite of next, I won’t analyze it. The logic is pretty much the same.

conclusion

Rax delete and traversal analysis is finished, stream is written based on RAx, will analyze stream source