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 _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	/***************************************************************************
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 _Iterator<T>;
338	friend class RTList<T>;
339	friend class Pool<T>;
340	};
341
342	template<typename T>
343	class RTList : public RTListBase<T> {
344	public:
345	typedef typename RTListBase<T>::Node Node;
346	typedef typename RTListBase<T>::Iterator Iterator;
347
348	/**
349	* Constructor
350	*
351	* @param pPool - pool this list uses for allocation and
352	* deallocation of elements
353	*/
354	RTList(Pool<T>* pPool) : RTListBase<T>::RTListBase() {
355	this->pPool = pPool;
356	}
357
358	virtual ~RTList() {
359	clear();
360	}
361
362	inline bool poolIsEmpty() {
363	return pPool->poolIsEmpty();
364	}
365
366	inline Iterator allocAppend() {
367	if (pPool->poolIsEmpty()) return RTListBase<T>::begin();
368	Iterator element = pPool->alloc();
369	append(element);
370	#if DEVMODE
371	element.list = this;
372	#endif // DEVMODE
373	return element;
374	}
375
376	inline Iterator allocPrepend() {
377	if (pPool->poolIsEmpty()) return RTListBase<T>::end();
378	Iterator element = pPool->alloc();
379	prepend(element);
380	#if DEVMODE
381	element.list = this;
382	#endif // DEVMODE
383	return element;
384	}
385
386	inline void free(Iterator& itElement) {
387	itElement.detach();
388	pPool->freeToPool(itElement);
389	itElement.current = itElement.fallback;
390	}
391
392	inline void clear() {
393	if (!RTListBase<T>::isEmpty()) {
394	Node* first = RTListBase<T>::_begin.next;
395	Node* last = RTListBase<T>::_end.prev;
396	RTListBase<T>::detach(first, last);
397	pPool->freeToPool(first, last);
398	}
399	}
400
401	protected:
402	Pool<T>* pPool;
403	};
404
405	template<typename T>
406	class Pool : public RTList<T> {
407	public:
408	typedef typename RTList<T>::Node Node;
409	typedef typename RTList<T>::Iterator Iterator;
410
411	Node* nodes;
412	T* data;
413	RTListBase<T> freelist; // not yet allocated elements
414
415	Pool(int Elements) : RTList<T>::RTList(this) {
416	data = new T[Elements];
417	nodes = new Node[Elements];
418	for (int i = 0; i < Elements; i++) {
419	nodes[i].data = &data[i];
420	freelist.append(&nodes[i]);
421	}
422	}
423
424	virtual ~Pool() {
425	if (nodes) delete[] nodes;
426	if (data) delete[] data;
427	}
428
429	inline bool poolIsEmpty() {
430	return freelist.isEmpty();
431	}
432
433	protected:
434	// caution: assumes pool (that is freelist) is not empty!
435	inline Iterator alloc() {
436	Iterator element = freelist.last();
437	element.detach();
438	return element;
439	}
440
441	inline void freeToPool(Iterator itElement) {
442	freelist.append(itElement);
443	}
444
445	inline void freeToPool(Iterator itFirst, Iterator itLast) {
446	freelist.append(itFirst, itLast);
447	}
448
449	friend class RTList<T>;
450	};
451
452	#endif // __LS_POOL_H__