Function raxRemoveChildAtPtr

rax.c:1141–1205

Low level child removal from node. 'childptr' must point to the child * pointer stored inside the parent node, and is used directly instead of * searching by child value. The new node pointer (after the child * removal) is returned. Note that this function does not fix the pointer * of the parent node in its parent, so this task is up to the caller. * The function never fails for out of memor

 * of the parent node in its parent, so this task is up to the caller.
 * The function never fails for out of memory. */
static inline raxNode *raxRemoveChildAtPtr(raxNode *parent, raxNode **childptr) {
    debugnode("raxRemoveChild before", parent);
    /* If parent is a compressed node (having a single child, as for definition
     * of the data structure), the removal of the child consists into turning
     * it into a normal node without children. */
    if (parent->iscompr) {
        void *data = NULL;
        if (parent->iskey) data = raxGetData(parent);
        parent->isnull = 0;
        parent->iscompr = 0;
        parent->size = 0;
        parent->leafbitmap = 0;
        if (parent->iskey) raxSetData(parent,data);
        debugnode("raxRemoveChild after", parent);
        return parent;
    }

    /* Otherwise we need to scan for the child pointer and memmove()
     * accordingly.
     *
     * 1. To start we seek the first element in both the children
     *    pointers and edge bytes in the node. */
    raxNode **cp = raxNodeFirstChildPtr(parent);
    raxNode **c = childptr;
    unsigned char *e = parent->data + (c - cp);

    /* 3. Remove the edge and the pointer by memmoving the remaining children
     *    pointer and edge bytes one position before. */
    int taillen = parent->size - (e - parent->data) - 1;
    debugf("raxRemoveChild tail len: %d\n", taillen);
    memmove(e,e+1,taillen);

    /* Compute the shift, that is the amount of bytes we should move our
     * child pointers to the left, since the removal of one edge character
     * and the corresponding padding change, may change the layout.
     * We just check if in the old version of the node there was at the
     * end just a single byte and all padding: in that case removing one char
     * will remove a whole sizeof(void*) word. */
    size_t shift = ((parent->size+4) % sizeof(void*)) == 1 ? sizeof(void*) : 0;

    /* Move the children pointers before the deletion point. */
    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_t valuelen = (parent->iskey && !parent->isnull) ? sizeof(void*) : 0;
    memmove(((char*)c)-shift,c+1,taillen*sizeof(raxNode**)+valuelen);

    /* 4. Update size and shift the leaf bitmap accordingly. Bits above
     *    the removed position shift down by one. */
    int pos = (int)(e - parent->data);
    parent->size--;
    if (parent->leafbitmap && pos < 13) {
        uint16_t above = parent->leafbitmap & ~((1u << (pos+1)) - 1);
        uint16_t below = pos ? (parent->leafbitmap & ((1u << pos) - 1)) : 0;
        parent->leafbitmap = below | (above >> 1);
    }