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 codeAgain, 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 codeRaxLowWalk 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 codeTrycompress 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 codeRaxRemoveChild 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 codeSee 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 codeThe 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 codeThe steps are as follows:
- Take nodes out of the Stack and keep going up until the compression condition is not satisfied
- Get down from this node and count the number of nodes that can be compressed
- Create a new node, traverse down again to add node data to the new node, and release the old node
- 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 codeThe 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 codeEle 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 codeIf 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 codeIf 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 codeIf 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 codeRaxIteratorNextStep 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 codeSee 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