diff options
Diffstat (limited to 'include/EASTL/internal/red_black_tree.h')
| -rw-r--r-- | include/EASTL/internal/red_black_tree.h | 2366 |
1 files changed, 0 insertions, 2366 deletions
diff --git a/include/EASTL/internal/red_black_tree.h b/include/EASTL/internal/red_black_tree.h deleted file mode 100644 index 5b29b7c..0000000 --- a/include/EASTL/internal/red_black_tree.h +++ /dev/null @@ -1,2366 +0,0 @@ -///////////////////////////////////////////////////////////////////////////// -// Copyright (c) Electronic Arts Inc. All rights reserved. -///////////////////////////////////////////////////////////////////////////// - - -#ifndef EASTL_RED_BLACK_TREE_H -#define EASTL_RED_BLACK_TREE_H - - -#include <EABase/eabase.h> -#if defined(EA_PRAGMA_ONCE_SUPPORTED) - #pragma once -#endif - -#include <EASTL/internal/config.h> -#include <EASTL/type_traits.h> -#include <EASTL/allocator.h> -#include <EASTL/iterator.h> -#include <EASTL/utility.h> -#include <EASTL/algorithm.h> -#include <EASTL/initializer_list.h> -#include <EASTL/tuple.h> - -EA_DISABLE_ALL_VC_WARNINGS() -#include <new> -#include <stddef.h> -EA_RESTORE_ALL_VC_WARNINGS() - - -// 4512 - 'class' : assignment operator could not be generated -// 4530 - C++ exception handler used, but unwind semantics are not enabled. Specify /EHsc -// 4571 - catch(...) semantics changed since Visual C++ 7.1; structured exceptions (SEH) are no longer caught. -EA_DISABLE_VC_WARNING(4512 4530 4571); - - -namespace eastl -{ - - /// EASTL_RBTREE_DEFAULT_NAME - /// - /// Defines a default container name in the absence of a user-provided name. - /// - #ifndef EASTL_RBTREE_DEFAULT_NAME - #define EASTL_RBTREE_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " rbtree" // Unless the user overrides something, this is "EASTL rbtree". - #endif - - - /// EASTL_RBTREE_DEFAULT_ALLOCATOR - /// - #ifndef EASTL_RBTREE_DEFAULT_ALLOCATOR - #define EASTL_RBTREE_DEFAULT_ALLOCATOR allocator_type(EASTL_RBTREE_DEFAULT_NAME) - #endif - - - /// EASTL_RBTREE_LEGACY_SWAP_BEHAVIOUR_REQUIRES_COPY_CTOR - /// - #ifndef EASTL_RBTREE_LEGACY_SWAP_BEHAVIOUR_REQUIRES_COPY_CTOR - #define EASTL_RBTREE_LEGACY_SWAP_BEHAVIOUR_REQUIRES_COPY_CTOR 0 - #endif - - - /// RBTreeColor - /// - enum RBTreeColor - { - kRBTreeColorRed, - kRBTreeColorBlack - }; - - - - /// RBTreeColor - /// - enum RBTreeSide - { - kRBTreeSideLeft, - kRBTreeSideRight - }; - - - - /// rbtree_node_base - /// - /// We define a rbtree_node_base separately from rbtree_node (below), because it - /// allows us to have non-templated operations, and it makes it so that the - /// rbtree anchor node doesn't carry a T with it, which would waste space and - /// possibly lead to surprising the user due to extra Ts existing that the user - /// didn't explicitly create. The downside to all of this is that it makes debug - /// viewing of an rbtree harder, given that the node pointers are of type - /// rbtree_node_base and not rbtree_node. - /// - struct rbtree_node_base - { - typedef rbtree_node_base this_type; - - public: - this_type* mpNodeRight; // Declared first because it is used most often. - this_type* mpNodeLeft; - this_type* mpNodeParent; - char mColor; // We only need one bit here, would be nice if we could stuff that bit somewhere else. - }; - - - /// rbtree_node - /// - template <typename Value> - struct rbtree_node : public rbtree_node_base - { - Value mValue; // For set and multiset, this is the user's value, for map and multimap, this is a pair of key/value. - - // This type is never constructed, so to avoid a MSVC warning we "delete" the copy constructor. - // - // Potentially we could provide a constructor that would satisfy the compiler and change the code to use this constructor - // instead of constructing mValue in place within an unconstructed rbtree_node. - #if defined(_MSC_VER) - rbtree_node(const rbtree_node&) = delete; - #endif - }; - - - - - // rbtree_node_base functions - // - // These are the fundamental functions that we use to maintain the - // tree. The bulk of the work of the tree maintenance is done in - // these functions. - // - EASTL_API rbtree_node_base* RBTreeIncrement (const rbtree_node_base* pNode); - EASTL_API rbtree_node_base* RBTreeDecrement (const rbtree_node_base* pNode); - EASTL_API rbtree_node_base* RBTreeGetMinChild (const rbtree_node_base* pNode); - EASTL_API rbtree_node_base* RBTreeGetMaxChild (const rbtree_node_base* pNode); - EASTL_API size_t RBTreeGetBlackCount(const rbtree_node_base* pNodeTop, - const rbtree_node_base* pNodeBottom); - EASTL_API void RBTreeInsert ( rbtree_node_base* pNode, - rbtree_node_base* pNodeParent, - rbtree_node_base* pNodeAnchor, - RBTreeSide insertionSide); - EASTL_API void RBTreeErase ( rbtree_node_base* pNode, - rbtree_node_base* pNodeAnchor); - - - - - - - - /// rbtree_iterator - /// - template <typename T, typename Pointer, typename Reference> - struct rbtree_iterator - { - typedef rbtree_iterator<T, Pointer, Reference> this_type; - typedef rbtree_iterator<T, T*, T&> iterator; - typedef rbtree_iterator<T, const T*, const T&> const_iterator; - typedef eastl_size_t size_type; // See config.h for the definition of eastl_size_t, which defaults to size_t. - typedef ptrdiff_t difference_type; - typedef T value_type; - typedef rbtree_node_base base_node_type; - typedef rbtree_node<T> node_type; - typedef Pointer pointer; - typedef Reference reference; - typedef EASTL_ITC_NS::bidirectional_iterator_tag iterator_category; - - public: - node_type* mpNode; - - public: - rbtree_iterator(); - explicit rbtree_iterator(const node_type* pNode); - rbtree_iterator(const iterator& x); - rbtree_iterator& operator=(const iterator& x); - - reference operator*() const; - pointer operator->() const; - - rbtree_iterator& operator++(); - rbtree_iterator operator++(int); - - rbtree_iterator& operator--(); - rbtree_iterator operator--(int); - - }; // rbtree_iterator - - - /////////////////////////////////////////////////////////////////////////////// - // rb_base_compare_ebo - // - // Utilizes the "empty base-class optimization" to reduce the size of the rbtree - // when its Compare template argument is an empty class. - /////////////////////////////////////////////////////////////////////////////// - - template <typename Compare, bool /*isEmpty*/ = is_empty<Compare>::value> - struct rb_base_compare_ebo - { - protected: - rb_base_compare_ebo() : mCompare() {} - rb_base_compare_ebo(const Compare& compare) : mCompare(compare) {} - - Compare& get_compare() { return mCompare; } - const Compare& get_compare() const { return mCompare; } - - template <typename T> - bool compare(const T& lhs, const T& rhs) - { - return mCompare(lhs, rhs); - } - - template <typename T> - bool compare(const T& lhs, const T& rhs) const - { - return mCompare(lhs, rhs); - } - - private: - Compare mCompare; - }; - - template <typename Compare> - struct rb_base_compare_ebo<Compare, true> : private Compare - { - protected: - rb_base_compare_ebo() {} - rb_base_compare_ebo(const Compare& compare) : Compare(compare) {} - - Compare& get_compare() { return *this; } - const Compare& get_compare() const { return *this; } - - template <typename T> - bool compare(const T& lhs, const T& rhs) - { - return Compare::operator()(lhs, rhs); - } - - template <typename T> - bool compare(const T& lhs, const T& rhs) const - { - return Compare::operator()(lhs, rhs); - } - }; - - - - /////////////////////////////////////////////////////////////////////////////// - // rb_base - // - // This class allows us to use a generic rbtree as the basis of map, multimap, - // set, and multiset transparently. The vital template parameters for this are - // the ExtractKey and the bUniqueKeys parameters. - // - // If the rbtree has a value type of the form pair<T1, T2> (i.e. it is a map or - // multimap and not a set or multiset) and a key extraction policy that returns - // the first part of the pair, the rbtree gets a mapped_type typedef. - // If it satisfies those criteria and also has unique keys, then it also gets an - // operator[] (which only map and set have and multimap and multiset don't have). - // - /////////////////////////////////////////////////////////////////////////////// - - - - /// rb_base - /// This specialization is used for 'set'. In this case, Key and Value - /// will be the same as each other and ExtractKey will be eastl::use_self. - /// - template <typename Key, typename Value, typename Compare, typename ExtractKey, bool bUniqueKeys, typename RBTree> - struct rb_base : public rb_base_compare_ebo<Compare> - { - typedef ExtractKey extract_key; - - protected: - using rb_base_compare_ebo<Compare>::compare; - using rb_base_compare_ebo<Compare>::get_compare; - - public: - rb_base() {} - rb_base(const Compare& compare) : rb_base_compare_ebo<Compare>(compare) {} - }; - - - /// rb_base - /// This class is used for 'multiset'. - /// In this case, Key and Value will be the same as each - /// other and ExtractKey will be eastl::use_self. - /// - template <typename Key, typename Value, typename Compare, typename ExtractKey, typename RBTree> - struct rb_base<Key, Value, Compare, ExtractKey, false, RBTree> : public rb_base_compare_ebo<Compare> - { - typedef ExtractKey extract_key; - - protected: - using rb_base_compare_ebo<Compare>::compare; - using rb_base_compare_ebo<Compare>::get_compare; - - public: - rb_base() {} - rb_base(const Compare& compare) : rb_base_compare_ebo<Compare>(compare) {} - }; - - - /// rb_base - /// This specialization is used for 'map'. - /// - template <typename Key, typename Pair, typename Compare, typename RBTree> - struct rb_base<Key, Pair, Compare, eastl::use_first<Pair>, true, RBTree> : public rb_base_compare_ebo<Compare> - { - typedef eastl::use_first<Pair> extract_key; - - using rb_base_compare_ebo<Compare>::compare; - using rb_base_compare_ebo<Compare>::get_compare; - - public: - rb_base() {} - rb_base(const Compare& compare) : rb_base_compare_ebo<Compare>(compare) {} - }; - - - /// rb_base - /// This specialization is used for 'multimap'. - /// - template <typename Key, typename Pair, typename Compare, typename RBTree> - struct rb_base<Key, Pair, Compare, eastl::use_first<Pair>, false, RBTree> : public rb_base_compare_ebo<Compare> - { - typedef eastl::use_first<Pair> extract_key; - - using rb_base_compare_ebo<Compare>::compare; - using rb_base_compare_ebo<Compare>::get_compare; - - public: - rb_base() {} - rb_base(const Compare& compare) : rb_base_compare_ebo<Compare>(compare) {} - }; - - - /// rbtree - /// - /// rbtree is the red-black tree basis for the map, multimap, set, and multiset - /// containers. Just about all the work of those containers is done here, and - /// they are merely a shell which sets template policies that govern the code - /// generation for this rbtree. - /// - /// This rbtree implementation is pretty much the same as all other modern - /// rbtree implementations, as the topic is well known and researched. We may - /// choose to implement a "relaxed balancing" option at some point in the - /// future if it is deemed worthwhile. Most rbtree implementations don't do this. - /// - /// The primary rbtree member variable is mAnchor, which is a node_type and - /// acts as the end node. However, like any other node, it has mpNodeLeft, - /// mpNodeRight, and mpNodeParent members. We do the conventional trick of - /// assigning begin() (left-most rbtree node) to mpNodeLeft, assigning - /// 'end() - 1' (a.k.a. rbegin()) to mpNodeRight, and assigning the tree root - /// node to mpNodeParent. - /// - /// Compare (functor): This is a comparison class which defaults to 'less'. - /// It is a common STL thing which takes two arguments and returns true if - /// the first is less than the second. - /// - /// ExtractKey (functor): This is a class which gets the key from a stored - /// node. With map and set, the node is a pair, whereas with set and multiset - /// the node is just the value. ExtractKey will be either eastl::use_first (map and multimap) - /// or eastl::use_self (set and multiset). - /// - /// bMutableIterators (bool): true if rbtree::iterator is a mutable - /// iterator, false if iterator and const_iterator are both const iterators. - /// It will be true for map and multimap and false for set and multiset. - /// - /// bUniqueKeys (bool): true if the keys are to be unique, and false if there - /// can be multiple instances of a given key. It will be true for set and map - /// and false for multiset and multimap. - /// - /// To consider: Add an option for relaxed tree balancing. This could result - /// in performance improvements but would require a more complicated implementation. - /// - /////////////////////////////////////////////////////////////////////// - /// find_as - /// In order to support the ability to have a tree of strings but - /// be able to do efficiently lookups via char pointers (i.e. so they - /// aren't converted to string objects), we provide the find_as - /// function. This function allows you to do a find with a key of a - /// type other than the tree's key type. See the find_as function - /// for more documentation on this. - /// - template <typename Key, typename Value, typename Compare, typename Allocator, - typename ExtractKey, bool bMutableIterators, bool bUniqueKeys> - class rbtree - : public rb_base<Key, Value, Compare, ExtractKey, bUniqueKeys, - rbtree<Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys> > - { - public: - typedef ptrdiff_t difference_type; - typedef eastl_size_t size_type; // See config.h for the definition of eastl_size_t, which defaults to size_t. - typedef Key key_type; - typedef Value value_type; - typedef rbtree_node<value_type> node_type; - typedef value_type& reference; - typedef const value_type& const_reference; - typedef value_type* pointer; - typedef const value_type* const_pointer; - - typedef typename type_select<bMutableIterators, - rbtree_iterator<value_type, value_type*, value_type&>, - rbtree_iterator<value_type, const value_type*, const value_type&> >::type iterator; - typedef rbtree_iterator<value_type, const value_type*, const value_type&> const_iterator; - typedef eastl::reverse_iterator<iterator> reverse_iterator; - typedef eastl::reverse_iterator<const_iterator> const_reverse_iterator; - - typedef Allocator allocator_type; - typedef Compare key_compare; - typedef typename type_select<bUniqueKeys, eastl::pair<iterator, bool>, iterator>::type insert_return_type; // map/set::insert return a pair, multimap/multiset::iterator return an iterator. - typedef rbtree<Key, Value, Compare, Allocator, - ExtractKey, bMutableIterators, bUniqueKeys> this_type; - typedef rb_base<Key, Value, Compare, ExtractKey, bUniqueKeys, this_type> base_type; - typedef integral_constant<bool, bUniqueKeys> has_unique_keys_type; - typedef typename base_type::extract_key extract_key; - - protected: - using base_type::compare; - using base_type::get_compare; - - public: - rbtree_node_base mAnchor; /// This node acts as end() and its mpLeft points to begin(), and mpRight points to rbegin() (the last node on the right). - size_type mnSize; /// Stores the count of nodes in the tree (not counting the anchor node). - allocator_type mAllocator; // To do: Use base class optimization to make this go away. - - public: - // ctor/dtor - rbtree(); - rbtree(const allocator_type& allocator); - rbtree(const Compare& compare, const allocator_type& allocator = EASTL_RBTREE_DEFAULT_ALLOCATOR); - rbtree(const this_type& x); - rbtree(this_type&& x); - rbtree(this_type&& x, const allocator_type& allocator); - - template <typename InputIterator> - rbtree(InputIterator first, InputIterator last, const Compare& compare, const allocator_type& allocator = EASTL_RBTREE_DEFAULT_ALLOCATOR); - - ~rbtree(); - - public: - // properties - const allocator_type& get_allocator() const EA_NOEXCEPT; - allocator_type& get_allocator() EA_NOEXCEPT; - void set_allocator(const allocator_type& allocator); - - const key_compare& key_comp() const { return get_compare(); } - key_compare& key_comp() { return get_compare(); } - - this_type& operator=(const this_type& x); - this_type& operator=(std::initializer_list<value_type> ilist); - this_type& operator=(this_type&& x); - - void swap(this_type& x); - - public: - // iterators - iterator begin() EA_NOEXCEPT; - const_iterator begin() const EA_NOEXCEPT; - const_iterator cbegin() const EA_NOEXCEPT; - - iterator end() EA_NOEXCEPT; - const_iterator end() const EA_NOEXCEPT; - const_iterator cend() const EA_NOEXCEPT; - - reverse_iterator rbegin() EA_NOEXCEPT; - const_reverse_iterator rbegin() const EA_NOEXCEPT; - const_reverse_iterator crbegin() const EA_NOEXCEPT; - - reverse_iterator rend() EA_NOEXCEPT; - const_reverse_iterator rend() const EA_NOEXCEPT; - const_reverse_iterator crend() const EA_NOEXCEPT; - - public: - bool empty() const EA_NOEXCEPT; - size_type size() const EA_NOEXCEPT; - - template <class... Args> - insert_return_type emplace(Args&&... args); - - template <class... Args> - iterator emplace_hint(const_iterator position, Args&&... args); - - // Standard conversion overload to avoid the overhead of mismatched 'pair<const Key, Value>' types. - template <class P, class = typename eastl::enable_if<eastl::is_constructible<value_type, P&&>::value>::type> - insert_return_type insert(P&& otherValue); - - // Currently limited to value_type instead of P because it collides with insert(InputIterator, InputIterator). - // To allow this to work with templated P we need to implement a compile-time specialization for the - // case that P&& is const_iterator and have that specialization handle insert(InputIterator, InputIterator) - // instead of insert(InputIterator, InputIterator). Curiously, neither libstdc++ nor libc++ - // implement this function either, which suggests they ran into the same problem I did here - // and haven't yet resolved it (at least as of March 2014, GCC 4.8.1). - iterator insert(const_iterator hint, value_type&& value); - - /// map::insert and set::insert return a pair, while multimap::insert and - /// multiset::insert return an iterator. - insert_return_type insert(const value_type& value); - - // C++ standard: inserts value if and only if there is no element with - // key equivalent to the key of t in containers with unique keys; always - // inserts value in containers with equivalent keys. Always returns the - // iterator pointing to the element with key equivalent to the key of value. - // iterator position is a hint pointing to where the insert should start - // to search. However, there is a potential defect/improvement report on this behaviour: - // LWG issue #233 (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html) - // We follow the same approach as SGI STL/STLPort and use the position as - // a forced insertion position for the value when possible. - iterator insert(const_iterator position, const value_type& value); - - void insert(std::initializer_list<value_type> ilist); - - template <typename InputIterator> - void insert(InputIterator first, InputIterator last); - - // TODO(rparolin): - // insert_return_type insert(node_type&& nh); - // iterator insert(const_iterator hint, node_type&& nh); - - template <class M> pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); - template <class M> pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); - template <class M> iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); - template <class M> iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); - - iterator erase(const_iterator position); - iterator erase(const_iterator first, const_iterator last); - reverse_iterator erase(const_reverse_iterator position); - reverse_iterator erase(const_reverse_iterator first, const_reverse_iterator last); - - // For some reason, multiple STL versions make a specialization - // for erasing an array of key_types. I'm pretty sure we don't - // need this, but just to be safe we will follow suit. - // The implementation is trivial. Returns void because the values - // could well be randomly distributed throughout the tree and thus - // a return value would be nearly meaningless. - void erase(const key_type* first, const key_type* last); - - void clear(); - void reset_lose_memory(); // This is a unilateral reset to an initially empty state. No destructors are called, no deallocation occurs. - - iterator find(const key_type& key); - const_iterator find(const key_type& key) const; - - /// Implements a find whereby the user supplies a comparison of a different type - /// than the tree's value_type. A useful case of this is one whereby you have - /// a container of string objects but want to do searches via passing in char pointers. - /// The problem is that without this kind of find, you need to do the expensive operation - /// of converting the char pointer to a string so it can be used as the argument to the - /// find function. - /// - /// Example usage (note that the compare uses string as first type and char* as second): - /// set<string> strings; - /// strings.find_as("hello", less_2<string, const char*>()); - /// - template <typename U, typename Compare2> iterator find_as(const U& u, Compare2 compare2); - template <typename U, typename Compare2> const_iterator find_as(const U& u, Compare2 compare2) const; - - iterator lower_bound(const key_type& key); - const_iterator lower_bound(const key_type& key) const; - - iterator upper_bound(const key_type& key); - const_iterator upper_bound(const key_type& key) const; - - bool validate() const; - int validate_iterator(const_iterator i) const; - - protected: - node_type* DoAllocateNode(); - void DoFreeNode(node_type* pNode); - - node_type* DoCreateNodeFromKey(const key_type& key); - - template<class... Args> - node_type* DoCreateNode(Args&&... args); - node_type* DoCreateNode(const value_type& value); - node_type* DoCreateNode(value_type&& value); - node_type* DoCreateNode(const node_type* pNodeSource, node_type* pNodeParent); - - node_type* DoCopySubtree(const node_type* pNodeSource, node_type* pNodeDest); - void DoNukeSubtree(node_type* pNode); - - template <class... Args> - eastl::pair<iterator, bool> DoInsertValue(true_type, Args&&... args); - - template <class... Args> - iterator DoInsertValue(false_type, Args&&... args); - - eastl::pair<iterator, bool> DoInsertValue(true_type, value_type&& value); - iterator DoInsertValue(false_type, value_type&& value); - - template <class... Args> - iterator DoInsertValueImpl(node_type* pNodeParent, bool bForceToLeft, const key_type& key, Args&&... args); - iterator DoInsertValueImpl(node_type* pNodeParent, bool bForceToLeft, const key_type& key, node_type* pNodeNew); - - eastl::pair<iterator, bool> DoInsertKey(true_type, const key_type& key); - iterator DoInsertKey(false_type, const key_type& key); - - template <class... Args> - iterator DoInsertValueHint(true_type, const_iterator position, Args&&... args); - - template <class... Args> - iterator DoInsertValueHint(false_type, const_iterator position, Args&&... args); - - iterator DoInsertValueHint(true_type, const_iterator position, value_type&& value); - iterator DoInsertValueHint(false_type, const_iterator position, value_type&& value); - - iterator DoInsertKey(true_type, const_iterator position, const key_type& key); // By design we return iterator and not a pair. - iterator DoInsertKey(false_type, const_iterator position, const key_type& key); - iterator DoInsertKeyImpl(node_type* pNodeParent, bool bForceToLeft, const key_type& key); - - node_type* DoGetKeyInsertionPositionUniqueKeys(bool& canInsert, const key_type& key); - node_type* DoGetKeyInsertionPositionNonuniqueKeys(const key_type& key); - - node_type* DoGetKeyInsertionPositionUniqueKeysHint(const_iterator position, bool& bForceToLeft, const key_type& key); - node_type* DoGetKeyInsertionPositionNonuniqueKeysHint(const_iterator position, bool& bForceToLeft, const key_type& key); - - }; // rbtree - - - - - - /////////////////////////////////////////////////////////////////////// - // rbtree_node_base functions - /////////////////////////////////////////////////////////////////////// - - EASTL_API inline rbtree_node_base* RBTreeGetMinChild(const rbtree_node_base* pNodeBase) - { - while(pNodeBase->mpNodeLeft) - pNodeBase = pNodeBase->mpNodeLeft; - return const_cast<rbtree_node_base*>(pNodeBase); - } - - EASTL_API inline rbtree_node_base* RBTreeGetMaxChild(const rbtree_node_base* pNodeBase) - { - while(pNodeBase->mpNodeRight) - pNodeBase = pNodeBase->mpNodeRight; - return const_cast<rbtree_node_base*>(pNodeBase); - } - - // The rest of the functions are non-trivial and are found in - // the corresponding .cpp file to this file. - - - - /////////////////////////////////////////////////////////////////////// - // rbtree_iterator functions - /////////////////////////////////////////////////////////////////////// - - template <typename T, typename Pointer, typename Reference> - rbtree_iterator<T, Pointer, Reference>::rbtree_iterator() - : mpNode(NULL) { } - - - template <typename T, typename Pointer, typename Reference> - rbtree_iterator<T, Pointer, Reference>::rbtree_iterator(const node_type* pNode) - : mpNode(static_cast<node_type*>(const_cast<node_type*>(pNode))) { } - - - template <typename T, typename Pointer, typename Reference> - rbtree_iterator<T, Pointer, Reference>::rbtree_iterator(const iterator& x) - : mpNode(x.mpNode) { } - - template <typename T, typename Pointer, typename Reference> - typename rbtree_iterator<T, Pointer, Reference>::this_type& - rbtree_iterator<T, Pointer, Reference>::operator=(const iterator& x) - { - mpNode = x.mpNode; - return *this; - } - - template <typename T, typename Pointer, typename Reference> - typename rbtree_iterator<T, Pointer, Reference>::reference - rbtree_iterator<T, Pointer, Reference>::operator*() const - { return mpNode->mValue; } - - - template <typename T, typename Pointer, typename Reference> - typename rbtree_iterator<T, Pointer, Reference>::pointer - rbtree_iterator<T, Pointer, Reference>::operator->() const - { return &mpNode->mValue; } - - - template <typename T, typename Pointer, typename Reference> - typename rbtree_iterator<T, Pointer, Reference>::this_type& - rbtree_iterator<T, Pointer, Reference>::operator++() - { - mpNode = static_cast<node_type*>(RBTreeIncrement(mpNode)); - return *this; - } - - - template <typename T, typename Pointer, typename Reference> - typename rbtree_iterator<T, Pointer, Reference>::this_type - rbtree_iterator<T, Pointer, Reference>::operator++(int) - { - this_type temp(*this); - mpNode = static_cast<node_type*>(RBTreeIncrement(mpNode)); - return temp; - } - - - template <typename T, typename Pointer, typename Reference> - typename rbtree_iterator<T, Pointer, Reference>::this_type& - rbtree_iterator<T, Pointer, Reference>::operator--() - { - mpNode = static_cast<node_type*>(RBTreeDecrement(mpNode)); - return *this; - } - - - template <typename T, typename Pointer, typename Reference> - typename rbtree_iterator<T, Pointer, Reference>::this_type - rbtree_iterator<T, Pointer, Reference>::operator--(int) - { - this_type temp(*this); - mpNode = static_cast<node_type*>(RBTreeDecrement(mpNode)); - return temp; - } - - - // The C++ defect report #179 requires that we support comparisons between const and non-const iterators. - // Thus we provide additional template paremeters here to support this. The defect report does not - // require us to support comparisons between reverse_iterators and const_reverse_iterators. - template <typename T, typename PointerA, typename ReferenceA, typename PointerB, typename ReferenceB> - inline bool operator==(const rbtree_iterator<T, PointerA, ReferenceA>& a, - const rbtree_iterator<T, PointerB, ReferenceB>& b) - { - return a.mpNode == b.mpNode; - } - - - template <typename T, typename PointerA, typename ReferenceA, typename PointerB, typename ReferenceB> - inline bool operator!=(const rbtree_iterator<T, PointerA, ReferenceA>& a, - const rbtree_iterator<T, PointerB, ReferenceB>& b) - { - return a.mpNode != b.mpNode; - } - - - // We provide a version of operator!= for the case where the iterators are of the - // same type. This helps prevent ambiguity errors in the presence of rel_ops. - template <typename T, typename Pointer, typename Reference> - inline bool operator!=(const rbtree_iterator<T, Pointer, Reference>& a, - const rbtree_iterator<T, Pointer, Reference>& b) - { - return a.mpNode != b.mpNode; - } - - - - - /////////////////////////////////////////////////////////////////////// - // rbtree functions - /////////////////////////////////////////////////////////////////////// - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline rbtree<K, V, C, A, E, bM, bU>::rbtree() - : mAnchor(), - mnSize(0), - mAllocator(EASTL_RBTREE_DEFAULT_NAME) - { - reset_lose_memory(); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline rbtree<K, V, C, A, E, bM, bU>::rbtree(const allocator_type& allocator) - : mAnchor(), - mnSize(0), - mAllocator(allocator) - { - reset_lose_memory(); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline rbtree<K, V, C, A, E, bM, bU>::rbtree(const C& compare, const allocator_type& allocator) - : base_type(compare), - mAnchor(), - mnSize(0), - mAllocator(allocator) - { - reset_lose_memory(); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline rbtree<K, V, C, A, E, bM, bU>::rbtree(const this_type& x) - : base_type(x.get_compare()), - mAnchor(), - mnSize(0), - mAllocator(x.mAllocator) - { - reset_lose_memory(); - - if(x.mAnchor.mpNodeParent) // mAnchor.mpNodeParent is the rb_tree root node. - { - mAnchor.mpNodeParent = DoCopySubtree((const node_type*)x.mAnchor.mpNodeParent, (node_type*)&mAnchor); - mAnchor.mpNodeRight = RBTreeGetMaxChild(mAnchor.mpNodeParent); - mAnchor.mpNodeLeft = RBTreeGetMinChild(mAnchor.mpNodeParent); - mnSize = x.mnSize; - } - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline rbtree<K, V, C, A, E, bM, bU>::rbtree(this_type&& x) - : base_type(x.get_compare()), - mAnchor(), - mnSize(0), - mAllocator(x.mAllocator) - { - reset_lose_memory(); - swap(x); - } - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline rbtree<K, V, C, A, E, bM, bU>::rbtree(this_type&& x, const allocator_type& allocator) - : base_type(x.get_compare()), - mAnchor(), - mnSize(0), - mAllocator(allocator) - { - reset_lose_memory(); - swap(x); // swap will directly or indirectly handle the possibility that mAllocator != x.mAllocator. - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <typename InputIterator> - inline rbtree<K, V, C, A, E, bM, bU>::rbtree(InputIterator first, InputIterator last, const C& compare, const allocator_type& allocator) - : base_type(compare), - mAnchor(), - mnSize(0), - mAllocator(allocator) - { - reset_lose_memory(); - - #if EASTL_EXCEPTIONS_ENABLED - try - { - #endif - for(; first != last; ++first) - insert(*first); - #if EASTL_EXCEPTIONS_ENABLED - } - catch(...) - { - clear(); - throw; - } - #endif - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline rbtree<K, V, C, A, E, bM, bU>::~rbtree() - { - // Erase the entire tree. DoNukeSubtree is not a - // conventional erase function, as it does no rebalancing. - DoNukeSubtree((node_type*)mAnchor.mpNodeParent); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline const typename rbtree<K, V, C, A, E, bM, bU>::allocator_type& - rbtree<K, V, C, A, E, bM, bU>::get_allocator() const EA_NOEXCEPT - { - return mAllocator; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::allocator_type& - rbtree<K, V, C, A, E, bM, bU>::get_allocator() EA_NOEXCEPT - { - return mAllocator; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline void rbtree<K, V, C, A, E, bM, bU>::set_allocator(const allocator_type& allocator) - { - mAllocator = allocator; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::size_type - rbtree<K, V, C, A, E, bM, bU>::size() const EA_NOEXCEPT - { return mnSize; } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline bool rbtree<K, V, C, A, E, bM, bU>::empty() const EA_NOEXCEPT - { return (mnSize == 0); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::begin() EA_NOEXCEPT - { return iterator(static_cast<node_type*>(mAnchor.mpNodeLeft)); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator - rbtree<K, V, C, A, E, bM, bU>::begin() const EA_NOEXCEPT - { return const_iterator(static_cast<node_type*>(const_cast<rbtree_node_base*>(mAnchor.mpNodeLeft))); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator - rbtree<K, V, C, A, E, bM, bU>::cbegin() const EA_NOEXCEPT - { return const_iterator(static_cast<node_type*>(const_cast<rbtree_node_base*>(mAnchor.mpNodeLeft))); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::end() EA_NOEXCEPT - { return iterator(static_cast<node_type*>(&mAnchor)); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator - rbtree<K, V, C, A, E, bM, bU>::end() const EA_NOEXCEPT - { return const_iterator(static_cast<node_type*>(const_cast<rbtree_node_base*>(&mAnchor))); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator - rbtree<K, V, C, A, E, bM, bU>::cend() const EA_NOEXCEPT - { return const_iterator(static_cast<node_type*>(const_cast<rbtree_node_base*>(&mAnchor))); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator - rbtree<K, V, C, A, E, bM, bU>::rbegin() EA_NOEXCEPT - { return reverse_iterator(end()); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_reverse_iterator - rbtree<K, V, C, A, E, bM, bU>::rbegin() const EA_NOEXCEPT - { return const_reverse_iterator(end()); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_reverse_iterator - rbtree<K, V, C, A, E, bM, bU>::crbegin() const EA_NOEXCEPT - { return const_reverse_iterator(end()); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator - rbtree<K, V, C, A, E, bM, bU>::rend() EA_NOEXCEPT - { return reverse_iterator(begin()); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_reverse_iterator - rbtree<K, V, C, A, E, bM, bU>::rend() const EA_NOEXCEPT - { return const_reverse_iterator(begin()); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_reverse_iterator - rbtree<K, V, C, A, E, bM, bU>::crend() const EA_NOEXCEPT - { return const_reverse_iterator(begin()); } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::this_type& - rbtree<K, V, C, A, E, bM, bU>::operator=(const this_type& x) - { - if(this != &x) - { - clear(); - - #if EASTL_ALLOCATOR_COPY_ENABLED - mAllocator = x.mAllocator; - #endif - - get_compare() = x.get_compare(); - - if(x.mAnchor.mpNodeParent) // mAnchor.mpNodeParent is the rb_tree root node. - { - mAnchor.mpNodeParent = DoCopySubtree((const node_type*)x.mAnchor.mpNodeParent, (node_type*)&mAnchor); - mAnchor.mpNodeRight = RBTreeGetMaxChild(mAnchor.mpNodeParent); - mAnchor.mpNodeLeft = RBTreeGetMinChild(mAnchor.mpNodeParent); - mnSize = x.mnSize; - } - } - return *this; - } - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::this_type& - rbtree<K, V, C, A, E, bM, bU>::operator=(this_type&& x) - { - if(this != &x) - { - clear(); // To consider: Are we really required to clear here? x is going away soon and will clear itself in its dtor. - swap(x); // member swap handles the case that x has a different allocator than our allocator by doing a copy. - } - return *this; - } - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::this_type& - rbtree<K, V, C, A, E, bM, bU>::operator=(std::initializer_list<value_type> ilist) - { - // The simplest means of doing this is to clear and insert. There probably isn't a generic - // solution that's any more efficient without having prior knowledge of the ilist contents. - clear(); - - for(typename std::initializer_list<value_type>::iterator it = ilist.begin(), itEnd = ilist.end(); it != itEnd; ++it) - DoInsertValue(has_unique_keys_type(), eastl::move(*it)); - - return *this; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - void rbtree<K, V, C, A, E, bM, bU>::swap(this_type& x) - { - #if EASTL_RBTREE_LEGACY_SWAP_BEHAVIOUR_REQUIRES_COPY_CTOR - if(mAllocator == x.mAllocator) // If allocators are equivalent... - #endif - { - // Most of our members can be exchaged by a basic swap: - // We leave mAllocator as-is. - eastl::swap(mnSize, x.mnSize); - eastl::swap(get_compare(), x.get_compare()); - #if !EASTL_RBTREE_LEGACY_SWAP_BEHAVIOUR_REQUIRES_COPY_CTOR - eastl::swap(mAllocator, x.mAllocator); - #endif - - - // However, because our anchor node is a part of our class instance and not - // dynamically allocated, we can't do a swap of it but must do a more elaborate - // procedure. This is the downside to having the mAnchor be like this, but - // otherwise we consider it a good idea to avoid allocating memory for a - // nominal container instance. - - // We optimize for the expected most common case: both pointers being non-null. - if(mAnchor.mpNodeParent && x.mAnchor.mpNodeParent) // If both pointers are non-null... - { - eastl::swap(mAnchor.mpNodeRight, x.mAnchor.mpNodeRight); - eastl::swap(mAnchor.mpNodeLeft, x.mAnchor.mpNodeLeft); - eastl::swap(mAnchor.mpNodeParent, x.mAnchor.mpNodeParent); - - // We need to fix up the anchors to point to themselves (we can't just swap them). - mAnchor.mpNodeParent->mpNodeParent = &mAnchor; - x.mAnchor.mpNodeParent->mpNodeParent = &x.mAnchor; - } - else if(mAnchor.mpNodeParent) - { - x.mAnchor.mpNodeRight = mAnchor.mpNodeRight; - x.mAnchor.mpNodeLeft = mAnchor.mpNodeLeft; - x.mAnchor.mpNodeParent = mAnchor.mpNodeParent; - x.mAnchor.mpNodeParent->mpNodeParent = &x.mAnchor; - - // We need to fix up our anchor to point it itself (we can't have it swap with x). - mAnchor.mpNodeRight = &mAnchor; - mAnchor.mpNodeLeft = &mAnchor; - mAnchor.mpNodeParent = NULL; - } - else if(x.mAnchor.mpNodeParent) - { - mAnchor.mpNodeRight = x.mAnchor.mpNodeRight; - mAnchor.mpNodeLeft = x.mAnchor.mpNodeLeft; - mAnchor.mpNodeParent = x.mAnchor.mpNodeParent; - mAnchor.mpNodeParent->mpNodeParent = &mAnchor; - - // We need to fix up x's anchor to point it itself (we can't have it swap with us). - x.mAnchor.mpNodeRight = &x.mAnchor; - x.mAnchor.mpNodeLeft = &x.mAnchor; - x.mAnchor.mpNodeParent = NULL; - } // Else both are NULL and there is nothing to do. - } - #if EASTL_RBTREE_LEGACY_SWAP_BEHAVIOUR_REQUIRES_COPY_CTOR - else - { - const this_type temp(*this); // Can't call eastl::swap because that would - *this = x; // itself call this member swap function. - x = temp; - } - #endif - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class... Args> - inline typename rbtree<K, V, C, A, E, bM, bU>::insert_return_type // map/set::insert return a pair, multimap/multiset::iterator return an iterator. - rbtree<K, V, C, A, E, bM, bU>::emplace(Args&&... args) - { - return DoInsertValue(has_unique_keys_type(), eastl::forward<Args>(args)...); - } - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class... Args> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::emplace_hint(const_iterator position, Args&&... args) - { - return DoInsertValueHint(has_unique_keys_type(), position, eastl::forward<Args>(args)...); - } - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class P, class> - inline typename rbtree<K, V, C, A, E, bM, bU>::insert_return_type // map/set::insert return a pair, multimap/multiset::iterator return an iterator. - rbtree<K, V, C, A, E, bM, bU>::insert(P&& otherValue) - { - // Need to use forward instead of move because P&& is a "universal reference" instead of an rvalue reference. - return emplace(eastl::forward<P>(otherValue)); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::insert(const_iterator position, value_type&& value) - { - return DoInsertValueHint(has_unique_keys_type(), position, eastl::move(value)); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::insert_return_type // map/set::insert return a pair, multimap/multiset::iterator return an iterator. - rbtree<K, V, C, A, E, bM, bU>::insert(const value_type& value) - { - return DoInsertValue(has_unique_keys_type(), value); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::insert(const_iterator position, const value_type& value) - { - return DoInsertValueHint(has_unique_keys_type(), position, value); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class M> - eastl::pair<typename rbtree<K, V, C, A, E, bM, bU>::iterator, bool> - rbtree<K, V, C, A, E, bM, bU>::insert_or_assign(const key_type& k, M&& obj) - { - auto iter = find(k); - - if(iter == end()) - { - return insert(value_type(piecewise_construct, eastl::forward_as_tuple(k), eastl::forward_as_tuple(eastl::forward<M>(obj)))); - } - else - { - iter->second = eastl::forward<M>(obj); - return {iter, false}; - } - } - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class M> - eastl::pair<typename rbtree<K, V, C, A, E, bM, bU>::iterator, bool> - rbtree<K, V, C, A, E, bM, bU>::insert_or_assign(key_type&& k, M&& obj) - { - auto iter = find(k); - - if(iter == end()) - { - return insert(value_type(piecewise_construct, eastl::forward_as_tuple(eastl::move(k)), eastl::forward_as_tuple(eastl::forward<M>(obj)))); - } - else - { - iter->second = eastl::forward<M>(obj); - return {iter, false}; - } - } - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class M> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::insert_or_assign(const_iterator hint, const key_type& k, M&& obj) - { - auto iter = find(k); - - if(iter == end()) - { - return insert(hint, value_type(piecewise_construct, eastl::forward_as_tuple(k), eastl::forward_as_tuple(eastl::forward<M>(obj)))); - } - else - { - iter->second = eastl::forward<M>(obj); - return iter; - } - } - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class M> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::insert_or_assign(const_iterator hint, key_type&& k, M&& obj) - { - auto iter = find(k); - - if(iter == end()) - { - return insert(hint, value_type(piecewise_construct, eastl::forward_as_tuple(eastl::move(k)), eastl::forward_as_tuple(eastl::forward<M>(obj)))); - } - else - { - iter->second = eastl::forward<M>(obj); - return iter; - } - } - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoGetKeyInsertionPositionUniqueKeys(bool& canInsert, const key_type& key) - { - // This code is essentially a slightly modified copy of the the rbtree::insert - // function whereby this version takes a key and not a full value_type. - extract_key extractKey; - - node_type* pCurrent = (node_type*)mAnchor.mpNodeParent; // Start with the root node. - node_type* pLowerBound = (node_type*)&mAnchor; // Set it to the container end for now. - node_type* pParent; // This will be where we insert the new node. - - bool bValueLessThanNode = true; // If the tree is empty, this will result in an insertion at the front. - - // Find insertion position of the value. This will either be a position which - // already contains the value, a position which is greater than the value or - // end(), which we treat like a position which is greater than the value. - while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree. - { - bValueLessThanNode = compare(key, extractKey(pCurrent->mValue)); - pLowerBound = pCurrent; - - if(bValueLessThanNode) - { - EASTL_VALIDATE_COMPARE(!compare(extractKey(pCurrent->mValue), key)); // Validate that the compare function is sane. - pCurrent = (node_type*)pCurrent->mpNodeLeft; - } - else - pCurrent = (node_type*)pCurrent->mpNodeRight; - } - - pParent = pLowerBound; // pLowerBound is actually upper bound right now (i.e. it is > value instead of <=), but we will make it the lower bound below. - - if(bValueLessThanNode) // If we ended up on the left side of the last parent node... - { - if(EASTL_LIKELY(pLowerBound != (node_type*)mAnchor.mpNodeLeft)) // If the tree was empty or if we otherwise need to insert at the very front of the tree... - { - // At this point, pLowerBound points to a node which is > than value. - // Move it back by one, so that it points to a node which is <= value. - pLowerBound = (node_type*)RBTreeDecrement(pLowerBound); - } - else - { - canInsert = true; - return pLowerBound; - } - } - - // Since here we require values to be unique, we will do nothing if the value already exists. - if(compare(extractKey(pLowerBound->mValue), key)) // If the node is < the value (i.e. if value is >= the node)... - { - EASTL_VALIDATE_COMPARE(!compare(key, extractKey(pLowerBound->mValue))); // Validate that the compare function is sane. - canInsert = true; - return pParent; - } - - // The item already exists (as found by the compare directly above), so return false. - canInsert = false; - return pLowerBound; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoGetKeyInsertionPositionNonuniqueKeys(const key_type& key) - { - // This is the pathway for insertion of non-unique keys (multimap and multiset, but not map and set). - node_type* pCurrent = (node_type*)mAnchor.mpNodeParent; // Start with the root node. - node_type* pRangeEnd = (node_type*)&mAnchor; // Set it to the container end for now. - extract_key extractKey; - - while(pCurrent) - { - pRangeEnd = pCurrent; - - if(compare(key, extractKey(pCurrent->mValue))) - { - EASTL_VALIDATE_COMPARE(!compare(extractKey(pCurrent->mValue), key)); // Validate that the compare function is sane. - pCurrent = (node_type*)pCurrent->mpNodeLeft; - } - else - pCurrent = (node_type*)pCurrent->mpNodeRight; - } - - return pRangeEnd; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - eastl::pair<typename rbtree<K, V, C, A, E, bM, bU>::iterator, bool> - rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(true_type, value_type&& value) - { - extract_key extractKey; - key_type key(extractKey(value)); - bool canInsert; - node_type* pPosition = DoGetKeyInsertionPositionUniqueKeys(canInsert, key); - - if(canInsert) - { - const iterator itResult(DoInsertValueImpl(pPosition, false, key, eastl::move(value))); - return pair<iterator, bool>(itResult, true); - } - - return pair<iterator, bool>(iterator(pPosition), false); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(false_type, value_type&& value) - { - extract_key extractKey; - key_type key(extractKey(value)); - node_type* pPosition = DoGetKeyInsertionPositionNonuniqueKeys(key); - - return DoInsertValueImpl(pPosition, false, key, eastl::move(value)); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class... Args> - eastl::pair<typename rbtree<K, V, C, A, E, bM, bU>::iterator, bool> - rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(true_type, Args&&... args) // true_type means keys are unique. - { - // This is the pathway for insertion of unique keys (map and set, but not multimap and multiset). - // Note that we return a pair and not an iterator. This is because the C++ standard for map - // and set is to return a pair and not just an iterator. - - node_type* pNodeNew = DoCreateNode(eastl::forward<Args>(args)...); // Note that pNodeNew->mpLeft, mpRight, mpParent, will be uninitialized. - const key_type& key = extract_key{}(pNodeNew->mValue); - - bool canInsert; - node_type* pPosition = DoGetKeyInsertionPositionUniqueKeys(canInsert, key); - - if(canInsert) - { - iterator itResult(DoInsertValueImpl(pPosition, false, key, pNodeNew)); - return pair<iterator, bool>(itResult, true); - } - - DoFreeNode(pNodeNew); - return pair<iterator, bool>(iterator(pPosition), false); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class... Args> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(false_type, Args&&... args) // false_type means keys are not unique. - { - // We have a problem here if sizeof(value_type) is too big for the stack. We may want to consider having a specialization for large value_types. - // To do: Change this so that we call DoCreateNode(eastl::forward<Args>(args)...) here and use the value from the resulting pNode to get the - // key, and make DoInsertValueImpl take that node as an argument. That way there is no value created on the stack. - - node_type* const pNodeNew = DoCreateNode(eastl::forward<Args>(args)...); // Note that pNodeNew->mpLeft, mpRight, mpParent, will be uninitialized. - const key_type& key = extract_key{}(pNodeNew->mValue); - - node_type* pPosition = DoGetKeyInsertionPositionNonuniqueKeys(key); - - return DoInsertValueImpl(pPosition, false, key, pNodeNew); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class... Args> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertValueImpl(node_type* pNodeParent, bool bForceToLeft, const key_type& key, Args&&... args) - { - node_type* const pNodeNew = DoCreateNode(eastl::forward<Args>(args)...); // Note that pNodeNew->mpLeft, mpRight, mpParent, will be uninitialized. - - return DoInsertValueImpl(pNodeParent, bForceToLeft, key, pNodeNew); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertValueImpl(node_type* pNodeParent, bool bForceToLeft, const key_type& key, node_type* pNodeNew) - { - EASTL_ASSERT_MSG(pNodeNew != nullptr, "node to insert to the rbtree must not be null"); - - RBTreeSide side; - extract_key extractKey; - - // The reason we may want to have bForceToLeft == true is that pNodeParent->mValue and value may be equal. - // In that case it doesn't matter what side we insert on, except that the C++ LWG #233 improvement report - // suggests that we should use the insert hint position to force an ordering. So that's what we do. - if(bForceToLeft || (pNodeParent == &mAnchor) || compare(key, extractKey(pNodeParent->mValue))) - side = kRBTreeSideLeft; - else - side = kRBTreeSideRight; - - RBTreeInsert(pNodeNew, pNodeParent, &mAnchor, side); - mnSize++; - - return iterator(pNodeNew); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - eastl::pair<typename rbtree<K, V, C, A, E, bM, bU>::iterator, bool> - rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(true_type, const key_type& key) // true_type means keys are unique. - { - // This is the pathway for insertion of unique keys (map and set, but not multimap and multiset). - // Note that we return a pair and not an iterator. This is because the C++ standard for map - // and set is to return a pair and not just an iterator. - bool canInsert; - node_type* pPosition = DoGetKeyInsertionPositionUniqueKeys(canInsert, key); - - if(canInsert) - { - const iterator itResult(DoInsertKeyImpl(pPosition, false, key)); - return pair<iterator, bool>(itResult, true); - } - - return pair<iterator, bool>(iterator(pPosition), false); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(false_type, const key_type& key) // false_type means keys are not unique. - { - node_type* pPosition = DoGetKeyInsertionPositionNonuniqueKeys(key); - - return DoInsertKeyImpl(pPosition, false, key); - } - - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoGetKeyInsertionPositionUniqueKeysHint(const_iterator position, bool& bForceToLeft, const key_type& key) - { - extract_key extractKey; - - if((position.mpNode != mAnchor.mpNodeRight) && (position.mpNode != &mAnchor)) // If the user specified a specific insertion position... - { - iterator itNext(position.mpNode); - ++itNext; - - // To consider: Change this so that 'position' specifies the position after - // where the insertion goes and not the position before where the insertion goes. - // Doing so would make this more in line with user expectations and with LWG #233. - const bool bPositionLessThanValue = compare(extractKey(position.mpNode->mValue), key); - - if(bPositionLessThanValue) // If (value > *position)... - { - EASTL_VALIDATE_COMPARE(!compare(key, extractKey(position.mpNode->mValue))); // Validate that the compare function is sane. - - const bool bValueLessThanNext = compare(key, extractKey(itNext.mpNode->mValue)); - - if(bValueLessThanNext) // If value < *itNext... - { - EASTL_VALIDATE_COMPARE(!compare(extractKey(itNext.mpNode->mValue), key)); // Validate that the compare function is sane. - - if(position.mpNode->mpNodeRight) - { - bForceToLeft = true; // Specifically insert in front of (to the left of) itNext (and thus after 'position'). - return itNext.mpNode; - } - - bForceToLeft = false; - return position.mpNode; - } - } - - bForceToLeft = false; - return NULL; // The above specified hint was not useful, then we do a regular insertion. - } - - if(mnSize && compare(extractKey(((node_type*)mAnchor.mpNodeRight)->mValue), key)) - { - EASTL_VALIDATE_COMPARE(!compare(key, extractKey(((node_type*)mAnchor.mpNodeRight)->mValue))); // Validate that the compare function is sane. - bForceToLeft = false; - return (node_type*)mAnchor.mpNodeRight; - } - - bForceToLeft = false; - return NULL; // The caller can do a default insert. - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoGetKeyInsertionPositionNonuniqueKeysHint(const_iterator position, bool& bForceToLeft, const key_type& key) - { - extract_key extractKey; - - if((position.mpNode != mAnchor.mpNodeRight) && (position.mpNode != &mAnchor)) // If the user specified a specific insertion position... - { - iterator itNext(position.mpNode); - ++itNext; - - // To consider: Change this so that 'position' specifies the position after - // where the insertion goes and not the position before where the insertion goes. - // Doing so would make this more in line with user expectations and with LWG #233. - if(!compare(key, extractKey(position.mpNode->mValue)) && // If value >= *position && - !compare(extractKey(itNext.mpNode->mValue), key)) // if value <= *itNext... - { - if(position.mpNode->mpNodeRight) // If there are any nodes to the right... [this expression will always be true as long as we aren't at the end()] - { - bForceToLeft = true; // Specifically insert in front of (to the left of) itNext (and thus after 'position'). - return itNext.mpNode; - } - - bForceToLeft = false; - return position.mpNode; - } - - bForceToLeft = false; - return NULL; // The above specified hint was not useful, then we do a regular insertion. - } - - // This pathway shouldn't be commonly executed, as the user shouldn't be calling - // this hinted version of insert if the user isn't providing a useful hint. - if(mnSize && !compare(key, extractKey(((node_type*)mAnchor.mpNodeRight)->mValue))) // If we are non-empty and the value is >= the last node... - { - bForceToLeft =false; - return (node_type*)mAnchor.mpNodeRight; - } - - bForceToLeft = false; - return NULL; - } - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class... Args> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertValueHint(true_type, const_iterator position, Args&&... args) // true_type means keys are unique. - { - // This is the pathway for insertion of unique keys (map and set, but not multimap and multiset). - // - // We follow the same approach as SGI STL/STLPort and use the position as - // a forced insertion position for the value when possible. - - node_type* pNodeNew = DoCreateNode(eastl::forward<Args>(args)...); // Note that pNodeNew->mpLeft, mpRight, mpParent, will be uninitialized. - const key_type& key(extract_key{}(pNodeNew->mValue)); - - bool bForceToLeft; - node_type* pPosition = DoGetKeyInsertionPositionUniqueKeysHint(position, bForceToLeft, key); - - if (!pPosition) - { - bool canInsert; - pPosition = DoGetKeyInsertionPositionUniqueKeys(canInsert, key); - - if (!canInsert) - { - DoFreeNode(pNodeNew); - return iterator(pPosition); - } - - bForceToLeft = false; - } - - return DoInsertValueImpl(pPosition, bForceToLeft, key, pNodeNew); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <class... Args> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertValueHint(false_type, const_iterator position, Args&&... args) // false_type means keys are not unique. - { - // This is the pathway for insertion of non-unique keys (multimap and multiset, but not map and set). - // - // We follow the same approach as SGI STL/STLPort and use the position as - // a forced insertion position for the value when possible. - - node_type* pNodeNew = DoCreateNode(eastl::forward<Args>(args)...); // Note that pNodeNew->mpLeft, mpRight, mpParent, will be uninitialized. - const key_type& key(extract_key{}(pNodeNew->mValue)); - - bool bForceToLeft; - node_type* pPosition = DoGetKeyInsertionPositionNonuniqueKeysHint(position, bForceToLeft, key); - - if (!pPosition) - { - pPosition = DoGetKeyInsertionPositionNonuniqueKeys(key); - bForceToLeft = false; - } - - return DoInsertValueImpl(pPosition, bForceToLeft, key, pNodeNew); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertValueHint(true_type, const_iterator position, value_type&& value) // true_type means keys are unique. - { - // This is the pathway for insertion of unique keys (map and set, but not multimap and multiset). - // - // We follow the same approach as SGI STL/STLPort and use the position as - // a forced insertion position for the value when possible. - - extract_key extractKey; - key_type key(extractKey(value)); - bool bForceToLeft; - node_type* pPosition = DoGetKeyInsertionPositionUniqueKeysHint(position, bForceToLeft, key); - - if(pPosition) - return DoInsertValueImpl(pPosition, bForceToLeft, key, eastl::move(value)); - else - return DoInsertValue(has_unique_keys_type(), eastl::move(value)).first; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertValueHint(false_type, const_iterator position, value_type&& value) // false_type means keys are not unique. - { - // This is the pathway for insertion of non-unique keys (multimap and multiset, but not map and set). - // - // We follow the same approach as SGI STL/STLPort and use the position as - // a forced insertion position for the value when possible. - extract_key extractKey; - key_type key(extractKey(value)); - bool bForceToLeft; - node_type* pPosition = DoGetKeyInsertionPositionNonuniqueKeysHint(position, bForceToLeft, key); - - if(pPosition) - return DoInsertValueImpl(pPosition, bForceToLeft, key, eastl::move(value)); - else - return DoInsertValue(has_unique_keys_type(), eastl::move(value)); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(true_type, const_iterator position, const key_type& key) // true_type means keys are unique. - { - bool bForceToLeft; - node_type* pPosition = DoGetKeyInsertionPositionUniqueKeysHint(position, bForceToLeft, key); - - if(pPosition) - return DoInsertKeyImpl(pPosition, bForceToLeft, key); - else - return DoInsertKey(has_unique_keys_type(), key).first; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(false_type, const_iterator position, const key_type& key) // false_type means keys are not unique. - { - // This is the pathway for insertion of non-unique keys (multimap and multiset, but not map and set). - // - // We follow the same approach as SGI STL/STLPort and use the position as - // a forced insertion position for the value when possible. - bool bForceToLeft; - node_type* pPosition = DoGetKeyInsertionPositionNonuniqueKeysHint(position, bForceToLeft, key); - - if(pPosition) - return DoInsertKeyImpl(pPosition, bForceToLeft, key); - else - return DoInsertKey(has_unique_keys_type(), key); // We are empty or we are inserting at the end. - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::DoInsertKeyImpl(node_type* pNodeParent, bool bForceToLeft, const key_type& key) - { - RBTreeSide side; - extract_key extractKey; - - // The reason we may want to have bForceToLeft == true is that pNodeParent->mValue and value may be equal. - // In that case it doesn't matter what side we insert on, except that the C++ LWG #233 improvement report - // suggests that we should use the insert hint position to force an ordering. So that's what we do. - if(bForceToLeft || (pNodeParent == &mAnchor) || compare(key, extractKey(pNodeParent->mValue))) - side = kRBTreeSideLeft; - else - side = kRBTreeSideRight; - - node_type* const pNodeNew = DoCreateNodeFromKey(key); // Note that pNodeNew->mpLeft, mpRight, mpParent, will be uninitialized. - RBTreeInsert(pNodeNew, pNodeParent, &mAnchor, side); - mnSize++; - - return iterator(pNodeNew); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - void rbtree<K, V, C, A, E, bM, bU>::insert(std::initializer_list<value_type> ilist) - { - for(typename std::initializer_list<value_type>::iterator it = ilist.begin(), itEnd = ilist.end(); it != itEnd; ++it) - DoInsertValue(has_unique_keys_type(), eastl::move(*it)); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <typename InputIterator> - void rbtree<K, V, C, A, E, bM, bU>::insert(InputIterator first, InputIterator last) - { - for( ; first != last; ++first) - DoInsertValue(has_unique_keys_type(), *first); // Or maybe we should call 'insert(end(), *first)' instead. If the first-last range was sorted then this might make some sense. - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline void rbtree<K, V, C, A, E, bM, bU>::clear() - { - // Erase the entire tree. DoNukeSubtree is not a - // conventional erase function, as it does no rebalancing. - DoNukeSubtree((node_type*)mAnchor.mpNodeParent); - reset_lose_memory(); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline void rbtree<K, V, C, A, E, bM, bU>::reset_lose_memory() - { - // The reset_lose_memory function is a special extension function which unilaterally - // resets the container to an empty state without freeing the memory of - // the contained objects. This is useful for very quickly tearing down a - // container built into scratch memory. - mAnchor.mpNodeRight = &mAnchor; - mAnchor.mpNodeLeft = &mAnchor; - mAnchor.mpNodeParent = NULL; - mAnchor.mColor = kRBTreeColorRed; - mnSize = 0; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::erase(const_iterator position) - { - const iterator iErase(position.mpNode); - --mnSize; // Interleave this between the two references to itNext. We expect no exceptions to occur during the code below. - ++position; - RBTreeErase(iErase.mpNode, &mAnchor); - DoFreeNode(iErase.mpNode); - return iterator(position.mpNode); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::erase(const_iterator first, const_iterator last) - { - // We expect that if the user means to clear the container, they will call clear. - if(EASTL_LIKELY((first.mpNode != mAnchor.mpNodeLeft) || (last.mpNode != &mAnchor))) // If (first != begin or last != end) ... - { - // Basic implementation: - while(first != last) - first = erase(first); - return iterator(first.mpNode); - - // Inlined implementation: - //size_type n = 0; - //while(first != last) - //{ - // const iterator itErase(first); - // ++n; - // ++first; - // RBTreeErase(itErase.mpNode, &mAnchor); - // DoFreeNode(itErase.mpNode); - //} - //mnSize -= n; - //return first; - } - - clear(); - return iterator((node_type*)&mAnchor); // Same as: return end(); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator - rbtree<K, V, C, A, E, bM, bU>::erase(const_reverse_iterator position) - { - return reverse_iterator(erase((++position).base())); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator - rbtree<K, V, C, A, E, bM, bU>::erase(const_reverse_iterator first, const_reverse_iterator last) - { - // Version which erases in order from first to last. - // difference_type i(first.base() - last.base()); - // while(i--) - // first = erase(first); - // return first; - - // Version which erases in order from last to first, but is slightly more efficient: - return reverse_iterator(erase((++last).base(), (++first).base())); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline void rbtree<K, V, C, A, E, bM, bU>::erase(const key_type* first, const key_type* last) - { - // We have no choice but to run a loop like this, as the first/last range could - // have values that are discontiguously located in the tree. And some may not - // even be in the tree. - while(first != last) - erase(*first++); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::find(const key_type& key) - { - // To consider: Implement this instead via calling lower_bound and - // inspecting the result. The following is an implementation of this: - // const iterator it(lower_bound(key)); - // return ((it.mpNode == &mAnchor) || compare(key, extractKey(it.mpNode->mValue))) ? iterator(&mAnchor) : it; - // We don't currently implement the above because in practice people tend to call - // find a lot with trees, but very uncommonly call lower_bound. - extract_key extractKey; - - node_type* pCurrent = (node_type*)mAnchor.mpNodeParent; // Start with the root node. - node_type* pRangeEnd = (node_type*)&mAnchor; // Set it to the container end for now. - - while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree. - { - if(EASTL_LIKELY(!compare(extractKey(pCurrent->mValue), key))) // If pCurrent is >= key... - { - pRangeEnd = pCurrent; - pCurrent = (node_type*)pCurrent->mpNodeLeft; - } - else - { - EASTL_VALIDATE_COMPARE(!compare(key, extractKey(pCurrent->mValue))); // Validate that the compare function is sane. - pCurrent = (node_type*)pCurrent->mpNodeRight; - } - } - - if(EASTL_LIKELY((pRangeEnd != &mAnchor) && !compare(key, extractKey(pRangeEnd->mValue)))) - return iterator(pRangeEnd); - return iterator((node_type*)&mAnchor); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator - rbtree<K, V, C, A, E, bM, bU>::find(const key_type& key) const - { - typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type; - return const_iterator(const_cast<rbtree_type*>(this)->find(key)); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <typename U, typename Compare2> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::find_as(const U& u, Compare2 compare2) - { - extract_key extractKey; - - node_type* pCurrent = (node_type*)mAnchor.mpNodeParent; // Start with the root node. - node_type* pRangeEnd = (node_type*)&mAnchor; // Set it to the container end for now. - - while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree. - { - if(EASTL_LIKELY(!compare2(extractKey(pCurrent->mValue), u))) // If pCurrent is >= u... - { - pRangeEnd = pCurrent; - pCurrent = (node_type*)pCurrent->mpNodeLeft; - } - else - { - EASTL_VALIDATE_COMPARE(!compare2(u, extractKey(pCurrent->mValue))); // Validate that the compare function is sane. - pCurrent = (node_type*)pCurrent->mpNodeRight; - } - } - - if(EASTL_LIKELY((pRangeEnd != &mAnchor) && !compare2(u, extractKey(pRangeEnd->mValue)))) - return iterator(pRangeEnd); - return iterator((node_type*)&mAnchor); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template <typename U, typename Compare2> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator - rbtree<K, V, C, A, E, bM, bU>::find_as(const U& u, Compare2 compare2) const - { - typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type; - return const_iterator(const_cast<rbtree_type*>(this)->find_as(u, compare2)); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::lower_bound(const key_type& key) - { - extract_key extractKey; - - node_type* pCurrent = (node_type*)mAnchor.mpNodeParent; // Start with the root node. - node_type* pRangeEnd = (node_type*)&mAnchor; // Set it to the container end for now. - - while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree. - { - if(EASTL_LIKELY(!compare(extractKey(pCurrent->mValue), key))) // If pCurrent is >= key... - { - pRangeEnd = pCurrent; - pCurrent = (node_type*)pCurrent->mpNodeLeft; - } - else - { - EASTL_VALIDATE_COMPARE(!compare(key, extractKey(pCurrent->mValue))); // Validate that the compare function is sane. - pCurrent = (node_type*)pCurrent->mpNodeRight; - } - } - - return iterator(pRangeEnd); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator - rbtree<K, V, C, A, E, bM, bU>::lower_bound(const key_type& key) const - { - typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type; - return const_iterator(const_cast<rbtree_type*>(this)->lower_bound(key)); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::iterator - rbtree<K, V, C, A, E, bM, bU>::upper_bound(const key_type& key) - { - extract_key extractKey; - - node_type* pCurrent = (node_type*)mAnchor.mpNodeParent; // Start with the root node. - node_type* pRangeEnd = (node_type*)&mAnchor; // Set it to the container end for now. - - while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree. - { - if(EASTL_LIKELY(compare(key, extractKey(pCurrent->mValue)))) // If key is < pCurrent... - { - EASTL_VALIDATE_COMPARE(!compare(extractKey(pCurrent->mValue), key)); // Validate that the compare function is sane. - pRangeEnd = pCurrent; - pCurrent = (node_type*)pCurrent->mpNodeLeft; - } - else - pCurrent = (node_type*)pCurrent->mpNodeRight; - } - - return iterator(pRangeEnd); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator - rbtree<K, V, C, A, E, bM, bU>::upper_bound(const key_type& key) const - { - typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type; - return const_iterator(const_cast<rbtree_type*>(this)->upper_bound(key)); - } - - - // To do: Move this validate function entirely to a template-less implementation. - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - bool rbtree<K, V, C, A, E, bM, bU>::validate() const - { - // Red-black trees have the following canonical properties which we validate here: - // 1 Every node is either red or black. - // 2 Every leaf (NULL) is black by defintion. Any number of black nodes may appear in a sequence. - // 3 If a node is red, then both its children are black. Thus, on any path from - // the root to a leaf, red nodes must not be adjacent. - // 4 Every simple path from a node to a descendant leaf contains the same number of black nodes. - // 5 The mnSize member of the tree must equal the number of nodes in the tree. - // 6 The tree is sorted as per a conventional binary tree. - // 7 The comparison function is sane; it obeys strict weak ordering. If compare(a,b) is true, then compare(b,a) must be false. Both cannot be true. - - extract_key extractKey; - - if(mnSize) - { - // Verify basic integrity. - //if(!mAnchor.mpNodeParent || (mAnchor.mpNodeLeft == mAnchor.mpNodeRight)) - // return false; // Fix this for case of empty tree. - - if(mAnchor.mpNodeLeft != RBTreeGetMinChild(mAnchor.mpNodeParent)) - return false; - - if(mAnchor.mpNodeRight != RBTreeGetMaxChild(mAnchor.mpNodeParent)) - return false; - - const size_t nBlackCount = RBTreeGetBlackCount(mAnchor.mpNodeParent, mAnchor.mpNodeLeft); - size_type nIteratedSize = 0; - - for(const_iterator it = begin(); it != end(); ++it, ++nIteratedSize) - { - const node_type* const pNode = (const node_type*)it.mpNode; - const node_type* const pNodeRight = (const node_type*)pNode->mpNodeRight; - const node_type* const pNodeLeft = (const node_type*)pNode->mpNodeLeft; - - // Verify #7 above. - if(pNodeRight && compare(extractKey(pNodeRight->mValue), extractKey(pNode->mValue)) && compare(extractKey(pNode->mValue), extractKey(pNodeRight->mValue))) // Validate that the compare function is sane. - return false; - - // Verify #7 above. - if(pNodeLeft && compare(extractKey(pNodeLeft->mValue), extractKey(pNode->mValue)) && compare(extractKey(pNode->mValue), extractKey(pNodeLeft->mValue))) // Validate that the compare function is sane. - return false; - - // Verify item #1 above. - if((pNode->mColor != kRBTreeColorRed) && (pNode->mColor != kRBTreeColorBlack)) - return false; - - // Verify item #3 above. - if(pNode->mColor == kRBTreeColorRed) - { - if((pNodeRight && (pNodeRight->mColor == kRBTreeColorRed)) || - (pNodeLeft && (pNodeLeft->mColor == kRBTreeColorRed))) - return false; - } - - // Verify item #6 above. - if(pNodeRight && compare(extractKey(pNodeRight->mValue), extractKey(pNode->mValue))) - return false; - - if(pNodeLeft && compare(extractKey(pNode->mValue), extractKey(pNodeLeft->mValue))) - return false; - - if(!pNodeRight && !pNodeLeft) // If we are at a bottom node of the tree... - { - // Verify item #4 above. - if(RBTreeGetBlackCount(mAnchor.mpNodeParent, pNode) != nBlackCount) - return false; - } - } - - // Verify item #5 above. - if(nIteratedSize != mnSize) - return false; - - return true; - } - else - { - if((mAnchor.mpNodeLeft != &mAnchor) || (mAnchor.mpNodeRight != &mAnchor)) - return false; - } - - return true; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline int rbtree<K, V, C, A, E, bM, bU>::validate_iterator(const_iterator i) const - { - // To do: Come up with a more efficient mechanism of doing this. - - for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp) - { - if(temp == i) - return (isf_valid | isf_current | isf_can_dereference); - } - - if(i == end()) - return (isf_valid | isf_current); - - return isf_none; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoAllocateNode() - { - auto* pNode = (node_type*)allocate_memory(mAllocator, sizeof(node_type), EASTL_ALIGN_OF(node_type), 0); - EASTL_ASSERT_MSG(pNode != nullptr, "the behaviour of eastl::allocators that return nullptr is not defined."); - - return pNode; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - inline void rbtree<K, V, C, A, E, bM, bU>::DoFreeNode(node_type* pNode) - { - pNode->~node_type(); - EASTLFree(mAllocator, pNode, sizeof(node_type)); - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoCreateNodeFromKey(const key_type& key) - { - // Note that this function intentionally leaves the node pointers uninitialized. - // The caller would otherwise just turn right around and modify them, so there's - // no point in us initializing them to anything (except in a debug build). - node_type* const pNode = DoAllocateNode(); - - #if EASTL_EXCEPTIONS_ENABLED - try - { - #endif - ::new (eastl::addressof(pNode->mValue)) value_type(pair_first_construct, key); - - #if EASTL_EXCEPTIONS_ENABLED - } - catch(...) - { - DoFreeNode(pNode); - throw; - } - #endif - - #if EASTL_DEBUG - pNode->mpNodeRight = NULL; - pNode->mpNodeLeft = NULL; - pNode->mpNodeParent = NULL; - pNode->mColor = kRBTreeColorBlack; - #endif - - return pNode; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoCreateNode(const value_type& value) - { - // Note that this function intentionally leaves the node pointers uninitialized. - // The caller would otherwise just turn right around and modify them, so there's - // no point in us initializing them to anything (except in a debug build). - node_type* const pNode = DoAllocateNode(); - - #if EASTL_EXCEPTIONS_ENABLED - try - { - #endif - ::new(eastl::addressof(pNode->mValue)) value_type(value); - #if EASTL_EXCEPTIONS_ENABLED - } - catch(...) - { - DoFreeNode(pNode); - throw; - } - #endif - - #if EASTL_DEBUG - pNode->mpNodeRight = NULL; - pNode->mpNodeLeft = NULL; - pNode->mpNodeParent = NULL; - pNode->mColor = kRBTreeColorBlack; - #endif - - return pNode; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoCreateNode(value_type&& value) - { - // Note that this function intentionally leaves the node pointers uninitialized. - // The caller would otherwise just turn right around and modify them, so there's - // no point in us initializing them to anything (except in a debug build). - node_type* const pNode = DoAllocateNode(); - - #if EASTL_EXCEPTIONS_ENABLED - try - { - #endif - ::new(eastl::addressof(pNode->mValue)) value_type(eastl::move(value)); - #if EASTL_EXCEPTIONS_ENABLED - } - catch(...) - { - DoFreeNode(pNode); - throw; - } - #endif - - #if EASTL_DEBUG - pNode->mpNodeRight = NULL; - pNode->mpNodeLeft = NULL; - pNode->mpNodeParent = NULL; - pNode->mColor = kRBTreeColorBlack; - #endif - - return pNode; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - template<class... Args> - typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoCreateNode(Args&&... args) - { - // Note that this function intentionally leaves the node pointers uninitialized. - // The caller would otherwise just turn right around and modify them, so there's - // no point in us initializing them to anything (except in a debug build). - node_type* const pNode = DoAllocateNode(); - - #if EASTL_EXCEPTIONS_ENABLED - try - { - #endif - ::new(eastl::addressof(pNode->mValue)) value_type(eastl::forward<Args>(args)...); - #if EASTL_EXCEPTIONS_ENABLED - } - catch(...) - { - DoFreeNode(pNode); - throw; - } - #endif - - #if EASTL_DEBUG - pNode->mpNodeRight = NULL; - pNode->mpNodeLeft = NULL; - pNode->mpNodeParent = NULL; - pNode->mColor = kRBTreeColorBlack; - #endif - - return pNode; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoCreateNode(const node_type* pNodeSource, node_type* pNodeParent) - { - node_type* const pNode = DoCreateNode(pNodeSource->mValue); - - pNode->mpNodeRight = NULL; - pNode->mpNodeLeft = NULL; - pNode->mpNodeParent = pNodeParent; - pNode->mColor = pNodeSource->mColor; - - return pNode; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - typename rbtree<K, V, C, A, E, bM, bU>::node_type* - rbtree<K, V, C, A, E, bM, bU>::DoCopySubtree(const node_type* pNodeSource, node_type* pNodeDest) - { - node_type* const pNewNodeRoot = DoCreateNode(pNodeSource, pNodeDest); - - #if EASTL_EXCEPTIONS_ENABLED - try - { - #endif - // Copy the right side of the tree recursively. - if(pNodeSource->mpNodeRight) - pNewNodeRoot->mpNodeRight = DoCopySubtree((const node_type*)pNodeSource->mpNodeRight, pNewNodeRoot); - - node_type* pNewNodeLeft; - - for(pNodeSource = (node_type*)pNodeSource->mpNodeLeft, pNodeDest = pNewNodeRoot; - pNodeSource; - pNodeSource = (node_type*)pNodeSource->mpNodeLeft, pNodeDest = pNewNodeLeft) - { - pNewNodeLeft = DoCreateNode(pNodeSource, pNodeDest); - - pNodeDest->mpNodeLeft = pNewNodeLeft; - - // Copy the right side of the tree recursively. - if(pNodeSource->mpNodeRight) - pNewNodeLeft->mpNodeRight = DoCopySubtree((const node_type*)pNodeSource->mpNodeRight, pNewNodeLeft); - } - #if EASTL_EXCEPTIONS_ENABLED - } - catch(...) - { - DoNukeSubtree(pNewNodeRoot); - throw; - } - #endif - - return pNewNodeRoot; - } - - - template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU> - void rbtree<K, V, C, A, E, bM, bU>::DoNukeSubtree(node_type* pNode) - { - while(pNode) // Recursively traverse the tree and destroy items as we go. - { - DoNukeSubtree((node_type*)pNode->mpNodeRight); - - node_type* const pNodeLeft = (node_type*)pNode->mpNodeLeft; - DoFreeNode(pNode); - pNode = pNodeLeft; - } - } - - - - /////////////////////////////////////////////////////////////////////// - // global operators - /////////////////////////////////////////////////////////////////////// - - template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU> - inline bool operator==(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b) - { - return (a.size() == b.size()) && eastl::equal(a.begin(), a.end(), b.begin()); - } - - - // Note that in operator< we do comparisons based on the tree value_type with operator<() of the - // value_type instead of the tree's Compare function. For set/multiset, the value_type is T, while - // for map/multimap the value_type is a pair<Key, T>. operator< for pair can be seen by looking - // utility.h, but it basically is uses the operator< for pair.first and pair.second. The C++ standard - // appears to require this behaviour, whether intentionally or not. If anything, a good reason to do - // this is for consistency. A map and a vector that contain the same items should compare the same. - template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU> - inline bool operator<(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b) - { - return eastl::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); - } - - - template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU> - inline bool operator!=(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b) - { - return !(a == b); - } - - - template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU> - inline bool operator>(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b) - { - return b < a; - } - - - template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU> - inline bool operator<=(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b) - { - return !(b < a); - } - - - template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU> - inline bool operator>=(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b) - { - return !(a < b); - } - - - template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU> - inline void swap(rbtree<K, V, C, A, E, bM, bU>& a, rbtree<K, V, C, A, E, bM, bU>& b) - { - a.swap(b); - } - - -} // namespace eastl - - -EA_RESTORE_VC_WARNING(); - - -#endif // Header include guard |