From 8140170f4b3fe308f346712a4bc93cdeecf55e8c Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sat, 10 Feb 2007 01:11:44 +0000 Subject: Made Raul::List read/write thread safe. Uh.. kinda, a bit. :) Reorganized machina into libraries. git-svn-id: http://svn.drobilla.net/lad/raul@295 a436a847-0d15-0410-975c-d299462d15a1 --- raul/AtomicPtr.h | 3 + raul/List.h | 191 +++++++++++++++++++++++++++++++--------------------- tests/list_test.cpp | 29 +++++--- 3 files changed, 136 insertions(+), 87 deletions(-) diff --git a/raul/AtomicPtr.h b/raul/AtomicPtr.h index c70dd39..bc24f59 100644 --- a/raul/AtomicPtr.h +++ b/raul/AtomicPtr.h @@ -27,6 +27,9 @@ template class AtomicPtr { public: + inline AtomicPtr() + { g_atomic_pointer_set(&_val, NULL); } + inline AtomicPtr(const AtomicPtr& copy) { g_atomic_pointer_set(&_val, copy.get()); } diff --git a/raul/List.h b/raul/List.h index 79dc4b2..4d12a63 100644 --- a/raul/List.h +++ b/raul/List.h @@ -21,6 +21,8 @@ #include #include #include "Deletable.h" +#include "AtomicPtr.h" +#include "AtomicInt.h" namespace Raul { @@ -35,44 +37,43 @@ template class ListNode : public Raul::Deletable { public: - ListNode(T elem) : _elem(elem), _next(NULL), _prev(NULL) {} + ListNode(T elem) : _elem(elem) {} virtual ~ListNode() {} - ListNode* next() const { return _next; } + ListNode* next() const { return _next.get(); } void next(ListNode* ln) { _next = ln; } - ListNode* prev() const { return _prev; } + ListNode* prev() const { return _prev.get(); } void prev(ListNode* ln) { _prev = ln; } T& elem() { return _elem;} const T& elem() const { return _elem; } private: - T _elem; - ListNode* _next; - ListNode* _prev; + T _elem; + AtomicPtr _next; + AtomicPtr _prev; }; /** A realtime safe, (partially) thread safe doubly linked list. * - * Elements can be added safely while another thread is reading the list. See - * documentation for specific functions for realtime/thread safeness. + * Elements can be added safely while another thread is reading the list. + * Like a typical ringbuffer, this is single-reader single-writer threadsafe + * only. See documentation for specific functions for specifics. */ template class List : public Raul::Deletable { public: - List() : _head(NULL), _tail(NULL), _size(0), _end_iter(this), _const_end_iter(this) + List() : _size(0), _end_iter(this), _const_end_iter(this) { _end_iter._listnode = NULL; - _end_iter._next = NULL; _const_end_iter._listnode = NULL; - _const_end_iter._next = NULL; } ~List(); - void push_back(ListNode* elem); - ListNode* remove(const T elem); + void push_back(ListNode* elem); // realtime safe + void push_back(T& elem); // NOT realtime safe void clear(); size_t size() const { return _size; } @@ -85,7 +86,7 @@ public: public: const_iterator(const List* const list); const_iterator(const iterator& i) - : _list(i._list), _listnode(i._listnode), _next(i._next) {} + : _list(i._list), _listnode(i._listnode) {} inline const T& operator*(); inline const_iterator& operator++(); @@ -97,7 +98,6 @@ public: private: const List* const _list; const ListNode* _listnode; - const ListNode* _next; // use this instead of _listnode->next() to allow deleting }; @@ -113,16 +113,17 @@ public: inline bool operator!=(const const_iterator& iter) const; friend class List; - friend class List::const_iterator; + //friend class List::const_iterator; private: const List* _list; ListNode* _listnode; - ListNode* _next; // use this instead of _listnode->next() to allow deleting }; - ListNode* remove(const iterator iter); + ListNode* erase(const iterator iter); + + iterator find(const T& val); iterator begin(); const iterator end() const; @@ -131,11 +132,11 @@ public: //const_iterator end() const; private: - ListNode* _head; - ListNode* _tail; - size_t _size; - iterator _end_iter; - const_iterator _const_end_iter; + AtomicPtr > _head; + AtomicPtr > _tail; ///< writer only + AtomicInt _size; + iterator _end_iter; + const_iterator _const_end_iter; }; @@ -156,12 +157,9 @@ template void List::clear() { - if (!_head) - return; - - ListNode* node = _head; + ListNode* node = _head.get(); ListNode* next = NULL; - + while (node) { next = node->next(); delete node; @@ -176,7 +174,7 @@ List::clear() /** Add an element to the list. * - * This method can be called while another thread is reading the list. + * Thread safe (may be called while another thread is reading the list). * Realtime safe. */ template @@ -186,27 +184,57 @@ List::push_back(ListNode* const ln) assert(ln); ln->next(NULL); - // FIXME: atomicity? relevant? - if (_head) { + + 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 ListNode is allocated). + */ +template +void +List::push_back(T& elem) +{ + ListNode* const ln = new ListNode(elem); + + assert(ln); + + ln->next(NULL); + + if ( ! _head.get()) { // empty ln->prev(NULL); - _head = _tail = ln; + _tail = ln; + _head = ln; } else { - ln->prev(_tail); - _tail->next(ln); + ln->prev(_tail.get()); + _tail.get()->next(ln); _tail = ln; } ++_size; } -/** Remove an element from the list. +/** 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 ListNode* -List::remove(const T elem) +List::remove(const T val) { // FIXME: atomicity? ListNode* n = _head; @@ -231,31 +259,62 @@ List::remove(const T elem) } 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 List::iterator +List::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 ListNode, or there will be a leak. + * Thread safe (safe to call while another thread reads the list). + * @iter is invalid immediately following this call. */ template ListNode* -List::remove(const iterator iter) +List::erase(const iterator iter) { - ListNode* n = iter._listnode; + ListNode* const n = iter._listnode; + 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()); + + ListNode* const prev = n->prev(); + ListNode* 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; - if (_size == 0) - _head = _tail = NULL; // FIXME: Shouldn't be necessary - return n; } - return NULL; + + return n; } @@ -264,8 +323,7 @@ List::remove(const iterator iter) template List::iterator::iterator(List* list) : _list(list), - _listnode(NULL), - _next(NULL) + _listnode(NULL) { } @@ -284,11 +342,7 @@ inline typename List::iterator& List::iterator::operator++() { assert(_listnode); - _listnode = _next; - if (_next) - _next = _next->next(); - else - _next = NULL; + _listnode = _listnode->next(); return *this; } @@ -315,11 +369,9 @@ inline typename List::iterator List::begin() { typename List::iterator iter(this); - iter._listnode = _head; - if (_head) - iter._next = _head->next(); - else - iter._next = NULL; + + iter._listnode = _head.get(); + return iter; } @@ -328,10 +380,6 @@ template inline const typename List::iterator List::end() const { - /*typename List::iterator iter(this); - iter._listnode = NULL; - iter._next = NULL; - return iter;*/ return _end_iter; } @@ -343,8 +391,7 @@ List::end() const template List::const_iterator::const_iterator(const List* const list) : _list(list), - _listnode(NULL), - _next(NULL) + _listnode(NULL) { } @@ -363,11 +410,7 @@ inline typename List::const_iterator& List::const_iterator::operator++() { assert(_listnode); - _listnode = _next; - if (_next) - _next = _next->next(); - else - _next = NULL; + _listnode = _listnode->next(); return *this; } @@ -394,11 +437,7 @@ inline typename List::const_iterator List::begin() const { typename List::const_iterator iter(this); - iter._listnode = _head; - if (_head) - iter._next = _head->next(); - else - iter._next = NULL; + iter._listnode = _head.get(); return iter; } diff --git a/tests/list_test.cpp b/tests/list_test.cpp index 641dc5a..faee491 100644 --- a/tests/list_test.cpp +++ b/tests/list_test.cpp @@ -27,8 +27,10 @@ int main() for (List::iterator i = l.begin(); i != l.end(); ++i) { - if ((*i) == 4) - l.remove(i); + if ((*i) == 4) { + l.erase(i); + break; + } } std::cerr << "Removed 4 (by iterator)...\n"; @@ -37,17 +39,20 @@ int main() } cout << endl; - l.remove(1); + /*l.remove(1); std::cerr << "Removed 1 (head) (by value)...\n"; for (List::iterator i = l.begin(); i != l.end(); ++i) { cout << *i << endl; } cout << endl; - + */ + for (List::iterator i = l.begin(); i != l.end(); ++i) { - if ((*i) == 2) - l.remove(i); + if ((*i) == 2) { + l.erase(i); + break; + } } std::cerr << "Removed 2 (head) (by iterator)...\n"; @@ -56,7 +61,7 @@ int main() } cout << endl; - l.remove(5); + /*l.remove(5); std::cerr << "Removed 5 (by value)...\n"; for (List::iterator i = l.begin(); i != l.end(); ++i) { @@ -71,10 +76,12 @@ int main() cout << *i << endl; } cout << endl; - + */ for (List::iterator i = l.begin(); i != l.end(); ++i) { - if ((*i) == 7) - l.remove(i); + if ((*i) == 7) { + l.erase(i); + break; + } } std::cerr << "Removed 7 (tail) (by iterator)...\n"; @@ -85,7 +92,7 @@ int main() List r; r.push_back(new ListNode(9)); - r.remove(9); + r.erase(r.begin()); std::cerr << "Should not see ANY numbers:\n"; for (List::iterator i = r.begin(); i != r.end(); ++i) { cout << *i << endl; -- cgit v1.2.1