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