aboutsummaryrefslogtreecommitdiff
path: root/include/EASTL/bonus/list_map.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/EASTL/bonus/list_map.h')
-rw-r--r--include/EASTL/bonus/list_map.h932
1 files changed, 932 insertions, 0 deletions
diff --git a/include/EASTL/bonus/list_map.h b/include/EASTL/bonus/list_map.h
new file mode 100644
index 0000000..8a080d6
--- /dev/null
+++ b/include/EASTL/bonus/list_map.h
@@ -0,0 +1,932 @@
+/////////////////////////////////////////////////////////////////////////////
+// Copyright (c) Electronic Arts Inc. All rights reserved.
+/////////////////////////////////////////////////////////////////////////////
+
+
+#ifndef EASTL_LIST_MAP_H
+#define EASTL_LIST_MAP_H
+
+
+#include <EASTL/map.h>
+
+
+namespace eastl
+{
+
+ /// EASTL_MAP_DEFAULT_NAME
+ ///
+ /// Defines a default container name in the absence of a user-provided name.
+ ///
+ #ifndef EASTL_LIST_MAP_DEFAULT_NAME
+ #define EASTL_LIST_MAP_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " list_map" // Unless the user overrides something, this is "EASTL list_map".
+ #endif
+
+ /// EASTL_MAP_DEFAULT_ALLOCATOR
+ ///
+ #ifndef EASTL_LIST_MAP_DEFAULT_ALLOCATOR
+ #define EASTL_LIST_MAP_DEFAULT_ALLOCATOR allocator_type(EASTL_LIST_MAP_DEFAULT_NAME)
+ #endif
+
+
+ /// list_map_data_base
+ ///
+ /// We define a list_map_data_base separately from list_map_data (below), because it
+ /// allows us to have non-templated operations, and it makes it so that the
+ /// list_map 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 list_map harder, given that the node pointers are of type
+ /// list_map_data_base and not list_map_data.
+ ///
+ struct list_map_data_base
+ {
+ list_map_data_base* mpNext;
+ list_map_data_base* mpPrev;
+ };
+
+
+ /// list_map_data
+ ///
+ template <typename Value>
+ struct list_map_data : public list_map_data_base
+ {
+ typedef Value value_type;
+
+ list_map_data(const value_type& value);
+
+ value_type mValue; // This is a pair of key/value.
+ };
+
+
+ /// list_map_iterator
+ ///
+ template <typename T, typename Pointer, typename Reference>
+ struct list_map_iterator
+ {
+ typedef list_map_iterator<T, Pointer, Reference> this_type;
+ typedef list_map_iterator<T, T*, T&> iterator;
+ typedef list_map_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 list_map_data_base base_node_type;
+ typedef list_map_data<T> node_type;
+ typedef Pointer pointer;
+ typedef Reference reference;
+ typedef EASTL_ITC_NS::bidirectional_iterator_tag iterator_category;
+
+ public:
+ node_type* mpNode;
+
+ public:
+ list_map_iterator();
+ list_map_iterator(const base_node_type* pNode);
+ list_map_iterator(const iterator& x);
+
+ reference operator*() const;
+ pointer operator->() const;
+
+ this_type& operator++();
+ this_type operator++(int);
+
+ this_type& operator--();
+ this_type operator--(int);
+
+ }; // list_map_iterator
+
+
+ /// use_value_first
+ ///
+ /// operator()(x) simply returns x.mValue.first. Used in list_map.
+ /// This is similar to eastl::use_first, however it assumes that the input type is an object
+ /// whose mValue is an eastl::pair, and the first value in the pair is the desired return.
+ ///
+ template <typename Object>
+ struct use_value_first
+ {
+ typedef Object argument_type;
+ typedef typename Object::value_type::first_type result_type;
+
+ const result_type& operator()(const Object& x) const
+ { return x.mValue.first; }
+ };
+
+
+ /// list_map
+ ///
+ /// Implements a map like container, which also provides functionality similar to a list.
+ ///
+ /// Note: Like a map, keys must still be unique. As such, push_back() and push_front() operations
+ /// return a bool indicating success, or failure if the entry's key is already in use.
+ ///
+ /// list_map is designed to improve performance for situations commonly implemented as:
+ /// A map, which must be iterated over to find the oldest entry, or purge expired entries.
+ /// A list, which must be iterated over to remove a player's record when they sign off.
+ ///
+ /// list_map requires a little more memory per node than either a list or map alone,
+ /// and many of list_map's functions have a higher operational cost (CPU time) than their
+ /// counterparts in list and map. However, as the node count increases, list_map quickly outperforms
+ /// either a list or a map when find [by-index] and front/back type operations are required.
+ ///
+ /// In essence, list_map avoids O(n) iterations at the expense of additional costs to quick (O(1) and O(log n) operations:
+ /// push_front(), push_back(), pop_front() and pop_back() have O(log n) operation time, similar to map::insert(), rather than O(1) time like a list,
+ /// however, front() and back() maintain O(1) operation time.
+ ///
+ /// As a canonical example, consider a large backlog of player group invites, which are removed when either:
+ /// The invitation times out - in main loop: while( !listMap.empty() && listMap.front().IsExpired() ) { listMap.pop_front(); }
+ /// The player rejects the outstanding invitation - on rejection: iter = listMap.find(playerId); if (iter != listMap.end()) { listMap.erase(iter); }
+ ///
+ /// For a similar example, consider a high volume pending request container which must:
+ /// Time out old requests (similar to invites timing out above)
+ /// Remove requests once they've been handled (similar to rejecting invites above)
+ ///
+ /// For such usage patterns, the performance benefits of list_map become dramatic with
+ /// common O(n) operations once the node count rises to hundreds or more.
+ ///
+ /// When high performance is a priority, Containers with thousands of nodes or more
+ /// can quickly result in unacceptable performance when executing even infrequenty O(n) operations.
+ ///
+ /// In order to maintain strong performance, avoid iterating over list_map whenever possible.
+ ///
+ ///////////////////////////////////////////////////////////////////////
+ /// 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.
+ ///
+ ///////////////////////////////////////////////////////////////////////
+ /// Pool allocation
+ /// If you want to make a custom memory pool for a list_map container, your pool
+ /// needs to contain items of type list_map::node_type. So if you have a memory
+ /// pool that has a constructor that takes the size of pool items and the
+ /// count of pool items, you would do this (assuming that MemoryPool implements
+ /// the Allocator interface):
+ /// typedef list_map<Widget, int, less<Widget>, MemoryPool> WidgetMap; // Delare your WidgetMap type.
+ /// MemoryPool myPool(sizeof(WidgetMap::node_type), 100); // Make a pool of 100 Widget nodes.
+ /// WidgetMap myMap(&myPool); // Create a map that uses the pool.
+ ///
+ template <typename Key, typename T, typename Compare = eastl::less<Key>, typename Allocator = EASTLAllocatorType>
+ class list_map
+ : protected rbtree<Key, eastl::list_map_data<eastl::pair<const Key, T> >, Compare, Allocator, eastl::use_value_first<eastl::list_map_data<eastl::pair<const Key, T> > >, true, true>
+ {
+ public:
+ typedef rbtree<Key, eastl::list_map_data<eastl::pair<const Key, T> >, Compare, Allocator,
+ eastl::use_value_first<eastl::list_map_data<eastl::pair<const Key, T> > >, true, true> base_type;
+ typedef list_map<Key, T, Compare, Allocator> this_type;
+ typedef typename base_type::size_type size_type;
+ typedef typename base_type::key_type key_type;
+ typedef T mapped_type;
+ typedef typename eastl::pair<const Key, T> value_type; // This is intentionally different from base_type::value_type
+ typedef value_type& reference;
+ typedef const value_type& const_reference;
+ typedef typename base_type::node_type node_type; // Despite the internal and external values being different, we're keeping the node type the same as the base
+ // in order to allow for pool allocation. See EASTL/map.h for more information.
+ typedef typename eastl::list_map_iterator<value_type, value_type*, value_type&> iterator; // This is intentionally different from base_type::iterator
+ typedef typename eastl::list_map_iterator<value_type, const value_type*, const value_type&> const_iterator; // This is intentionally different from base_type::const_iterator
+ typedef eastl::reverse_iterator<iterator> reverse_iterator;
+ typedef eastl::reverse_iterator<const_iterator> const_reverse_iterator;
+ typedef typename base_type::allocator_type allocator_type;
+ typedef typename eastl::pair<iterator, bool> insert_return_type; // This is intentionally removed, as list_map doesn't support insert() functions, in favor of list like push_back and push_front
+ typedef typename eastl::use_first<value_type> extract_key; // This is intentionally different from base_type::extract_key
+
+ using base_type::get_allocator;
+ using base_type::set_allocator;
+ using base_type::key_comp;
+ using base_type::empty;
+ using base_type::size;
+
+ protected:
+ typedef typename eastl::list_map_data<eastl::pair<const Key, T> > internal_value_type;
+
+ protected:
+ // internal base node, acting as the sentinel for list like behaviors
+ list_map_data_base mNode;
+
+ public:
+ list_map(const allocator_type& allocator = EASTL_LIST_MAP_DEFAULT_ALLOCATOR);
+ list_map(const Compare& compare, const allocator_type& allocator = EASTL_MAP_DEFAULT_ALLOCATOR);
+
+ // To do: Implement the following:
+
+ //list_map(const this_type& x);
+ //list_map(this_type&& x);
+ //list_map(this_type&& x, const allocator_type& allocator);
+ //list_map(std::initializer_list<mapped_type> ilist, const Compare& compare = Compare(), const allocator_type& allocator = EASTL_LIST_MAP_DEFAULT_ALLOCATOR);
+
+ //template <typename Iterator>
+ //list_map(Iterator itBegin, Iterator itEnd);
+
+ //this_type& operator=(const this_type& x);
+ //this_type& operator=(std::initializer_list<mapped_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:
+ // List like methods
+ reference front();
+ const_reference front() const;
+
+ reference back();
+ const_reference back() const;
+
+ // push_front and push_back which takes in a key/value pair
+ bool push_front(const value_type& value);
+ bool push_back(const value_type& value);
+
+ // push_front and push_back which take key and value separately, for convenience
+ bool push_front(const key_type& key, const mapped_type& value);
+ bool push_back(const key_type& key, const mapped_type& value);
+
+ void pop_front();
+ void pop_back();
+
+ public:
+ // Map like methods
+ iterator find(const key_type& key);
+ const_iterator find(const key_type& key) const;
+
+ 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;
+
+ size_type count(const key_type& key) const;
+ size_type erase(const key_type& key);
+
+ public:
+ // Shared methods which are common to list and map
+ iterator erase(const_iterator position);
+ reverse_iterator erase(const_reverse_iterator position);
+
+ void clear();
+ void reset_lose_memory();
+
+ bool validate() const;
+ int validate_iterator(const_iterator i) const;
+
+ public:
+ // list like functionality which is in consideration for implementation:
+ // iterator insert(const_iterator position, const value_type& value);
+ // void remove(const mapped_type& x);
+
+ public:
+ // list like functionality which may be implemented, but is discouraged from implementation:
+ // due to the liklihood that they would require O(n) time to execute.
+ // template <typename Predicate>
+ // void remove_if(Predicate);
+ // void reverse();
+ // void sort();
+ // template<typename Compare>
+ // void sort(Compare compare);
+
+ public:
+ // map like functionality which list_map does not support, due to abmiguity with list like functionality:
+ #if !defined(EA_COMPILER_NO_DELETED_FUNCTIONS)
+ template <typename InputIterator>
+ list_map(InputIterator first, InputIterator last, const Compare& compare, const allocator_type& allocator = EASTL_RBTREE_DEFAULT_ALLOCATOR) = delete;
+
+ insert_return_type insert(const value_type& value) = delete;
+ iterator insert(const_iterator position, const value_type& value) = delete;
+
+ template <typename InputIterator>
+ void insert(InputIterator first, InputIterator last) = delete;
+
+ insert_return_type insert(const key_type& key) = delete;
+
+ iterator erase(const_iterator first, const_iterator last) = delete;
+ reverse_iterator erase(reverse_iterator first, reverse_iterator last) = delete;
+
+ void erase(const key_type* first, const key_type* last) = delete;
+
+ iterator lower_bound(const key_type& key) = delete;
+ const_iterator lower_bound(const key_type& key) const = delete;
+
+ iterator upper_bound(const key_type& key) = delete;
+ const_iterator upper_bound(const key_type& key) const = delete;
+
+ eastl::pair<iterator, iterator> equal_range(const key_type& key) = delete;
+ eastl::pair<const_iterator, const_iterator> equal_range(const key_type& key) const = delete;
+
+ mapped_type& operator[](const key_type& key) = delete; // Of map, multimap, set, and multimap, only map has operator[].
+ #endif
+
+ public:
+ // list like functionality which list_map does not support, due to ambiguity with map like functionality:
+ #if 0
+ reference push_front() = delete;
+ void* push_front_uninitialized() = delete;
+
+ reference push_back() = delete;
+ void* push_back_uninitialized() = delete;
+
+ iterator insert(const_iterator position) = delete;
+
+ void insert(const_iterator position, size_type n, const value_type& value) = delete;
+
+ template <typename InputIterator>
+ void insert(const_iterator position, InputIterator first, InputIterator last) = delete;
+
+ iterator erase(const_iterator first, const_iterator last) = delete;
+ reverse_iterator erase(const_reverse_iterator first, const_reverse_iterator last) = delete;
+
+ void splice(const_iterator position, this_type& x) = delete
+ void splice(const_iterator position, this_type& x, const_iterator i) = delete;
+ void splice(const_iterator position, this_type& x, const_iterator first, const_iterator last) = delete;
+
+ void merge(this_type& x) = delete;
+
+ template <typename Compare>
+ void merge(this_type& x, Compare compare) = delete;
+
+ void unique() = delete; // Uniqueness is enforced by map functionality
+
+ template <typename BinaryPredicate>
+ void unique(BinaryPredicate) = delete; // Uniqueness is enforced by map functionality
+ #endif
+
+ }; // list_map
+
+
+ ///////////////////////////////////////////////////////////////////////
+ // list_map_data
+ ///////////////////////////////////////////////////////////////////////
+
+ template <typename Value>
+ inline list_map_data<Value>::list_map_data(const Value& value)
+ : mValue(value)
+ {
+ mpNext = NULL; // GCC 4.8 is generating warnings about referencing these values in list_map::push_front unless we
+ mpPrev = NULL; // initialize them here. The compiler seems to be mistaken, as our code isn't actually using them unintialized.
+ }
+
+
+ ///////////////////////////////////////////////////////////////////////
+ // list_map_iterator
+ ///////////////////////////////////////////////////////////////////////
+
+ template <typename T, typename Pointer, typename Reference>
+ inline list_map_iterator<T, Pointer, Reference>::list_map_iterator()
+ : mpNode(NULL)
+ {
+ // Empty
+ }
+
+
+ template <typename T, typename Pointer, typename Reference>
+ inline list_map_iterator<T, Pointer, Reference>::list_map_iterator(const base_node_type* pNode)
+ : mpNode(static_cast<node_type*>(const_cast<base_node_type*>(pNode)))
+ {
+ // Empty
+ }
+
+
+ template <typename T, typename Pointer, typename Reference>
+ inline list_map_iterator<T, Pointer, Reference>::list_map_iterator(const iterator& x)
+ : mpNode(const_cast<node_type*>(x.mpNode))
+ {
+ // Empty
+ }
+
+
+ template <typename T, typename Pointer, typename Reference>
+ inline typename list_map_iterator<T, Pointer, Reference>::reference
+ list_map_iterator<T, Pointer, Reference>::operator*() const
+ {
+ return mpNode->mValue;
+ }
+
+
+ template <typename T, typename Pointer, typename Reference>
+ inline typename list_map_iterator<T, Pointer, Reference>::pointer
+ list_map_iterator<T, Pointer, Reference>::operator->() const
+ {
+ return &mpNode->mValue;
+ }
+
+
+ template <typename T, typename Pointer, typename Reference>
+ inline typename list_map_iterator<T, Pointer, Reference>::this_type&
+ list_map_iterator<T, Pointer, Reference>::operator++()
+ {
+ mpNode = static_cast<node_type*>(mpNode->mpNext);
+ return *this;
+ }
+
+
+ template <typename T, typename Pointer, typename Reference>
+ inline typename list_map_iterator<T, Pointer, Reference>::this_type
+ list_map_iterator<T, Pointer, Reference>::operator++(int)
+ {
+ this_type temp(*this);
+ mpNode = static_cast<node_type*>(mpNode->mpNext);
+ return temp;
+ }
+
+
+ template <typename T, typename Pointer, typename Reference>
+ inline typename list_map_iterator<T, Pointer, Reference>::this_type&
+ list_map_iterator<T, Pointer, Reference>::operator--()
+ {
+ mpNode = static_cast<node_type*>(mpNode->mpPrev);
+ return *this;
+ }
+
+
+ template <typename T, typename Pointer, typename Reference>
+ inline typename list_map_iterator<T, Pointer, Reference>::this_type
+ list_map_iterator<T, Pointer, Reference>::operator--(int)
+ {
+ this_type temp(*this);
+ mpNode = static_cast<node_type*>(mpNode->mpPrev);
+ return temp;
+ }
+
+
+ // We provide additional template paremeters here to support comparisons between const and non-const iterators.
+ // See C++ defect report #179, or EASTL/list.h for more information.
+ template <typename T, typename PointerA, typename ReferenceA, typename PointerB, typename ReferenceB>
+ inline bool operator==(const list_map_iterator<T, PointerA, ReferenceA>& a,
+ const list_map_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 list_map_iterator<T, PointerA, ReferenceA>& a,
+ const list_map_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 list_map_iterator<T, Pointer, Reference>& a,
+ const list_map_iterator<T, Pointer, Reference>& b)
+ {
+ return a.mpNode != b.mpNode;
+ }
+
+
+ ///////////////////////////////////////////////////////////////////////
+ // list_map
+ ///////////////////////////////////////////////////////////////////////
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline list_map<Key, T, Compare, Allocator>::list_map(const allocator_type& allocator)
+ : base_type(allocator)
+ {
+ mNode.mpNext = &mNode;
+ mNode.mpPrev = &mNode;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline list_map<Key, T, Compare, Allocator>::list_map(const Compare& compare, const allocator_type& allocator)
+ : base_type(compare, allocator)
+ {
+ mNode.mpNext = &mNode;
+ mNode.mpPrev = &mNode;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::iterator
+ list_map<Key, T, Compare, Allocator>::begin() EA_NOEXCEPT
+ {
+ return iterator(mNode.mpNext);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_iterator
+ list_map<Key, T, Compare, Allocator>::begin() const EA_NOEXCEPT
+ {
+ return const_iterator(mNode.mpNext);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_iterator
+ list_map<Key, T, Compare, Allocator>::cbegin() const EA_NOEXCEPT
+ {
+ return const_iterator(mNode.mpNext);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::iterator
+ list_map<Key, T, Compare, Allocator>::end() EA_NOEXCEPT
+ {
+ return iterator(&mNode);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_iterator
+ list_map<Key, T, Compare, Allocator>::end() const EA_NOEXCEPT
+ {
+ return const_iterator(&mNode);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_iterator
+ list_map<Key, T, Compare, Allocator>::cend() const EA_NOEXCEPT
+ {
+ return const_iterator(&mNode);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::reverse_iterator
+ list_map<Key, T, Compare, Allocator>::rbegin() EA_NOEXCEPT
+ {
+ return reverse_iterator(&mNode);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_reverse_iterator
+ list_map<Key, T, Compare, Allocator>::rbegin() const EA_NOEXCEPT
+ {
+ return const_reverse_iterator(&mNode);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_reverse_iterator
+ list_map<Key, T, Compare, Allocator>::crbegin() const EA_NOEXCEPT
+ {
+ return const_reverse_iterator(&mNode);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::reverse_iterator
+ list_map<Key, T, Compare, Allocator>::rend() EA_NOEXCEPT
+ {
+ return reverse_iterator(mNode.mpNext);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_reverse_iterator
+ list_map<Key, T, Compare, Allocator>::rend() const EA_NOEXCEPT
+ {
+ return const_reverse_iterator(mNode.mpNext);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_reverse_iterator
+ list_map<Key, T, Compare, Allocator>::crend() const EA_NOEXCEPT
+ {
+ return const_reverse_iterator(mNode.mpNext);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::reference
+ list_map<Key, T, Compare, Allocator>::front()
+ {
+ #if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
+ if (EASTL_UNLIKELY(static_cast<internal_value_type*>(mNode.mpNext) == &mNode))
+ EASTL_FAIL_MSG("list_map::front -- empty container");
+ #else
+ // We allow the user to reference an empty container.
+ #endif
+
+ return static_cast<internal_value_type*>(mNode.mpNext)->mValue;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_reference
+ list_map<Key, T, Compare, Allocator>::front() const
+ {
+ #if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
+ if (EASTL_UNLIKELY(static_cast<internal_value_type*>(mNode.mpNext) == &mNode))
+ EASTL_FAIL_MSG("list_map::front -- empty container");
+ #else
+ // We allow the user to reference an empty container.
+ #endif
+
+ return static_cast<internal_value_type*>(mNode.mpNext)->mValue;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::reference
+ list_map<Key, T, Compare, Allocator>::back()
+ {
+ #if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
+ if (EASTL_UNLIKELY(static_cast<internal_value_type*>(mNode.mpNext) == &mNode))
+ EASTL_FAIL_MSG("list_map::back -- empty container");
+ #else
+ // We allow the user to reference an empty container.
+ #endif
+
+ return static_cast<internal_value_type*>(mNode.mpPrev)->mValue;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_reference
+ list_map<Key, T, Compare, Allocator>::back() const
+ {
+ #if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
+ if (EASTL_UNLIKELY(static_cast<internal_value_type*>(mNode.mpNext) == &mNode))
+ EASTL_FAIL_MSG("list_map::back -- empty container");
+ #else
+ // We allow the user to reference an empty container.
+ #endif
+
+ return static_cast<internal_value_type*>(mNode.mpPrev)->mValue;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ bool list_map<Key, T, Compare, Allocator>::push_front(const value_type& value)
+ {
+ internal_value_type tempValue(value);
+ typename base_type::insert_return_type baseReturn = base_type::insert(tempValue);
+
+ // Did the insert succeed?
+ if (baseReturn.second)
+ {
+ internal_value_type* pNode = &(*baseReturn.first);
+
+ pNode->mpNext = mNode.mpNext;
+ pNode->mpPrev = &mNode;
+
+ mNode.mpNext->mpPrev = pNode;
+ mNode.mpNext = pNode;
+
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ bool list_map<Key, T, Compare, Allocator>::push_back(const value_type& value)
+ {
+ internal_value_type tempValue(value);
+ typename base_type::insert_return_type baseReturn = base_type::insert(tempValue);
+
+ // Did the insert succeed?
+ if (baseReturn.second)
+ {
+ internal_value_type* pNode = &(*baseReturn.first);
+
+ pNode->mpPrev = mNode.mpPrev;
+ pNode->mpNext = &mNode;
+
+ mNode.mpPrev->mpNext = pNode;
+ mNode.mpPrev = pNode;
+
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ bool list_map<Key, T, Compare, Allocator>::push_front(const key_type& key, const mapped_type& value)
+ {
+ return push_front(eastl::make_pair(key, value));
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ bool list_map<Key, T, Compare, Allocator>::push_back(const key_type& key, const mapped_type& value)
+ {
+ return push_back(eastl::make_pair(key, value));
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ void list_map<Key, T, Compare, Allocator>::pop_front()
+ {
+ #if EASTL_ASSERT_ENABLED
+ if (EASTL_UNLIKELY(empty()))
+ EASTL_FAIL_MSG("list_map::pop_front -- empty container");
+ #endif
+
+ erase(static_cast<internal_value_type*>(mNode.mpNext)->mValue.first);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ void list_map<Key, T, Compare, Allocator>::pop_back()
+ {
+ #if EASTL_ASSERT_ENABLED
+ if (EASTL_UNLIKELY(empty()))
+ EASTL_FAIL_MSG("list_map::pop_back -- empty container");
+ #endif
+
+ erase(static_cast<internal_value_type*>(mNode.mpPrev)->mValue.first);
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::iterator
+ list_map<Key, T, Compare, Allocator>::find(const key_type& key)
+ {
+ typename base_type::iterator baseIter = base_type::find(key);
+ if (baseIter != base_type::end())
+ {
+ return iterator(&(*baseIter));
+ }
+ else
+ {
+ return end();
+ }
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::const_iterator
+ list_map<Key, T, Compare, Allocator>::find(const key_type& key) const
+ {
+ typename base_type::const_iterator baseIter = base_type::find(key);
+ if (baseIter != base_type::end())
+ {
+ return const_iterator(&(*baseIter));
+ }
+ else
+ {
+ return end();
+ }
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ template <typename U, typename Compare2>
+ inline typename list_map<Key, T, Compare, Allocator>::iterator
+ list_map<Key, T, Compare, Allocator>::find_as(const U& u, Compare2 compare2)
+ {
+ typename base_type::iterator baseIter = base_type::find_as(u, compare2);
+ if (baseIter != base_type::end())
+ {
+ return iterator(&(*baseIter));
+ }
+ else
+ {
+ return end();
+ }
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ template <typename U, typename Compare2>
+ inline typename list_map<Key, T, Compare, Allocator>::const_iterator
+ list_map<Key, T, Compare, Allocator>::find_as(const U& u, Compare2 compare2) const
+ {
+ typename base_type::const_iterator baseIter = base_type::find_as(u, compare2);
+ if (baseIter != base_type::end())
+ {
+ return const_iterator(&(*baseIter));
+ }
+ else
+ {
+ return end();
+ }
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::size_type
+ list_map<Key, T, Compare, Allocator>::count(const key_type& key) const
+ {
+ const typename base_type::const_iterator it = base_type::find(key);
+ return (it != base_type::end()) ? 1 : 0;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::size_type
+ list_map<Key, T, Compare, Allocator>::erase(const key_type& key)
+ {
+ typename base_type::iterator baseIter = base_type::find(key);
+ if (baseIter != base_type::end())
+ {
+ internal_value_type* node = &(*baseIter);
+
+ node->mpNext->mpPrev = node->mpPrev;
+ node->mpPrev->mpNext = node->mpNext;
+
+ base_type::erase(baseIter);
+
+ return 1;
+ }
+ return 0;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::iterator
+ list_map<Key, T, Compare, Allocator>::erase(const_iterator position)
+ {
+ iterator posIter(position.mpNode); // Convert from const.
+ iterator eraseIter(posIter++);
+ erase(eraseIter->first);
+ return posIter;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ inline typename list_map<Key, T, Compare, Allocator>::reverse_iterator
+ list_map<Key, T, Compare, Allocator>::erase(const_reverse_iterator position)
+ {
+ return reverse_iterator(erase((++position).base()));
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ void list_map<Key, T, Compare, Allocator>::clear()
+ {
+ base_type::clear();
+
+ mNode.mpNext = &mNode;
+ mNode.mpPrev = &mNode;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ void list_map<Key, T, Compare, Allocator>::reset_lose_memory()
+ {
+ base_type::reset_lose_memory();
+
+ mNode.mpNext = &mNode;
+ mNode.mpPrev = &mNode;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ bool list_map<Key, T, Compare, Allocator>::validate() const
+ {
+ if (!base_type::validate())
+ {
+ return false;
+ }
+
+ size_type nodeCount(0);
+ list_map_data_base* node = mNode.mpNext;
+ while (node != &mNode)
+ {
+ internal_value_type* data = static_cast<internal_value_type*>(node);
+ if (base_type::find(data->mValue.first) == base_type::end())
+ {
+ return false;
+ }
+ node = node->mpNext;
+ ++nodeCount;
+ }
+ if (nodeCount != size())
+ {
+ return false;
+ }
+ nodeCount = 0;
+ node = mNode.mpPrev;
+ while (node != &mNode)
+ {
+ internal_value_type* data = static_cast<internal_value_type*>(node);
+ if (base_type::find(data->mValue.first) == base_type::end())
+ {
+ return false;
+ }
+ node = node->mpPrev;
+ ++nodeCount;
+ }
+ if (nodeCount != size())
+ {
+ return false;
+ }
+
+ return true;
+ }
+
+ template <typename Key, typename T, typename Compare, typename Allocator>
+ int list_map<Key, T, Compare, Allocator>::validate_iterator(const_iterator iter) const
+ {
+ for (const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp)
+ {
+ if (temp == iter)
+ {
+ return (isf_valid | isf_current | isf_can_dereference);
+ }
+ }
+
+ if (iter == end())
+ return (isf_valid | isf_current);
+
+ return isf_none;
+ }
+
+
+} // namespace eastl
+
+
+#endif // Header include guard
+
+
+
+
Powered by cgit, Themed by Ted Yin.