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	/***************************************************************************
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	#if DEVMODE
41	const std::string __err_msg_iterator_invalidated = "Pool/RTList iterator invalidated";
42	#endif
43
44	// 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	template<typename T1>
52	struct _Node {
53	_Node<T1>* next;
54	_Node<T1>* prev;
55	T1* data;
56	#if DEVMODE
57	RTListBase<T1>* list; // list to which this node currently belongs to
58	#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	template<typename T1>
73	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	#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	#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	++*this; // use prefix operator implementation
104	return preval;
105	}
106
107	/// prefix decrement op.
108	inline _Iterator& operator--() {
109	#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	#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	--*this; // use prefix operator implementation
128	return preval;
129	}
130
131	inline T1& operator*() {
132	#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	return *current->data;
143
144	}
145
146	inline T1* operator->() {
147	#if DEVMODE
148	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	#endif // DEVMODE
157	return current->data;
158	}
159
160	inline bool operator==(const _Iterator<T1> other) {
161	return current == other.current;
162	}
163
164	inline bool operator!=(const _Iterator<T1> other) {
165	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	inline _Iterator moveToEndOf(RTListBase<T1>* pDstList) {
177	detach();
178	pDstList->append(*this);
179	_Iterator iterOnDstList = _Iterator(current);
180	current = fallback;
181	return iterOnDstList;
182	}
183
184	inline _Iterator moveToBeginOf(RTListBase<T1>* pDstList) {
185	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	RTListBase<T1>* list;
207	#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	RTListBase<T1>::detach(*this);
232	}
233
234	friend class RTListBase<T1>;
235	friend class RTList<T1>;
236	friend class Pool<T1>;
237	};
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	friend class _Iterator<T>;
350	friend class RTList<T>;
351	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__