From 7163b21136944ac77afc67f79a1152f389cf3fde Mon Sep 17 00:00:00 2001 From: David Robillard Date: Wed, 18 May 2011 16:12:49 +0000 Subject: Move ListImpl.hpp into List.hpp. git-svn-id: http://svn.drobilla.net/lad/trunk/raul@3280 a436a847-0d15-0410-975c-d299462d15a1 --- raul/List.hpp | 299 +++++++++++++++++++++++++++++++++++++++--- raul/ListImpl.hpp | 381 ------------------------------------------------------ 2 files changed, 280 insertions(+), 400 deletions(-) delete mode 100644 raul/ListImpl.hpp (limited to 'raul') diff --git a/raul/List.hpp b/raul/List.hpp index 38c4609..4ef23a1 100644 --- a/raul/List.hpp +++ b/raul/List.hpp @@ -101,17 +101,35 @@ public: /** Realtime safe const iterator for a List. */ class const_iterator { public: - explicit const_iterator(const List* const list); + explicit const_iterator(const List* const list) + : _list(list) + , _listnode(NULL) + {} + const_iterator(const iterator& i) - : _list(i._list), _listnode(i._listnode) {} + : _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; - inline bool operator==(const const_iterator& iter) const; - inline bool operator==(const iterator& iter) const; + inline const T& operator*() { return _listnode->elem(); } + inline const T* operator->() { return &_listnode->elem(); } + inline const_iterator& operator++() { + _listnode = _listnode->next(); + return *this; + } + + inline bool operator!=(const const_iterator& iter) const { + return (_listnode != iter._listnode); + } + inline bool operator!=(const iterator& iter) const { + return (_listnode != iter._listnode); + } + inline bool operator==(const const_iterator& iter) const { + return (_listnode == iter._listnode); + } + inline bool operator==(const iterator& iter) const { + return (_listnode == iter._listnode); + } inline typename List::Node* node() { return _listnode; } inline const typename List::Node* node() const { return _listnode; } @@ -126,15 +144,30 @@ public: /** Realtime safe iterator for a List. */ class iterator { public: - explicit iterator(List* const list); + explicit iterator(List* const list) + : _list(list) + , _listnode(NULL) + {} - inline T& operator*(); - inline T* operator->(); - inline iterator& operator++(); - inline bool operator!=(const iterator& iter) const; - inline bool operator!=(const const_iterator& iter) const; - inline bool operator==(const iterator& iter) const; - inline bool operator==(const const_iterator& iter) const; + inline T& operator*() { return _listnode->elem(); } + inline T* operator->() { return &_listnode->elem(); } + inline iterator& operator++() { + _listnode = _listnode->next(); + return *this; + } + + inline bool operator!=(const const_iterator& iter) const { + return (_listnode != iter._listnode); + } + inline bool operator!=(const iterator& iter) const { + return (_listnode != iter._listnode); + } + inline bool operator==(const const_iterator& iter) const { + return (_listnode == iter._listnode); + } + inline bool operator==(const iterator& iter) const { + return (_listnode == iter._listnode); + } friend class List; friend class List::const_iterator; @@ -168,9 +201,237 @@ private: const_iterator _const_end_iter; }; +template +List::~List() +{ + clear(); +} + +template +inline typename List::iterator +List::begin() +{ + typename List::iterator iter(this); + + iter._listnode = _head.get(); + + return iter; +} + +template +inline typename List::const_iterator +List::begin() const +{ + typename List::const_iterator iter(this); + iter._listnode = _head.get(); + return iter; +} + +template +inline const typename List::iterator +List::end() const +{ + return _end_iter; +} + +/** Clear the list, deleting all Nodes contained (but NOT their contents!) + * + * Not realtime safe. + */ +template +void +List::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 +void +List::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 +void +List::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 +void +List::append(List& 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(); + + assert((my_head && my_tail) || (!my_head && !my_tail)); + assert((other_head && other_tail) || (!other_head && !other_tail)); + + // Appending to an empty list + if (my_head == NULL && my_tail == NULL) { + _tail = other_tail; + _head = other_head; + _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 guarantee 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; +} + +/** Find an element in the list. + * + * This will return the first element equal to @a val found in the list. + */ +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 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 List::Node* +List::erase(const iterator iter) +{ + assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get())); + + 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; + } + + assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get())); + return n; +} + +template +void +List::chop_front(List& front, size_t front_size, Node* front_tail) +{ + assert(front_tail); + assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get())); + assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get())); + front._size = front_size; + front._head = _head; + front._tail = front_tail; + Node* new_head = front_tail->next(); + if (new_head) { + new_head->prev(NULL); + _head = new_head; + } else { + // FIXME: race? + _head = NULL; + _tail = NULL; + } + _size -= front_size; + front_tail->next(NULL); + assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get())); + assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get())); +} + } // namespace Raul #endif // RAUL_LIST_HPP -#include "ListImpl.hpp" - diff --git a/raul/ListImpl.hpp b/raul/ListImpl.hpp deleted file mode 100644 index c5f9fd3..0000000 --- a/raul/ListImpl.hpp +++ /dev/null @@ -1,381 +0,0 @@ -/* This file is part of Raul. - * Copyright 2007-2011 David 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_IMPL_HPP -#define RAUL_LIST_IMPL_HPP - -namespace Raul { - -template -List::~List() -{ - clear(); -} - -/** Clear the list, deleting all Nodes contained (but NOT their contents!) - * - * Not realtime safe. - */ -template -void -List::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 -void -List::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 -void -List::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 -void -List::append(List& 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(); - - assert((my_head && my_tail) || (!my_head && !my_tail)); - assert((other_head && other_tail) || (!other_head && !other_tail)); - - // Appending to an empty list - if (my_head == NULL && my_tail == NULL) { - _tail = other_tail; - _head = other_head; - _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 guarantee 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; -} - -/** Find an element in the list. - * - * This will return the first element equal to @a val found in the list. - */ -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 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 List::Node* -List::erase(const iterator iter) -{ - assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get())); - - 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; - } - - assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get())); - return n; -} - -template -void -List::chop_front(List& front, size_t front_size, Node* front_tail) -{ - assert(front_tail); - assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get())); - assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get())); - front._size = front_size; - front._head = _head; - front._tail = front_tail; - Node* new_head = front_tail->next(); - if (new_head) { - new_head->prev(NULL); - _head = new_head; - } else { - // FIXME: race? - _head = NULL; - _tail = NULL; - } - _size -= front_size; - front_tail->next(NULL); - assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get())); - assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get())); -} - -//// Iterator stuff //// - -template -List::iterator::iterator(List* list) -: _list(list), - _listnode(NULL) -{ -} - -template -T& -List::iterator::operator*() -{ - assert(_listnode); - return _listnode->elem(); -} - -template -T* -List::iterator::operator->() -{ - assert(_listnode); - return &_listnode->elem(); -} - -template -inline typename List::iterator& -List::iterator::operator++() -{ - assert(_listnode); - _listnode = _listnode->next(); - - 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 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.get(); - - return iter; -} - -template -inline const typename List::iterator -List::end() const -{ - return _end_iter; -} - -/// const_iterator stuff /// - -template -List::const_iterator::const_iterator(const List* const list) -: _list(list), - _listnode(NULL) -{ -} - -template -const T& -List::const_iterator::operator*() -{ - assert(_listnode); - return _listnode->elem(); -} - -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 = _listnode->next(); - - 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 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.get(); - return iter; -} - -} // namespace Raul - -#endif // RAUL_LIST_IMPL_HPP -- cgit v1.2.1