From e343345cf54172720f3494ccef87d62b2c688d0a 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/ingen@294 a436a847-0d15-0410-975c-d299462d15a1 --- src/libs/engine/List.h | 409 ------------------------------------------------- 1 file changed, 409 deletions(-) delete mode 100644 src/libs/engine/List.h (limited to 'src/libs/engine/List.h') diff --git a/src/libs/engine/List.h b/src/libs/engine/List.h deleted file mode 100644 index a051b037..00000000 --- a/src/libs/engine/List.h +++ /dev/null @@ -1,409 +0,0 @@ -/* This file is part of Ingen. - * Copyright (C) 2007 Dave Robillard - * - * Ingen 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. - * - * Ingen 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 LIST_H -#define LIST_H - -#include -#include "types.h" -#include "MaidObject.h" - - -/** A node in a List. - * - * This class is (unusually) exposed to the user to allow list operations - * to be realtime safe (ie so events can allocate list nodes in other threads - * and then insert them in the realtime thread. - */ -template -class ListNode : public MaidObject -{ -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 MaidObject -{ -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 == NULL) return; - - ListNode* node = _head; - ListNode* next = NULL; - - while (node != NULL) { - next = node->next(); - delete node; - node = next; - } - _tail = _head = NULL; - _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 != NULL); - - ln->next(NULL); - // FIXME: atomicity? relevant? - if (_head == NULL) { - 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 != NULL) { - if (n->elem() == elem) - break; - n = n->next(); - } - if (n != NULL) { - if (n == _head) _head = _head->next(); - if (n == _tail) _tail = _tail->prev(); - if (n->prev() != NULL) - n->prev()->next(n->next()); - if (n->next() != NULL) - 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 != NULL) { - if (n == _head) _head = _head->next(); - if (n == _tail) _tail = _tail->prev(); - if (n->prev() != NULL) - n->prev()->next(n->next()); - if (n->next() != NULL) - 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 != NULL); - return _listnode->elem(); -} - - -template -inline typename List::iterator& -List::iterator::operator++() -{ - assert(_listnode != NULL); - _listnode = _next; - if (_next != NULL) - _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 != NULL) - 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 != NULL); - return _listnode->elem(); -} - - -template -inline typename List::const_iterator& -List::const_iterator::operator++() -{ - assert(_listnode != NULL); - _listnode = _next; - if (_next != NULL) - _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 != NULL) - 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 - -#endif // LIST_H -- cgit v1.2.1