src/common/Pool.h

/***************************************************************************
 *                                                                         *
 *   LinuxSampler - modular, streaming capable sampler                     *
 *                                                                         *
 *   Copyright (C) 2003, 2004 by Benno Senoner and 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__

#ifndef DEVMODE
# include "global.h" // just to check if we should compile in 'DEVMODE'
#endif

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

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

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

// 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 DEVMODE
            RTListBase<T1>* list; // list to which this node currently belongs to
            #endif // DEVMODE

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

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

                /// prefix increment op.
                inline _Iterator& operator++() {
                    #if DEVMODE                    
                    if (!isValid()) {
                        #if USE_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 // USE_EXCEPTIONS
                    }
                    #endif // 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 DEVMODE                    
                    if (!isValid()) {
                        #if USE_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 // USE_EXCEPTIONS
                    }                    
                    #endif // 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 DEVMODE                    
                    if (!isValid()) { // if iterator became invalidated
                        #if USE_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 // USE_EXCEPTIONS
                    }
                    #endif // DEVMODE
                    return *current->data;
                    
                }

                inline T1* operator->() {
                    #if DEVMODE
                    if (!isValid()) { // if iterator became invalidated
                        #if USE_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 // USE_EXCEPTIONS
                    }
                    #endif // 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 DEVMODE
                inline bool isValid() {
                    return current->list == list;
                }
                #endif // DEVMODE

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

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

                inline Node* node() {
                    #if DEVMODE
                    #if USE_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 // USE_EXCEPTIONS
                    #else
                    return current;
                    #endif // 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 DEVMODE
            _begin.list = this;
            _end.list   = this;
            #endif // 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 DEVMODE
            pNode->list = this;
            #endif // 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 DEVMODE
            for (Node* pNode = pFirst; true; pNode = pNode->next) {
                pNode->list = this;
                if (pNode == pLast) break;
            }
            #endif // 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 DEVMODE
            pNode->list = this;
            #endif // 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 DEVMODE
            for (Node* pNode = pFirst; true; pNode = pNode->next) {
                pNode->list = this;
                if (pNode == pLast) break;
            }
            #endif // 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 DEVMODE
            element.list = this;
            #endif // DEVMODE
            return element;
        }

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