Method insert

Fleece/Tree/MutableNode.hh:171–215

Recursive insertion method. On success returns either 'this', or a new node that replaces 'this'. On failure (i.e. callback returned nullptr) returns nullptr.

        // Recursive insertion method. On success returns either 'this', or a new node that
        // replaces 'this'. On failure (i.e. callback returned nullptr) returns nullptr.
        MutableInterior* insert(const Target &target, unsigned shift) {
            assert_precondition(shift + kBitShift < 8*sizeof(hash_t));//FIX: //TODO: Handle hash collisions
            unsigned bitNo = childBitNumber(target.hash, shift);
            if (!hasChild(bitNo)) {
                // No child -- add a leaf:
                Value val = (*target.insertCallback)(nullptr);
                if (!val)
                    return nullptr;
                return addChild(bitNo, new MutableLeaf(target, val));
            }
            NodeRef &childRef = childForBitNumber(bitNo);
            if (childRef.isLeaf()) {
                if (childRef.matches(target)) {
                    // Leaf node matches this key; update or copy it:
                    Value val = (*target.insertCallback)(childRef.value());
                    if (!val)
                        return nullptr;
                    if (childRef.isMutable())
                        ((MutableLeaf*)childRef.asMutable())->_value = val;
                    else
                        childRef = new MutableLeaf(target, val);
                    return this;
                } else {
                    // Nope, need to promote the leaf to an interior node & add new key:
                    MutableInterior *node = promoteLeaf(childRef, shift);
                    auto insertedNode = node->insert(target, shift+kBitShift);
                    if (!insertedNode) {
                        delete node;
                        return nullptr;
                    }
                    childRef = insertedNode;
                    return this;
                }
            } else {
                // Progress down to interior node...
                auto child = (MutableInterior*)childRef.asMutable();
                if (!child)
                    child = mutableCopy(&childRef.asImmutable()->interior, 1);
                child = child->insert(target, shift+kBitShift);
                if (child)
                    childRef = child;
                //FIX: This can leak if child is created by mutableCopy, but then
                return this;
            }
        }


        bool remove(Target target, unsigned shift) {