summaryrefslogtreecommitdiffstats
path: root/raul/List.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'raul/List.hpp')
-rw-r--r--raul/List.hpp416
1 files changed, 20 insertions, 396 deletions
diff --git a/raul/List.hpp b/raul/List.hpp
index a090251..f695421 100644
--- a/raul/List.hpp
+++ b/raul/List.hpp
@@ -49,28 +49,36 @@ public:
public:
Node(T elem) : _elem(elem) {}
virtual ~Node() {}
+
+ template <typename Y>
+ Node(const typename List<Y>::Node& copy)
+ : _elem(copy._elem), _prev(copy._prev), _next(copy._next)
+ {}
- Node* next() const { return _next.get(); }
- void next(Node* ln) { _next = ln; }
- Node* prev() const { return _prev.get(); }
+ Node* prev() const { return _prev.get(); }
void prev(Node* ln) { _prev = ln; }
- T& elem() { return _elem;}
- const T& elem() const { return _elem; }
+ Node* next() const { return _next.get(); }
+ void next(Node* ln) { _next = ln; }
+
+ T& elem() { return _elem;}
+ const T& elem() const { return _elem; }
private:
- T _elem;
- AtomicPtr<Node> _next;
+ T _elem;
AtomicPtr<Node> _prev;
+ AtomicPtr<Node> _next;
};
// List
- List() : _size(0), _end_iter(this), _const_end_iter(this)
+ List()
+ : _size(0), _end_iter(this), _const_end_iter(this)
{
_end_iter._listnode = NULL;
_const_end_iter._listnode = NULL;
}
+
~List();
void push_back(Node* elem); // realtime safe
@@ -97,6 +105,7 @@ public:
: _list(i._list), _listnode(i._listnode) {}
inline const T& operator*();
+ inline const T* operator->();
inline const_iterator& operator++();
inline bool operator!=(const const_iterator& iter) const;
inline bool operator!=(const iterator& iter) const;
@@ -118,6 +127,7 @@ public:
iterator(List<T>* const list);
inline T& operator*();
+ inline T* operator->();
inline iterator& operator++();
inline bool operator!=(const iterator& iter) const;
inline bool operator!=(const const_iterator& iter) const;
@@ -152,394 +162,8 @@ private:
};
-
-
-template <typename T>
-List<T>::~List<T>()
-{
- clear();
-}
-
-
-/** Clear the list, deleting all Nodes contained (but NOT their contents!)
- *
- * Not realtime safe.
- */
-template <typename T>
-void
-List<T>::clear()
-{
- Node* node = _head.get();
- Node* next = NULL;
-
- while (node) {
- next = node->next();
- delete node;
- node = next;
- }
-
- _head = 0;
- _tail = 0;
- _size = 0;
-}
-
-
-/** Add an element to the list.
- *
- * Thread safe (may be called while another thread is reading the list).
- * Realtime safe.
- */
-template <typename T>
-void
-List<T>::push_back(Node* const ln)
-{
- assert(ln);
-
- ln->next(NULL);
-
- if ( ! _head.get()) { // empty
- ln->prev(NULL);
- _tail = ln;
- _head = ln;
- } else {
- ln->prev(_tail.get());
- _tail.get()->next(ln);
- _tail = ln;
- }
- ++_size;
-}
-
-
-/** Add an element to the list.
- *
- * Thread safe (may be called while another thread is reading the list).
- * NOT realtime safe (a Node is allocated).
- */
-template <typename T>
-void
-List<T>::push_back(T& elem)
-{
- Node* const ln = new Node(elem);
-
- assert(ln);
-
- ln->next(NULL);
-
- if ( ! _head.get()) { // empty
- ln->prev(NULL);
- _tail = ln;
- _head = ln;
- } else {
- ln->prev(_tail.get());
- _tail.get()->next(ln);
- _tail = ln;
- }
- ++_size;
-}
-
-
-/** Append a list to this list.
- *
- * This operation is fast ( O(1) ).
- * The appended list is not safe to use concurrently with this call.
- *
- * The appended list will be empty after this call.
- *
- * Thread safe (may be called while another thread is reading the list).
- * Realtime safe.
- */
-template <typename T>
-void
-List<T>::append(List<T>& list)
-{
- Node* const my_head = _head.get();
- Node* const my_tail = _tail.get();
- Node* const other_head = list._head.get();
- Node* const other_tail = list._tail.get();
-
- // Appending to an empty list
- if (my_head == NULL && my_tail == NULL) {
- _head = other_head;
- _tail = other_tail;
- _size = list._size;
- } else if (other_head != NULL && other_tail != NULL) {
-
- other_head->prev(my_tail);
-
- // FIXME: atomicity an issue? _size < true size is probably fine...
- // no gurantee an iteration runs exactly size times though. verify/document this.
- // assuming comment above that says tail is writer only, this is fine
- my_tail->next(other_head);
- _tail = other_tail;
- _size += list.size();
- }
-
- list._head = NULL;
- list._tail = NULL;
- list._size = 0;
-}
-
-
-/** Remove all elements equal to @val from the list.
- *
- * This function is realtime safe - it is the caller's responsibility to
- * delete the returned ListNode, or there will be a leak.
- */
-#if 0
-template <typename T>
-ListNode<T>*
-List<T>::remove(const T val)
-{
- // FIXME: atomicity?
- ListNode<T>* n = _head;
- while (n) {
- if (n->elem() == elem)
- break;
- n = n->next();
- }
- if (n) {
- if (n == _head) _head = _head->next();
- if (n == _tail) _tail = _tail->prev();
- if (n->prev())
- n->prev()->next(n->next());
- if (n->next())
- n->next()->prev(n->prev());
- --_size;
-
- if (_size == 0)
- _head = _tail = NULL; // FIXME: Shouldn't be necessary
-
- return n;
- }
- return NULL;
-}
-#endif
-
-
-/** Find an element in the list.
- *
- * This will only return the first element found. If there are duplicated,
- * another call to find() will return the next, etc.
- */
-template <typename T>
-typename List<T>::iterator
-List<T>::find(const T& val)
-{
- for (iterator i = begin(); i != end(); ++i)
- if (*i == val)
- return i;
-
- return end();
-}
-
-
-/** Remove an element from the list using an iterator.
- *
- * This function is realtime safe - it is the caller's responsibility to
- * delete the returned Node, or there will be a leak.
- * Thread safe (safe to call while another thread reads the list).
- * @a iter is invalid immediately following this call.
- */
-template <typename T>
-typename List<T>::Node*
-List<T>::erase(const iterator iter)
-{
- Node* const n = iter._listnode;
-
- if (n) {
-
- Node* const prev = n->prev();
- Node* const next = n->next();
-
- // Removing the head (or the only element)
- if (n == _head.get())
- _head = next;
-
- // Removing the tail (or the only element)
- if (n == _tail.get())
- _tail = _tail.get()->prev();
-
- if (prev)
- n->prev()->next(next);
-
- if (next)
- n->next()->prev(prev);
-
- --_size;
- }
-
- return n;
-}
-
-
-//// Iterator stuff ////
-
-template <typename T>
-List<T>::iterator::iterator(List<T>* list)
-: _list(list),
- _listnode(NULL)
-{
-}
-
-
-template <typename T>
-T&
-List<T>::iterator::operator*()
-{
- assert(_listnode);
- return _listnode->elem();
-}
-
-
-template <typename T>
-inline typename List<T>::iterator&
-List<T>::iterator::operator++()
-{
- assert(_listnode);
- _listnode = _listnode->next();
-
- return *this;
-}
-
-
-template <typename T>
-inline bool
-List<T>::iterator::operator!=(const iterator& iter) const
-{
- return (_listnode != iter._listnode);
-}
-
-
-template <typename T>
-inline bool
-List<T>::iterator::operator!=(const const_iterator& iter) const
-{
- return (_listnode != iter._listnode);
-}
-
-
-template <typename T>
-inline bool
-List<T>::iterator::operator==(const iterator& iter) const
-{
- return (_listnode == iter._listnode);
-}
-
-
-template <typename T>
-inline bool
-List<T>::iterator::operator==(const const_iterator& iter) const
-{
- return (_listnode == iter._listnode);
-}
-
-
-template <typename T>
-inline typename List<T>::iterator
-List<T>::begin()
-{
- typename List<T>::iterator iter(this);
-
- iter._listnode = _head.get();
-
- return iter;
-}
-
-
-template <typename T>
-inline const typename List<T>::iterator
-List<T>::end() const
-{
- return _end_iter;
-}
-
-
-
-/// const_iterator stuff ///
-
-
-template <typename T>
-List<T>::const_iterator::const_iterator(const List<T>* const list)
-: _list(list),
- _listnode(NULL)
-{
-}
-
-
-template <typename T>
-const T&
-List<T>::const_iterator::operator*()
-{
- assert(_listnode);
- return _listnode->elem();
-}
-
-
-template <typename T>
-inline typename List<T>::const_iterator&
-List<T>::const_iterator::operator++()
-{
- assert(_listnode);
- _listnode = _listnode->next();
-
- return *this;
-}
-
-
-template <typename T>
-inline bool
-List<T>::const_iterator::operator!=(const const_iterator& iter) const
-{
- return (_listnode != iter._listnode);
-}
-
-
-template <typename T>
-inline bool
-List<T>::const_iterator::operator!=(const iterator& iter) const
-{
- return (_listnode != iter._listnode);
-}
-
-
-template <typename T>
-inline bool
-List<T>::const_iterator::operator==(const const_iterator& iter) const
-{
- return (_listnode == iter._listnode);
-}
-
-
-template <typename T>
-inline bool
-List<T>::const_iterator::operator==(const iterator& iter) const
-{
- return (_listnode == iter._listnode);
-}
-
-template <typename T>
-inline typename List<T>::const_iterator
-List<T>::begin() const
-{
- typename List<T>::const_iterator iter(this);
- iter._listnode = _head.get();
- return iter;
-}
-
-#if 0
-template <typename T>
-inline typename List<T>::const_iterator
-List<T>::end() const
-{
- /*typename List<T>::const_iterator iter(this);
- iter._listnode = NULL;
- iter._next = NULL;
- return iter;*/
- return _const_end_iter;
-}
-#endif
-
-
} // namespace Raul
+#include "ListImpl.hpp"
+
#endif // RAUL_LIST_HPP
generated by cgit v1.2.1 (git 2.18.0) at 2025-02-02 00:32:21 +0000