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);
        }

        /**
         * 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;
        }

        /**
         * 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	* Allocate one element from the pool and append it to this list.
255	*
256	* @returns allocated element
257	*/
258	inline T* alloc() {
259	return pPool->alloc_append(this);
260	}
261
262	/**
263	* Allocate one element from the pool, assign given value and
264	* append element to this list.
265	*
266	* @returns allocated element with already assigned value
267	*/
268	inline T* alloc_assign(T data) {
269	T* pData = alloc();
270	if (pData) *pData = data;
271	return pData;
272	}
273
274	/**
275	* Free the given (allocated) element from this list. The element
276	* will be readded to the pool's list of free elements.
277	*/
278	inline void free(T* element) {
279	pPool->free(element);
280	}
281
282	/**
283	* Returns true if the list is empty.
284	*/
285	inline bool is_empty() {
286	return !first();
287	}
288
289	/**
290	* Free all allocated elements in the list. All elements of this list
291	* will be readded to the pool's internal list of free nodes.
292	*
293	* @returns number of freed elements
294	*/
295	inline int clear() {
296	int count = 0;
297	acurrentnode = firstnode.anext;
298	while (acurrentnode != acurrentnode->anext) {
299	pPool->free(&acurrentnode->data); count++;
300	acurrentnode = firstnode.anext;
301	}
302	return count;
303	}
304	};
305
306	template<class T>
307	class RTELMemoryPool : public RTEList<T> {
308	protected:
309	RTEList<T>::Node<T>* currentnode;
310
311	// array that contains the elements:
312	// each list element is made of list header (prev,next) and the data
313	// of type T
314	RTEList<T>::Node<T>* memory_pool;
315
316	/**
317	* Allocate one element of the memory pool
318	* if no elements are free return NULL
319	* we find the first element of the list
320	* remove it from the free list and then
321	* return the data associated to the element
322	*/
323	inline T* alloc_append(RTEList<T>* rtelist) {
324	// get the first element
325	currentnode = firstnode.next;
326	// element->next points to itself which means last element
327	// return NULL to signal end of list
328	if (currentnode->next == currentnode) return NULL;
329
330	// now remove the element from the freelist
331	RTEList<T>::Node<T>* prevelem = currentnode->prev;
332	RTEList<T>::Node<T>* nextelem = currentnode->next;
333	prevelem->next = nextelem;
334	nextelem->prev = prevelem;
335
336	// append the element to the external rtelist
337	RTEList<T>::Node<T>* el_lastnode = (RTEList<T>::Node<T>*) &rtelist->lastnode;
338	RTEList<T>::Node<T>* last = el_lastnode->aprev;
339
340	last->anext = currentnode;
341	currentnode->anext = el_lastnode;
342	el_lastnode->aprev = currentnode;
343	currentnode->aprev = last;
344
345	// finally return the allocated elment
346	//printf("alloc_append returning elem=%d\n",&currentnode->data);
347	return &currentnode->data;
348	}
349
350	/**
351	* same as alloc_append but the element is inserted at the
352	* beginning of the list
353	*/
354	inline T* alloc_prepend(RTEList<T>* rtelist) {
355	RTEList<T>::Node<T>* prevelem;
356	RTEList<T>::Node<T>* nextelem;
357	// get the first element
358	currentnode = firstnode.next;
359	// element->next points to itself which means last element
360	// return NULL to signal end of list
361	if (currentnode->next == currentnode) return NULL;
362
363	// now remove the element from the freelist
364	prevelem = currentnode->prev;
365	nextelem = currentnode->next;
366	prevelem->next = nextelem;
367	nextelem->prev = prevelem;
368
369	// prepend the element to the external rtelist
370	RTEList<T>::Node<T>* el_firstnode = (RTEList<T>::Node<T>*) &rtelist->firstnode;
371	RTEList<T>::Node<T>* first = el_firstnode->anext;
372
373	currentnode->anext = first;
374	currentnode->aprev = el_firstnode;
375	el_firstnode->anext = currentnode;
376	first->aprev = currentnode;
377
378	// finally return the allocated elment
379	return &currentnode->data;
380	}
381
382	inline void append(RTEList<T>::Node<T>* elem) {
383	RTEList<T>::Node<T>* last = lastnode.prev;
384
385	last->next = elem;
386	elem->next = &lastnode;
387	lastnode.prev = elem;
388	elem->prev = last;
389	}
390
391	inline void prepend(RTEList<T>::Node<T>* elem) {
392	RTEList<T>::Node<T>* first = firstnode.next;
393
394	elem->next = first;
395	elem->prev = &firstnode;
396	firstnode.next = elem;
397	first->prev = elem;
398	}
399
400	friend class RTEList<T>;
401
402	public:
403	/**
404	* Constructor
405	*
406	* @param numelements - number of elements this pool should offer
407	*/
408	RTELMemoryPool(int numelements) : RTEList<T>::RTEList(this) {
409	// initialize freelist listnode and lastnode pointers
410	firstnode.prev = &firstnode;
411	firstnode.next = &lastnode;
412	lastnode.next = &lastnode;
413	lastnode.prev = &firstnode;
414
415	currentnode = &lastnode;
416
417	// initialize alloclist listnode and lastnode pointers
418	firstnode.aprev = &firstnode;
419	firstnode.anext = &lastnode;
420	lastnode.anext = &lastnode;
421	lastnode.aprev = &firstnode;
422
423
424	memory_pool = new RTEList<T>::Node<T>[numelements];
425
426	for (int i = 0; i < numelements; i++) {
427	append(&memory_pool[i]);
428	}
429	}
430
431	inline ~RTELMemoryPool() {
432	if (memory_pool) delete[] memory_pool;
433	}
434
435	/**
436	* Allocate one element of the memory pool
437	* if no elements are free return NULL
438	* we find the first element of the list
439	* remove it from the free list and then
440	* return the data associated to the element
441	*/
442	inline T* alloc() {
443	// get the first element
444	currentnode = firstnode.next;
445	// element->next points to itself which means last element
446	// return NULL to signal end of list
447	if (currentnode->next == currentnode) return NULL;
448
449	// now remove the element from the freelist
450	RTEList<T>::Node<T>* prevelem = currentnode->prev;
451	RTEList<T>::Node<T>* nextelem = currentnode->next;
452	prevelem->next = nextelem;
453	nextelem->prev = prevelem;
454
455	// append the element to the alloc list
456	RTEList<T>::Node<T>* last = lastnode.aprev;
457	last->anext = currentnode;
458	currentnode->anext = &lastnode;
459	lastnode.aprev = currentnode;
460	currentnode->aprev = last;
461
462	// finally return the allocated elment
463	return &currentnode->data;
464	}
465
466	/**
467	* Free an allocated element by putting it back to the freelist.
468	*/
469	inline void free(T* element) {
470	RTEList<T>::Node<T>* prevelem;
471	RTEList<T>::Node<T>* nextelem;
472	RTEList<T>::Node<T>* node;
473
474	char* node_to_free = (char*) element;
475	// calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
476	node_to_free -= free_offset;
477	// insert the node to the beginning of the freelist
478	node = (RTEList<T>::Node<T>*) node_to_free;
479	prepend(node);
480
481	// now remove the element from the alloclist
482	prevelem = node->aprev;
483	nextelem = node->anext;
484	prevelem->anext = nextelem;
485	nextelem->aprev = prevelem;
486	//printf("free returning elem=%d\n",&currentnode->data);
487	}
488
489	/**
490	* Frees all allocated elements in the internal allocation list.
491	* This method does not free elements allocated for external lists!
492	* For freeing elements allocated for external lists, use the empty()
493	* method of the respective RTEList object.
494	*
495	* @returns number of freed elements
496	*/
497	inline int clear() {
498	RTEList<T>::Node<T>* nextnode;
499	RTEList<T>::Node<T>* prevelem;
500	RTEList<T>::Node<T>* nextelem;
501
502	int count = 0;
503
504	acurrentnode = firstnode.anext;
505	if (acurrentnode->anext == acurrentnode) return 0;
506
507	while (true) {
508	nextnode = acurrentnode->anext;
509
510	// prepend (insert at the beginning) the node to the freelist
511	//printf("empty: putting back elem (node) %d to freelist\n",acurrentnode);
512	prepend(acurrentnode); count++;
513
514	// now remove the element from the alloclist
515	prevelem = acurrentnode->aprev;
516	nextelem = acurrentnode->anext;
517	prevelem->anext = nextelem;
518	nextelem->aprev = prevelem;
519
520	if (nextnode->anext == nextnode) return count;
521	acurrentnode = nextnode;
522	}
523	}
524	};
525
526
527	#endif