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 259 of file rbtree.h.

                                                 {
        Node* parent = nullptr;
        Node* current = root_;
        
        while (current != nullptr) {
            parent = current;
            if (comp_(value, current->data)) {
                current = current->left;
            } else if (comp_(current->data, value)) {
                current = current->right;
            } else {
                return fl::pair<iterator, bool>(iterator(current, this), false);
            }
        }
        
        Node* newNode = alloc_.allocate(1);
        if (newNode == nullptr) {
            return fl::pair<iterator, bool>(end(), false);
        }
        
        alloc_.construct(newNode, fl::forward<U>(value), RED, parent);
        
        if (parent == nullptr) {
            root_ = newNode;
        } else if (comp_(newNode->data, parent->data)) {
            parent->left = newNode;
        } else {
            parent->right = newNode;
        }
        
        insertFixup(newNode);
        ++size_;
        
        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: