aboutsummaryrefslogtreecommitdiff
path: root/include/EASTL/bonus/intrusive_slist.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/EASTL/bonus/intrusive_slist.h')
-rw-r--r--include/EASTL/bonus/intrusive_slist.h321
1 files changed, 0 insertions, 321 deletions
diff --git a/include/EASTL/bonus/intrusive_slist.h b/include/EASTL/bonus/intrusive_slist.h
deleted file mode 100644
index 28d445d..0000000
--- a/include/EASTL/bonus/intrusive_slist.h
+++ /dev/null
@@ -1,321 +0,0 @@
-/////////////////////////////////////////////////////////////////////////////
-// Copyright (c) Electronic Arts Inc. All rights reserved.
-/////////////////////////////////////////////////////////////////////////////
-
-
-///////////////////////////////////////////////////////////////////////////////
-// *** Note ***
-// This implementation is incomplete.
-///////////////////////////////////////////////////////////////////////////////
-
-
-#ifndef EASTL_INTRUSIVE_SLIST_H
-#define EASTL_INTRUSIVE_SLIST_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_slist_node
- ///
- struct intrusive_slist_node
- {
- intrusive_slist_node* mpNext;
- };
-
-
- /// IntrusiveSListIterator
- ///
- template <typename T, typename Pointer, typename Reference>
- struct IntrusiveSListIterator
- {
- typedef IntrusiveSListIterator<T, Pointer, Reference> this_type;
- typedef IntrusiveSListIterator<T, T*, T&> iterator;
- typedef IntrusiveSListIterator<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:
- node_type* mpNode;
-
- public:
- IntrusiveSListIterator();
- explicit IntrusiveSListIterator(pointer pNode); // Note that you can also construct an iterator from T via this, since value_type == node_type.
- IntrusiveSListIterator(const iterator& x);
-
- reference operator*() const;
- pointer operator->() const;
-
- this_type& operator++();
- this_type operator++(int);
-
- }; // struct IntrusiveSListIterator
-
-
-
- /// intrusive_slist_base
- ///
- /// Provides a template-less base class for intrusive_slist.
- ///
- class intrusive_slist_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_slist_node* mpNext;
-
- public:
- intrusive_slist_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_slist_base
-
-
-
- /// intrusive_slist
- ///
- template <typename T = intrusive_slist_node>
- class intrusive_slist : public intrusive_slist_base
- {
- public:
- typedef intrusive_slist<T> this_type;
- typedef intrusive_slist_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 IntrusiveSListIterator<T, T*, T&> iterator;
- typedef IntrusiveSListIterator<T, const T*, const T&> const_iterator;
-
- public:
- intrusive_slist(); ///< Creates an empty list.
- //intrusive_slist(const this_type& x); ///< Creates an empty list; ignores the argument. To consider: Is this a useful function?
- //this_type& operator=(const this_type& x); ///< Clears the list; ignores the argument. To consider: Is this a useful function?
-
- iterator begin(); ///< Returns an iterator pointing to the first element in the list. O(1).
- const_iterator begin() const; ///< Returns a const_iterator pointing to the first element in the list. O(1).
- const_iterator cbegin() const; ///< Returns a const_iterator pointing to the first element in the list. O(1).
- iterator end(); ///< Returns an iterator pointing one-after the last element in the list. O(1).
- const_iterator end() const; ///< Returns a const_iterator pointing one-after the last element in the list. O(1).
- const_iterator cend() const; ///< Returns a const_iterator pointing one-after the last element in the list. O(1).
- iterator before_begin(); ///< Returns iterator to position before begin. O(1).
- const_iterator before_begin() const; ///< Returns iterator to previous position. O(1).
- const_iterator cbefore_begin() const; ///< Returns iterator to previous position. O(1).
-
- iterator previous(const_iterator position); ///< Returns iterator to previous position. O(n).
- const_iterator previous(const_iterator position) const; ///< Returns iterator to previous position. O(n).
-
- 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 pop_front(); ///< 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(n)
- iterator insert_after(iterator position, value_type& value); ///< Inserts an element after the element pointed to by the iterator. O(1)
-
- iterator erase(iterator position); ///< Erases the element pointed to by the iterator. O(n)
- iterator erase_after(iterator position); ///< Erases the element after the element pointed to by the iterator. O(1)
-
- iterator erase(iterator first, iterator last); ///< Erases elements within the iterator range [first, last). O(n).
- iterator erase_after(iterator before_first, iterator last); ///< Erases elements within the iterator range [before_first, last). O(1).
-
- void swap(this_type& x); ///< Swaps the contents of two intrusive lists; O(1).
-
-
- void splice(iterator position, value_type& value); ///< Moves the given element into this list before the element pointed to by position; O(n).
- ///< 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(n).
- ///< 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(n).
-
- 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(n).
- ///< Required: position must not be in [first, last). (same as std::list).
-
- void splice_after(iterator position, value_type& value); ///< Moves the given element into this list after 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_after(iterator position, this_type& x); ///< Moves the contents of a list into this list after the element pointed to by position; O(n).
- ///< Required: &x != this (same as std::list).
-
- void splice_after(iterator position, this_type& x, iterator xPrevious); ///< Moves the element after xPrevious to be after position. O(1).
- ///< Required: &x != this (same as std::list).
-
- void splice_after(iterator position, this_type& x, iterator before_first, iterator before_last); ///< Moves the elements in the range of [before_first+1, before_last+1) to be after position. O(1).
-
- bool validate() const;
- int validate_iterator(const_iterator i) const;
-
- }; // intrusive_slist
-
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // IntrusiveSListIterator
- ///////////////////////////////////////////////////////////////////////
-
- template <typename T, typename Pointer, typename Reference>
- inline IntrusiveSListIterator<T, Pointer, Reference>::IntrusiveSListIterator()
- {
- #if EASTL_DEBUG
- mpNode = NULL;
- #endif
- }
-
- template <typename T, typename Pointer, typename Reference>
- inline IntrusiveSListIterator<T, Pointer, Reference>::IntrusiveSListIterator(pointer pNode)
- : mpNode(pNode)
- {
- }
-
- template <typename T, typename Pointer, typename Reference>
- inline IntrusiveSListIterator<T, Pointer, Reference>::IntrusiveSListIterator(const iterator& x)
- : mpNode(x.mpNode)
- {
- }
-
-
- ///////////////////////////////////////////////////////////////////////
- // intrusive_slist_base
- ///////////////////////////////////////////////////////////////////////
-
- // To do.
-
-
- ///////////////////////////////////////////////////////////////////////
- // intrusive_slist
- ///////////////////////////////////////////////////////////////////////
-
- // To do.
-
-
- ///////////////////////////////////////////////////////////////////////
- // global operators
- ///////////////////////////////////////////////////////////////////////
-
-
-
- ///////////////////////////////////////////////////////////////////////
- // global operators
- ///////////////////////////////////////////////////////////////////////
-
- template <typename T>
- bool operator==(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
- {
- // If we store an mSize member for intrusive_slist, we want to take advantage of it here.
- typename intrusive_slist<T>::const_iterator ia = a.begin();
- typename intrusive_slist<T>::const_iterator ib = b.begin();
- typename intrusive_slist<T>::const_iterator enda = a.end();
- typename intrusive_slist<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_slist<T>& a, const intrusive_slist<T>& b)
- {
- return eastl::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
- }
-
- template <typename T>
- bool operator!=(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
- {
- return !(a == b);
- }
-
- template <typename T>
- bool operator>(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
- {
- return b < a;
- }
-
- template <typename T>
- bool operator<=(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
- {
- return !(b < a);
- }
-
- template <typename T>
- bool operator>=(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
- {
- return !(a < b);
- }
-
- template <typename T>
- void swap(intrusive_slist<T>& a, intrusive_slist<T>& b)
- {
- a.swap(b);
- }
-
-} // namespace eastl
-
-
-#endif // Header include guard
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
Powered by cgit, Themed by Ted Yin.