8000 ds4/rax.c at main · kiminh/ds4 · GitHub
[go: up one dir, main page]
Skip to content

rax.c

Latest commit

 

History

History
2747 lines (2519 loc) · 103 KB

rax.c

File metadata and controls

2747 lines (2519 loc) · 103 KB
Raw
/* Rax -- A radix tree implementation.
*
* Version 2.0 -- 18 March 2026
*
* Copyright (c) 2017-2026, Salvatore Sanfilippo <antirez at gmail dot com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Redis nor the names of its contributors may be used
* to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <errno.h>
#include <math.h>
#include "rax.h"
#ifndef RAX_MALLOC_INCLUDE
#define RAX_MALLOC_INCLUDE "rax_malloc.h"
#endif
#include RAX_MALLOC_INCLUDE
/* This is a special pointer that is guaranteed to never have the same value
* of a radix tree node. It's used in order to report "not found" error without
* requiring the function to have multiple return values. */
void *raxNotFound = (void*)"rax-not-found-pointer";
/* -------------------------------- Debugging ------------------------------ */
void raxDebugShowNode(const char *msg, raxNode *n);
/* Turn debugging messages on/off by compiling with RAX_DEBUG_MSG macro on.
* When RAX_DEBUG_MSG is defined by default Rax operations will emit a lot
* of debugging info to the standard output, however you can still turn
* debugging on/off in order to enable it only when you suspect there is an
* operation causing a bug using the function raxSetDebugMsg(). */
#ifdef RAX_DEBUG_MSG
#define debugf(...) \
if (raxDebugMsg) { \
printf("%s:%s:%d:\t", __FILE__, __func__, __LINE__); \
printf(__VA_ARGS__); \
fflush(stdout); \
}
#define debugnode(msg,n) raxDebugShowNode(msg,n)
#else
#define debugf(...)
#define debugnode(msg,n)
#endif
/* By default log debug info if RAX_DEBUG_MSG is defined. */
static int raxDebugMsg = 1;
/* When debug messages are enabled, turn them on/off dynamically. By
* default they are enabled. Set the state to 0 to disable, and 1 to
* re-enable. */
void raxSetDebugMsg(int onoff) {
raxDebugMsg = onoff;
}
/* ------------------------- raxStack functions --------------------------
* The raxStack is a simple stack of pointers that is capable of switching
* from using a stack-allocated array to dynamic heap once a given number of
* items are reached. It is used in order to retain the list of parent nodes
* while walking the radix tree in order to implement certain operations that
* need to navigate the tree upward.
* ------------------------------------------------------------------------- */
/* Initialize the stack. */
static inline void raxStackInit(raxStack *ts) {
ts->stack = ts->static_items;
ts->items = 0;
ts->maxitems = RAX_STACK_STATIC_ITEMS;
ts->oom = 0;
}
/* Push an item into the stack, returns 1 on success, 0 on out of memory. */
static inline int raxStackPush(raxStack *ts, void *ptr) {
if (ts->items == ts->maxitems) {
if (ts->stack == ts->static_items) {
ts->stack = rax_malloc(sizeof(void*)*ts->maxitems*2);
if (ts->stack == NULL) {
ts->stack = ts->static_items;
ts->oom = 1;
errno = ENOMEM;
return 0;
}
memcpy(ts->stack,ts->static_items,sizeof(void*)*ts->maxitems);
} else {
void **newalloc = rax_realloc(ts->stack,sizeof(void*)*ts->maxitems*2);
if (newalloc == NULL) {
ts->oom = 1;
errno = ENOMEM;
return 0;
}
ts->stack = newalloc;
}
ts->maxitems *= 2;
}
ts->stack[ts->items] = ptr;
ts->items++;
return 1;
}
/* Pop an item from the stack, the function returns NULL if there are no
* items to pop. */
static inline void *raxStackPop(raxStack *ts) {
if (ts->items == 0) return NULL;
ts->items--;
return ts->stack[ts->items];
}
/* Return the stack item at the top of the stack without actually consuming
* it. */
static inline void *raxStackPeek(raxStack *ts) {
if (ts->items == 0) return NULL;
return ts->stack[ts->items-1];
}
/* Free the stack in case we used heap allocation. */
static inline void raxStackFree(raxStack *ts) {
if (ts->stack != ts->static_items) rax_free(ts->stack);
}
/* ----------------------------------------------------------------------------
* Radix tree implementation
* --------------------------------------------------------------------------*/
/* Return the padding needed in the characters section of a node having size
* 'nodesize'. The padding is needed to store the child pointers to aligned
* addresses. Note that we add 4 to the node size because the node has a four
* bytes header. */
#define raxPadding(nodesize) ((sizeof(void*)-(((nodesize)+4) % sizeof(void*))) & (sizeof(void*)-1))
/* Return the pointer to the last child pointer in a node. For the compressed
* nodes this is the only child pointer. */
#define raxNodeLastChildPtr(n) ((raxNode**) ( \
((char*)(n)) + \
raxNodeCurrentLength(n) - \
sizeof(raxNode*) - \
(((n)->iskey && !(n)->isnull) ? sizeof(void*) : 0) \
))
/* Return the pointer to the first child pointer. */
#define raxNodeFirstChildPtr(n) ((raxNode**) ( \
(n)->data + \
(n)->size + \
raxPadding((n)->size)))
/* Return the current total size of the node. Note that the second line
* computes the padding after the string of characters, needed in order to
* save pointers to aligned addresses. */
#define raxNodeCurrentLength(n) ( \
sizeof(raxNode)+(n)->size+ \
raxPadding((n)->size)+ \
((n)->iscompr ? sizeof(raxNode*) : 10000 sizeof(raxNode*)*(n)->size)+ \
(((n)->iskey && !(n)->isnull)*sizeof(void*)) \
)
/* Return 1 if the child at index 'childidx' of node 'n' is an inline leaf
* value rather than a pointer to a child node. Inline leaves are stored
* directly in the child pointer slot to avoid allocating a separate leaf
* node. For compressed nodes only child index 0 is meaningful. Children
* at index >= 13 can never be inline (the bitmap only has 13 bits). */
static inline int raxIsInlineLeaf(raxNode *n, int childidx) {
if (childidx < 0 || childidx >= 13) return 0;
return (n->leafbitmap >> childidx) & 1;
}
raxNode *raxNewNode(size_t children, int datafield);
void raxSetData(raxNode *n, void *data);
/* Create a standalone leaf node storing the specified value. */
static inline raxNode *raxNewValueNode(void *data) {
raxNode *leaf = raxNewNode(0,data != NULL);
if (leaf == NULL) return NULL;
leaf->iskey = 1;
if (data != NULL) {
leaf->isnull = 0;
raxSetData(leaf,data);
} else {
leaf->isnull = 1;
}
return leaf;
}
/* Convert an inline leaf value stored in 'parentlink' into a real leaf node. */
static inline int raxMaterializeInlineLeaf(rax *rax, raxNode *parent,
raxNode **parentlink,
raxNode **childptr)
{
void *value;
memcpy(&value,parentlink,sizeof(value));
raxNode *leaf = raxNewValueNode(value);
if (leaf == NULL) return 0;
memcpy(parentlink,&leaf,sizeof(leaf));
int childidx = (int)(parentlink - raxNodeFirstChildPtr(parent));
if (childidx < 13) parent->leafbitmap &= ~(1 << childidx);
rax->numnodes++;
if (childptr) *childptr = leaf;
return 1;
}
/* Allocate a new non compressed node with the specified number of children.
* If datafield is true, the allocation is made large enough to hold the
* associated data pointer.
* Returns the new node pointer. On out of memory NULL is returned. */
raxNode *raxNewNode(size_t children, int datafield) {
size_t nodesize = sizeof(raxNode)+children+raxPadding(children)+
sizeof(raxNode*)*children;
if (datafield) nodesize += sizeof(void*);
raxNode *node = rax_malloc(nodesize);
if (node == NULL) return NULL;
node->iskey = 0;
node->isnull = 0;
node->iscompr = 0;
node->leafbitmap = 0;
node->size = children;
return node;
}
/* Allocate a new rax and return its pointer. On out of memory the function
* returns NULL. */
rax *raxNew(void) {
rax *rax = rax_malloc(sizeof(*rax));
if (rax == NULL) return NULL;
rax->numele = 0;
rax->numnodes = 1;
rax->head = raxNewNode(0,0);
if (rax->head == NULL) {
rax_free(rax);
return NULL;
} else {
return rax;
}
}
/* realloc the node to make room for auxiliary data in order
* to store an item in that node. On out of memory NULL is returned. */
raxNode *raxReallocForData(raxNode *n, void *data) {
if (data == NULL) return n; /* No reallocation needed, setting isnull=1 */
size_t curlen = raxNodeCurrentLength(n);
return rax_realloc(n,curlen+sizeof(void*));
}
/* Set the node auxiliary data to the specified pointer. */
void raxSetData(raxNode *n, void *data) {
n->iskey = 1;
if (data != NULL) {
n->isnull = 0;
void **ndata = (void**)
((char*)n+raxNodeCurrentLength(n)-sizeof(void*));
memcpy(ndata,&data,sizeof(data));
} else {
n->isnull = 1;
}
}
/* Get the node auxiliary data. */
void *raxGetData(raxNode *n) {
if (n->isnull) return NULL;
void **ndata =(void**)((char*)n+raxNodeCurrentLength(n)-sizeof(void*));
void *data;
memcpy(&data,ndata,sizeof(data));
return data;
}
/* Return the position where the edge 'c' should be inserted in order to
* preserve lexicographic ordering. */
static inline int raxNodeFindChildPos(raxNode *n, unsigned char c) {
int pos;
assert(n->iscompr == 0);
for (pos = 0; pos < n->size; pos++) {
if (n->data[pos] > c) break;
}
return pos;
}
/* Like raxAddChild() but does not allocate the child node. Instead it
* returns in 'parentlink' the address of the new child pointer, so that the
* caller can store either a node pointer or an inline leaf value there. */
static inline raxNode *raxAddChildNoAlloc(rax *rax, raxNode *n,
unsigned char c,
raxNode ***parentlink)
{
assert(n->iscompr == 0);
size_t curlen = raxNodeCurrentLength(n);
n->size++;
size_t newlen = raxNodeCurrentLength(n);
n->size--; /* For now restore the original size. We'll update it only on
success at the end. */
/* Make space in the original node. */
raxNode *newn = rax_realloc(n,newlen);
if (newn == NULL) return NULL;
n = newn;
/* After the reallocation, we have up to 8/16 (depending on the system
* pointer size, and the required node padding) bytes at the end, that is,
* the additional char in the 'data' section, plus one pointer to the new
* child, plus the padding needed in order to store addresses into aligned
* locations.
*
* So if we start with the following node, having "abde" edges.
*
* Note:
* - We assume 4 bytes pointer for simplicity.
* - Each space below corresponds to one byte
*
* [HDR*][abde][Aptr][Bptr][Dptr][Eptr]|AUXP|
*
* After the reallocation we need: 1 byte for the new edge character
* plus 4 bytes for a new child pointer (assuming 32 bit machine).
* However after adding 1 byte to the edge char, the header + the edge
* characters are no longer aligned, so we also need 3 bytes of padding.
* In total the reallocation will add 1+4+3 bytes = 8 bytes:
*
* (Blank bytes are represented by ".")
*
* [HDR*][abde][Aptr][Bptr][Dptr][Eptr]|AUXP|[....][....]
*
* Let's find where to insert the new child in order to make sure
* it is inserted in-place lexicographically. Assuming we are adding
* a child "c" in our case pos will be = 2 after the end of the following
* loop. */
int pos = raxNodeFindChildPos(n,c);
/* If child 12 is inline and we insert before or at it, that child
* will move to slot 13. The bitmap cannot represent slot 13, so
* pre-materialize it as a real node before we mutate the parent. */
raxNode *materialized_child = NULL;
if (pos <= 12 && raxIsInlineLeaf(n,12)) {
void *value;
raxNode **child12 = raxNodeFirstChildPtr(n)+12;
memcpy(&value,child12,sizeof(value));
materialized_child = raxNewValueNode(value);
if (materialized_child == NULL) return NULL;
}
/* Now, if present, move auxiliary data pointer at the end
* so that we can mess with the other data without overwriting it.
* We will obtain something like that:
*
* [HDR*][abde][Aptr][Bptr][Dptr][Eptr][....][....]|AUXP|
*/
unsigned char *src, *dst;
if (n->iskey && !n->isnull) {
src = ((unsigned char*)n+curlen-sizeof(void*));
dst = ((unsigned char*)n+newlen-sizeof(void*));
memmove(dst,src,sizeof(void*));
}
/* Compute the "shift", that is, how many bytes we need to move the
* pointers section forward because of the addition of the new child
* byte in the string section. Note that if we had no padding, that
* would be always "1", since we are adding a single byte in the string
* section of the node (where now there is "abde" basically).
*
* However we have padding, so it could be zero, or up to 8.
*
* Another way to think at the shift is, how many bytes we need to
* move child pointers forward *other than* the obvious sizeof(void*)
* needed for the additional pointer itself. */
size_t shift = newlen - curlen - sizeof(void*);
/* We said we are adding a node with edge 'c'. The insertion
* point is between 'b' and 'd', so the 'pos' variable value is
* the index of the first child pointer that we need to move forward
* to make space for our new pointer.
*
* To start, move all the child pointers after the insertion point
* of shift+sizeof(pointer) bytes on the right, to obtain:
*
* [HDR*][abde][Aptr][Bptr][....][....][Dptr][Eptr]|AUXP|
*/
src = n->data+n->size+
raxPadding(n->size)+
sizeof(raxNode*)*pos;
memmove(src+shift+sizeof(raxNode*),src,sizeof(raxNode*)*(n->size-pos));
/* Move the pointers to the left of the insertion position as well. Often
* we don't need to do anything if there was already some padding to use. In
* that case the final destination of the pointers will be the same, however
* in our example there was no pre-existing padding, so we added one byte
* plus three bytes of padding. After the next memmove() things will look
* like that:
*
* [HDR*][abde][....][Aptr][Bptr][....][Dptr][Eptr]|AUXP|
*/
if (shift) {
src = (unsigned char*) raxNodeFirstChildPtr(n);
memmove(src+shift,src,sizeof(raxNode*)*pos);
}
/* Now make the space for the additional char in the data section,
* but also move the pointers before the insertion point to the right
* by shift bytes, in order to obtain the following:
*
* [HDR*][ab.d][e...][Aptr][Bptr][....][Dptr][Eptr]|AUXP|
*/
src = n->data+pos;
memmove(src+1,src,n->size-pos);
/* We can now set the character and account for the additional child
* pointer to get:
*
* [HDR*][abcd][e...][Aptr][Bptr][....][Dptr][Eptr]|AUXP|
*/
n->data[pos] = c;
n->size++;
/* Shift leaf bitmap to account for the new child at position pos.
* Bits at positions >= pos move up by one to make room. The new
* child starts as a regular (non-inline) child. */
if (n->leafbitmap && pos < 13) {
uint16_t below = pos ? (n->leafbitmap & ((1u << pos) - 1)) : 0;
uint16_t above = n->leafbitmap & ~below;
n->leafbitmap = below | ((above << 1) & ((1u << 13) - 1));
}
src = (unsigned char*) raxNodeFirstChildPtr(n);
if (materialized_child) {
raxNode **spillfield = (raxNode**)(src+sizeof(raxNode*)*13);
memcpy(spillfield,&materialized_child,sizeof(materialized_child));
rax->numnodes++;
}
*parentlink = (raxNode**)(src+sizeof(raxNode*)*pos);
return n;
}
/* Add a new child to the node 'n' representing the character 'c' and return
* its new pointer, as well as the child pointer by reference. Additionally
* '***parentlink' is populated with the raxNode pointer-to-pointer of where
* the new child was stored, which is useful for the caller to replace the
* child pointer if it gets reallocated.
*
* On success the new parent node pointer is returned (it may change because
* of the realloc, so the caller should discard 'n' and use the new value).
* On out of memory NULL is returned, and the old node is still valid. */
raxNode *raxAddChild(rax *rax, raxNode *n, unsigned char c, raxNode **childptr, raxNode ***parentlink) {
/* Alloc the new child we will link to 'n'. */
raxNode *child = raxNewNode(0,0);
if (child == NULL) return NULL;
raxNode *newn = raxAddChildNoAlloc(rax,n,c,parentlink);
if (newn == NULL) {
rax_free(child);
return NULL;
}
memcpy(*parentlink,&child,sizeof(child));
*childptr = child;
return newn;
}
/* Turn the node 'n', that must be a node without any children, into a
* compressed node representing a set of nodes linked one after the other
* and having exactly one child each. The node can be a key or not: this
* property and the associated value if any will be preserved.
*
* The function also returns a child node, since the last node of the
* compressed chain cannot be part of the chain: it has zero children while
* we can only compress inner nodes with exactly one child each. */
static inline raxNode *raxCompressNodeNoAlloc(raxNode *n, unsigned char *s,
size_t len)
{
assert(n->size == 0 && n->iscompr == 0);
void *data = NULL; /* Initialized only to avoid warnings. */
size_t newsize;
debugf("Compress node: %.*s\n", (int)len,s);
/* Make space in the parent node. */
newsize = sizeof(raxNode)+len+raxPadding(len)+sizeof(raxNode*);
if (n->iskey) {
data = raxGetData(n); /* To restore it later. */
if (!n->isnull) newsize += sizeof(void*);
}
raxNode *newn = rax_realloc(n,newsize);
if (newn == NULL) return NULL;
n = newn;
n->iscompr = 1;
n->size = len;
memcpy(n->data,s,len);
if (n->iskey) raxSetData(n,data);
return n;
}
raxNode *raxCompressNode(raxNode *n, unsigned char *s, size_t len, raxNode **child) {
/* Allocate the child to link to this node. */
*child = raxNewNode(0,0);
if (*child == NULL) return NULL;
raxNode *newn = raxCompressNodeNoAlloc(n,s,len);
if (newn == NULL) {
rax_free(*child);
return NULL;
}
n = newn;
raxNode **childfield = raxNodeLastChildPtr(n);
memcpy(childfield,child,sizeof(*child));
return n;
}
/* Low level function that walks the tree looking for the string
* 's' of 'len' bytes. The function returns the number of characters
* of the key that was possible to process: if the returned integer
* is the same as 'len', then it means that the node corresponding to the
* string was found (however it may not be a key in case the node->iskey is
* zero or if simply we stopped in the middle of a compressed node, so that
* 'splitpos' is non zero).
*
* Otherwise if the returned integer is not the same as 'len', there was an
* early stop during the tree walk because of a character mismatch.
*
* The node where the search ended (because the full string was processed
* or because there was an early stop) is returned by reference as
* '*stopnode' if the passed pointer is not NULL. This node link in the
* parent's node is returned as '*plink' if not NULL. Finally, if the
* search stopped in a compressed node, '*splitpos' returns the index
* inside the compressed node where the search ended. This is useful to
* know where to split the node for insertion.
*
* Note that when we stop in the middle of a compressed node with
* a perfect match, this function will return a length equal to the
* 'len' argument (all the key matched), and will return a *splitpos which is
* always positive (that will represent the index of the character immediately
* *after* the last match in the current compressed node).
*
* When instead we stop at a compressed node and *splitpos is zero, it
* means that the current node represents the key (that is, none of the
* compressed node characters are needed to represent the key, just all
* its parents nodes). */
static inline size_t raxLowWalk(rax *rax, unsigned char *s, size_t len, raxNode **stopnode, raxNode ***plink, int *splitpos, raxStack *ts, int *inline_leaf) {
raxNode *h = rax->head;
raxNode **parentlink = &rax->head;
if (inline_leaf) *inline_leaf = 0;
size_t i = 0; /* Position in the string. */
size_t j = 0; /* Position in the node children (or bytes if compressed).*/
while(h->size && i < len) {
debugnode("Lookup current node",h);
unsigned char *v = h->data;
if (h->iscompr) {
for (j = 0; j < h->size && i < len; j++, i++) {
if (v[j] != s[i]) break;
}
if (j != h->size) break;
} else {
/* Even when h->size is large, linear scan provides good
* performances compared to other approaches that are in theory
* more sounding, like performing a binary search. However
* for nodes with many children, using memchr() is faster
* since it is SIMD-accelerated on modern architectures. */
if (h->size > 16) {
unsigned char *found = memchr(v,s[i],h->size);
if (found == NULL) break;
j = found - v;
} else {
for (j = 0; j < h->size; j++) {
if (v[j] == s[i]) break;
}
if (j == h->size) break;
}
i++;
}
raxNode **children = raxNodeFirstChildPtr(h);
if (h->iscompr) j = 0; /* Compressed node only child is at index 0. */
/* If the child we are about to follow is an inline leaf (a value
* stored directly in the child pointer slot), we can't descend
* further. Stop the walk here: h remains as the parent, and
* parentlink will point to the slot containing the inline value.
* We do NOT push h onto the stack since we're not descending. */
if (raxIsInlineLeaf(h,j)) {
if (inline_leaf) *inline_leaf = 1;
parentlink = children+j;
break;
}
if (ts) raxStackPush(ts,h); /* Save stack of parent nodes. */
memcpy(&h,children+j,sizeof(h));
parentlink = children+j;
j = 0; /* If the new node is compressed and we do not
iterate again (since i == l) set the split
position to 0 to signal this node represents
the searched key. */
}
debugnode("Lookup stop node is",h);
if (stopnode) *stopnode = h;
if (plink) *plink = parentlink;
if (splitpos && h->iscompr) *splitpos = j;
return i;
}
/* Insert the element 's' of size 'len', setting as auxiliary data
* the pointer 'data'. If the element is already present, the associated
* data is updated (only if 'overwrite' is set to 1), and 0 is returned,
* otherwise the element is inserted and 1 is returned. On out of memory the
* function returns 0 as well but sets errno to ENOMEM, otherwise errno will
* be set to 0.
*/
int raxGenericInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old, int overwrite) {
size_t i;
int j = 0; /* Split position. If raxLowWalk() stops in a compressed
node, the index 'j' represents the char we stopped within the
compressed node, that is, the position where to split the
node for insertion. */
raxNode *h, **parentlink;
debugf("### Insert %.*s with value %p\n", (int)len, s, data);
int inline_leaf = 0;
i = raxLowWalk(rax,s,len,&h,&parentlink,&j,NULL,&inline_leaf);
/* If the key was found as an inline leaf, the value is stored
* directly in the parent's child pointer slot. Update it in place
* without any allocation. */
if (i == len && inline_leaf) {
void *curval;
memcpy(&curval,parentlink,sizeof(curval));
if (old) *old = curval;
if (overwrite) memcpy(parentlink,&data,sizeof(data));
errno = 0;
return 0; /* Element already exists. */
}
/* If we stopped because we hit an inline leaf but still have
* characters to insert, we must "un-inline" the leaf: allocate
* a real node for it so we can continue the insertion. */
if (inline_leaf && i < len) {
raxNode *leaf;
if (!raxMaterializeInlineLeaf(rax,h,parentlink,&leaf)) {
errno = ENOMEM;
return 0;
}
h = leaf;
j = 0;
/* h is now a real node with size=0 and iskey=1, iscompr=0.
* Neither ALGO 1 nor ALGO 2 will trigger. We fall through to
* the "insert remaining chars" loop. */
}
/* If i == len we walked following the whole string. If we are not
* in the middle of a compressed node, the string is either already
* inserted or this middle node is currently not a key, but can represent
* our key. We have just to reallocate the node and make space for the
* data pointer. */
if (i == len && (!h->iscompr || j == 0 /* not in the middle if j is 0 */)) {
debugf("### Insert: node representing key exists\n");
/* Make space for the value pointer if needed. */
if (!h->iskey || (h->isnull && overwrite)) {
h = raxReallocForData(h,data);
if (h) memcpy(parentlink,&h,sizeof(h));
}
if (h == NULL) {
errno = ENOMEM;
return 0;
}
/* Update the existing key if there is already one. */
if (h->iskey) {
10BC8
if (old) *old = raxGetData(h);
if (overwrite) raxSetData(h,data);
errno = 0;
return 0; /* Element already exists. */
}
/* Otherwise set the node as a key. Note that raxSetData()
* will set h->iskey. */
raxSetData(h,data);
rax->numele++;
return 1; /* Element inserted. */
}
/* If the node we stopped at is a compressed node, we need to
* split it before to continue.
*
* Splitting a compressed node have a few possible cases.
* Imagine that the node 'h' we are currently at is a compressed
* node containing the string "ANNIBALE" (it means that it represents
* nodes A -> N -> N -> I -> B -> A -> L -> E with the only child
* pointer of this node pointing at the 'E' node, because remember that
* we have characters at the edges of the graph, not inside the nodes
* themselves.
*
* In order to show a real case imagine our node to also point to
* another compressed node, that finally points at the node without
* children, representing 'O':
*
* "ANNIBALE" -> "SCO" -> []
*
* When inserting we may face the following cases. Note that all the cases
* require the insertion of a non compressed node with exactly two
* children, except for the last case which just requires splitting a
* compressed node.
*
* 1) Inserting "ANNIENTARE"
*
* |B| -> "ALE" -> "SCO" -> []
* "ANNI" -> |-|
* |E| -> (... continue algo ...) "NTARE" -> []
*
* 2) Inserting "ANNIBALI"
*
* |E| -> "SCO" -> []
* "ANNIBAL" -> |-|
* |I| -> (... continue algo ...) []
*
* 3) Inserting "AGO" (Like case 1, but set iscompr = 0 into original node)
*
* |N| -> "NIBALE" -> "SCO" -> []
* |A| -> |-|
* |G| -> (... continue algo ...) |O| -> []
*
* 4) Inserting "CIAO"
*
* |A| -> "NNIBALE" -> "SCO" -> []
* |-|
* |C| -> (... continue algo ...) "IAO" -> []
*
* 5) Inserting "ANNI"
*
* "ANNI" -> "BALE" -> "SCO" -> []
*
* The final algorithm for insertion covering all the above cases is as
* follows.
*
* ============================= ALGO 1 =============================
*
* For the above cases 1 to 4, that is, all cases where we stopped in
* the middle of a compressed node for a character mismatch, do:
*
* Let $SPLITPOS be the zero-based index at which, in the
* compressed node array of characters, we found the mismatching
* character. For example if the node contains "ANNIBALE" and we add
* "ANNIENTARE" the $SPLITPOS is 4, that is, the index at which the
* mismatching character is found.
*
* 1. Save the current compressed node $NEXT pointer (the pointer to the
* child element, that is always present in compressed nodes).
*
* 2. Create "split node" having as child the non common letter
* at the compressed node. The other non common letter (at the key)
* will be added later as we continue the normal insertion algorithm
* at step "6".
*
* 3a. IF $SPLITPOS == 0:
* Replace the old node with the split node, by copying the auxiliary
* data if any. Fix parent's reference. Free old node eventually
* (we still need its data for the next steps of the algorithm).
*
* 3b. IF $SPLITPOS != 0:
* Trim the compressed node (reallocating it as well) in order to
* contain $splitpos characters. Change child pointer in order to link
* to the split node. If new compressed node len is just 1, set
* iscompr to 0 (layout is the same). Fix parent's reference.
*
* 4a. IF the postfix len (the length of the remaining string of the
* original compressed node after the split character) is non zero,
* create a "postfix node". If the postfix node has just one character
* set iscompr to 0, otherwise iscompr to 1. Set the postfix node
* child pointer to $NEXT.
*
* 4b. IF the postfix len is zero, just use $NEXT as postfix pointer.
*
* 5. Set child[0] of split node to postfix node.
*
* 6. Set the split node as the current node, set current index at child[1]
* and continue insertion algorithm as usually.
*
* ============================= ALGO 2 =============================
*
* For case 5, that is, if we stopped in the middle of a compressed
* node but no mismatch was found, do:
*
* Let $SPLITPOS be the zero-based index at which, in the
* compressed node array of characters, we stopped iterating because
* there were no more keys character to match. So in the example of
* the node "ANNIBALE", adding the string "ANNI", the $SPLITPOS is 4.
*
* 1. Save the current compressed node $NEXT pointer (the pointer to the
* child element, that is always present in compressed nodes).
*
* 2. Create a "postfix node" containing all the characters from $SPLITPOS
* to the end. Use $NEXT as the postfix node child pointer.
* If the postfix node length is 1, set iscompr to 0.
* Set the node as a key with the associated value of the new
* inserted key.
*
* 3. Trim the current node to contain the first $SPLITPOS characters.
* As usually if the new node length is just 1, set iscompr to 0.
* Take the iskey / associated value as it was in the original node.
* Fix the parent's reference.
*
* 4. Set the postfix node as the only child pointer of the trimmed
* node created at step 1.
*/
/* ------------------------- ALGORITHM 1 --------------------------- */
if (h->iscompr && i != len) {
debugf("ALGO 1: Stopped at compressed node %.*s (%p)\n",
h->size, h->data, (void*)h);
debugf("Still to insert: %.*s\n", (int)(len-i), s+i);
debugf("Splitting at %d: '%c'\n", j, ((char*)h->data)[j]);
debugf("Other (key) letter is '%c'\n", s[i]);
/* 1: Save next pointer (or inline value if the child was inlined). */
raxNode **childfield = raxNodeLastChildPtr(h);
raxNode *next;
memcpy(&next,childfield,sizeof(next));
int next_is_inline = h->leafbitmap & 1;
debugf("Next is %p (inline=%d)\n", (void*)next, next_is_inline);
debugf("iskey %d\n", h->iskey);
if (h->iskey) {
debugf("key value is %p\n", raxGetData(h));
}
/* Set the length of the additional nodes we will need. */
size_t trimmedlen = j;
size_t postfixlen = h->size - j - 1;
int split_node_is_key = !trimmedlen && h->iskey && !h->isnull;
size_t nodesize;
/* 2: Create the split node. Also allocate the other nodes we'll need
* ASAP, so that it will be simpler to handle OOM. */
raxNode *splitnode = raxNewNode(1, split_node_is_key);
raxNode *trimmed = NULL;
raxNode *postfix = NULL;
if (trimmedlen) {
nodesize = sizeof(raxNode)+trimmedlen+raxPadding(trimmedlen)+
sizeof(raxNode*);
if (h->iskey && !h->isnull) nodesize += sizeof(void*);
trimmed = rax_malloc(nodesize);
}
if (postfixlen) {
nodesize = sizeof(raxNode)+postfixlen+raxPadding(postfixlen)+
sizeof(raxNode*);
postfix = rax_malloc(nodesize);
}
/* OOM? Abort now that the tree is untouched. */
if (splitnode == NULL ||
(trimmedlen && trimmed == NULL) ||
(postfixlen && postfix == NULL))
{
rax_free(splitnode);
rax_free(trimmed);
rax_free(postfix);
errno = ENOMEM;
return 0;
}
splitnode->data[0] = h->data[j];
if (j == 0) {
/* 3a: Replace the old node with the split node. */
if (h->iskey) {
void *ndata = raxGetData(h);
raxSetData(splitnode,ndata);
}
memcpy(parentlink,&splitnode,sizeof(splitnode));
} else {
/* 3b: Trim the compressed node. */
trimmed->size = j;
memcpy(trimmed->data,h->data,j);
trimmed->iscompr = j > 1 ? 1 : 0;
trimmed->iskey = h->iskey;
trimmed->isnull = h->isnull;
trimmed->leafbitmap = 0;
if (h->iskey && !h->isnull) {
void *ndata = raxGetData(h);
raxSetData(trimmed,ndata);
}
raxNode **cp = raxNodeLastChildPtr(trimmed);
memcpy(cp,&splitnode,sizeof(splitnode));
memcpy(parentlink,&trimmed,sizeof(trimmed));
parentlink = cp; /* Set parentlink to splitnode parent. */
rax->numnodes++;
}
/* 4: Create the postfix node: what remains of the original
* compressed node after the split. */
if (postfixlen) {
/* 4a: create a postfix node. */
postfix->iskey = 0;
postfix->isnull = 0;
postfix->size = postfixlen;
postfix->iscompr = postfixlen > 1;
postfix->leafbitmap = next_is_inline ? 1 : 0;
memcpy(postfix->data,h->data+j+1,postfixlen);
raxNode **cp = raxNodeLastChildPtr(postfix);
memcpy(cp,&next,sizeof(next));
rax->numnodes++;
} else {
/* 4b: just use next as postfix node. */
postfix = next;
}
/* 5: Set splitnode first child as the postfix node.
* If postfixlen was 0, postfix is actually 'next' which may be
* an inline value. In that case propagate the inline status. */
raxNode **splitchild = raxNodeLastChildPtr(splitnode);
memcpy(splitchild,&postfix,sizeof(postfix));
if (!postfixlen && next_is_inline)
splitnode->leafbitmap = 1;
/* 6. Continue insertion: this will cause the splitnode to
* get a new child (the non common character at the currently
* inserted key). */
rax_free(h);
h = splitnode;
} else if (h->iscompr && i == len) {
/* ------------------------- ALGORITHM 2 --------------------------- */
debugf("ALGO 2: Stopped at compressed node %.*s (%p) j = %d\n",
h->size, h->data, (void*)h, j);
/* Allocate postfix & trimmed nodes ASAP to fail for OOM gracefully. */
size_t postfixlen = h->size - j;
size_t nodesize = sizeof(raxNode)+postfixlen+raxPadding(postfixlen)+
sizeof(raxNode*);
if (data != NULL) nodesize += sizeof(void*);
raxNode *postfix = rax_malloc(nodesize);
nodesize = sizeof(raxNode)+j+raxPadding(j)+sizeof(raxNode*);
if (h->iskey && !h->isnull) nodesize += sizeof(void*);
raxNode *trimmed = rax_malloc(nodesize);
if (postfix == NULL || trimmed == NULL) {
rax_free(postfix);
rax_free(trimmed);
errno = ENOMEM;
return 0;
}
/* 1: Save next pointer (or inline value). */
raxNode **childfield = raxNodeLastChildPtr(h);
raxNode *next;
memcpy(&next,childfield,sizeof(next));
int next_is_inline = h->leafbitmap & 1;
/* 2: Create the postfix node. */
postfix->size = postfixlen;
postfix->iscompr = postfixlen > 1;
postfix->iskey = 1;
postfix->isnull = 0;
postfix->leafbitmap = next_is_inline ? 1 : 0;
memcpy(postfix->data,h->data+j,postfixlen);
raxSetData(postfix,data);
raxNode **cp = raxNodeLastChildPtr(postfix);
memcpy(cp,&next,sizeof(next));
rax->numnodes++;
/* 3: Trim the compressed node. */
trimmed->size = j;
trimmed->iscompr = j > 1;
trimmed->iskey = 0;
trimmed->isnull = 0;
trimmed->leafbitmap = 0;
memcpy(trimmed->data,h->data,j);
memcpy(parentlink,&trimmed,sizeof(trimmed));
if (h->iskey) {
void *aux = raxGetData(h);
raxSetData(trimmed,aux);
}
/* Fix the trimmed node child pointer to point to
* the postfix node. */
cp = raxNodeLastChildPtr(trimmed);
memcpy(cp,&postfix,sizeof(postfix));
/* Finish! We don't need to continue with the insertion
* algorithm for ALGO 2. The key is already inserted. */
rax->numele++;
View remainder of file in raw view
0