src/common/RTELMemoryPool.h

/*
  Copyright (C) 2003, 2004 by Benno Senoner ( benno@gardena.net )
  http://www.linuxaudiodev.org

  For questions, suggestions, improvements contact me via E-Mail.

  LICENSE:

  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., 675 Mass Ave, Cambridge, MA 02139, USA.

  DESCRIPTION:

  This C++ class is an fast Real Time memory allocator suitable
  for elements of constant size.
  This is often needed in real time audio applications and I wrote
  this allocator because of my frustration of still seeing
  real time audio applications that call new,delete malloc() and free()
  within the real time loop !

  The allocappend(), allocprepend() and free() methods take only a few machine cycles providing
  deterministic execution times.

  the class is designed to provide element allocation which can
  be put in an external list ( RTEList<T>) which can be traversed
  forwards and backwards using
  for(elem=rtelist->first(); elem; elem=rtelist->next() ) { .... }
  or: for(elem=rtelist->last(); elem; elem=rtelist->prev() ) { .... }


  USAGE:

  //TODO: update usage documentation here to the new interface, means things below don't work anymore!

  creation of the memory pool:

  RTELMemoryPool *mypool=RTLMemoryPool<my_datatype>(number_of_elements);

  the above constructor creates a memory pool which contains
  number_of_elements elements that can be allocated and freed
  efficienty without calling system functions like new, delete malloc(),free()
  which cause non-deterministic behaviour in Real Time applications that
  need deterministic execution time.

  allocation of an element:

  RTEList<T> *rtelist;
  rtelist=new RTEList<T>;
  my_datatype *element;
  // append the allocated element to rtelist
  element=mypool->allocappend(rtelist);
  // prepend (insert at first position) the allocated element to rtelist
  element=mypool->allocprepend(rtelist);

  if there is no space left in the array alloc() returns NULL

  freeing of an element:

  mypool->free(element);


  THAT'S ALL FOLKS !


*/


#ifndef RTELMEMORYPOOL_H
#define RTELMEMORYPOOL_H

template<class T> class RTELMemoryPool;

template<class T>
class RTEList {
    public:
        /**
         * RTEList::Node contains the next and prev pointers needed to manage
         * the free element list, and anext, aprev needed to manage the list
         * of allocated elements. This list is handy for the routines that make
         * use of RTELMemoryPool because the list of elements can be traversed without
         * building a separate list outside RTELMemoryPool
         */
        template<class _T>
        class Node {
            public:
                Node<_T>* next;
                Node<_T>* prev;
                Node<_T>* anext;
                Node<_T>* aprev;
                _T data;
                Node() {}
        };
    protected:
        Node<T>  firstnode;
        Node<T>  lastnode;
        Node<T>* acurrentnode;
        int   free_offset;
        RTELMemoryPool<T>* pPool;

        inline void move(Node<T>* pNode, RTEList<T>* pDstList) {
            // remove element from this list
            RTEList<T>::Node<T>* prev = pNode->aprev;
            RTEList<T>::Node<T>* next = pNode->anext;
            prev->anext = next;
            next->aprev = prev;

            // add element to destination list
            Node<T>* last            = pDstList->lastnode.aprev;
            last->anext              = pNode;
            pNode->anext             = &pDstList->lastnode;
            pDstList->lastnode.aprev = pNode;
            pNode->aprev             = last;
        }

        friend class RTELMemoryPool<T>;
    public:
        /**
         * Constructor
         *
         * @param pPool - the allocation pool this external list belongs to
         */
        RTEList(RTELMemoryPool<T>* pPool) {
            this->pPool = pPool;
            // initialize alloclist fistnode and lastnode pointers
            firstnode.aprev = &firstnode;
            firstnode.anext = &lastnode;
            lastnode.anext  = &lastnode;
            lastnode.aprev  = &firstnode;
            acurrentnode    = firstnode.anext;

            /* yes ugly hack but assuming that the difference of between
               RTEList::Node and RTList::Node.data is constant for all
               elements of the same class seems reasonable to me
               this is needed because when calling free() the user supplies
               the pointer to the data T and not to the RTEListNode
             */
            free_offset = (int)(&firstnode.data) - (int)&firstnode;
        }

        ~RTEList() {}

        /**
         * Returns the first element of the alloclist
         * NULL if the list is empty (no elements allocated)
         */
        inline T* first() {
            acurrentnode = firstnode.anext;
            // if element->anext points to itself it means last element
            // return NULL to signal end of list
            if (acurrentnode->anext == acurrentnode) return NULL;
            return &acurrentnode->data;
        }

        /**
         * Returns the last element of the alloclist
         * NULL if the list is empty (no elements allocated)
         */
        inline T* last() {
            acurrentnode = lastnode.aprev;
            // if element->aprev points to itself it means first element
            // return NULL to signal begin of list
            if (acurrentnode->aprev == acurrentnode) return NULL;
            return &acurrentnode->data;
        }

        /**
         * Returns the next element of the alloclist
         * NULL if we reach the end of the list
         */
        inline T* next() {
            acurrentnode = acurrentnode->anext;
            // if element->anext points to itself it means last element
            // return NULL to signal end of list
            if (acurrentnode->anext == acurrentnode) return NULL;
            return &acurrentnode->data;
        }

        /**
         * Returns the previous element of the alloclist
         * NULL if we reach the begin of the list
         */
        inline T* prev() {
            acurrentnode = acurrentnode->aprev;
            // if element->aprev points to itself it means last element
            // return NULL to signal begin of list
            if (acurrentnode->aprev == acurrentnode) return NULL;
            return &acurrentnode->data;
        }

        /**
         * Selects the node in the list respective to the given element;
         * mandatory for subsequent operations like prev() or next().
         *
         * @param element - element to be selected in the list
         */
        inline void set_current(T* element) {
            char* node = (char*) element;
            // calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
            node -= free_offset;
            // select the node
            acurrentnode = (Node<T>*) node;
        }

        /**
         * Moves current selected element from this list to another list.
         * The element will be appended to the destination list.
         *
         * @param pDstList - destination list
         * @returns          the moved element or NULL on error
         */
        inline T* move(RTEList<T>* pDstList) {
            // if there's a valid element selected
            if (acurrentnode != &firstnode && acurrentnode != &lastnode) {
                Node<T>* pNode = acurrentnode;
                acurrentnode   = acurrentnode->aprev; // select previous element
                move(pNode, pDstList); // move element's node
                return &pNode->data;
            }
            return NULL;
        }

        /**
         * Moves the given element from this list to another list.
         * The element will be appended to the destination list.
         *
         * @param pElement - element to be moved
         * @param pDstList - destination list
         */
        inline void move(T* pElement, RTEList<T>* pDstList) {
            char* cNode = (char*) pElement;
            // calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
            cNode -= free_offset;
            Node<T>* pNode = (Node<T>*) cNode;

            // if the node is selected, select previous element
            if (acurrentnode == pNode) acurrentnode = acurrentnode->aprev;

            // move the element's node
            move(pNode, pDstList);
        }

        /**
         * Returns true if no more element can be allocated from the pool.
         */
        inline bool pool_is_empty() {
            return pPool->pool_is_empty();
        }

        /**
         * Allocate one element from the pool and append it to this list.
         *
         * @returns allocated element
         */
        inline T* alloc() {
            return pPool->alloc_append(this);
        }

        /**
         * Allocate one element from the pool, assign given value and
         * append element to this list.
         *
         * @returns allocated element with already assigned value
         */
        inline T* alloc_assign(T data) {
            T* pData = alloc();
            if (pData) *pData = data;
            return pData;
        }

        /**
         * Free the given (allocated) element from this list. The element
         * will be readded to the pool's list of free elements.
         */
        inline void free(T* element) {
            pPool->free(element);
        }

        /**
         * Returns true if the list is empty.
         */
        inline bool is_empty() {
            return !first();
        }

        /**
         * Free all allocated elements in the list. All elements of this list
         * will be readded to the pool's internal list of free nodes.
         *
         * @returns number of freed elements
         */
        inline int clear() {
            int count = 0;
            acurrentnode = firstnode.anext;
            while (acurrentnode != acurrentnode->anext) {
                pPool->free(&acurrentnode->data); count++;
                acurrentnode = firstnode.anext;
            }
            return count;
        }
};

template<class T>
class RTELMemoryPool : public RTEList<T> {
    protected:
        RTEList<T>::Node<T>* currentnode;

        // array that contains the elements:
        // each list element is made of list header (prev,next) and the data
        // of type T
        RTEList<T>::Node<T>* memory_pool;

        /**
         * Allocate one element of the memory pool
         * if no elements are free return NULL
         * we find the first element of the list
         * remove it from the free list and then
         * return the data associated to the element
         */
        inline T* alloc_append(RTEList<T>* rtelist) {
            // get the first element
            currentnode = firstnode.next;
            // element->next points to itself which means last element
            // return NULL to signal end of list
            if (currentnode->next == currentnode) return NULL;

            // now remove the element from the freelist
            RTEList<T>::Node<T>* prevelem = currentnode->prev;
            RTEList<T>::Node<T>* nextelem = currentnode->next;
            prevelem->next = nextelem;
            nextelem->prev = prevelem;

            // append the element to the external rtelist
            RTEList<T>::Node<T>* el_lastnode = (RTEList<T>::Node<T>*) &rtelist->lastnode;
            RTEList<T>::Node<T>* last        = el_lastnode->aprev;

            last->anext        = currentnode;
            currentnode->anext = el_lastnode;
            el_lastnode->aprev = currentnode;
            currentnode->aprev = last;

            // finally return the allocated elment
            //printf("alloc_append returning elem=%d\n",&currentnode->data);
            return &currentnode->data;
        }

        /**
         * same as alloc_append but the element is inserted at the
         * beginning of the list
         */
        inline T* alloc_prepend(RTEList<T>* rtelist) {
            RTEList<T>::Node<T>* prevelem;
            RTEList<T>::Node<T>* nextelem;
            // get the first element
            currentnode = firstnode.next;
            // element->next points to itself which means last element
            // return NULL to signal end of list
            if (currentnode->next == currentnode) return NULL;

            // now remove the element from the freelist
            prevelem       = currentnode->prev;
            nextelem       = currentnode->next;
            prevelem->next = nextelem;
            nextelem->prev = prevelem;

            // prepend the element to the external rtelist
            RTEList<T>::Node<T>* el_firstnode = (RTEList<T>::Node<T>*) &rtelist->firstnode;
            RTEList<T>::Node<T>* first        = el_firstnode->anext;

            currentnode->anext  = first;
            currentnode->aprev  = el_firstnode;
            el_firstnode->anext = currentnode;
            first->aprev        = currentnode;

            // finally return the allocated elment
            return &currentnode->data;
        }

        inline void append(RTEList<T>::Node<T>* elem) {
            RTEList<T>::Node<T>* last = lastnode.prev;

            last->next    = elem;
            elem->next    = &lastnode;
            lastnode.prev = elem;
            elem->prev    = last;
        }

        inline void prepend(RTEList<T>::Node<T>* elem) {
            RTEList<T>::Node<T>* first = firstnode.next;

            elem->next     = first;
            elem->prev     = &firstnode;
            firstnode.next = elem;
            first->prev    = elem;
        }

        friend class RTEList<T>;

    public:
        /**
         * Constructor
         *
         * @param numelements - number of elements this pool should offer
         */
        RTELMemoryPool(int numelements) : RTEList<T>::RTEList(this) {
            // initialize freelist listnode and lastnode pointers
            firstnode.prev = &firstnode;
            firstnode.next = &lastnode;
            lastnode.next  = &lastnode;
            lastnode.prev  = &firstnode;

            currentnode = &lastnode;

            // initialize alloclist listnode and lastnode pointers
            firstnode.aprev = &firstnode;
            firstnode.anext = &lastnode;
            lastnode.anext  = &lastnode;
            lastnode.aprev  = &firstnode;


            memory_pool = new RTEList<T>::Node<T>[numelements];

            for (int i = 0; i < numelements; i++) {
                append(&memory_pool[i]);
            }
        }

        inline ~RTELMemoryPool() {
            if (memory_pool) delete[] memory_pool;
        }

        /**
         * Returns true if no more element can be allocated.
         */
        inline bool pool_is_empty() {
            RTEList<T>::Node<T>* nextnode = firstnode.next;
            return (nextnode->next == nextnode);
        }

        /**
         * Allocate one element of the memory pool
         * if no elements are free return NULL
         * we find the first element of the list
         * remove it from the free list and then
         * return the data associated to the element
         */
        inline T* alloc() {
            // get the first element
            currentnode = firstnode.next;
            // element->next points to itself which means last element
            // return NULL to signal end of list
            if (currentnode->next == currentnode) return NULL;

            // now remove the element from the freelist
            RTEList<T>::Node<T>* prevelem = currentnode->prev;
            RTEList<T>::Node<T>* nextelem = currentnode->next;
            prevelem->next = nextelem;
            nextelem->prev = prevelem;

            // append the element to the alloc list
            RTEList<T>::Node<T>* last = lastnode.aprev;
            last->anext        = currentnode;
            currentnode->anext = &lastnode;
            lastnode.aprev     = currentnode;
            currentnode->aprev = last;

            // finally return the allocated elment
            return &currentnode->data;
        }

        /**
         * Free an allocated element by putting it back to the freelist.
         */
        inline void free(T* element) {
            RTEList<T>::Node<T>* prevelem;
            RTEList<T>::Node<T>* nextelem;
            RTEList<T>::Node<T>* node;

            char* node_to_free = (char*) element;
            // calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
            node_to_free -= free_offset;
            // insert the node to the beginning of the freelist
            node = (RTEList<T>::Node<T>*) node_to_free;
            prepend(node);

            // now remove the element from the alloclist
            prevelem        = node->aprev;
            nextelem        = node->anext;
            prevelem->anext = nextelem;
            nextelem->aprev = prevelem;
            //printf("free returning elem=%d\n",&currentnode->data);
        }

        /**
         * Frees all allocated elements in the internal allocation list.
         * This method does not free elements allocated for external lists!
         * For freeing elements allocated for external lists, use the empty()
         * method of the respective RTEList object.
         *
         * @returns number of freed elements
         */
        inline int clear() {
            RTEList<T>::Node<T>* nextnode;
            RTEList<T>::Node<T>* prevelem;
            RTEList<T>::Node<T>* nextelem;

            int count = 0;

            acurrentnode = firstnode.anext;
            if (acurrentnode->anext == acurrentnode) return 0;

            while (true) {
                nextnode = acurrentnode->anext;

                // prepend (insert at the beginning) the node to the freelist
                //printf("empty: putting back elem (node) %d to freelist\n",acurrentnode);
                prepend(acurrentnode); count++;

                // now remove the element from the alloclist
                prevelem        = acurrentnode->aprev;
                nextelem        = acurrentnode->anext;
                prevelem->anext = nextelem;
                nextelem->aprev = prevelem;

                if (nextnode->anext == nextnode) return count;
                acurrentnode = nextnode;
            }
        }
};


#endif
1	/*
2	Copyright (C) 2003, 2004 by Benno Senoner ( benno@gardena.net )
3	http://www.linuxaudiodev.org
4
5	For questions, suggestions, improvements contact me via E-Mail.
6
7	LICENSE:
8
9	This program is free software; you can redistribute it and/or modify
10	it under the terms of the GNU General Public License as published by
11	the Free Software Foundation; either version 2 of the License, or
12	(at your option) any later version.
13
14	This program is distributed in the hope that it will be useful,
15	but WITHOUT ANY WARRANTY; without even the implied warranty of
16	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17	GNU General Public License for more details.
18
19	You should have received a copy of the GNU General Public License
20	along with this program; if not, write to the Free Software
21	Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22
23	DESCRIPTION:
24
25	This C++ class is an fast Real Time memory allocator suitable
26	for elements of constant size.
27	This is often needed in real time audio applications and I wrote
28	this allocator because of my frustration of still seeing
29	real time audio applications that call new,delete malloc() and free()
30	within the real time loop !
31
32	The allocappend(), allocprepend() and free() methods take only a few machine cycles providing
33	deterministic execution times.
34
35	the class is designed to provide element allocation which can
36	be put in an external list ( RTEList<T>) which can be traversed
37	forwards and backwards using
38	for(elem=rtelist->first(); elem; elem=rtelist->next() ) { .... }
39	or: for(elem=rtelist->last(); elem; elem=rtelist->prev() ) { .... }
40
41
42	USAGE:
43
44	//TODO: update usage documentation here to the new interface, means things below don't work anymore!
45
46	creation of the memory pool:
47
48	RTELMemoryPool *mypool=RTLMemoryPool<my_datatype>(number_of_elements);
49
50	the above constructor creates a memory pool which contains
51	number_of_elements elements that can be allocated and freed
52	efficienty without calling system functions like new, delete malloc(),free()
53	which cause non-deterministic behaviour in Real Time applications that
54	need deterministic execution time.
55
56	allocation of an element:
57
58	RTEList<T> *rtelist;
59	rtelist=new RTEList<T>;
60	my_datatype *element;
61	// append the allocated element to rtelist
62	element=mypool->allocappend(rtelist);
63	// prepend (insert at first position) the allocated element to rtelist
64	element=mypool->allocprepend(rtelist);
65
66	if there is no space left in the array alloc() returns NULL
67
68	freeing of an element:
69
70	mypool->free(element);
71
72
73	THAT'S ALL FOLKS !
74
75
76	*/
77
78
79	#ifndef RTELMEMORYPOOL_H
80	#define RTELMEMORYPOOL_H
81
82	template<class T> class RTELMemoryPool;
83
84	template<class T>
85	class RTEList {
86	public:
87	/**
88	* RTEList::Node contains the next and prev pointers needed to manage
89	* the free element list, and anext, aprev needed to manage the list
90	* of allocated elements. This list is handy for the routines that make
91	* use of RTELMemoryPool because the list of elements can be traversed without
92	* building a separate list outside RTELMemoryPool
93	*/
94	template<class _T>
95	class Node {
96	public:
97	Node<_T>* next;
98	Node<_T>* prev;
99	Node<_T>* anext;
100	Node<_T>* aprev;
101	_T data;
102	Node() {}
103	};
104	protected:
105	Node<T> firstnode;
106	Node<T> lastnode;
107	Node<T>* acurrentnode;
108	int free_offset;
109	RTELMemoryPool<T>* pPool;
110
111	inline void move(Node<T>* pNode, RTEList<T>* pDstList) {
112	// remove element from this list
113	RTEList<T>::Node<T>* prev = pNode->aprev;
114	RTEList<T>::Node<T>* next = pNode->anext;
115	prev->anext = next;
116	next->aprev = prev;
117
118	// add element to destination list
119	Node<T>* last = pDstList->lastnode.aprev;
120	last->anext = pNode;
121	pNode->anext = &pDstList->lastnode;
122	pDstList->lastnode.aprev = pNode;
123	pNode->aprev = last;
124	}
125
126	friend class RTELMemoryPool<T>;
127	public:
128	/**
129	* Constructor
130	*
131	* @param pPool - the allocation pool this external list belongs to
132	*/
133	RTEList(RTELMemoryPool<T>* pPool) {
134	this->pPool = pPool;
135	// initialize alloclist fistnode and lastnode pointers
136	firstnode.aprev = &firstnode;
137	firstnode.anext = &lastnode;
138	lastnode.anext = &lastnode;
139	lastnode.aprev = &firstnode;
140	acurrentnode = firstnode.anext;
141
142	/* yes ugly hack but assuming that the difference of between
143	RTEList::Node and RTList::Node.data is constant for all
144	elements of the same class seems reasonable to me
145	this is needed because when calling free() the user supplies
146	the pointer to the data T and not to the RTEListNode
147	*/
148	free_offset = (int)(&firstnode.data) - (int)&firstnode;
149	}
150
151	~RTEList() {}
152
153	/**
154	* Returns the first element of the alloclist
155	* NULL if the list is empty (no elements allocated)
156	*/
157	inline T* first() {
158	acurrentnode = firstnode.anext;
159	// if element->anext points to itself it means last element
160	// return NULL to signal end of list
161	if (acurrentnode->anext == acurrentnode) return NULL;
162	return &acurrentnode->data;
163	}
164
165	/**
166	* Returns the last element of the alloclist
167	* NULL if the list is empty (no elements allocated)
168	*/
169	inline T* last() {
170	acurrentnode = lastnode.aprev;
171	// if element->aprev points to itself it means first element
172	// return NULL to signal begin of list
173	if (acurrentnode->aprev == acurrentnode) return NULL;
174	return &acurrentnode->data;
175	}
176
177	/**
178	* Returns the next element of the alloclist
179	* NULL if we reach the end of the list
180	*/
181	inline T* next() {
182	acurrentnode = acurrentnode->anext;
183	// if element->anext points to itself it means last element
184	// return NULL to signal end of list
185	if (acurrentnode->anext == acurrentnode) return NULL;
186	return &acurrentnode->data;
187	}
188
189	/**
190	* Returns the previous element of the alloclist
191	* NULL if we reach the begin of the list
192	*/
193	inline T* prev() {
194	acurrentnode = acurrentnode->aprev;
195	// if element->aprev points to itself it means last element
196	// return NULL to signal begin of list
197	if (acurrentnode->aprev == acurrentnode) return NULL;
198	return &acurrentnode->data;
199	}
200
201	/**
202	* Selects the node in the list respective to the given element;
203	* mandatory for subsequent operations like prev() or next().
204	*
205	* @param element - element to be selected in the list
206	*/
207	inline void set_current(T* element) {
208	char* node = (char*) element;
209	// calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
210	node -= free_offset;
211	// select the node
212	acurrentnode = (Node<T>*) node;
213	}
214
215	/**
216	* Moves current selected element from this list to another list.
217	* The element will be appended to the destination list.
218	*
219	* @param pDstList - destination list
220	* @returns the moved element or NULL on error
221	*/
222	inline T* move(RTEList<T>* pDstList) {
223	// if there's a valid element selected
224	if (acurrentnode != &firstnode && acurrentnode != &lastnode) {
225	Node<T>* pNode = acurrentnode;
226	acurrentnode = acurrentnode->aprev; // select previous element
227	move(pNode, pDstList); // move element's node
228	return &pNode->data;
229	}
230	return NULL;
231	}
232
233	/**
234	* Moves the given element from this list to another list.
235	* The element will be appended to the destination list.
236	*
237	* @param pElement - element to be moved
238	* @param pDstList - destination list
239	*/
240	inline void move(T* pElement, RTEList<T>* pDstList) {
241	char* cNode = (char*) pElement;
242	// calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
243	cNode -= free_offset;
244	Node<T>* pNode = (Node<T>*) cNode;
245
246	// if the node is selected, select previous element
247	if (acurrentnode == pNode) acurrentnode = acurrentnode->aprev;
248
249	// move the element's node
250	move(pNode, pDstList);
251	}
252
253	/**
254	* Returns true if no more element can be allocated from the pool.
255	*/
256	inline bool pool_is_empty() {
257	return pPool->pool_is_empty();
258	}
259
260	/**
261	* Allocate one element from the pool and append it to this list.
262	*
263	* @returns allocated element
264	*/
265	inline T* alloc() {
266	return pPool->alloc_append(this);
267	}
268
269	/**
270	* Allocate one element from the pool, assign given value and
271	* append element to this list.
272	*
273	* @returns allocated element with already assigned value
274	*/
275	inline T* alloc_assign(T data) {
276	T* pData = alloc();
277	if (pData) *pData = data;
278	return pData;
279	}
280
281	/**
282	* Free the given (allocated) element from this list. The element
283	* will be readded to the pool's list of free elements.
284	*/
285	inline void free(T* element) {
286	pPool->free(element);
287	}
288
289	/**
290	* Returns true if the list is empty.
291	*/
292	inline bool is_empty() {
293	return !first();
294	}
295
296	/**
297	* Free all allocated elements in the list. All elements of this list
298	* will be readded to the pool's internal list of free nodes.
299	*
300	* @returns number of freed elements
301	*/
302	inline int clear() {
303	int count = 0;
304	acurrentnode = firstnode.anext;
305	while (acurrentnode != acurrentnode->anext) {
306	pPool->free(&acurrentnode->data); count++;
307	acurrentnode = firstnode.anext;
308	}
309	return count;
310	}
311	};
312
313	template<class T>
314	class RTELMemoryPool : public RTEList<T> {
315	protected:
316	RTEList<T>::Node<T>* currentnode;
317
318	// array that contains the elements:
319	// each list element is made of list header (prev,next) and the data
320	// of type T
321	RTEList<T>::Node<T>* memory_pool;
322
323	/**
324	* Allocate one element of the memory pool
325	* if no elements are free return NULL
326	* we find the first element of the list
327	* remove it from the free list and then
328	* return the data associated to the element
329	*/
330	inline T* alloc_append(RTEList<T>* rtelist) {
331	// get the first element
332	currentnode = firstnode.next;
333	// element->next points to itself which means last element
334	// return NULL to signal end of list
335	if (currentnode->next == currentnode) return NULL;
336
337	// now remove the element from the freelist
338	RTEList<T>::Node<T>* prevelem = currentnode->prev;
339	RTEList<T>::Node<T>* nextelem = currentnode->next;
340	prevelem->next = nextelem;
341	nextelem->prev = prevelem;
342
343	// append the element to the external rtelist
344	RTEList<T>::Node<T>* el_lastnode = (RTEList<T>::Node<T>*) &rtelist->lastnode;
345	RTEList<T>::Node<T>* last = el_lastnode->aprev;
346
347	last->anext = currentnode;
348	currentnode->anext = el_lastnode;
349	el_lastnode->aprev = currentnode;
350	currentnode->aprev = last;
351
352	// finally return the allocated elment
353	//printf("alloc_append returning elem=%d\n",&currentnode->data);
354	return &currentnode->data;
355	}
356
357	/**
358	* same as alloc_append but the element is inserted at the
359	* beginning of the list
360	*/
361	inline T* alloc_prepend(RTEList<T>* rtelist) {
362	RTEList<T>::Node<T>* prevelem;
363	RTEList<T>::Node<T>* nextelem;
364	// get the first element
365	currentnode = firstnode.next;
366	// element->next points to itself which means last element
367	// return NULL to signal end of list
368	if (currentnode->next == currentnode) return NULL;
369
370	// now remove the element from the freelist
371	prevelem = currentnode->prev;
372	nextelem = currentnode->next;
373	prevelem->next = nextelem;
374	nextelem->prev = prevelem;
375
376	// prepend the element to the external rtelist
377	RTEList<T>::Node<T>* el_firstnode = (RTEList<T>::Node<T>*) &rtelist->firstnode;
378	RTEList<T>::Node<T>* first = el_firstnode->anext;
379
380	currentnode->anext = first;
381	currentnode->aprev = el_firstnode;
382	el_firstnode->anext = currentnode;
383	first->aprev = currentnode;
384
385	// finally return the allocated elment
386	return &currentnode->data;
387	}
388
389	inline void append(RTEList<T>::Node<T>* elem) {
390	RTEList<T>::Node<T>* last = lastnode.prev;
391
392	last->next = elem;
393	elem->next = &lastnode;
394	lastnode.prev = elem;
395	elem->prev = last;
396	}
397
398	inline void prepend(RTEList<T>::Node<T>* elem) {
399	RTEList<T>::Node<T>* first = firstnode.next;
400
401	elem->next = first;
402	elem->prev = &firstnode;
403	firstnode.next = elem;
404	first->prev = elem;
405	}
406
407	friend class RTEList<T>;
408
409	public:
410	/**
411	* Constructor
412	*
413	* @param numelements - number of elements this pool should offer
414	*/
415	RTELMemoryPool(int numelements) : RTEList<T>::RTEList(this) {
416	// initialize freelist listnode and lastnode pointers
417	firstnode.prev = &firstnode;
418	firstnode.next = &lastnode;
419	lastnode.next = &lastnode;
420	lastnode.prev = &firstnode;
421
422	currentnode = &lastnode;
423
424	// initialize alloclist listnode and lastnode pointers
425	firstnode.aprev = &firstnode;
426	firstnode.anext = &lastnode;
427	lastnode.anext = &lastnode;
428	lastnode.aprev = &firstnode;
429
430
431	memory_pool = new RTEList<T>::Node<T>[numelements];
432
433	for (int i = 0; i < numelements; i++) {
434	append(&memory_pool[i]);
435	}
436	}
437
438	inline ~RTELMemoryPool() {
439	if (memory_pool) delete[] memory_pool;
440	}
441
442	/**
443	* Returns true if no more element can be allocated.
444	*/
445	inline bool pool_is_empty() {
446	RTEList<T>::Node<T>* nextnode = firstnode.next;
447	return (nextnode->next == nextnode);
448	}
449
450	/**
451	* Allocate one element of the memory pool
452	* if no elements are free return NULL
453	* we find the first element of the list
454	* remove it from the free list and then
455	* return the data associated to the element
456	*/
457	inline T* alloc() {
458	// get the first element
459	currentnode = firstnode.next;
460	// element->next points to itself which means last element
461	// return NULL to signal end of list
462	if (currentnode->next == currentnode) return NULL;
463
464	// now remove the element from the freelist
465	RTEList<T>::Node<T>* prevelem = currentnode->prev;
466	RTEList<T>::Node<T>* nextelem = currentnode->next;
467	prevelem->next = nextelem;
468	nextelem->prev = prevelem;
469
470	// append the element to the alloc list
471	RTEList<T>::Node<T>* last = lastnode.aprev;
472	last->anext = currentnode;
473	currentnode->anext = &lastnode;
474	lastnode.aprev = currentnode;
475	currentnode->aprev = last;
476
477	// finally return the allocated elment
478	return &currentnode->data;
479	}
480
481	/**
482	* Free an allocated element by putting it back to the freelist.
483	*/
484	inline void free(T* element) {
485	RTEList<T>::Node<T>* prevelem;
486	RTEList<T>::Node<T>* nextelem;
487	RTEList<T>::Node<T>* node;
488
489	char* node_to_free = (char*) element;
490	// calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
491	node_to_free -= free_offset;
492	// insert the node to the beginning of the freelist
493	node = (RTEList<T>::Node<T>*) node_to_free;
494	prepend(node);
495
496	// now remove the element from the alloclist
497	prevelem = node->aprev;
498	nextelem = node->anext;
499	prevelem->anext = nextelem;
500	nextelem->aprev = prevelem;
501	//printf("free returning elem=%d\n",&currentnode->data);
502	}
503
504	/**
505	* Frees all allocated elements in the internal allocation list.
506	* This method does not free elements allocated for external lists!
507	* For freeing elements allocated for external lists, use the empty()
508	* method of the respective RTEList object.
509	*
510	* @returns number of freed elements
511	*/
512	inline int clear() {
513	RTEList<T>::Node<T>* nextnode;
514	RTEList<T>::Node<T>* prevelem;
515	RTEList<T>::Node<T>* nextelem;
516
517	int count = 0;
518
519	acurrentnode = firstnode.anext;
520	if (acurrentnode->anext == acurrentnode) return 0;
521
522	while (true) {
523	nextnode = acurrentnode->anext;
524
525	// prepend (insert at the beginning) the node to the freelist
526	//printf("empty: putting back elem (node) %d to freelist\n",acurrentnode);
527	prepend(acurrentnode); count++;
528
529	// now remove the element from the alloclist
530	prevelem = acurrentnode->aprev;
531	nextelem = acurrentnode->anext;
532	prevelem->anext = nextelem;
533	nextelem->aprev = prevelem;
534
535	if (nextnode->anext == nextnode) return count;
536	acurrentnode = nextnode;
537	}
538	}
539	};
540
541
542	#endif