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, 0 insertions, 932 deletions
diff --git a/include/EASTL/bonus/list_map.h b/include/EASTL/bonus/list_map.h
deleted file mode 100644
index 8a080d6..0000000
--- a/include/EASTL/bonus/list_map.h
+++ /dev/null
@@ -1,932 +0,0 @@
-/////////////////////////////////////////////////////////////////////////////
-// 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.