src/common/RTELMemoryPool.h

/*
  Copyright (C) 2003 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	schoenebeck	53	/*
2			Copyright (C) 2003 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