From d9269cb513631751e951c07b32b41a496de0a493 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Mon, 8 Oct 2007 04:21:18 +0000 Subject: Fixed missing symbol in Raul. Made Raul::List interface and uses thereof less fugly. git-svn-id: http://svn.drobilla.net/lad/raul@845 a436a847-0d15-0410-975c-d299462d15a1 --- raul/List.hpp | 111 +++++++++++++++++++++++++++-------------------------- raul/Table.hpp | 2 +- raul/TableImpl.hpp | 13 ++++++- 3 files changed, 68 insertions(+), 58 deletions(-) (limited to 'raul') diff --git a/raul/List.hpp b/raul/List.hpp index d3f4707..a090251 100644 --- a/raul/List.hpp +++ b/raul/List.hpp @@ -27,34 +27,6 @@ namespace Raul { -/** A node in a List. - * - * This is exposed so the user can allocate ListNodes in different thread - * than the list reader, and insert (e.g. via an Event) it later in the - * reader thread. - */ -template -class ListNode : public Raul::Deletable -{ -public: - ListNode(T elem) : _elem(elem) {} - virtual ~ListNode() {} - - ListNode* next() const { return _next.get(); } - void next(ListNode* ln) { _next = ln; } - 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; - 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. @@ -65,6 +37,35 @@ template class List : public Raul::Deletable { public: + + /** A node in a List. + * + * This is exposed so the user can allocate Nodes in different thread + * than the list reader, and insert (e.g. via an Event) it later in the + * reader thread. + */ + class Node : public Raul::Deletable + { + public: + Node(T elem) : _elem(elem) {} + virtual ~Node() {} + + Node* next() const { return _next.get(); } + void next(Node* ln) { _next = ln; } + Node* prev() const { return _prev.get(); } + void prev(Node* ln) { _prev = ln; } + T& elem() { return _elem;} + const T& elem() const { return _elem; } + + private: + T _elem; + AtomicPtr _next; + AtomicPtr _prev; + }; + + + // List + List() : _size(0), _end_iter(this), _const_end_iter(this) { _end_iter._listnode = NULL; @@ -72,8 +73,8 @@ public: } ~List(); - void push_back(ListNode* elem); // realtime safe - void push_back(T& elem); // NOT realtime safe + void push_back(Node* elem); // realtime safe + void push_back(T& elem); // NOT realtime safe void append(List& list); @@ -105,8 +106,8 @@ public: friend class List; private: - const List* const _list; - const ListNode* _listnode; + const List* const _list; + const typename List::Node* _listnode; }; @@ -127,12 +128,12 @@ public: friend class List::const_iterator; private: - const List* _list; - ListNode* _listnode; + const List* _list; + typename List::Node* _listnode; }; - ListNode* erase(const iterator iter); + Node* erase(const iterator iter); iterator find(const T& val); @@ -143,11 +144,11 @@ public: //const_iterator end() const; private: - AtomicPtr > _head; - AtomicPtr > _tail; ///< writer only - AtomicInt _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; }; @@ -160,7 +161,7 @@ List::~List() } -/** Clear the list, deleting all ListNodes contained (but NOT their contents!) +/** Clear the list, deleting all Nodes contained (but NOT their contents!) * * Not realtime safe. */ @@ -168,8 +169,8 @@ template void List::clear() { - ListNode* node = _head.get(); - ListNode* next = NULL; + Node* node = _head.get(); + Node* next = NULL; while (node) { next = node->next(); @@ -190,7 +191,7 @@ List::clear() */ template void -List::push_back(ListNode* const ln) +List::push_back(Node* const ln) { assert(ln); @@ -212,13 +213,13 @@ List::push_back(ListNode* const ln) /** 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). + * NOT realtime safe (a Node is allocated). */ template void List::push_back(T& elem) { - ListNode* const ln = new ListNode(elem); + Node* const ln = new Node(elem); assert(ln); @@ -251,10 +252,10 @@ template void List::append(List& list) { - ListNode* const my_head = _head.get(); - ListNode* const my_tail = _tail.get(); - ListNode* const other_head = list._head.get(); - ListNode* const other_tail = list._tail.get(); + 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) { @@ -335,20 +336,20 @@ List::find(const T& val) /** 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. + * 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 -ListNode* +typename List::Node* List::erase(const iterator iter) { - ListNode* const n = iter._listnode; + Node* const n = iter._listnode; if (n) { - ListNode* const prev = n->prev(); - ListNode* const next = n->next(); + Node* const prev = n->prev(); + Node* const next = n->next(); // Removing the head (or the only element) if (n == _head.get()) diff --git a/raul/Table.hpp b/raul/Table.hpp index fa3848c..a7f7c39 100644 --- a/raul/Table.hpp +++ b/raul/Table.hpp @@ -89,7 +89,7 @@ public: const_iterator find(const_iterator start, const_iterator end, const K& key) const; const_iterator find(const K& key) const; - iterator find(iterator start, iterator end, const K& key); + iterator find(const_iterator start, const_iterator end, const K& key); iterator find(const K& key); const_iterator find_range_end(const_iterator left, bool (*comp)(const K&,const K&)) const; diff --git a/raul/TableImpl.hpp b/raul/TableImpl.hpp index d01c0ca..4ccf7f3 100644 --- a/raul/TableImpl.hpp +++ b/raul/TableImpl.hpp @@ -66,14 +66,23 @@ template typename Table::iterator Table::find(const K& key) { - return find(begin(), end(), key); + return find(begin(), end(), key); +} + + +/** Binary search (O(log(end - start))) */ +template +typename Table::const_iterator +Table::find(const_iterator start, const_iterator finish, const K& key) const +{ + return ((Table*)this)->find(start, finish, key); } /** Binary search (O(log(end - start))) */ template typename Table::iterator -Table::find(iterator start, iterator finish, const K& key) +Table::find(const_iterator start, const_iterator finish, const K& key) { if (size() == 0) return end(); -- cgit v1.2.1