aboutsummaryrefslogtreecommitdiff
path: root/include/EASTL/bonus/intrusive_sdlist.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/EASTL/bonus/intrusive_sdlist.h')
-rw-r--r--include/EASTL/bonus/intrusive_sdlist.h694
1 files changed, 0 insertions, 694 deletions
diff --git a/include/EASTL/bonus/intrusive_sdlist.h b/include/EASTL/bonus/intrusive_sdlist.h
deleted file mode 100644
index 1b126d4..0000000
--- a/include/EASTL/bonus/intrusive_sdlist.h
+++ /dev/null
@@ -1,694 +0,0 @@
-/////////////////////////////////////////////////////////////////////////////
-// Copyright (c) Electronic Arts Inc. All rights reserved.
-/////////////////////////////////////////////////////////////////////////////
-
-///////////////////////////////////////////////////////////////////////////////
-// intrusive_sdlist is a special kind of intrusive list which we say is
-// "singly-doubly" linked. Instead of having a typical intrusive list node
-// which looks like this:
-//
-// struct intrusive_sdlist_node {
-// intrusive_sdlist_node *mpNext;
-// intrusive_sdlist_node *mpPrev;
-// };
-//
-// We instead have one that looks like this:
-//
-// struct intrusive_sdlist_node {
-// intrusive_sdlist_node* mpNext;
-// intrusive_sdlist_node** mppPrevNext;
-// };
-//
-// This may seem to be suboptimal, but it has one specific advantage: it allows
-// the intrusive_sdlist class to be the size of only one pointer instead of two.
-// This may seem like a minor optimization, but some users have wanted to create
-// thousands of empty instances of these.
-// This is because while an intrusive_list class looks like this:
-//
-// class intrusive_list {
-// intrusive_list_node mBaseNode;
-// };
-//
-// an intrusive_sdlist class looks like this:
-//
-// class intrusive_sdlist {
-// intrusive_sdlist_node* mpNext;
-// };
-//
-// So here we make a list of plusses and minuses of intrusive sdlists
-// compared to intrusive_lists and intrusive_slists:
-//
-// | list | slist | sdlist
-// ---------------------------------------------------------
-// min size | 8 | 4 | 4
-// node size | 8 | 4 | 8
-// anonymous erase | yes | no | yes
-// reverse iteration | yes | no | no
-//
-///////////////////////////////////////////////////////////////////////////////
-
-
-#ifndef EASTL_INTRUSIVE_SDLIST_H
-#define EASTL_INTRUSIVE_SDLIST_H
-
-
-#include <EASTL/internal/config.h>
-#include <EASTL/iterator.h>
-#include <EASTL/algorithm.h>
-
-#if defined(EA_PRAGMA_ONCE_SUPPORTED)
- #pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result.
-#endif
-
-
-
-namespace eastl
-{
-
-
- /// intrusive_sdlist_node
- ///
- struct intrusive_sdlist_node
- {
- intrusive_sdlist_node* mpNext;
- intrusive_sdlist_node** mppPrevNext;
- };
-
-
- /// IntrusiveSDListIterator
- ///
- template <typename T, typename Pointer, typename Reference>
- struct IntrusiveSDListIterator
- {
- typedef IntrusiveSDListIterator<T, Pointer, Reference> this_type;
- typedef IntrusiveSDListIterator<T, T*, T&> iterator;
- typedef IntrusiveSDListIterator<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 T node_type;
- typedef Pointer pointer;
- typedef Reference reference;
- typedef EASTL_ITC_NS::forward_iterator_tag iterator_category;
-
- public:
- pointer mpNode;
-
- public:
- IntrusiveSDListIterator();
- explicit IntrusiveSDListIterator(pointer pNode); // Note that you can also construct an iterator from T via this, since value_type == node_type.
- IntrusiveSDListIterator(const iterator& x);
-
- reference operator*() const;
- pointer operator->() const;
-
- this_type& operator++();
- this_type operator++(int);
-
- }; // struct IntrusiveSDListIterator
-
-
-
-
- /// intrusive_sdlist_base
- ///
- /// Provides a template-less base class for intrusive_sdlist.
- ///
- class intrusive_sdlist_base
- {
- public:
- 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;
-
- protected:
- intrusive_sdlist_node* mpNext;
-
- public:
- intrusive_sdlist_base();
-
- bool empty() const; ///< Returns true if the container is empty.
- size_type size() const; ///< Returns the number of elements in the list; O(n).
-
- void clear(); ///< Clears the list; O(1). No deallocation occurs.
- void pop_front(); ///< Removes an element from the front of the list; O(1). The element must be present, but is not deallocated.
- void reverse(); ///< Reverses a list so that front and back are swapped; O(n).
-
- //bool validate() const; ///< Scans a list for linkage inconsistencies; O(n) time, O(1) space. Returns false if errors are detected, such as loops or branching.
-
- }; // class intrusive_sdlist_base
-
-
-
- /// intrusive_sdlist
- ///
- template <typename T = intrusive_sdlist_node>
- class intrusive_sdlist : public intrusive_sdlist_base
- {
- public:
- typedef intrusive_sdlist<T> this_type;
- typedef intrusive_sdlist_base base_type;
- typedef T node_type;
- typedef T value_type;
- typedef typename base_type::size_type size_type;
- typedef typename base_type::difference_type difference_type;
- typedef T& reference;
- typedef const T& const_reference;
- typedef T* pointer;
- typedef const T* const_pointer;
- typedef IntrusiveSDListIterator<T, T*, T&> iterator;
- typedef IntrusiveSDListIterator<T, const T*, const T&> const_iterator;
- typedef eastl::reverse_iterator<iterator> reverse_iterator;
- typedef eastl::reverse_iterator<const_iterator> const_reverse_iterator;
-
- public:
- intrusive_sdlist(); ///< Creates an empty list.
- intrusive_sdlist(const this_type& x); ///< Creates an empty list; ignores the argument.
- this_type& operator=(const this_type& x); ///< Clears the list; ignores the argument.
-
- iterator begin(); ///< Returns an iterator pointing to the first element in the list.
- const_iterator begin() const; ///< Returns a const_iterator pointing to the first element in the list.
- const_iterator cbegin() const; ///< Returns a const_iterator pointing to the first element in the list.
-
- iterator end(); ///< Returns an iterator pointing one-after the last element in the list.
- const_iterator end() const; ///< Returns a const_iterator pointing one-after the last element in the list.
- const_iterator cend() const; ///< Returns a const_iterator pointing one-after the last element in the list.
-
- reference front(); ///< Returns a reference to the first element. The list must be empty.
- const_reference front() const; ///< Returns a const reference to the first element. The list must be empty.
-
- void push_front(value_type& value); ///< Adds an element to the front of the list; O(1). The element is not copied. The element must not be in any other list.
- void push_back(value_type& value); ///< Adds an element to the back of the list; O(N). The element is not copied. The element must not be in any other list.
- void pop_back(); ///< Removes an element from the back of the list; O(N). The element must be present, but is not deallocated.
-
- bool contains(const value_type& value) const; ///< Returns true if the given element is in the list; O(n). Equivalent to (locate(x) != end()).
-
- iterator locate(value_type& value); ///< Converts a reference to an object in the list back to an iterator, or returns end() if it is not part of the list. O(n)
- const_iterator locate(const value_type& value) const; ///< Converts a const reference to an object in the list back to a const iterator, or returns end() if it is not part of the list. O(n)
-
- iterator insert(iterator position, value_type& value); ///< Inserts an element before the element pointed to by the iterator. O(1)
- iterator erase(iterator position); ///< Erases the element pointed to by the iterator. O(1)
- iterator erase(iterator first, iterator last); ///< Erases elements within the iterator range [first, last). O(1).
- void swap(intrusive_sdlist& x); ///< Swaps the contents of two intrusive lists; O(1).
-
- static void remove(value_type& value); ///< Erases an element from a list; O(1). Note that this is static so you don't need to know which list the element, although it must be in some list.
-
- void splice(iterator position, value_type& value); ///< Moves the given element into this list before the element pointed to by position; O(1).
- ///< Required: x must be in some list or have first/next pointers that point it itself.
-
- void splice(iterator position, this_type& x); ///< Moves the contents of a list into this list before the element pointed to by position; O(1).
- ///< Required: &x != this (same as std::list).
-
- void splice(iterator position, this_type& x, iterator xPosition); ///< Moves the given element pointed to i within the list x into the current list before
- ///< the element pointed to by position; O(1).
-
- void splice(iterator position, this_type& x, iterator first, iterator last); ///< Moves the range of elements [first, last) from list x into the current list before
- ///< the element pointed to by position; O(1).
- ///< Required: position must not be in [first, last). (same as std::list).
- bool validate() const;
- int validate_iterator(const_iterator i) const;
-
- }; // intrusive_sdlist
-
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // IntrusiveSDListIterator functions
- ///////////////////////////////////////////////////////////////////////
-
- template <typename T, typename Pointer, typename Reference>
- inline IntrusiveSDListIterator<T, Pointer, Reference>::IntrusiveSDListIterator()
- {
- #if EASTL_DEBUG
- mpNode = NULL;
- #endif
- }
-
- template <typename T, typename Pointer, typename Reference>
- inline IntrusiveSDListIterator<T, Pointer, Reference>::IntrusiveSDListIterator(pointer pNode)
- : mpNode(pNode)
- {
- }
-
- template <typename T, typename Pointer, typename Reference>
- inline IntrusiveSDListIterator<T, Pointer, Reference>::IntrusiveSDListIterator(const iterator& x)
- : mpNode(x.mpNode)
- {
- }
-
- template <typename T, typename Pointer, typename Reference>
- inline typename IntrusiveSDListIterator<T, Pointer, Reference>::reference
- IntrusiveSDListIterator<T, Pointer, Reference>::operator*() const
- {
- return *mpNode;
- }
-
- template <typename T, typename Pointer, typename Reference>
- inline typename IntrusiveSDListIterator<T, Pointer, Reference>::pointer
- IntrusiveSDListIterator<T, Pointer, Reference>::operator->() const
- {
- return mpNode;
- }
-
- template <typename T, typename Pointer, typename Reference>
- inline typename IntrusiveSDListIterator<T, Pointer, Reference>::this_type&
- IntrusiveSDListIterator<T, Pointer, Reference>::operator++()
- {
- mpNode = static_cast<node_type*>(mpNode->mpNext);
- return *this;
- }
-
- template <typename T, typename Pointer, typename Reference>
- inline typename IntrusiveSDListIterator<T, Pointer, Reference>::this_type
- IntrusiveSDListIterator<T, Pointer, Reference>::operator++(int)
- {
- this_type temp = *this;
- mpNode = static_cast<node_type*>(mpNode->mpNext);
- 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 IntrusiveSDListIterator<T, PointerA, ReferenceA>& a,
- const IntrusiveSDListIterator<T, PointerB, ReferenceB>& b)
- {
- return a.mpNode == b.mpNode;
- }
-
-
- template <typename T, typename PointerA, typename ReferenceA, typename PointerB, typename ReferenceB>
- inline bool operator!=(const IntrusiveSDListIterator<T, PointerA, ReferenceA>& a,
- const IntrusiveSDListIterator<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 IntrusiveSDListIterator<T, Pointer, Reference>& a,
- const IntrusiveSDListIterator<T, Pointer, Reference>& b)
- {
- return a.mpNode != b.mpNode;
- }
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // intrusive_sdlist_base
- ///////////////////////////////////////////////////////////////////////
-
- inline intrusive_sdlist_base::intrusive_sdlist_base()
- { mpNext = NULL; }
-
-
- inline bool intrusive_sdlist_base::empty() const
- { return mpNext == NULL; }
-
-
- inline intrusive_sdlist_base::size_type intrusive_sdlist_base::size() const
- {
- size_type n = 0;
- for(const intrusive_sdlist_node* pCurrent = mpNext; pCurrent; pCurrent = pCurrent->mpNext)
- n++;
- return n;
- }
-
-
- inline void intrusive_sdlist_base::clear()
- { mpNext = NULL; } // Note that we don't do anything with the list nodes.
-
-
- inline void intrusive_sdlist_base::pop_front()
- {
- // To consider: Set mpNext's pointers to NULL in debug builds.
- mpNext = mpNext->mpNext;
- mpNext->mppPrevNext = &mpNext;
- }
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // intrusive_sdlist
- ///////////////////////////////////////////////////////////////////////
-
- template <typename T>
- inline intrusive_sdlist<T>::intrusive_sdlist()
- {
- }
-
-
- template <typename T>
- inline intrusive_sdlist<T>::intrusive_sdlist(const this_type& /*x*/)
- : intrusive_sdlist_base()
- {
- // We intentionally ignore argument x.
- }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::this_type& intrusive_sdlist<T>::operator=(const this_type& /*x*/)
- {
- return *this; // We intentionally ignore argument x.
- }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::iterator intrusive_sdlist<T>::begin()
- { return iterator(static_cast<T*>(mpNext)); }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::const_iterator intrusive_sdlist<T>::begin() const
- { return const_iterator(static_cast<T*>(const_cast<intrusive_sdlist_node*>(mpNext))); }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::const_iterator intrusive_sdlist<T>::cbegin() const
- { return const_iterator(static_cast<T*>(const_cast<intrusive_sdlist_node*>(mpNext))); }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::iterator intrusive_sdlist<T>::end()
- { return iterator(static_cast<T*>(NULL)); }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::const_iterator intrusive_sdlist<T>::end() const
- { return const_iterator(static_cast<const T*>(NULL)); }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::const_iterator intrusive_sdlist<T>::cend() const
- { return const_iterator(static_cast<const T*>(NULL)); }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::reference intrusive_sdlist<T>::front()
- { return *static_cast<T*>(mpNext); }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::const_reference intrusive_sdlist<T>::front() const
- { return *static_cast<const T*>(mpNext); }
-
-
- template <typename T>
- inline void intrusive_sdlist<T>::push_front(value_type& value)
- {
- value.mpNext = mpNext;
- value.mppPrevNext = &mpNext;
- if(mpNext)
- mpNext->mppPrevNext = &value.mpNext;
- mpNext = &value;
- }
-
-
- template <typename T>
- inline void intrusive_sdlist<T>::push_back(value_type& value)
- {
- intrusive_sdlist_node* pNext = mpNext;
- intrusive_sdlist_node** ppPrevNext = &mpNext;
-
- while(pNext)
- {
- ppPrevNext = &pNext->mpNext;
- pNext = pNext->mpNext;
- }
-
- *ppPrevNext = &value;
- value.mppPrevNext = ppPrevNext;
- value.mpNext = NULL;
- }
-
-
- template <typename T>
- inline void intrusive_sdlist<T>::pop_back()
- {
- node_type* pCurrent = static_cast<node_type*>(mpNext);
-
- while(pCurrent->mpNext)
- pCurrent = static_cast<node_type*>(pCurrent->mpNext);
-
- *pCurrent->mppPrevNext = NULL;
- }
-
- template <typename T>
- inline bool intrusive_sdlist<T>::contains(const value_type& value) const
- {
- const intrusive_sdlist_node* pCurrent;
-
- for(pCurrent = mpNext; pCurrent; pCurrent = pCurrent->mpNext)
- {
- if(pCurrent == &value)
- break;
- }
-
- return (pCurrent != NULL);
- }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::iterator intrusive_sdlist<T>::locate(value_type& value)
- {
- intrusive_sdlist_node* pCurrent;
-
- for(pCurrent = static_cast<value_type*>(mpNext); pCurrent; pCurrent = pCurrent->mpNext)
- {
- if(pCurrent == &value)
- break;
- }
-
- return iterator(static_cast<value_type*>(pCurrent));
- }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::const_iterator intrusive_sdlist<T>::locate(const T& value) const
- {
- const intrusive_sdlist_node* pCurrent;
-
- for(pCurrent = static_cast<value_type*>(mpNext); pCurrent; pCurrent = pCurrent->mpNext)
- {
- if(pCurrent == &value)
- break;
- }
-
- return const_iterator(static_cast<value_type*>(const_cast<intrusive_sdlist_node*>(pCurrent)));
- }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::iterator
- intrusive_sdlist<T>::insert(iterator position, value_type& value)
- {
- value.mppPrevNext = position.mpNode->mppPrevNext;
- value.mpNext = position.mpNode;
- *value.mppPrevNext = &value;
- position.mpNode->mppPrevNext = &value.mpNext;
-
- return iterator(&value);
- }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::iterator
- intrusive_sdlist<T>::erase(iterator position)
- {
- *position.mpNode->mppPrevNext = position.mpNode->mpNext;
- position.mpNode->mpNext->mppPrevNext = position.mpNode->mppPrevNext;
-
- return iterator(position.mpNode);
- }
-
-
- template <typename T>
- inline typename intrusive_sdlist<T>::iterator
- intrusive_sdlist<T>::erase(iterator first, iterator last)
- {
- if(first.mpNode) // If not erasing the end...
- {
- *first.mpNode->mppPrevNext = last.mpNode;
-
- if(last.mpNode) // If not erasing to the end...
- last.mpNode->mppPrevNext = first.mpNode->mppPrevNext;
- }
-
- return last;
- }
-
-
- template <typename T>
- inline void intrusive_sdlist<T>::remove(value_type& value)
- {
- *value.mppPrevNext = value.mpNext;
- if(value.mpNext)
- value.mpNext->mppPrevNext = value.mppPrevNext;
- }
-
-
- template <typename T>
- void intrusive_sdlist<T>::swap(intrusive_sdlist& x)
- {
- // swap anchors
- intrusive_sdlist_node* const temp(mpNext);
- mpNext = x.mpNext;
- x.mpNext = temp;
-
- if(x.mpNext)
- x.mpNext->mppPrevNext = &mpNext;
-
- if(mpNext)
- mpNext->mppPrevNext = &x.mpNext;
- }
-
-
-
-
-
- // To do: Complete these splice functions. Might want to look at intrusive_sdlist for help.
-
- template <typename T>
- void intrusive_sdlist<T>::splice(iterator /*position*/, value_type& /*value*/)
- {
- EASTL_ASSERT(false); // If you need this working, ask Paul Pedriana or submit a working version for inclusion.
- }
-
-
- template <typename T>
- void intrusive_sdlist<T>::splice(iterator /*position*/, intrusive_sdlist& /*x*/)
- {
- EASTL_ASSERT(false); // If you need this working, ask Paul Pedriana or submit a working version for inclusion.
- }
-
-
- template <typename T>
- void intrusive_sdlist<T>::splice(iterator /*position*/, intrusive_sdlist& /*x*/, iterator /*xPosition*/)
- {
- EASTL_ASSERT(false); // If you need this working, ask Paul Pedriana or submit a working version for inclusion.
- }
-
-
- template <typename T>
- void intrusive_sdlist<T>::splice(iterator /*position*/, intrusive_sdlist& /*x*/, iterator /*first*/, iterator /*last*/)
- {
- EASTL_ASSERT(false); // If you need this working, ask Paul Pedriana or submit a working version for inclusion.
- }
-
-
- template <typename T>
- inline bool intrusive_sdlist<T>::validate() const
- {
- return true; // To do.
- }
-
-
- template <typename T>
- inline int intrusive_sdlist<T>::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;
- }
-
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // global operators
- ///////////////////////////////////////////////////////////////////////
-
- template <typename T>
- bool operator==(const intrusive_sdlist<T>& a, const intrusive_sdlist<T>& b)
- {
- // If we store an mSize member for intrusive_sdlist, we want to take advantage of it here.
- typename intrusive_sdlist<T>::const_iterator ia = a.begin();
- typename intrusive_sdlist<T>::const_iterator ib = b.begin();
- typename intrusive_sdlist<T>::const_iterator enda = a.end();
- typename intrusive_sdlist<T>::const_iterator endb = b.end();
-
- while((ia != enda) && (ib != endb) && (*ia == *ib))
- {
- ++ia;
- ++ib;
- }
- return (ia == enda) && (ib == endb);
- }
-
- template <typename T>
- bool operator<(const intrusive_sdlist<T>& a, const intrusive_sdlist<T>& b)
- {
- return eastl::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
- }
-
- template <typename T>
- bool operator!=(const intrusive_sdlist<T>& a, const intrusive_sdlist<T>& b)
- {
- return !(a == b);
- }
-
- template <typename T>
- bool operator>(const intrusive_sdlist<T>& a, const intrusive_sdlist<T>& b)
- {
- return b < a;
- }
-
- template <typename T>
- bool operator<=(const intrusive_sdlist<T>& a, const intrusive_sdlist<T>& b)
- {
- return !(b < a);
- }
-
- template <typename T>
- bool operator>=(const intrusive_sdlist<T>& a, const intrusive_sdlist<T>& b)
- {
- return !(a < b);
- }
-
- template <typename T>
- void swap(intrusive_sdlist<T>& a, intrusive_sdlist<T>& b)
- {
- a.swap(b);
- }
-
-
-} // namespace eastl
-
-
-#endif // Header include guard
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
Powered by cgit, Themed by Ted Yin.