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>
const std::string __err_msg_iterator_invalidated = "Pool/RTList iterator invalidated";
#endif // USE_EXCEPTIONS

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

template<typename T>
class RTListBase {
    protected:
        template<typename _T>
        struct _Node {
            _Node<_T>* next;
            _Node<_T>* prev;
            _T* data;
            #if DEVMODE
            RTListBase<_T>* 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 _T>
        class _Iterator {
            public:
                _Iterator() {
                    current  = NULL;
                    fallback = NULL;
                    #if DEVMODE
                    list = NULL;
                    #endif // DEVMODE
                }

                /// prefix increment op.
                inline _Iterator& operator++() {
                    #if DEVMODE
                    #if USE_EXCEPTIONS
                    if (!isValid()) throw std::runtime_error(__err_msg_iterator_invalidated);
                    #else
                    if (!isValid()) 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;
                    return preval;
                }

                /// prefix decrement op.
                inline _Iterator& operator--() {
                    #if DEVMODE
                    #if USE_EXCEPTIONS
                    if (!isValid()) throw std::runtime_error(__err_msg_iterator_invalidated);
                    #else
                    if (!isValid()) 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;
                    return preval;
                }

                inline _T& operator*() {
                    #if DEVMODE
                    #if USE_EXCEPTIONS
                    if (isValid()) return *current->data;
                    else throw std::runtime_error(__err_msg_iterator_invalidated);
                    #else
                    return *(isValid() ? current->data : (_T*)NULL); // force segfault if iterator became invalidated
                    #endif // USE_EXCEPTIONS
                    #else
                    return *current->data;
                    #endif // DEVMODE
                }

                inline _T* operator->() {
                    #if DEVMODE
                    #if USE_EXCEPTIONS
                    if (isValid()) return current->data;
                    else throw std::runtime_error(__err_msg_iterator_invalidated);
                    #else
                    return isValid() ? current->data : (_T*)NULL; // force segfault if iterator became invalidated
                    #endif // USE_EXCEPTIONS
                    #else
                    return current->data;
                    #endif // DEVMODE
                }

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

                inline bool operator!=(const _Iterator<_T> 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<_T>* pDstList) {
                    detach();
                    pDstList->append(*this);
                    _Iterator iterOnDstList = _Iterator(current);
                    current = fallback;
                    return iterOnDstList;
                }

                inline _Iterator moveToBeginOf(RTListBase<_T>* 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<_T>* 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<_T>::detach(*this);
                }

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