From 98fe0e7056e6697396249531785d3899f94d79be Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sat, 10 Jun 2006 01:52:02 +0000 Subject: More juggling git-svn-id: http://svn.drobilla.net/lad/grauph@15 a436a847-0d15-0410-975c-d299462d15a1 --- src/engine/List.h | 416 ------------------------------------------------------ 1 file changed, 416 deletions(-) delete mode 100644 src/engine/List.h (limited to 'src/engine/List.h') diff --git a/src/engine/List.h b/src/engine/List.h deleted file mode 100644 index cc51bc5d..00000000 --- a/src/engine/List.h +++ /dev/null @@ -1,416 +0,0 @@ -/* This file is part of Om. Copyright (C) 2006 Dave Robillard. - * - * Om 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. - * - * Om 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., - * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#ifndef LIST_H -#define LIST_H - -#include -#include "util/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) : m_elem(elem), m_next(NULL), m_prev(NULL) {} - virtual ~ListNode() {} - - ListNode* next() const { return m_next; } - void next(ListNode* ln) { m_next = ln; } - ListNode* prev() const { return m_prev; } - void prev(ListNode* ln) { m_prev = ln; } - T& elem() { return m_elem;} - const T& elem() const { return m_elem; } - -private: - // Prevent copies (undefined) - ListNode(const ListNode& copy); - ListNode& operator=(const ListNode& copy); - - T m_elem; - ListNode* m_next; - ListNode* m_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() : m_head(NULL), m_tail(NULL), m_size(0), m_end_iter(this), m_const_end_iter(this) - { - m_end_iter.m_listnode = NULL; - m_end_iter.m_next = NULL; - m_const_end_iter.m_listnode = NULL; - m_const_end_iter.m_next = NULL; - } - ~List(); - - void push_back(ListNode* elem); - ListNode* remove(const T elem); - - void clear(); - size_t size() const { return m_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) - : m_list(i.m_list), m_listnode(i.m_listnode), m_next(i.m_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 m_list; - const ListNode* m_listnode; - const ListNode* m_next; // use this instead of m_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* m_list; - ListNode* m_listnode; - ListNode* m_next; // use this instead of m_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: - // Prevent copies (undefined) - List(const List& copy); - List& operator=(const List& copy); - - ListNode* m_head; - ListNode* m_tail; - size_t m_size; - iterator m_end_iter; - const_iterator m_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 (m_head == NULL) return; - - ListNode* node = m_head; - ListNode* next = NULL; - - while (node != NULL) { - next = node->next(); - delete node; - node = next; - } - m_tail = m_head = NULL; - m_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 (m_head == NULL) { - ln->prev(NULL); - m_head = m_tail = ln; - } else { - ln->prev(m_tail); - m_tail->next(ln); - m_tail = ln; - } - ++m_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 = m_head; - while (n != NULL) { - if (n->elem() == elem) - break; - n = n->next(); - } - if (n != NULL) { - if (n == m_head) m_head = m_head->next(); - if (n == m_tail) m_tail = m_tail->prev(); - if (n->prev() != NULL) - n->prev()->next(n->next()); - if (n->next() != NULL) - n->next()->prev(n->prev()); - --m_size; - if (m_size == 0) m_head = m_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.m_listnode; - if (n != NULL) { - if (n == m_head) m_head = m_head->next(); - if (n == m_tail) m_tail = m_tail->prev(); - if (n->prev() != NULL) - n->prev()->next(n->next()); - if (n->next() != NULL) - n->next()->prev(n->prev()); - --m_size; - if (m_size == 0) m_head = m_tail = NULL; // FIXME: Shouldn't be necessary - return n; - } - return NULL; -} - - -//// Iterator stuff //// - -template -List::iterator::iterator(List* list) -: m_list(list), - m_listnode(NULL), - m_next(NULL) -{ -} - - -template -T& -List::iterator::operator*() -{ - assert(m_listnode != NULL); - return m_listnode->elem(); -} - - -template -inline typename List::iterator& -List::iterator::operator++() -{ - assert(m_listnode != NULL); - m_listnode = m_next; - if (m_next != NULL) - m_next = m_next->next(); - else - m_next = NULL; - - return *this; -} - - -template -inline bool -List::iterator::operator!=(const iterator& iter) const -{ - return (m_listnode != iter.m_listnode); -} - - -template -inline bool -List::iterator::operator!=(const const_iterator& iter) const -{ - return (m_listnode != iter.m_listnode); -} - - -template -inline typename List::iterator -List::begin() -{ - typename List::iterator iter(this); - iter.m_listnode = m_head; - if (m_head != NULL) - iter.m_next = m_head->next(); - else - iter.m_next = NULL; - return iter; -} - - -template -inline const typename List::iterator -List::end() const -{ - /*typename List::iterator iter(this); - iter.m_listnode = NULL; - iter.m_next = NULL; - return iter;*/ - return m_end_iter; -} - - - -/// const_iterator stuff /// - - -template -List::const_iterator::const_iterator(const List* const list) -: m_list(list), - m_listnode(NULL), - m_next(NULL) -{ -} - - -template -const T& -List::const_iterator::operator*() -{ - assert(m_listnode != NULL); - return m_listnode->elem(); -} - - -template -inline typename List::const_iterator& -List::const_iterator::operator++() -{ - assert(m_listnode != NULL); - m_listnode = m_next; - if (m_next != NULL) - m_next = m_next->next(); - else - m_next = NULL; - - return *this; -} - - -template -inline bool -List::const_iterator::operator!=(const const_iterator& iter) const -{ - return (m_listnode != iter.m_listnode); -} - - -template -inline bool -List::const_iterator::operator!=(const iterator& iter) const -{ - return (m_listnode != iter.m_listnode); -} - - -template -inline typename List::const_iterator -List::begin() const -{ - typename List::const_iterator iter(this); - iter.m_listnode = m_head; - if (m_head != NULL) - iter.m_next = m_head->next(); - else - iter.m_next = NULL; - return iter; -} - -#if 0 -template -inline typename List::const_iterator -List::end() const -{ - /*typename List::const_iterator iter(this); - iter.m_listnode = NULL; - iter.m_next = NULL; - return iter;*/ - return m_const_end_iter; -} -#endif - -#endif // LIST_H -- cgit v1.2.1