src/common/Pool.h

/***************************************************************************
 *                                                                         *
 *   LinuxSampler - modular, streaming capable sampler                     *
 *                                                                         *
 *   Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck   *
 *   Copyright (C) 2005 Christian Schoenebeck                              *
 *                                                                         *
 *   This program 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.                                   *
 *                                                                         *
 *   This program 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 more 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 __LS_POOL_H__
#define __LS_POOL_H__

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif

// we just use exceptions for debugging, better not in the final realtime thread !
#ifndef CONFIG_RT_EXCEPTIONS
# define CONFIG_RT_EXCEPTIONS 0
#endif

#if CONFIG_RT_EXCEPTIONS
# include <stdexcept>
# include <string>
#endif // CONFIG_RT_EXCEPTIONS

#if CONFIG_DEVMODE
# include <string>
# include <iostream>
const std::string __err_msg_iterator_invalidated = "Pool/RTList iterator invalidated";
#endif // CONFIG_DEVMODE

// just symbol prototyping
template<typename T> class Pool;
template<typename T> class RTList;

template<typename T>
class RTListBase {
    protected:
        template<typename T1>
        struct _Node {
            _Node<T1>* next;
            _Node<T1>* prev;
            T1* data;
            #if CONFIG_DEVMODE
            RTListBase<T1>* list; // list to which this node currently belongs to
            #endif // CONFIG_DEVMODE

            _Node() {
                next = NULL;
                prev = NULL;
                data = NULL;
                #if CONFIG_DEVMODE
                list = NULL;
                #endif // CONFIG_DEVMODE
            }
        };
        typedef _Node<T> Node;

    public:
        template<typename T1>
        class _Iterator {
            public:
                _Iterator() {
                    current  = NULL;
                    fallback = NULL;
                    #if CONFIG_DEVMODE
                    list = NULL;
                    #endif // CONFIG_DEVMODE
                }

                /// prefix increment op.
                inline _Iterator& operator++() {
                    #if CONFIG_DEVMODE
                    if (!isValid()) {
                        #if CONFIG_RT_EXCEPTIONS
                        throw std::runtime_error(__err_msg_iterator_invalidated);
                        #else
                        std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
                        return *(_Iterator*)NULL; // force segfault if iterator became invalidated
                        #endif // CONFIG_RT_EXCEPTIONS
                    }
                    #endif // CONFIG_DEVMODE
                    fallback = current;
                    current  = current->next;
                    return *this;
                }

                /// postfix increment op.
                inline _Iterator operator++(int) {
                    _Iterator preval = *this;
                    ++*this; // use prefix operator implementation
                    return preval;
                }

                /// prefix decrement op.
                inline _Iterator& operator--() {
                    #if CONFIG_DEVMODE
                    if (!isValid()) {
                        #if CONFIG_RT_EXCEPTIONS
                        throw std::runtime_error(__err_msg_iterator_invalidated);
                        #else
                        std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
                        return *(_Iterator*)NULL; // force segfault if iterator became invalidated
                        #endif // CONFIG_RT_EXCEPTIONS
                    }
                    #endif // CONFIG_DEVMODE
                    fallback = current;
                    current  = current->prev;
                    return *this;
                }

                /// postfix decrement op.
                inline _Iterator operator--(int) {
                    _Iterator preval = *this;
                    --*this; // use prefix operator implementation
                    return preval;
                }

                inline T1& operator*() {
                    #if CONFIG_DEVMODE
                    if (!isValid()) { // if iterator became invalidated
                        #if CONFIG_RT_EXCEPTIONS
                        throw std::runtime_error(__err_msg_iterator_invalidated);
                        #else
                        std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
                        return *((T1*)NULL); // force segfault if iterator became invalidated
                        #endif // CONFIG_RT_EXCEPTIONS
                    }
                    #endif // CONFIG_DEVMODE
                    return *current->data;

                }

                inline T1* operator->() {
                    #if CONFIG_DEVMODE
                    if (!isValid()) { // if iterator became invalidated
                        #if CONFIG_RT_EXCEPTIONS
                        throw std::runtime_error(__err_msg_iterator_invalidated);
                        #else
                        std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
                        return (T1*)NULL; // force segfault if iterator became invalidated
                        #endif // CONFIG_RT_EXCEPTIONS
                    }
                    #endif // CONFIG_DEVMODE
                    return current->data;
                }

                inline bool operator==(const _Iterator<T1> other) {
                    return current == other.current;
                }

                inline bool operator!=(const _Iterator<T1> other) {
                    return current != other.current;
                }

                inline operator bool() const {
                    return current && current->data;
                }

                inline bool operator!() const {
                    return !(current && current->data);
                }

                inline _Iterator moveToEndOf(RTListBase<T1>* pDstList) {
                    detach();
                    pDstList->append(*this);
                    _Iterator iterOnDstList = _Iterator(current);
                    current = fallback;
                    return iterOnDstList;
                }

                inline _Iterator moveToBeginOf(RTListBase<T1>* pDstList) {
                    detach();
                    pDstList->prepend(*this);
                    _Iterator iterOnDstList = _Iterator(current);
                    current = fallback;
                    return iterOnDstList;
                }

                #if CONFIG_DEVMODE
                inline bool isValid() {
                    return current->list == list;
                }
                #endif // CONFIG_DEVMODE

            protected:
                Node* current;
                Node* fallback;
                enum dir_t {
                    dir_forward,
                    dir_backward
                };
                #if CONFIG_DEVMODE
                RTListBase<T1>* list;
                #endif // CONFIG_DEVMODE

                _Iterator(Node* pNode, dir_t direction = dir_forward) {
                    current  = pNode;
                    fallback = (direction == dir_forward) ? pNode->prev : pNode->next;
                    #if CONFIG_DEVMODE
                    list = pNode->list;
                    #endif // CONFIG_DEVMODE
                }

                inline Node* node() {
                    #if CONFIG_DEVMODE
                    #if CONFIG_RT_EXCEPTIONS
                    if (isValid()) return current;
                    else throw std::runtime_error(__err_msg_iterator_invalidated);
                    #else
                    return (isValid()) ? current : (Node*)NULL; // force segfault if iterator became invalidated
                    #endif // CONFIG_RT_EXCEPTIONS
                    #else
                    return current;
                    #endif // CONFIG_DEVMODE
                }

                inline void detach() {
                    RTListBase<T1>::detach(*this);
                }

                friend class RTListBase<T1>;
                friend class RTList<T1>;
                friend class Pool<T1>;
        };
        typedef _Iterator<T> Iterator;

        inline Iterator first() {
            return Iterator(_begin.next, Iterator::dir_forward);
        }

        inline Iterator last() {
            return Iterator(_end.prev, Iterator::dir_backward);
        }

        inline Iterator begin() {
            return Iterator(&_begin, Iterator::dir_forward);
        }

        inline Iterator end() {
            return Iterator(&_end, Iterator::dir_backward);
        }

        inline bool isEmpty() {
            return _begin.next == &_end;
        }

    protected:
        Node _begin; // fake node (without data) which represents the begin of the list - not the first element!
        Node _end;   // fake node (without data) which represents the end of the list - not the last element!

        RTListBase() {
            // initialize boundary nodes
            _begin.prev = &_begin;
            _begin.next = &_end;
            _begin.data = NULL;
            _end.next = &_end;
            _end.prev = &_begin;
            _end.data = NULL;
            #if CONFIG_DEVMODE
            _begin.list = this;
            _end.list   = this;
            #endif // CONFIG_DEVMODE
        }

        inline void append(Iterator itElement) {
            Node* pNode = itElement.current;
            Node* last  = _end.prev;
            last->next  = pNode;
            pNode->prev = last; // if a segfault happens here, then because 'itElement' Iterator became invalidated
            pNode->next = &_end;
            _end.prev   = pNode;
            #if CONFIG_DEVMODE
            pNode->list = this;
            #endif // CONFIG_DEVMODE
        }

        inline void append(Iterator itFirst, Iterator itLast) {
            Node* pFirst = itFirst.current;
            Node* pLast  = itLast.current;
            Node* last   = _end.prev;
            last->next   = pFirst;
            pFirst->prev = last;  // if a segfault happens here, then because 'itFirst' Iterator became invalidated
            pLast->next  = &_end; // if a segfault happens here, then because 'itLast' Iterator became invalidated
            _end.prev    = pLast;
            #if CONFIG_DEVMODE
            for (Node* pNode = pFirst; true; pNode = pNode->next) {
                pNode->list = this;
                if (pNode == pLast) break;
            }
            #endif // CONFIG_DEVMODE
        }

        inline void prepend(Iterator itElement) {
            Node* pNode = itElement.current;
            Node* first = _begin.next;
            _begin.next = pNode;
            pNode->prev = &_begin; // if a segfault happens here, then because 'itElement' Iterator became invalidated
            pNode->next = first;
            first->prev = pNode;
            #if CONFIG_DEVMODE
            pNode->list = this;
            #endif // CONFIG_DEVMODE
        }

        inline void prepend(Iterator itFirst, Iterator itLast) {
            Node* pFirst = itFirst.current;
            Node* pLast  = itLast.current;
            Node* first  = _begin.next;
            _begin.next  = pFirst;
            pFirst->prev = &_begin; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
            pLast->next  = first;   // if a segfault happens here, then because 'itLast' Iterator became invalidated
            first->prev  = pLast;
            #if CONFIG_DEVMODE
            for (Node* pNode = pFirst; true; pNode = pNode->next) {
                pNode->list = this;
                if (pNode == pLast) break;
            }
            #endif // CONFIG_DEVMODE
        }

        static inline void detach(Iterator itElement) {
            Node* pNode = itElement.node();
            Node* prev = pNode->prev; // if a segfault happens here, then because 'itElement' Iterator became invalidated
            Node* next = pNode->next;
            prev->next = next;
            next->prev = prev;
        }

        static inline void detach(Iterator itFirst, Iterator itLast) {
            Node* prev = itFirst.node()->prev; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
            Node* next = itLast.node()->next;  // if a segfault happens here, then because 'itLast' Iterator became invalidated
            prev->next = next;
            next->prev = prev;
        }

        friend class _Iterator<T>;
        friend class RTList<T>;
        friend class Pool<T>;
};

template<typename T>
class RTList : public RTListBase<T> {
    public:
        typedef typename RTListBase<T>::Node     Node;
        typedef typename RTListBase<T>::Iterator Iterator;

        /**
         * Constructor
         *
         * @param pPool - pool this list uses for allocation and
         *                deallocation of elements
         */
        RTList(Pool<T>* pPool) : RTListBase<T>::RTListBase() {
            this->pPool = pPool;
        }

        virtual ~RTList() {
            clear();
        }

        inline bool poolIsEmpty() {
            return pPool->poolIsEmpty();
        }

        inline Iterator allocAppend() {
            if (pPool->poolIsEmpty()) return RTListBase<T>::begin();
            Iterator element = pPool->alloc();
            append(element);
            #if CONFIG_DEVMODE
            element.list = this;
            #endif // CONFIG_DEVMODE
            return element;
        }

        inline Iterator allocPrepend() {
            if (pPool->poolIsEmpty()) return RTListBase<T>::end();
            Iterator element = pPool->alloc();
            prepend(element);
            #if CONFIG_DEVMODE
            element.list = this;
            #endif // CONFIG_DEVMODE
            return element;
        }

        inline void free(Iterator& itElement) {
            itElement.detach();
            pPool->freeToPool(itElement);
            itElement.current = itElement.fallback;
        }

        inline void clear() {
            if (!RTListBase<T>::isEmpty()) {
                Node* first = RTListBase<T>::_begin.next;
                Node* last  = RTListBase<T>::_end.prev;
                RTListBase<T>::detach(first, last);
                pPool->freeToPool(first, last);
            }
        }

    protected:
        Pool<T>* pPool;
};

template<typename T>
class Pool : public RTList<T> {
    public:
        typedef typename RTList<T>::Node     Node;
        typedef typename RTList<T>::Iterator Iterator;

        Node*         nodes;
        T*            data;
        RTListBase<T> freelist; // not yet allocated elements

        Pool(int Elements) : RTList<T>::RTList(this) {
            data  = new T[Elements];
            nodes = new Node[Elements];
            for (int i = 0; i < Elements; i++) {
                nodes[i].data = &data[i];
                freelist.append(&nodes[i]);
            }
        }

        virtual ~Pool() {
            if (nodes) delete[] nodes;
            if (data)  delete[] data;
        }

        inline bool poolIsEmpty() {
            return freelist.isEmpty();
        }

    protected:
        // caution: assumes pool (that is freelist) is not empty!
        inline Iterator alloc() {
            Iterator element = freelist.last();
            element.detach();
            return element;
        }

        inline void freeToPool(Iterator itElement) {
            freelist.append(itElement);
        }

        inline void freeToPool(Iterator itFirst, Iterator itLast) {
            freelist.append(itFirst, itLast);
        }

        friend class RTList<T>;
};

#endif // __LS_POOL_H__
1	schoenebeck	271	/***************************************************************************
2			* *
3			* LinuxSampler - modular, streaming capable sampler *
4			* *
5			* Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck *
6	schoenebeck	554	* Copyright (C) 2005 Christian Schoenebeck *
7	schoenebeck	271	* *
8			* This program is free software; you can redistribute it and/or modify *
9			* it under the terms of the GNU General Public License as published by *
10			* the Free Software Foundation; either version 2 of the License, or *
11			* (at your option) any later version. *
12			* *
13			* This program is distributed in the hope that it will be useful, *
14			* but WITHOUT ANY WARRANTY; without even the implied warranty of *
15			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16			* GNU General Public License for more details. *
17			* *
18			* You should have received a copy of the GNU General Public License *
19			* along with this program; if not, write to the Free Software *
20			* Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
21			* MA 02111-1307 USA *
22			***************************************************************************/
23
24			#ifndef __LS_POOL_H__
25			#define __LS_POOL_H__
26
27	schoenebeck	554	#ifdef HAVE_CONFIG_H
28			# include <config.h>
29	schoenebeck	271	#endif
30
31			// we just use exceptions for debugging, better not in the final realtime thread !
32	schoenebeck	554	#ifndef CONFIG_RT_EXCEPTIONS
33			# define CONFIG_RT_EXCEPTIONS 0
34	schoenebeck	271	#endif
35
36	schoenebeck	554	#if CONFIG_RT_EXCEPTIONS
37	schoenebeck	271	# include <stdexcept>
38			# include <string>
39	schoenebeck	554	#endif // CONFIG_RT_EXCEPTIONS
40	schoenebeck	271
41	schoenebeck	554	#if CONFIG_DEVMODE
42			# include <string>
43			# include <iostream>
44	schoenebeck	472	const std::string __err_msg_iterator_invalidated = "Pool/RTList iterator invalidated";
45	schoenebeck	554	#endif // CONFIG_DEVMODE
46	schoenebeck	472
47	schoenebeck	271	// just symbol prototyping
48			template<typename T> class Pool;
49			template<typename T> class RTList;
50
51			template<typename T>
52			class RTListBase {
53			protected:
54	schoenebeck	361	template<typename T1>
55	schoenebeck	271	struct _Node {
56	schoenebeck	361	_Node<T1>* next;
57			_Node<T1>* prev;
58			T1* data;
59	schoenebeck	554	#if CONFIG_DEVMODE
60	schoenebeck	361	RTListBase<T1>* list; // list to which this node currently belongs to
61	schoenebeck	554	#endif // CONFIG_DEVMODE
62	schoenebeck	271
63			_Node() {
64			next = NULL;
65			prev = NULL;
66			data = NULL;
67	schoenebeck	554	#if CONFIG_DEVMODE
68	schoenebeck	271	list = NULL;
69	schoenebeck	554	#endif // CONFIG_DEVMODE
70	schoenebeck	271	}
71			};
72			typedef _Node<T> Node;
73
74			public:
75	schoenebeck	361	template<typename T1>
76	schoenebeck	271	class _Iterator {
77			public:
78			_Iterator() {
79			current = NULL;
80			fallback = NULL;
81	schoenebeck	554	#if CONFIG_DEVMODE
82	schoenebeck	271	list = NULL;
83	schoenebeck	554	#endif // CONFIG_DEVMODE
84	schoenebeck	271	}
85
86			/// prefix increment op.
87			inline _Iterator& operator++() {
88	schoenebeck	554	#if CONFIG_DEVMODE
89	schoenebeck	472	if (!isValid()) {
90	schoenebeck	554	#if CONFIG_RT_EXCEPTIONS
91	schoenebeck	472	throw std::runtime_error(__err_msg_iterator_invalidated);
92			#else
93			std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
94			return (_Iterator)NULL; // force segfault if iterator became invalidated
95	schoenebeck	554	#endif // CONFIG_RT_EXCEPTIONS
96	schoenebeck	472	}
97	schoenebeck	554	#endif // CONFIG_DEVMODE
98	schoenebeck	271	fallback = current;
99			current = current->next;
100			return *this;
101			}
102
103			/// postfix increment op.
104			inline _Iterator operator++(int) {
105			_Iterator preval = *this;
106	schoenebeck	472	++*this; // use prefix operator implementation
107	schoenebeck	271	return preval;
108			}
109
110			/// prefix decrement op.
111			inline _Iterator& operator--() {
112	schoenebeck	554	#if CONFIG_DEVMODE
113	schoenebeck	472	if (!isValid()) {
114	schoenebeck	554	#if CONFIG_RT_EXCEPTIONS
115	schoenebeck	472	throw std::runtime_error(__err_msg_iterator_invalidated);
116			#else
117			std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
118			return (_Iterator)NULL; // force segfault if iterator became invalidated
119	schoenebeck	554	#endif // CONFIG_RT_EXCEPTIONS
120			}
121			#endif // CONFIG_DEVMODE
122	schoenebeck	271	fallback = current;
123			current = current->prev;
124			return *this;
125			}
126
127			/// postfix decrement op.
128			inline _Iterator operator--(int) {
129			_Iterator preval = *this;
130	schoenebeck	472	--*this; // use prefix operator implementation
131	schoenebeck	271	return preval;
132			}
133
134	schoenebeck	361	inline T1& operator*() {
135	schoenebeck	554	#if CONFIG_DEVMODE
136	schoenebeck	472	if (!isValid()) { // if iterator became invalidated
137	schoenebeck	554	#if CONFIG_RT_EXCEPTIONS
138	schoenebeck	472	throw std::runtime_error(__err_msg_iterator_invalidated);
139			#else
140			std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
141			return ((T1)NULL); // force segfault if iterator became invalidated
142	schoenebeck	554	#endif // CONFIG_RT_EXCEPTIONS
143	schoenebeck	472	}
144	schoenebeck	554	#endif // CONFIG_DEVMODE
145	schoenebeck	271	return *current->data;
146	schoenebeck	554
147	schoenebeck	271	}
148
149	schoenebeck	361	inline T1* operator->() {
150	schoenebeck	554	#if CONFIG_DEVMODE
151	schoenebeck	472	if (!isValid()) { // if iterator became invalidated
152	schoenebeck	554	#if CONFIG_RT_EXCEPTIONS
153	schoenebeck	472	throw std::runtime_error(__err_msg_iterator_invalidated);
154			#else
155			std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
156			return (T1*)NULL; // force segfault if iterator became invalidated
157	schoenebeck	554	#endif // CONFIG_RT_EXCEPTIONS
158	schoenebeck	472	}
159	schoenebeck	554	#endif // CONFIG_DEVMODE
160			return current->data;
161	schoenebeck	271	}
162
163	schoenebeck	361	inline bool operator==(const _Iterator<T1> other) {
164	schoenebeck	271	return current == other.current;
165			}
166
167	schoenebeck	361	inline bool operator!=(const _Iterator<T1> other) {
168	schoenebeck	271	return current != other.current;
169			}
170
171			inline operator bool() const {
172			return current && current->data;
173			}
174
175			inline bool operator!() const {
176			return !(current && current->data);
177			}
178
179	schoenebeck	361	inline _Iterator moveToEndOf(RTListBase<T1>* pDstList) {
180	schoenebeck	271	detach();
181			pDstList->append(*this);
182			_Iterator iterOnDstList = _Iterator(current);
183			current = fallback;
184			return iterOnDstList;
185			}
186
187	schoenebeck	361	inline _Iterator moveToBeginOf(RTListBase<T1>* pDstList) {
188	schoenebeck	271	detach();
189			pDstList->prepend(*this);
190			_Iterator iterOnDstList = _Iterator(current);
191			current = fallback;
192			return iterOnDstList;
193			}
194
195	schoenebeck	554	#if CONFIG_DEVMODE
196	schoenebeck	271	inline bool isValid() {
197			return current->list == list;
198			}
199	schoenebeck	554	#endif // CONFIG_DEVMODE
200	schoenebeck	271
201			protected:
202			Node* current;
203			Node* fallback;
204			enum dir_t {
205			dir_forward,
206			dir_backward
207			};
208	schoenebeck	554	#if CONFIG_DEVMODE
209	schoenebeck	361	RTListBase<T1>* list;
210	schoenebeck	554	#endif // CONFIG_DEVMODE
211	schoenebeck	271
212			_Iterator(Node* pNode, dir_t direction = dir_forward) {
213			current = pNode;
214			fallback = (direction == dir_forward) ? pNode->prev : pNode->next;
215	schoenebeck	554	#if CONFIG_DEVMODE
216	schoenebeck	271	list = pNode->list;
217	schoenebeck	554	#endif // CONFIG_DEVMODE
218	schoenebeck	271	}
219
220			inline Node* node() {
221	schoenebeck	554	#if CONFIG_DEVMODE
222			#if CONFIG_RT_EXCEPTIONS
223	schoenebeck	271	if (isValid()) return current;
224			else throw std::runtime_error(__err_msg_iterator_invalidated);
225			#else
226			return (isValid()) ? current : (Node*)NULL; // force segfault if iterator became invalidated
227	schoenebeck	554	#endif // CONFIG_RT_EXCEPTIONS
228	schoenebeck	271	#else
229			return current;
230	schoenebeck	554	#endif // CONFIG_DEVMODE
231	schoenebeck	271	}
232
233			inline void detach() {
234	schoenebeck	361	RTListBase<T1>::detach(*this);
235	schoenebeck	271	}
236
237	schoenebeck	361	friend class RTListBase<T1>;
238			friend class RTList<T1>;
239			friend class Pool<T1>;
240	schoenebeck	271	};
241			typedef _Iterator<T> Iterator;
242
243			inline Iterator first() {
244			return Iterator(_begin.next, Iterator::dir_forward);
245			}
246
247			inline Iterator last() {
248			return Iterator(_end.prev, Iterator::dir_backward);
249			}
250
251			inline Iterator begin() {
252			return Iterator(&_begin, Iterator::dir_forward);
253			}
254
255			inline Iterator end() {
256			return Iterator(&_end, Iterator::dir_backward);
257			}
258
259			inline bool isEmpty() {
260			return _begin.next == &_end;
261			}
262
263			protected:
264			Node _begin; // fake node (without data) which represents the begin of the list - not the first element!
265			Node _end; // fake node (without data) which represents the end of the list - not the last element!
266
267			RTListBase() {
268			// initialize boundary nodes
269			_begin.prev = &_begin;
270			_begin.next = &_end;
271			_begin.data = NULL;
272			_end.next = &_end;
273			_end.prev = &_begin;
274			_end.data = NULL;
275	schoenebeck	554	#if CONFIG_DEVMODE
276	schoenebeck	271	_begin.list = this;
277			_end.list = this;
278	schoenebeck	554	#endif // CONFIG_DEVMODE
279	schoenebeck	271	}
280
281			inline void append(Iterator itElement) {
282			Node* pNode = itElement.current;
283			Node* last = _end.prev;
284			last->next = pNode;
285			pNode->prev = last; // if a segfault happens here, then because 'itElement' Iterator became invalidated
286			pNode->next = &_end;
287			_end.prev = pNode;
288	schoenebeck	554	#if CONFIG_DEVMODE
289	schoenebeck	271	pNode->list = this;
290	schoenebeck	554	#endif // CONFIG_DEVMODE
291	schoenebeck	271	}
292
293			inline void append(Iterator itFirst, Iterator itLast) {
294			Node* pFirst = itFirst.current;
295			Node* pLast = itLast.current;
296			Node* last = _end.prev;
297			last->next = pFirst;
298			pFirst->prev = last; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
299			pLast->next = &_end; // if a segfault happens here, then because 'itLast' Iterator became invalidated
300			_end.prev = pLast;
301	schoenebeck	554	#if CONFIG_DEVMODE
302	schoenebeck	271	for (Node* pNode = pFirst; true; pNode = pNode->next) {
303			pNode->list = this;
304			if (pNode == pLast) break;
305			}
306	schoenebeck	554	#endif // CONFIG_DEVMODE
307	schoenebeck	271	}
308
309			inline void prepend(Iterator itElement) {
310			Node* pNode = itElement.current;
311			Node* first = _begin.next;
312			_begin.next = pNode;
313			pNode->prev = &_begin; // if a segfault happens here, then because 'itElement' Iterator became invalidated
314			pNode->next = first;
315			first->prev = pNode;
316	schoenebeck	554	#if CONFIG_DEVMODE
317	schoenebeck	271	pNode->list = this;
318	schoenebeck	554	#endif // CONFIG_DEVMODE
319	schoenebeck	271	}
320
321			inline void prepend(Iterator itFirst, Iterator itLast) {
322			Node* pFirst = itFirst.current;
323			Node* pLast = itLast.current;
324			Node* first = _begin.next;
325			_begin.next = pFirst;
326			pFirst->prev = &_begin; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
327			pLast->next = first; // if a segfault happens here, then because 'itLast' Iterator became invalidated
328			first->prev = pLast;
329	schoenebeck	554	#if CONFIG_DEVMODE
330	schoenebeck	271	for (Node* pNode = pFirst; true; pNode = pNode->next) {
331			pNode->list = this;
332			if (pNode == pLast) break;
333			}
334	schoenebeck	554	#endif // CONFIG_DEVMODE
335	schoenebeck	271	}
336
337			static inline void detach(Iterator itElement) {
338			Node* pNode = itElement.node();
339			Node* prev = pNode->prev; // if a segfault happens here, then because 'itElement' Iterator became invalidated
340			Node* next = pNode->next;
341			prev->next = next;
342			next->prev = prev;
343			}
344
345			static inline void detach(Iterator itFirst, Iterator itLast) {
346			Node* prev = itFirst.node()->prev; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
347			Node* next = itLast.node()->next; // if a segfault happens here, then because 'itLast' Iterator became invalidated
348			prev->next = next;
349			next->prev = prev;
350			}
351
352	schoenebeck	277	friend class _Iterator<T>;
353			friend class RTList<T>;
354	schoenebeck	271	friend class Pool<T>;
355			};
356
357			template<typename T>
358			class RTList : public RTListBase<T> {
359			public:
360			typedef typename RTListBase<T>::Node Node;
361			typedef typename RTListBase<T>::Iterator Iterator;
362
363			/**
364			* Constructor
365			*
366			* @param pPool - pool this list uses for allocation and
367			* deallocation of elements
368			*/
369			RTList(Pool<T>* pPool) : RTListBase<T>::RTListBase() {
370			this->pPool = pPool;
371			}
372
373			virtual ~RTList() {
374			clear();
375			}
376
377			inline bool poolIsEmpty() {
378			return pPool->poolIsEmpty();
379			}
380
381			inline Iterator allocAppend() {
382			if (pPool->poolIsEmpty()) return RTListBase<T>::begin();
383			Iterator element = pPool->alloc();
384			append(element);
385	schoenebeck	554	#if CONFIG_DEVMODE
386	schoenebeck	271	element.list = this;
387	schoenebeck	554	#endif // CONFIG_DEVMODE
388	schoenebeck	271	return element;
389			}
390
391			inline Iterator allocPrepend() {
392			if (pPool->poolIsEmpty()) return RTListBase<T>::end();
393			Iterator element = pPool->alloc();
394			prepend(element);
395	schoenebeck	554	#if CONFIG_DEVMODE
396	schoenebeck	271	element.list = this;
397	schoenebeck	554	#endif // CONFIG_DEVMODE
398	schoenebeck	271	return element;
399			}
400
401			inline void free(Iterator& itElement) {
402			itElement.detach();
403			pPool->freeToPool(itElement);
404			itElement.current = itElement.fallback;
405			}
406
407			inline void clear() {
408			if (!RTListBase<T>::isEmpty()) {
409			Node* first = RTListBase<T>::_begin.next;
410			Node* last = RTListBase<T>::_end.prev;
411			RTListBase<T>::detach(first, last);
412			pPool->freeToPool(first, last);
413			}
414			}
415
416			protected:
417			Pool<T>* pPool;
418			};
419
420			template<typename T>
421			class Pool : public RTList<T> {
422			public:
423			typedef typename RTList<T>::Node Node;
424			typedef typename RTList<T>::Iterator Iterator;
425
426			Node* nodes;
427			T* data;
428			RTListBase<T> freelist; // not yet allocated elements
429
430			Pool(int Elements) : RTList<T>::RTList(this) {
431			data = new T[Elements];
432			nodes = new Node[Elements];
433			for (int i = 0; i < Elements; i++) {
434			nodes[i].data = &data[i];
435			freelist.append(&nodes[i]);
436			}
437			}
438
439			virtual ~Pool() {
440			if (nodes) delete[] nodes;
441			if (data) delete[] data;
442			}
443
444			inline bool poolIsEmpty() {
445			return freelist.isEmpty();
446			}
447
448			protected:
449			// caution: assumes pool (that is freelist) is not empty!
450			inline Iterator alloc() {
451			Iterator element = freelist.last();
452			element.detach();
453			return element;
454			}
455
456			inline void freeToPool(Iterator itElement) {
457			freelist.append(itElement);
458			}
459
460			inline void freeToPool(Iterator itFirst, Iterator itLast) {
461			freelist.append(itFirst, itLast);
462			}
463
464			friend class RTList<T>;
465			};
466
467			#endif // __LS_POOL_H__