insertImpl()

template<typename T, typename Compare = less<T>, typename Allocator = allocator_slab<char>>

template<typename U>

fl::pair< iterator, bool > fl::RedBlackTree< T, Compare, Allocator >::insertImpl ( U && value )

inlineprivate

Definition at line 266 of file rbtree.h.

                                                 {
        RBNode* parent = nullptr;
        RBNode* current = mRoot;
        
        while (current != nullptr) {
            parent = current;
            if (mComp(value, current->data)) {
                current = current->left;
            } else if (mComp(current->data, value)) {
                current = current->right;
            } else {
                return fl::pair<iterator, bool>(iterator(current, this), false);
            }
        }
        
        RBNode* newNode = mAlloc.allocate(1);
        if (newNode == nullptr) {
            return fl::pair<iterator, bool>(iterator(nullptr, this), false);
        }
 
        mAlloc.construct(newNode, Color::kRed, parent, fl::forward<U>(value));
        
        if (parent == nullptr) {
            mRoot = newNode;
        } else if (mComp(newNode->data, parent->data)) {
            parent->left = newNode;
        } else {
            parent->right = newNode;
        }
        
        insertFixup(newNode);
        ++mSize;
        
        return fl::pair<iterator, bool>(iterator(newNode, this), true);
    }

Referenced by fl::RedBlackTree< value_type, PairCompare, Allocator >::insert(), and fl::RedBlackTree< value_type, PairCompare, Allocator >::insert().

Here is the caller graph for this function: