diff options
Diffstat (limited to 'EASTL/include/EASTL/slist.h')
| -rw-r--r-- | EASTL/include/EASTL/slist.h | 1930 |
1 files changed, 1930 insertions, 0 deletions
diff --git a/EASTL/include/EASTL/slist.h b/EASTL/include/EASTL/slist.h new file mode 100644 index 0000000..2796692 --- /dev/null +++ b/EASTL/include/EASTL/slist.h @@ -0,0 +1,1930 @@ +/////////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +/////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////// +// An slist is a singly-linked list. The C++ standard library doesn't define +// such a thing as an slist, nor does the C++ TR1. Our implementation of slist +// largely follows the design of the SGI STL slist container, which is also +// found in STLPort. Singly-linked lists use less memory than doubly-linked +// lists, but are less flexible. +// +// In looking at slist, you will notice a lot of references to things like +// 'before first', 'before last', 'insert after', and 'erase after'. This is +// due to the fact that std::list insert and erase works on the node before +// the referenced node, whereas slist is singly linked and operations are only +// efficient if they work on the node after the referenced node. This is because +// with an slist node you know the node after it but not the node before it. +// +/////////////////////////////////////////////////////////////////////////////// + + + +#ifndef EASTL_SLIST_H +#define EASTL_SLIST_H + + +#include <EASTL/internal/config.h> +#include <EASTL/allocator.h> +#include <EASTL/type_traits.h> +#include <EASTL/iterator.h> +#include <EASTL/algorithm.h> +#include <EASTL/initializer_list.h> +#include <EASTL/sort.h> +#include <EASTL/bonus/compressed_pair.h> +#include <stddef.h> + +EA_DISABLE_ALL_VC_WARNINGS(); + + #include <new> + +EA_RESTORE_ALL_VC_WARNINGS(); + +EA_DISABLE_SN_WARNING(828); // The EDG SN compiler has a bug in its handling of variadic template arguments and mistakenly reports "parameter "args" was never referenced" + + +// 4530 - C++ exception handler used, but unwind semantics are not enabled. Specify /EHsc +// 4345 - Behavior change: an object of POD type constructed with an initializer of the form () will be default-initialized +// 4571 - catch(...) semantics changed since Visual C++ 7.1; structured exceptions (SEH) are no longer caught. +EA_DISABLE_VC_WARNING(4530 4345 4571); + + +#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 +{ + + /// EASTL_SLIST_DEFAULT_NAME + /// + /// Defines a default container name in the absence of a user-provided name. + /// + #ifndef EASTL_SLIST_DEFAULT_NAME + #define EASTL_SLIST_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " slist" // Unless the user overrides something, this is "EASTL slist". + #endif + + + /// EASTL_SLIST_DEFAULT_ALLOCATOR + /// + #ifndef EASTL_SLIST_DEFAULT_ALLOCATOR + #define EASTL_SLIST_DEFAULT_ALLOCATOR allocator_type(EASTL_SLIST_DEFAULT_NAME) + #endif + + + + /// SListNodeBase + /// + /// This is a standalone struct so that operations on it can be done without templates + /// and so that an empty slist can have an SListNodeBase and thus not create any + /// instances of T. + /// + struct SListNodeBase + { + SListNodeBase* mpNext; + } EASTL_LIST_PROXY_MAY_ALIAS; + + + #if EASTL_LIST_PROXY_ENABLED + + /// SListNodeBaseProxy + /// + /// In debug builds, we define SListNodeBaseProxy to be the same thing as + /// SListNodeBase, except it is templated on the parent SListNode class. + /// We do this because we want users in debug builds to be able to easily + /// view the slist's contents in a debugger GUI. We do this only in a debug + /// build for the reasons described above: that SListNodeBase needs to be + /// as efficient as possible and not cause code bloat or extra function + /// calls (inlined or not). + /// + /// SListNodeBaseProxy *must* be separate from its parent class SListNode + /// because the slist class must have a member node which contains no T value. + /// It is thus incorrect for us to have one single SListNode class which + /// has both mpNext and mValue. So we do a recursive template trick in the + /// definition and use of SListNodeBaseProxy. + /// + template <typename SLN> + struct SListNodeBaseProxy + { + SLN* mpNext; + }; + + template <typename T> + struct SListNode : public SListNodeBaseProxy< SListNode<T> > + { + T mValue; + }; + + #else + template <typename T> + struct SListNode : public SListNodeBase + { + T mValue; + }; + #endif + + + /// SListIterator + /// + template <typename T, typename Pointer, typename Reference> + struct SListIterator + { + typedef SListIterator<T, Pointer, Reference> this_type; + typedef SListIterator<T, T*, T&> iterator; + typedef SListIterator<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 SListNode<T> node_type; + typedef Pointer pointer; + typedef Reference reference; + typedef EASTL_ITC_NS::forward_iterator_tag iterator_category; + + public: + node_type* mpNode; + + public: + SListIterator(); + SListIterator(const SListNodeBase* pNode); + SListIterator(const iterator& x); + + reference operator*() const; + pointer operator->() const; + + this_type& operator++(); + this_type operator++(int); + }; + + + + /// SListBase + /// + /// See VectorBase (class vector) for an explanation of why we + /// create this separate base class. + /// + template <typename T, typename Allocator> + struct SListBase + { + public: + typedef Allocator allocator_type; + typedef SListNode<T> node_type; + 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; + #if EASTL_LIST_PROXY_ENABLED + typedef SListNodeBaseProxy< SListNode<T> > base_node_type; + #else + typedef SListNodeBase base_node_type; // We use SListNodeBase instead of SListNode<T> because we don't want to create a T. + #endif + + protected: + eastl::compressed_pair<base_node_type, allocator_type> mNodeAllocator; + #if EASTL_SLIST_SIZE_CACHE + size_type mSize; + #endif + + base_node_type& internalNode() EA_NOEXCEPT { return mNodeAllocator.first(); } + base_node_type const& internalNode() const EA_NOEXCEPT { return mNodeAllocator.first(); } + allocator_type& internalAllocator() EA_NOEXCEPT { return mNodeAllocator.second(); } + const allocator_type& internalAllocator() const EA_NOEXCEPT { return mNodeAllocator.second(); } + + public: + const allocator_type& get_allocator() const EA_NOEXCEPT; + allocator_type& get_allocator() EA_NOEXCEPT; + void set_allocator(const allocator_type& allocator); + + protected: + SListBase(); + SListBase(const allocator_type& a); + ~SListBase(); + + node_type* DoAllocateNode(); + void DoFreeNode(node_type* pNode); + + SListNodeBase* DoEraseAfter(SListNodeBase* pNode); + SListNodeBase* DoEraseAfter(SListNodeBase* pNode, SListNodeBase* pNodeLast); + + }; // class SListBase + + + + /// slist + /// + /// This is the equivalent of C++11's forward_list. + /// + /// -- size() is O(n) -- + /// Note that as of this writing, list::size() is an O(n) operation when EASTL_SLIST_SIZE_CACHE is disabled. + /// That is, getting the size of the list is not a fast operation, as it requires traversing the list and + /// counting the nodes. We could make list::size() be fast by having a member mSize variable. There are reasons + /// for having such functionality and reasons for not having such functionality. We currently choose + /// to not have a member mSize variable as it would add four bytes to the class, add a tiny amount + /// of processing to functions such as insert and erase, and would only serve to improve the size + /// function, but no others. The alternative argument is that the C++ standard states that std::list + /// should be an O(1) operation (i.e. have a member size variable), most C++ standard library list + /// implementations do so, the size is but an integer which is quick to update, and many users + /// expect to have a fast size function. The EASTL_SLIST_SIZE_CACHE option changes this. + /// To consider: Make size caching an optional template parameter. + /// + /// Pool allocation + /// If you want to make a custom memory pool for a list container, your pool + /// needs to contain items of type slist::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 slist<Widget, MemoryPool> WidgetList; // Delare your WidgetList type. + /// MemoryPool myPool(sizeof(WidgetList::node_type), 100); // Make a pool of 100 Widget nodes. + /// WidgetList myList(&myPool); // Create a list that uses the pool. + /// + template <typename T, typename Allocator = EASTLAllocatorType > + class slist : public SListBase<T, Allocator> + { + typedef SListBase<T, Allocator> base_type; + typedef slist<T, Allocator> this_type; + + public: + typedef T value_type; + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef SListIterator<T, T*, T&> iterator; + typedef SListIterator<T, const T*, const T&> const_iterator; + typedef typename base_type::size_type size_type; + typedef typename base_type::difference_type difference_type; + typedef typename base_type::allocator_type allocator_type; + typedef typename base_type::node_type node_type; + typedef typename base_type::base_node_type base_node_type; + + using base_type::mNodeAllocator; + using base_type::DoEraseAfter; + using base_type::DoAllocateNode; + using base_type::DoFreeNode; + #if EASTL_SLIST_SIZE_CACHE + using base_type::mSize; + #endif + using base_type::internalNode; + using base_type::internalAllocator; + + public: + slist(); + slist(const allocator_type& allocator); + explicit slist(size_type n, const allocator_type& allocator = EASTL_SLIST_DEFAULT_ALLOCATOR); + slist(size_type n, const value_type& value, const allocator_type& allocator = EASTL_SLIST_DEFAULT_ALLOCATOR); + slist(const this_type& x); + slist(std::initializer_list<value_type> ilist, const allocator_type& allocator = EASTL_SLIST_DEFAULT_ALLOCATOR); + slist(this_type&& x); + slist(this_type&& x, const allocator_type& allocator); + + template <typename InputIterator> + slist(InputIterator first, InputIterator last); // allocator arg removed because VC7.1 fails on the default arg. To do: Make a second version of this function without a default arg. + + this_type& operator=(const this_type& x); + this_type& operator=(std::initializer_list<value_type>); + this_type& operator=(this_type&& x); + + void swap(this_type& x); + + void assign(size_type n, const value_type& value); + void assign(std::initializer_list<value_type> ilist); + + template <typename InputIterator> + void assign(InputIterator first, InputIterator last); + + 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; + + iterator before_begin() EA_NOEXCEPT; + const_iterator before_begin() const EA_NOEXCEPT; + const_iterator cbefore_begin() const EA_NOEXCEPT; + + iterator previous(const_iterator position); + const_iterator previous(const_iterator position) const; + + reference front(); + const_reference front() const; + + template <class... Args> + void emplace_front(Args&&... args); + + void push_front(const value_type& value); + reference push_front(); + void push_front(value_type&& value); + + void pop_front(); + + bool empty() const EA_NOEXCEPT; + size_type size() const EA_NOEXCEPT; + + void resize(size_type n, const value_type& value); + void resize(size_type n); + + iterator insert(const_iterator position); + iterator insert(const_iterator position, const value_type& value); + void insert(const_iterator position, size_type n, const value_type& value); + + template <typename InputIterator> + void insert(const_iterator position, InputIterator first, InputIterator last); + + // Returns an iterator pointing to the last inserted element, or position if insertion count is zero. + iterator insert_after(const_iterator position); + iterator insert_after(const_iterator position, const value_type& value); + iterator insert_after(const_iterator position, size_type n, const value_type& value); + iterator insert_after(const_iterator position, std::initializer_list<value_type> ilist); + iterator insert_after(const_iterator position, value_type&& value); + + template <class... Args> + iterator emplace_after(const_iterator position, Args&&... args); + + template <typename InputIterator> + iterator insert_after(const_iterator position, InputIterator first, InputIterator last); + + iterator erase(const_iterator position); + iterator erase(const_iterator first, const_iterator last); + + iterator erase_after(const_iterator position); + iterator erase_after(const_iterator before_first, const_iterator last); + + void clear() EA_NOEXCEPT; + void reset_lose_memory() EA_NOEXCEPT; // This is a unilateral reset to an initially empty state. No destructors are called, no deallocation occurs. + + void remove(const value_type& value); + + template <typename Predicate> + void remove_if(Predicate predicate); + + void reverse() EA_NOEXCEPT; + + // splice splices to before position, like with the list container. However, in order to do so + // it must walk the list from beginning to position, which is an O(n) operation that can thus + // be slow. It's recommended that the splice_after functions be used whenever possible as they are O(1). + void splice(const_iterator position, this_type& x); + void splice(const_iterator position, this_type& x, const_iterator i); + void splice(const_iterator position, this_type& x, const_iterator first, const_iterator last); + void splice(const_iterator position, this_type&& x); + void splice(const_iterator position, this_type&& x, const_iterator i); + void splice(const_iterator position, this_type&& x, const_iterator first, const_iterator last); + + void splice_after(const_iterator position, this_type& x); + void splice_after(const_iterator position, this_type& x, const_iterator i); + void splice_after(const_iterator position, this_type& x, const_iterator first, const_iterator last); + void splice_after(const_iterator position, this_type&& x); + void splice_after(const_iterator position, this_type&& x, const_iterator i); + void splice_after(const_iterator position, this_type&& x, const_iterator first, const_iterator last); + + // The following splice_after funcions are deprecated, as they don't allow for recognizing + // the allocator, cannot maintain the source mSize, and are not in the C++11 Standard definition + // of std::forward_list (which is the equivalent of this class). + void splice_after(const_iterator position, const_iterator before_first, const_iterator before_last); // before_first and before_last come from a source container. + void splice_after(const_iterator position, const_iterator previous); // previous comes from a source container. + + // Sorting functionality + // This is independent of the global sort algorithms, as lists are + // linked nodes and can be sorted more efficiently by moving nodes + // around in ways that global sort algorithms aren't privy to. + void sort(); + + template <class Compare> + void sort(Compare compare); + + // Not yet implemented: + // void merge(this_type& x); + // void merge(this_type&& x); + // template <class Compare> + // void merge(this_type& x, Compare compare); + // template <class Compare> + // void merge(this_type&& x, Compare compare); + // If these get implemented then make sure to override them in fixed_slist. + + bool validate() const; + int validate_iterator(const_iterator i) const; + + protected: + node_type* DoCreateNode(); + + template<typename... Args> + node_type* DoCreateNode(Args&&... args); + + template <typename Integer> + void DoAssign(Integer n, Integer value, true_type); + + template <typename InputIterator> + void DoAssign(InputIterator first, InputIterator last, false_type); + + void DoAssignValues(size_type n, const value_type& value); + + template <typename InputIterator> + node_type* DoInsertAfter(SListNodeBase* pNode, InputIterator first, InputIterator last); + + template <typename Integer> + node_type* DoInsertAfter(SListNodeBase* pNode, Integer n, Integer value, true_type); + + template <typename InputIterator> + node_type* DoInsertAfter(SListNodeBase* pNode, InputIterator first, InputIterator last, false_type); + + node_type* DoInsertValueAfter(SListNodeBase* pNode); + node_type* DoInsertValuesAfter(SListNodeBase* pNode, size_type n, const value_type& value); + + template<typename... Args> + node_type* DoInsertValueAfter(SListNodeBase* pNode, Args&&... args); + + void DoSwap(this_type& x); + + }; // class slist + + + + + + + + /////////////////////////////////////////////////////////////////////// + // SListNodeBase functions + /////////////////////////////////////////////////////////////////////// + + inline SListNodeBase* SListNodeInsertAfter(SListNodeBase* pPrevNode, SListNodeBase* pNode) + { + pNode->mpNext = pPrevNode->mpNext; + pPrevNode->mpNext = pNode; + return pNode; + } + + inline SListNodeBase* SListNodeGetPrevious(SListNodeBase* pNodeBase, const SListNodeBase* pNode) + { + while(pNodeBase && (pNodeBase->mpNext != pNode)) + pNodeBase = pNodeBase->mpNext; + return pNodeBase; + } + + inline const SListNodeBase* SListNodeGetPrevious(const SListNodeBase* pNodeBase, const SListNodeBase* pNode) + { + while(pNodeBase && (pNodeBase->mpNext != pNode)) + pNodeBase = pNodeBase->mpNext; + return pNodeBase; + } + + inline void SListNodeSpliceAfter(SListNodeBase* pNode, SListNodeBase* pNodeBeforeFirst, SListNodeBase* pNodeBeforeLast) + { + if((pNode != pNodeBeforeFirst) && (pNode != pNodeBeforeLast)) + { + SListNodeBase* const pFirst = pNodeBeforeFirst->mpNext; + SListNodeBase* const pPosition = pNode->mpNext; + + pNodeBeforeFirst->mpNext = pNodeBeforeLast->mpNext; + pNode->mpNext = pFirst; + pNodeBeforeLast->mpNext = pPosition; + } + } + + inline void SListNodeSpliceAfter(SListNodeBase* pNode, SListNodeBase* pNodeBase) + { + SListNodeBase* const pNodeBeforeLast = SListNodeGetPrevious(pNodeBase, NULL); + + if(pNodeBeforeLast != pNodeBase) + { + SListNodeBase* const pPosition = pNode->mpNext; + pNode->mpNext = pNodeBase->mpNext; + pNodeBase->mpNext = NULL; + pNodeBeforeLast->mpNext = pPosition; + } + } + + inline SListNodeBase* SListNodeReverse(SListNodeBase* pNode) + { + SListNodeBase* pNodeFirst = pNode; + pNode = pNode->mpNext; + pNodeFirst->mpNext = NULL; + + while(pNode) + { + SListNodeBase* const pTemp = pNode->mpNext; + pNode->mpNext = pNodeFirst; + pNodeFirst = pNode; + pNode = pTemp; + } + return pNodeFirst; + } + + inline uint32_t SListNodeGetSize(SListNodeBase* pNode) + { + uint32_t n = 0; + while(pNode) + { + ++n; + pNode = pNode->mpNext; + } + return n; + } + + + + + /////////////////////////////////////////////////////////////////////// + // SListIterator functions + /////////////////////////////////////////////////////////////////////// + + template <typename T, typename Pointer, typename Reference> + inline SListIterator<T, Pointer, Reference>::SListIterator() + : mpNode(NULL) + { + // Empty + } + + + template <typename T, typename Pointer, typename Reference> + inline SListIterator<T, Pointer, Reference>::SListIterator(const SListNodeBase* pNode) + : mpNode(static_cast<node_type*>((SListNode<T>*)const_cast<SListNodeBase*>(pNode))) // All this casting is in the name of making runtime debugging much easier on the user. + { + // Empty + } + + + template <typename T, typename Pointer, typename Reference> + inline SListIterator<T, Pointer, Reference>::SListIterator(const iterator& x) + : mpNode(const_cast<node_type*>(x.mpNode)) + { + // Empty + } + + + template <typename T, typename Pointer, typename Reference> + inline typename SListIterator<T, Pointer, Reference>::reference + SListIterator<T, Pointer, Reference>::operator*() const + { + return mpNode->mValue; + } + + + template <typename T, typename Pointer, typename Reference> + inline typename SListIterator<T, Pointer, Reference>::pointer + SListIterator<T, Pointer, Reference>::operator->() const + { + return &mpNode->mValue; + } + + + template <typename T, typename Pointer, typename Reference> + inline typename SListIterator<T, Pointer, Reference>::this_type& + SListIterator<T, Pointer, Reference>::operator++() + { + mpNode = static_cast<node_type*>(mpNode->mpNext); + return *this; + } + + + template <typename T, typename Pointer, typename Reference> + inline typename SListIterator<T, Pointer, Reference>::this_type + SListIterator<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 SListIterator<T, PointerA, ReferenceA>& a, + const SListIterator<T, PointerB, ReferenceB>& b) + { + return a.mpNode == b.mpNode; + } + + + template <typename T, typename PointerA, typename ReferenceA, typename PointerB, typename ReferenceB> + inline bool operator!=(const SListIterator<T, PointerA, ReferenceA>& a, + const SListIterator<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 SListIterator<T, Pointer, Reference>& a, + const SListIterator<T, Pointer, Reference>& b) + { + return a.mpNode != b.mpNode; + } + + + + + + /////////////////////////////////////////////////////////////////////// + // SListBase functions + /////////////////////////////////////////////////////////////////////// + + template <typename T, typename Allocator> + inline SListBase<T, Allocator>::SListBase() + : mNodeAllocator(base_node_type(), allocator_type(EASTL_SLIST_DEFAULT_NAME)) + #if EASTL_SLIST_SIZE_CACHE + , mSize(0) + #endif + { + internalNode().mpNext = NULL; + } + + + template <typename T, typename Allocator> + inline SListBase<T, Allocator>::SListBase(const allocator_type& allocator) + : mNodeAllocator(base_node_type(), allocator) + #if EASTL_SLIST_SIZE_CACHE + , mSize(0) + #endif + { + internalNode().mpNext = NULL; + } + + + template <typename T, typename Allocator> + inline SListBase<T, Allocator>::~SListBase() + { + DoEraseAfter((SListNodeBase*)&internalNode(), NULL); + } + + + template <typename T, typename Allocator> + inline const typename SListBase<T, Allocator>::allocator_type& + SListBase<T, Allocator>::get_allocator() const EA_NOEXCEPT + { + return internalAllocator(); + } + + + template <typename T, typename Allocator> + inline typename SListBase<T, Allocator>::allocator_type& + SListBase<T, Allocator>::get_allocator() EA_NOEXCEPT + { + return internalAllocator(); + } + + + template <typename T, typename Allocator> + void + SListBase<T, Allocator>::set_allocator(const allocator_type& allocator) + { + EASTL_ASSERT((internalAllocator() == allocator) || (static_cast<node_type*>(internalNode().mpNext) == NULL)); // We can only assign a different allocator if we are empty of elements. + internalAllocator() = allocator; + } + + + template <typename T, typename Allocator> + inline SListNode<T>* SListBase<T, Allocator>::DoAllocateNode() + { + return (node_type*)allocate_memory(internalAllocator(), sizeof(node_type), EASTL_ALIGN_OF(T), 0); + } + + + template <typename T, typename Allocator> + inline void SListBase<T, Allocator>::DoFreeNode(node_type* pNode) + { + EASTLFree(internalAllocator(), pNode, sizeof(node_type)); + } + + + template <typename T, typename Allocator> + SListNodeBase* SListBase<T, Allocator>::DoEraseAfter(SListNodeBase* pNode) + { + node_type* const pNodeNext = static_cast<node_type*>((base_node_type*)pNode->mpNext); + SListNodeBase* const pNodeNextNext = (SListNodeBase*)pNodeNext->mpNext; + + pNode->mpNext = pNodeNextNext; + pNodeNext->~node_type(); + DoFreeNode(pNodeNext); + #if EASTL_SLIST_SIZE_CACHE + --mSize; + #endif + return pNodeNextNext; + } + + + template <typename T, typename Allocator> + SListNodeBase* SListBase<T, Allocator>::DoEraseAfter(SListNodeBase* pNode, SListNodeBase* pNodeLast) + { + node_type* pNodeCurrent = static_cast<node_type*>((base_node_type*)pNode->mpNext); + + while(pNodeCurrent != (base_node_type*)pNodeLast) + { + node_type* const pNodeTemp = pNodeCurrent; + pNodeCurrent = static_cast<node_type*>((base_node_type*)pNodeCurrent->mpNext); + pNodeTemp->~node_type(); + DoFreeNode(pNodeTemp); + #if EASTL_SLIST_SIZE_CACHE + --mSize; + #endif + } + pNode->mpNext = pNodeLast; + return pNodeLast; + } + + + + + /////////////////////////////////////////////////////////////////////// + // slist functions + /////////////////////////////////////////////////////////////////////// + + template <typename T, typename Allocator> + inline slist<T, Allocator>::slist() + : base_type() + { + // Empty + } + + + template <typename T, typename Allocator> + inline slist<T, Allocator>::slist(const allocator_type& allocator) + : base_type(allocator) + { + // Empty + } + + + template <typename T, typename Allocator> + inline slist<T, Allocator>::slist(size_type n, const allocator_type& allocator) + : base_type(allocator) + { + DoInsertValuesAfter((SListNodeBase*)&internalNode(), n, value_type()); + } + + + template <typename T, typename Allocator> + inline slist<T, Allocator>::slist(size_type n, const value_type& value, const allocator_type& allocator) + : base_type(allocator) + { + DoInsertValuesAfter((SListNodeBase*)&internalNode(), n, value); + } + + + template <typename T, typename Allocator> + inline slist<T, Allocator>::slist(const slist& x) + : base_type(x.internalAllocator()) + { + DoInsertAfter((SListNodeBase*)&internalNode(), const_iterator((SListNodeBase*)x.internalNode().mpNext), const_iterator(NULL), false_type()); + } + + + template <typename T, typename Allocator> + slist<T, Allocator>::slist(this_type&& x) + : base_type(x.internalAllocator()) + { + swap(x); + } + + template <typename T, typename Allocator> + slist<T, Allocator>::slist(this_type&& x, const allocator_type& allocator) + : base_type(allocator) + { + swap(x); // member swap handles the case that x has a different allocator than our allocator by doing a copy. + } + + + template <typename T, typename Allocator> + inline slist<T, Allocator>::slist(std::initializer_list<value_type> ilist, const allocator_type& allocator) + : base_type(allocator) + { + DoInsertAfter((SListNodeBase*)&internalNode(), ilist.begin(), ilist.end()); + } + + + template <typename T, typename Allocator> + template <typename InputIterator> + inline slist<T, Allocator>::slist(InputIterator first, InputIterator last) + : base_type(EASTL_SLIST_DEFAULT_ALLOCATOR) + { + DoInsertAfter((SListNodeBase*)&internalNode(), first, last); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::begin() EA_NOEXCEPT + { + return iterator((SListNodeBase*)internalNode().mpNext); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::const_iterator + slist<T, Allocator>::begin() const EA_NOEXCEPT + { + return const_iterator((SListNodeBase*)internalNode().mpNext); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::const_iterator + slist<T, Allocator>::cbegin() const EA_NOEXCEPT + { + return const_iterator((SListNodeBase*)internalNode().mpNext); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::end() EA_NOEXCEPT + { + return iterator(NULL); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::const_iterator + slist<T, Allocator>::end() const EA_NOEXCEPT + { + return const_iterator(NULL); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::const_iterator + slist<T, Allocator>::cend() const EA_NOEXCEPT + { + return const_iterator(NULL); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::before_begin() EA_NOEXCEPT + { + return iterator((SListNodeBase*)&internalNode()); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::const_iterator + slist<T, Allocator>::before_begin() const EA_NOEXCEPT + { + return const_iterator((SListNodeBase*)&internalNode()); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::const_iterator + slist<T, Allocator>::cbefore_begin() const EA_NOEXCEPT + { + return const_iterator((SListNodeBase*)&internalNode()); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::previous(const_iterator position) + { + return iterator(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)position.mpNode)); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::const_iterator + slist<T, Allocator>::previous(const_iterator position) const + { + return const_iterator(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)position.mpNode)); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::reference + slist<T, Allocator>::front() + { + #if EASTL_ASSERT_ENABLED + if(EASTL_UNLIKELY(internalNode().mpNext == NULL)) + EASTL_FAIL_MSG("slist::front -- empty container"); + #endif + + EA_ANALYSIS_ASSUME(internalNode().mpNext != NULL); + + return ((node_type*)internalNode().mpNext)->mValue; + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::const_reference + slist<T, Allocator>::front() const + { + #if EASTL_ASSERT_ENABLED + if(EASTL_UNLIKELY(internalNode().mpNext == NULL)) + EASTL_FAIL_MSG("slist::front -- empty container"); + #endif + + EA_ANALYSIS_ASSUME(internalNode().mpNext != NULL); + + return static_cast<node_type*>(internalNode().mpNext)->mValue; + } + + + template <typename T, typename Allocator> + template <class... Args> + void slist<T, Allocator>::emplace_front(Args&&... args) + { + DoInsertValueAfter((SListNodeBase*)&internalNode(), eastl::forward<Args>(args)...); + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::push_front(const value_type& value) + { + SListNodeInsertAfter((SListNodeBase*)&internalNode(), (SListNodeBase*)DoCreateNode(value)); + #if EASTL_SLIST_SIZE_CACHE + ++mSize; + #endif + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::reference + slist<T, Allocator>::push_front() + { + SListNodeInsertAfter((SListNodeBase*)&internalNode(), (SListNodeBase*)DoCreateNode()); + #if EASTL_SLIST_SIZE_CACHE + ++mSize; + #endif + return ((node_type*)internalNode().mpNext)->mValue; // Same as return front(); + } + + template <typename T, typename Allocator> + void slist<T, Allocator>::push_front(value_type&& value) + { + emplace_after(before_begin(), eastl::move(value)); + } + + + template <typename T, typename Allocator> + void slist<T, Allocator>::pop_front() + { + #if EASTL_ASSERT_ENABLED + if(EASTL_UNLIKELY(internalNode().mpNext == NULL)) + EASTL_FAIL_MSG("slist::front -- empty container"); + #endif + + EA_ANALYSIS_ASSUME(internalNode().mpNext != NULL); + + node_type* const pNode = static_cast<node_type*>(internalNode().mpNext); + internalNode().mpNext = pNode->mpNext; + pNode->~node_type(); + DoFreeNode(pNode); + #if EASTL_SLIST_SIZE_CACHE + --mSize; + #endif + } + + + template <typename T, typename Allocator> + typename slist<T, Allocator>::this_type& slist<T, Allocator>::operator=(const this_type& x) + { + if(&x != this) + { + // If (EASTL_ALLOCATOR_COPY_ENABLED == 1) and the current contents are allocated by an + // allocator that's unequal to x's allocator, we need to reallocate our elements with + // our current allocator and reallocate it with x's allocator. If the allocators are + // equal then we can use a more optimal algorithm that doesn't reallocate our elements + // but instead can copy them in place. + + #if EASTL_ALLOCATOR_COPY_ENABLED + bool bSlowerPathwayRequired = (internalAllocator() != x.internalAllocator()); + #else + bool bSlowerPathwayRequired = false; + #endif + + if(bSlowerPathwayRequired) + { + clear(); + + #if EASTL_ALLOCATOR_COPY_ENABLED + internalAllocator() = x.internalAllocator(); + #endif + } + + DoAssign(x.begin(), x.end(), eastl::false_type()); + } + + return *this; + } + + + template <typename T, typename Allocator> + typename slist<T, Allocator>::this_type& slist<T, Allocator>::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 T, typename Allocator> + typename slist<T, Allocator>::this_type& slist<T, Allocator>::operator=(std::initializer_list<value_type> ilist) + { + DoAssign(ilist.begin(), ilist.end(), false_type()); + return *this; + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::assign(std::initializer_list<value_type> ilist) + { + DoAssign(ilist.begin(), ilist.end(), false_type()); + } + + + template <typename T, typename Allocator> + template <typename InputIterator> // It turns out that the C++ std::list specifies a two argument + inline void slist<T, Allocator>::assign(InputIterator first, InputIterator last) // version of assign that takes (int size, int value). These are not + { // iterators, so we need to do a template compiler trick to do the right thing. + DoAssign(first, last, is_integral<InputIterator>()); + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::assign(size_type n, const value_type& value) + { + // To do: get rid of DoAssignValues and put its implementation directly here. + DoAssignValues(n, value); + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::swap(this_type& x) + { + if(internalAllocator() == x.internalAllocator()) // If allocators are equivalent... + DoSwap(x); + else // else swap the contents. + { + const this_type temp(*this); // Can't call eastl::swap because that would + *this = x; // itself call this member swap function. + x = temp; + } + } + + + template <typename T, typename Allocator> + inline bool slist<T, Allocator>::empty() const EA_NOEXCEPT + { + return internalNode().mpNext == NULL; + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::size_type + slist<T, Allocator>::size() const EA_NOEXCEPT + { + return SListNodeGetSize((SListNodeBase*)internalNode().mpNext); + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::clear() EA_NOEXCEPT + { + DoEraseAfter((SListNodeBase*)&internalNode(), NULL); + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::reset_lose_memory() EA_NOEXCEPT + { + // The reset 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. + internalNode().mpNext = NULL; + #if EASTL_SLIST_SIZE_CACHE + mSize = 0; + #endif + } + + + template <typename T, typename Allocator> + void slist<T, Allocator>::resize(size_type n, const value_type& value) + { + SListNodeBase* pNode = (SListNodeBase*)&internalNode(); + + for(; pNode->mpNext && (n > 0); --n) + pNode = pNode->mpNext; + + if(pNode->mpNext) + DoEraseAfter(pNode, NULL); + else + DoInsertValuesAfter(pNode, n, value); + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::resize(size_type n) + { + resize(n, value_type()); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::insert(const_iterator position) + { + return iterator((SListNodeBase*)DoInsertValueAfter(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)position.mpNode), value_type())); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::insert(const_iterator position, const value_type& value) + { + return iterator((SListNodeBase*)DoInsertValueAfter(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)position.mpNode), value)); + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::insert(const_iterator position, size_type n, const value_type& value) + { + // To do: get rid of DoAssignValues and put its implementation directly here. + DoInsertValuesAfter(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)position.mpNode), n, value); + } + + + template <typename T, typename Allocator> + template <typename InputIterator> + inline void slist<T, Allocator>::insert(const_iterator position, InputIterator first, InputIterator last) + { + DoInsertAfter(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)position.mpNode), first, last); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::insert_after(const_iterator position) + { + return insert_after(position, value_type()); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::insert_after(const_iterator position, const value_type& value) + { + return iterator((SListNodeBase*)DoInsertValueAfter((SListNodeBase*)position.mpNode, value)); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::insert_after(const_iterator position, size_type n, const value_type& value) + { + return iterator((SListNodeBase*)DoInsertValuesAfter((SListNodeBase*)position.mpNode, n, value)); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::insert_after(const_iterator position, std::initializer_list<value_type> ilist) + { + return iterator((SListNodeBase*)DoInsertAfter((SListNodeBase*)position.mpNode, ilist.begin(), ilist.end(), false_type())); + } + + + template <typename T, typename Allocator> + template <typename InputIterator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::insert_after(const_iterator position, InputIterator first, InputIterator last) + { + return iterator((SListNodeBase*)DoInsertAfter((SListNodeBase*)position.mpNode, first, last)); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::insert_after(const_iterator position, value_type&& value) + { + return emplace_after(position, eastl::move(value)); + } + + + template <typename T, typename Allocator> + template <class... Args> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::emplace_after(const_iterator position, Args&&... args) + { + return iterator((SListNodeBase*)DoInsertValueAfter(position.mpNode, eastl::forward<Args>(args)...)); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::erase(const_iterator position) + { + return DoEraseAfter(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)position.mpNode)); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::erase(const_iterator first, const_iterator last) + { + return DoEraseAfter(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)first.mpNode), (SListNodeBase*)last.mpNode); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::erase_after(const_iterator position) + { + return iterator(DoEraseAfter((SListNodeBase*)position.mpNode)); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::iterator + slist<T, Allocator>::erase_after(const_iterator before_first, const_iterator last) + { + return iterator(DoEraseAfter((SListNodeBase*)before_first.mpNode, (SListNodeBase*)last.mpNode)); + } + + + template <typename T, typename Allocator> + void slist<T, Allocator>::remove(const value_type& value) + { + base_node_type* pNode = &internalNode(); + + while(pNode && pNode->mpNext) + { + if(static_cast<node_type*>(pNode->mpNext)->mValue == value) + DoEraseAfter((SListNodeBase*)pNode); // This will take care of modifying pNode->mpNext. + else + pNode = pNode->mpNext; + } + } + + template <typename T, typename Allocator> + template <typename Predicate> + void slist<T, Allocator>::remove_if(Predicate predicate) + { + base_node_type* pNode = &internalNode(); + + while(pNode && pNode->mpNext) + { + if(predicate(static_cast<node_type*>(pNode->mpNext)->mValue)) + DoEraseAfter((SListNodeBase*)pNode); // This will take care of modifying pNode->mpNext. + else + pNode = pNode->mpNext; + } + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice(const_iterator position, this_type& x) + { + // Splicing operations cannot succeed if the two containers use unequal allocators. + // This issue is not addressed in the C++ 1998 standard but is discussed in the + // LWG defect reports, such as #431. There is no simple solution to this problem. + // One option is to throw an exception. Another option which probably captures the + // user intent most of the time is to copy the range from the source to the dest and + // remove it from the source. Until then it's simply disallowed to splice with unequal allocators. + // EASTL_ASSERT(internalAllocator() == x.internalAllocator()); // Disabled because our member sort function uses splice but with allocators that may be unequal. There isn't a simple workaround aside from disabling this assert. + + if(x.internalNode().mpNext) // If there is anything to splice... + { + if(internalAllocator() == x.internalAllocator()) + { + SListNodeSpliceAfter(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)position.mpNode), + (SListNodeBase*)&x.internalNode(), + SListNodeGetPrevious((SListNodeBase*)&x.internalNode(), NULL)); + + #if EASTL_SLIST_SIZE_CACHE + mSize += x.mSize; + x.mSize = 0; + #endif + } + else + { + insert(position, x.begin(), x.end()); + x.clear(); + } + } + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice(const_iterator position, this_type& x, const_iterator i) + { + if(internalAllocator() == x.internalAllocator()) + { + SListNodeSpliceAfter(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)position.mpNode), + SListNodeGetPrevious((SListNodeBase*)&x.internalNode(), (SListNodeBase*)i.mpNode), + (SListNodeBase*)i.mpNode); + + #if EASTL_SLIST_SIZE_CACHE + ++mSize; + --x.mSize; + #endif + } + else + { + insert(position, *i); + x.erase(i); + } + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice(const_iterator position, this_type& x, const_iterator first, const_iterator last) + { + if(first != last) // If there is anything to splice... + { + if(internalAllocator() == x.internalAllocator()) + { + #if EASTL_SLIST_SIZE_CACHE + const size_type n = (size_type)eastl::distance(first, last); + mSize += n; + x.mSize -= n; + #endif + + SListNodeSpliceAfter(SListNodeGetPrevious((SListNodeBase*)&internalNode(), (SListNodeBase*)position.mpNode), + SListNodeGetPrevious((SListNodeBase*)&x.internalNode(), (SListNodeBase*)first.mpNode), + SListNodeGetPrevious((SListNodeBase*)first.mpNode, (SListNodeBase*)last.mpNode)); + } + else + { + insert(position, first, last); + x.erase(first, last); + } + } + } + + + template <typename T, typename Allocator> + void slist<T, Allocator>::splice(const_iterator position, this_type&& x) + { + return splice(position, x); // This will splice(const_iterator, this_type&) + } + + template <typename T, typename Allocator> + void slist<T, Allocator>::splice(const_iterator position, this_type&& x, const_iterator i) + { + return splice(position, x, i); // This will splice_after(const_iterator, this_type&, const_iterator) + } + + template <typename T, typename Allocator> + void slist<T, Allocator>::splice(const_iterator position, this_type&& x, const_iterator first, const_iterator last) + { + return splice(position, x, first, last); // This will splice(const_iterator, this_type&, const_iterator, const_iterator) + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice_after(const_iterator position, this_type& x) + { + if(!x.empty()) // If there is anything to splice... + { + if(internalAllocator() == x.internalAllocator()) + { + SListNodeSpliceAfter((SListNodeBase*)position.mpNode, (SListNodeBase*)&x.internalNode()); + + #if EASTL_SLIST_SIZE_CACHE + mSize += x.mSize; + x.mSize = 0; + #endif + } + else + { + insert_after(position, x.begin(), x.end()); + x.clear(); + } + } + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice_after(const_iterator position, this_type& x, const_iterator i) + { + if(internalAllocator() == x.internalAllocator()) + { + SListNodeSpliceAfter((SListNodeBase*)position.mpNode, (SListNodeBase*)i.mpNode); + + #if EASTL_SLIST_SIZE_CACHE + mSize++; + x.mSize--; + #endif + } + else + { + const_iterator iNext(i); + insert_after(position, i, ++iNext); + x.erase(i); + } + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice_after(const_iterator position, this_type& x, const_iterator first, const_iterator last) + { + if(first != last) // If there is anything to splice... + { + if(internalAllocator() == x.internalAllocator()) + { + #if EASTL_SLIST_SIZE_CACHE + const size_type n = (size_type)eastl::distance(first, last); + mSize += n; + x.mSize -= n; + #endif + + SListNodeSpliceAfter((SListNodeBase*)position.mpNode, (SListNodeBase*)first.mpNode, (SListNodeBase*)last.mpNode); + } + else + { + insert_after(position, first, last); + x.erase(first, last); + } + } + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice_after(const_iterator position, this_type&& x) + { + return splice_after(position, x); // This will call splice_after(const_iterator, this_type&) + } + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice_after(const_iterator position, this_type&& x, const_iterator i) + { + return splice_after(position, x, i); // This will call splice_after(const_iterator, this_type&, const_iterator) + } + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice_after(const_iterator position, this_type&& x, const_iterator first, const_iterator last) + { + return splice_after(position, x, first, last); // This will call splice_after(const_iterator, this_type&, const_iterator, const_iterator) + } + + + // This function is deprecated. + // We have no way of knowing what the container or allocator for before_first/before_last is. + // Thus this function requires that the iterators come from equivalent allocators. + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice_after(const_iterator position, const_iterator before_first, const_iterator before_last) + { + if(before_first != before_last) // If there is anything to splice... + { + #if EASTL_SLIST_SIZE_CACHE + // We have a problem here because the inserted range may come from *this or + // it may come from some other list. We have no choice but to implement an O(n) + // brute-force search in our list for 'previous'. + + iterator i((SListNodeBase*)&internalNode()); + iterator iEnd(NULL); + + for( ; i != iEnd; ++i) + { + if(i == before_first) + break; + } + + if(i == iEnd) // If the input came from an external range... + mSize += (size_type)eastl::distance(before_first, before_last); // Note that we have no way of knowing how to decrementing the size from the external container, assuming it came from one. + else + { EASTL_FAIL_MSG("slist::splice_after: Impossible to decrement source mSize. Use the other splice_after function instead."); } + #endif + + // Insert the range of [before_first + 1, before_last + 1) after position. + SListNodeSpliceAfter((SListNodeBase*)position.mpNode, (SListNodeBase*)before_first.mpNode, (SListNodeBase*)before_last.mpNode); + } + } + + + // This function is deprecated. + // We have no way of knowing what the container or allocator for previous is. + // Thus this function requires that the iterators come from equivalent allocators. + template <typename T, typename Allocator> + inline void slist<T, Allocator>::splice_after(const_iterator position, const_iterator previous) + { + #if EASTL_SLIST_SIZE_CACHE + // We have a problem here because the inserted range may come from *this or + // it may come from some other list. We have no choice but to implement an O(n) + // brute-force search in our list for 'previous'. + + iterator i((SListNodeBase*)&internalNode()); + iterator iEnd(NULL); + + for( ; i != iEnd; ++i) + { + if(i == previous) + break; + } + + if(i == iEnd) // If the input came from an external range... + ++mSize; // Note that we have no way of knowing how to decrementing the size from the external container, assuming it came from one. + else + { EASTL_FAIL_MSG("slist::splice_after: Impossible to decrement source mSize. Use the other splice_after function instead."); } + #endif + + // Insert the element at previous + 1 after position. + SListNodeSpliceAfter((SListNodeBase*)position.mpNode, (SListNodeBase*)previous.mpNode, (SListNodeBase*)previous.mpNode->mpNext); + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::sort() + { + // To do: look at using a merge sort, which may well be faster. + eastl::comb_sort(begin(), end()); + } + + + template <typename T, typename Allocator> + template <class Compare> + inline void slist<T, Allocator>::sort(Compare compare) + { + // To do: look at using a merge sort, which may well be faster. + eastl::comb_sort(begin(), end(), compare); + } + + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::reverse() EA_NOEXCEPT + { + if(internalNode().mpNext) + internalNode().mpNext = static_cast<node_type*>((base_node_type*)SListNodeReverse((SListNodeBase*)internalNode().mpNext)); + } + + + template <typename T, typename Allocator> + template<typename... Args> + inline typename slist<T, Allocator>::node_type* + slist<T, Allocator>::DoCreateNode(Args&&... args) + { + node_type* const pNode = DoAllocateNode(); // pNode is of type node_type, but it's uninitialized memory. + + #if EASTL_EXCEPTIONS_ENABLED + try + { + ::new((void*)&pNode->mValue) value_type(eastl::forward<Args>(args)...); + } + catch(...) + { + DoFreeNode(pNode); + throw; + } + #else + ::new((void*)&pNode->mValue) value_type(eastl::forward<Args>(args)...); + #endif + + return pNode; + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::node_type* + slist<T, Allocator>::DoCreateNode() + { + node_type* const pNode = DoAllocateNode(); + #if EASTL_EXCEPTIONS_ENABLED + try + { + ::new((void*)&pNode->mValue) value_type(); + } + catch(...) + { + DoFreeNode(pNode); + throw; + } + #else + ::new((void*)&pNode->mValue) value_type(); + #endif + return pNode; + } + + + template <typename T, typename Allocator> + template <typename Integer> + void slist<T, Allocator>::DoAssign(Integer n, Integer value, true_type) + { + DoAssignValues(static_cast<size_type>(n), static_cast<value_type>(value)); + } + + + template <typename T, typename Allocator> + template <typename InputIterator> + void slist<T, Allocator>::DoAssign(InputIterator first, InputIterator last, false_type) + { + base_node_type* pNodePrev = &internalNode(); + node_type* pNode = static_cast<node_type*>(internalNode().mpNext); + + for(; pNode && (first != last); ++first) + { + pNode->mValue = *first; + pNodePrev = pNode; + pNode = static_cast<node_type*>(pNode->mpNext); + } + + if(first == last) + DoEraseAfter((SListNodeBase*)pNodePrev, NULL); + else + DoInsertAfter((SListNodeBase*)pNodePrev, first, last); + } + + + template <typename T, typename Allocator> + void slist<T, Allocator>::DoAssignValues(size_type n, const value_type& value) + { + base_node_type* pNodePrev = &internalNode(); + node_type* pNode = static_cast<node_type*>(internalNode().mpNext); + + for(; pNode && (n > 0); --n) + { + pNode->mValue = value; + pNodePrev = pNode; + pNode = static_cast<node_type*>(pNode->mpNext); + } + + if(n) + DoInsertValuesAfter((SListNodeBase*)pNodePrev, n, value); + else + DoEraseAfter((SListNodeBase*)pNodePrev, NULL); + } + + + template <typename T, typename Allocator> + template <typename InputIterator> + inline typename slist<T, Allocator>::node_type* + slist<T, Allocator>::DoInsertAfter(SListNodeBase* pNode, InputIterator first, InputIterator last) + { + return DoInsertAfter(pNode, first, last, is_integral<InputIterator>()); + } + + + template <typename T, typename Allocator> + template <typename Integer> + inline typename slist<T, Allocator>::node_type* + slist<T, Allocator>::DoInsertAfter(SListNodeBase* pNode, Integer n, Integer value, true_type) + { + return DoInsertValuesAfter(pNode, n, value); + } + + + template <typename T, typename Allocator> + template <typename InputIterator> + inline typename slist<T, Allocator>::node_type* + slist<T, Allocator>::DoInsertAfter(SListNodeBase* pNode, InputIterator first, InputIterator last, false_type) + { + for(; first != last; ++first) + { + pNode = SListNodeInsertAfter((SListNodeBase*)pNode, (SListNodeBase*)DoCreateNode(*first)); + #if EASTL_SLIST_SIZE_CACHE + ++mSize; + #endif + } + + return static_cast<node_type*>((base_node_type*)pNode); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::node_type* + slist<T, Allocator>::DoInsertValueAfter(SListNodeBase* pNode) + { + #if EASTL_SLIST_SIZE_CACHE + pNode = SListNodeInsertAfter((SListNodeBase*)pNode, (SListNodeBase*)DoCreateNode()); + ++mSize; + return static_cast<node_type*>((base_node_type*)pNode); + #else + return static_cast<node_type*>((base_node_type*)SListNodeInsertAfter((SListNodeBase*)pNode, (SListNodeBase*)DoCreateNode())); + #endif + } + + + template <typename T, typename Allocator> + template<typename... Args> + inline typename slist<T, Allocator>::node_type* + slist<T, Allocator>::DoInsertValueAfter(SListNodeBase* pNode, Args&&... args) + { + SListNodeBase* pNodeNew = (SListNodeBase*)DoCreateNode(eastl::forward<Args>(args)...); + pNode = SListNodeInsertAfter(pNode, pNodeNew); + #if EASTL_LIST_SIZE_CACHE + ++mSize; // Increment the size after the node creation because we need to assume an exception can occur in the creation. + #endif + return static_cast<node_type*>((base_node_type*)pNode); + } + + + template <typename T, typename Allocator> + inline typename slist<T, Allocator>::node_type* + slist<T, Allocator>::DoInsertValuesAfter(SListNodeBase* pNode, size_type n, const value_type& value) + { + for(size_type i = 0; i < n; ++i) + { + pNode = SListNodeInsertAfter((SListNodeBase*)pNode, (SListNodeBase*)DoCreateNode(value)); + #if EASTL_SLIST_SIZE_CACHE + ++mSize; // We don't do a single mSize += n at the end because an exception may result in only a partial range insertion. + #endif + } + return static_cast<node_type*>((base_node_type*)pNode); + } + + + template <typename T, typename Allocator> + inline void slist<T, Allocator>::DoSwap(this_type& x) + { + eastl::swap(internalNode().mpNext, x.internalNode().mpNext); + eastl::swap(internalAllocator(), x.internalAllocator()); // We do this even if EASTL_ALLOCATOR_COPY_ENABLED is 0. + #if EASTL_LIST_SIZE_CACHE + eastl::swap(mSize, x.mSize); + #endif + } + + + template <typename T, typename Allocator> + inline bool slist<T, Allocator>::validate() const + { + #if EASTL_SLIST_SIZE_CACHE + size_type n = 0; + + for(const_iterator i(begin()), iEnd(end()); i != iEnd; ++i) + ++n; + + if(n != mSize) + return false; + #endif + + // To do: More validation. + return true; + } + + + template <typename T, typename Allocator> + inline int slist<T, Allocator>::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, typename Allocator> + bool operator==(const slist<T, Allocator>& a, const slist<T, Allocator>& b) + { + typename slist<T, Allocator>::const_iterator ia = a.begin(); + typename slist<T, Allocator>::const_iterator ib = b.begin(); + typename slist<T, Allocator>::const_iterator enda = a.end(); + + #if EASTL_SLIST_SIZE_CACHE + if(a.size() == b.size()) + { + while((ia != enda) && (*ia == *ib)) + { + ++ia; + ++ib; + } + return (ia == enda); + } + return false; + #else + typename slist<T, Allocator>::const_iterator endb = b.end(); + + while((ia != enda) && (ib != endb) && (*ia == *ib)) + { + ++ia; + ++ib; + } + return (ia == enda) && (ib == endb); + #endif + } + + + template <typename T, typename Allocator> + inline bool operator<(const slist<T, Allocator>& a, const slist<T, Allocator>& b) + { + return eastl::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); + } + + + template <typename T, typename Allocator> + inline bool operator!=(const slist<T, Allocator>& a, const slist<T, Allocator>& b) + { + return !(a == b); + } + + + template <typename T, typename Allocator> + inline bool operator>(const slist<T, Allocator>& a, const slist<T, Allocator>& b) + { + return b < a; + } + + + template <typename T, typename Allocator> + inline bool operator<=(const slist<T, Allocator>& a, const slist<T, Allocator>& b) + { + return !(b < a); + } + + + template <typename T, typename Allocator> + inline bool operator>=(const slist<T, Allocator>& a, const slist<T, Allocator>& b) + { + return !(a < b); + } + + + template <typename T, typename Allocator> + inline void swap(slist<T, Allocator>& a, slist<T, Allocator>& b) + { + a.swap(b); + } + + + /// erase / erase_if + /// + /// https://en.cppreference.com/w/cpp/container/forward_list/erase2 + template <class T, class Allocator, class U> + void erase(slist<T, Allocator>& c, const U& value) + { + // Erases all elements that compare equal to value from the container. + c.remove_if([&](auto& elem) { return elem == value; }); + } + + template <class T, class Allocator, class Predicate> + void erase_if(slist<T, Allocator>& c, Predicate predicate) + { + // Erases all elements that satisfy the predicate pred from the container. + c.remove_if(predicate); + } + + + /// insert_iterator + /// + /// We borrow a trick from SGI STL here and define an insert_iterator + /// specialization for slist. This allows slist insertions to be O(1) + /// instead of O(n/2), due to caching of the previous node. + /// + template <typename T, typename Allocator> + class insert_iterator< slist<T, Allocator> > + { + public: + typedef slist<T, Allocator> Container; + typedef typename Container::const_reference const_reference; + typedef typename Container::iterator iterator_type; + typedef EASTL_ITC_NS::output_iterator_tag iterator_category; + typedef void value_type; + typedef void difference_type; + typedef void pointer; + typedef void reference; + + protected: + Container& container; + iterator_type it; + + public: + insert_iterator(Container& x, iterator_type i) + : container(x) + { + if(i == x.begin()) + it = x.before_begin(); + else + it = x.previous(i); + } + + insert_iterator<Container>& operator=(const_reference value) + { it = container.insert_after(it, value); return *this; } + + insert_iterator<Container>& operator*() + { return *this; } + + insert_iterator<Container>& operator++() + { return *this; } // This is by design. + + insert_iterator<Container>& operator++(int) + { return *this; } // This is by design. + + }; // insert_iterator<slist> + + +} // namespace eastl + +EA_RESTORE_SN_WARNING() + +EA_RESTORE_VC_WARNING(); + + +#endif // Header include guard |