From e2f96603707c75071edaea6df940751c5e2fd261 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Fri, 9 Feb 2007 22:39:56 +0000 Subject: Moved Deletable (formerly MaidObject), List, and Array from Ingen to Raul. git-svn-id: http://svn.drobilla.net/lad/raul@294 a436a847-0d15-0410-975c-d299462d15a1 --- raul/Array.h | 110 ++++++++++++++ raul/Deletable.h | 38 +++++ raul/List.h | 421 ++++++++++++++++++++++++++++++++++++++++++++++++++++ raul/Makefile.am | 5 +- tests/Makefile.am | 4 +- tests/list_test.cpp | 94 ++++++++++++ 6 files changed, 670 insertions(+), 2 deletions(-) create mode 100644 raul/Array.h create mode 100644 raul/Deletable.h create mode 100644 raul/List.h create mode 100644 tests/list_test.cpp diff --git a/raul/Array.h b/raul/Array.h new file mode 100644 index 0000000..aa6aa70 --- /dev/null +++ b/raul/Array.h @@ -0,0 +1,110 @@ +/* This file is part of Raul. + * Copyright (C) 2007 Dave Robillard + * + * Raul is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * Raul is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef RAUL_ARRAY_H +#define RAUL_ARRAY_H + +#include +#include +#include "types.h" +#include "Deletable.h" + +namespace Raul { + + +/** An array. + * + * Has a stack-like push_back() too, for find_process_order... + */ +template +class Array : public Deletable +{ +public: + Array(size_t size = 0) : _size(size), _top(0), _elems(NULL) { + if (size > 0) + _elems = new T[size]; + } + + Array(size_t size, T initial_value) : _size(size), _top(0), _elems(NULL) { + if (size > 0) { + _elems = new T[size]; + for (size_t i=0; i < size; ++i) + _elems[i] = initial_value; + } + } + + Array(size_t size, const Array& contents) : _size(size), _top(size+1) { + _elems = new T[size]; + if (size <= contents.size()) + memcpy(_elems, contents._elems, size * sizeof(T)); + else + memcpy(_elems, contents._elems, contents.size() * sizeof(T)); + } + + ~Array() { + free(); + } + + void alloc(size_t num_elems) { + assert(num_elems > 0); + + delete[] _elems; + _size = num_elems; + _top = 0; + + _elems = new T[num_elems]; + } + + void alloc(size_t num_elems, T initial_value) { + assert(num_elems > 0); + + delete[] _elems; + _size = num_elems; + _top = 0; + + _elems = new T[num_elems]; + for (size_t i=0; i < _size; ++i) + _elems[i] = initial_value; + } + + void free() { + delete[] _elems; + _size = 0; + _top = 0; + } + + void push_back(T n) { + assert(_top < _size); + _elems[_top++] = n; + } + + inline size_t size() const { return _size; } + + inline T& operator[](size_t i) const { assert(i < _size); return _elems[i]; } + + inline T& at(size_t i) const { assert(i < _size); return _elems[i]; } + +private: + size_t _size; + size_t _top; // points to empty element above "top" element + T* _elems; +}; + + +} // namespace Raul + +#endif // RAUL_ARRAY_H diff --git a/raul/Deletable.h b/raul/Deletable.h new file mode 100644 index 0000000..1e47279 --- /dev/null +++ b/raul/Deletable.h @@ -0,0 +1,38 @@ +/* This file is part of Raul. + * Copyright (C) 2007 Dave Robillard + * + * Raul is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * Raul is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef RAUL_DELETABLE_H +#define RAUL_DELETABLE_H + +namespace Raul { + + +/** Something with a virtual destructor. + * + * \ingroup raul + */ +class Deletable +{ +public: + Deletable() {} + virtual ~Deletable() {} +}; + + +} // namespace Raul + +#endif // RAUL_DELETABLE_H diff --git a/raul/List.h b/raul/List.h new file mode 100644 index 0000000..79dc4b2 --- /dev/null +++ b/raul/List.h @@ -0,0 +1,421 @@ +/* This file is part of Raul. + * Copyright (C) 2007 Dave Robillard + * + * Raul is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * Raul is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef RAUL_LIST_H +#define RAUL_LIST_H + +#include +#include +#include "Deletable.h" + +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), _next(NULL), _prev(NULL) {} + virtual ~ListNode() {} + + ListNode* next() const { return _next; } + void next(ListNode* ln) { _next = ln; } + ListNode* prev() const { return _prev; } + void prev(ListNode* ln) { _prev = ln; } + T& elem() { return _elem;} + const T& elem() const { return _elem; } + +private: + T _elem; + ListNode* _next; + ListNode* _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. + */ +template +class List : public Raul::Deletable +{ +public: + List() : _head(NULL), _tail(NULL), _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 clear(); + size_t size() const { return _size; } + + class iterator; + + /** Realtime safe const iterator for a List. */ + class const_iterator + { + public: + const_iterator(const List* const list); + const_iterator(const iterator& i) + : _list(i._list), _listnode(i._listnode), _next(i._next) {} + + inline const T& operator*(); + inline const_iterator& operator++(); + inline bool operator!=(const const_iterator& iter) const; + inline bool operator!=(const iterator& iter) const; + + friend class List; + + private: + const List* const _list; + const ListNode* _listnode; + const ListNode* _next; // use this instead of _listnode->next() to allow deleting + }; + + + /** Realtime safe iterator for a List. */ + class iterator + { + public: + iterator(List* const list); + + inline T& operator*(); + inline iterator& operator++(); + inline bool operator!=(const iterator& iter) const; + inline bool operator!=(const const_iterator& iter) const; + + friend class List; + 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); + + iterator begin(); + const iterator end() const; + + const_iterator begin() const; + //const_iterator end() const; + +private: + ListNode* _head; + ListNode* _tail; + size_t _size; + iterator _end_iter; + const_iterator _const_end_iter; +}; + + + + +template +List::~List() +{ + clear(); +} + + +/** Clear the list, deleting all ListNodes contained (but NOT their contents!) + * + * Not realtime safe. + */ +template +void +List::clear() +{ + if (!_head) + return; + + ListNode* node = _head; + ListNode* next = NULL; + + while (node) { + next = node->next(); + delete node; + node = next; + } + + _head = 0; + _tail = 0; + _size = 0; +} + + +/** Add an element to the list. + * + * This method can be called while another thread is reading the list. + * Realtime safe. + */ +template +void +List::push_back(ListNode* const ln) +{ + assert(ln); + + ln->next(NULL); + // FIXME: atomicity? relevant? + if (_head) { + ln->prev(NULL); + _head = _tail = ln; + } else { + ln->prev(_tail); + _tail->next(ln); + _tail = ln; + } + ++_size; +} + + +/** Remove an element 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. + */ +template +ListNode* +List::remove(const T elem) +{ + // FIXME: atomicity? + ListNode* 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; +} + + +/** 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. + */ +template +ListNode* +List::remove(const iterator iter) +{ + ListNode* 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()); + --_size; + if (_size == 0) + _head = _tail = NULL; // FIXME: Shouldn't be necessary + return n; + } + return NULL; +} + + +//// Iterator stuff //// + +template +List::iterator::iterator(List* list) +: _list(list), + _listnode(NULL), + _next(NULL) +{ +} + + +template +T& +List::iterator::operator*() +{ + assert(_listnode); + return _listnode->elem(); +} + + +template +inline typename List::iterator& +List::iterator::operator++() +{ + assert(_listnode); + _listnode = _next; + if (_next) + _next = _next->next(); + else + _next = NULL; + + return *this; +} + + +template +inline bool +List::iterator::operator!=(const iterator& iter) const +{ + return (_listnode != iter._listnode); +} + + +template +inline bool +List::iterator::operator!=(const const_iterator& iter) const +{ + return (_listnode != iter._listnode); +} + + +template +inline typename List::iterator +List::begin() +{ + typename List::iterator iter(this); + iter._listnode = _head; + if (_head) + iter._next = _head->next(); + else + iter._next = NULL; + return iter; +} + + +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; +} + + + +/// const_iterator stuff /// + + +template +List::const_iterator::const_iterator(const List* const list) +: _list(list), + _listnode(NULL), + _next(NULL) +{ +} + + +template +const T& +List::const_iterator::operator*() +{ + assert(_listnode); + return _listnode->elem(); +} + + +template +inline typename List::const_iterator& +List::const_iterator::operator++() +{ + assert(_listnode); + _listnode = _next; + if (_next) + _next = _next->next(); + else + _next = NULL; + + return *this; +} + + +template +inline bool +List::const_iterator::operator!=(const const_iterator& iter) const +{ + return (_listnode != iter._listnode); +} + + +template +inline bool +List::const_iterator::operator!=(const iterator& iter) const +{ + return (_listnode != iter._listnode); +} + + +template +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; + return iter; +} + +#if 0 +template +inline typename List::const_iterator +List::end() const +{ + /*typename List::const_iterator iter(this); + iter._listnode = NULL; + iter._next = NULL; + return iter;*/ + return _const_end_iter; +} +#endif + + +} // namespace Raul + +#endif // RAUL_LIST_H diff --git a/raul/Makefile.am b/raul/Makefile.am index a536a0e..72ab43f 100644 --- a/raul/Makefile.am +++ b/raul/Makefile.am @@ -16,7 +16,10 @@ raulinclude_HEADERS = \ JackDriver.h \ RDFQuery.h \ Namespaces.h \ - AtomicInt.h + AtomicInt.h \ + Deletable.h \ + List.h \ + Array.h if WITH_LIBLO raulinclude_HEADERS += AtomLiblo.h diff --git a/tests/Makefile.am b/tests/Makefile.am index 9fba352..9ae9810 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -3,16 +3,18 @@ if BUILD_TESTS AM_CXXFLAGS = -I.. -lpthread @RASQAL_CFLAGS@ @GLIBMM_CFLAGS@ ALL_LIBS = @RASQAL_LIBS@ @GLIBMM_LIBS@ ../src/libraul.la -bin_PROGRAMS = path_test thread_test queue_test atomic_test +bin_PROGRAMS = path_test thread_test queue_test atomic_test list_test thread_test_LDADD = $(ALL_LIBS) path_test_LDADD = $(ALL_LIBS) queue_test_LDADD = $(ALL_LIBS) atomic_test_LDADD = $(ALL_LIBS) +list_test_LDADD = $(ALL_LIBS) path_test_SOURCES = path_test.cpp thread_test_SOURCES = thread_test.cpp queue_test_SOURCES = queue_test.cpp atomic_test_SOURCES = atomic_test.cpp +list_test_SOURCES = list_test.cpp endif diff --git a/tests/list_test.cpp b/tests/list_test.cpp new file mode 100644 index 0000000..641dc5a --- /dev/null +++ b/tests/list_test.cpp @@ -0,0 +1,94 @@ +#include +#include +#include + +using namespace std; +using namespace Raul; + + +int main() +{ + List l; + + l.push_back(new ListNode(1)); + l.push_back(new ListNode(2)); + l.push_back(new ListNode(3)); + l.push_back(new ListNode(4)); + l.push_back(new ListNode(5)); + l.push_back(new ListNode(6)); + l.push_back(new ListNode(7)); + l.push_back(new ListNode(8)); + + cout << "List:" << endl; + 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) == 4) + l.remove(i); + } + + std::cerr << "Removed 4 (by iterator)...\n"; + for (List::iterator i = l.begin(); i != l.end(); ++i) { + cout << *i << endl; + } + cout << endl; + + 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); + } + + std::cerr << "Removed 2 (head) (by iterator)...\n"; + for (List::iterator i = l.begin(); i != l.end(); ++i) { + cout << *i << endl; + } + cout << endl; + + l.remove(5); + + std::cerr << "Removed 5 (by value)...\n"; + for (List::iterator i = l.begin(); i != l.end(); ++i) { + cout << *i << endl; + } + cout << endl; + + l.remove(8); + + std::cerr << "Removed 8 (tail) (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) == 7) + l.remove(i); + } + + std::cerr << "Removed 7 (tail) (by iterator)...\n"; + for (List::iterator i = l.begin(); i != l.end(); ++i) { + cout << *i << endl; + } + cout << endl; + + List r; + r.push_back(new ListNode(9)); + r.remove(9); + std::cerr << "Should not see ANY numbers:\n"; + for (List::iterator i = r.begin(); i != r.end(); ++i) { + cout << *i << endl; + } + return 0; +} -- cgit v1.2.1