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;

/**
 * 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 RTELNode {
        public:
                RTELNode<T>* next;
                RTELNode<T>* prev;
                RTELNode<T>* anext;
                RTELNode<T>* aprev;
                T data;
                RTELNode() {}
};

template<class T>
class RTEList {
    protected:
        RTELNode<T>  firstnode;
        RTELNode<T>  lastnode;
        RTELNode<T>* acurrentnode;
        int   free_offset;
        RTELMemoryPool<T>* pPool;

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

            // add element to destination list
            RTELNode<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 = (RTELNode<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) {
                RTELNode<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;
            RTELNode<T>* pNode = (RTELNode<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:
        RTELNode<T>* currentnode;

        // array that contains the elements:
        // each list element is made of list header (prev,next) and the data
        // of type T
        RTELNode<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 = this->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
            RTELNode<T>* prevelem = currentnode->prev;
            RTELNode<T>* nextelem = currentnode->next;
            prevelem->next = nextelem;
            nextelem->prev = prevelem;

            // append the element to the external rtelist
            RTELNode<T>* el_lastnode = (RTELNode<T>*) &rtelist->lastnode;
            RTELNode<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) {
            RTELNode<T>* prevelem;
            RTELNode<T>* nextelem;
            // get the first element
            currentnode = this->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
            RTELNode<T>* el_firstnode = (RTELNode<T>*) &rtelist->firstnode;
            RTELNode<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(RTELNode<T>* elem) {
            RTELNode<T>* last = this->lastnode.prev;

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

        inline void prepend(RTELNode<T>* elem) {
            RTELNode<T>* first = this->firstnode.next;

            elem->next     = first;
            elem->prev     = &(this->firstnode);
            this->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
            this->firstnode.prev = &(this->firstnode);
            this->firstnode.next = &(this->lastnode);
            this->lastnode.next  = &(this->lastnode);
            this->lastnode.prev  = &(this->firstnode);

            currentnode = &(this->lastnode);

            // initialize alloclist listnode and lastnode pointers
            this->firstnode.aprev = &(this->firstnode);
            this->firstnode.anext = &(this->lastnode);
            this->lastnode.anext  = &(this->lastnode);
            this->lastnode.aprev  = &(this->firstnode);


            memory_pool = new RTELNode<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() {
            RTELNode<T>* nextnode = this->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 = this->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
            RTELNode<T>* prevelem = currentnode->prev;
            RTELNode<T>* nextelem = currentnode->next;
            prevelem->next = nextelem;
            nextelem->prev = prevelem;

            // append the element to the alloc list
            RTELNode<T>* last = this->lastnode.aprev;
            last->anext        = currentnode;
            currentnode->anext = &(this->lastnode);
            this->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) {
            RTELNode<T>* prevelem;
            RTELNode<T>* nextelem;
            RTELNode<T>* node;

            char* node_to_free = (char*) element;
            // calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
            node_to_free -= this->free_offset;
            // insert the node to the beginning of the freelist
            node = (RTELNode<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() {
            RTELNode<T>* nextnode;
            RTELNode<T>* prevelem;
            RTELNode<T>* nextelem;

            int count = 0;

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

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

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

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

                if (nextnode->anext == nextnode) return count;
                this->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	/**
85	* RTEList::Node contains the next and prev pointers needed to manage
86	* the free element list, and anext, aprev needed to manage the list
87	* of allocated elements. This list is handy for the routines that make
88	* use of RTELMemoryPool because the list of elements can be traversed without
89	* building a separate list outside RTELMemoryPool
90	*/
91	template<class T>
92	class RTELNode {
93	public:
94	RTELNode<T>* next;
95	RTELNode<T>* prev;
96	RTELNode<T>* anext;
97	RTELNode<T>* aprev;
98	T data;
99	RTELNode() {}
100	};
101
102	template<class T>
103	class RTEList {
104	protected:
105	RTELNode<T> firstnode;
106	RTELNode<T> lastnode;
107	RTELNode<T>* acurrentnode;
108	int free_offset;
109	RTELMemoryPool<T>* pPool;
110
111	inline void move(RTELNode<T>* pNode, RTEList<T>* pDstList) {
112	// remove element from this list
113	RTELNode<T>* prev = pNode->aprev;
114	RTELNode<T>* next = pNode->anext;
115	prev->anext = next;
116	next->aprev = prev;
117
118	// add element to destination list
119	RTELNode<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
128	public:
129	/**
130	* Constructor
131	*
132	* @param pPool - the allocation pool this external list belongs to
133	*/
134	RTEList(RTELMemoryPool<T>* pPool) {
135	this->pPool = pPool;
136	// initialize alloclist fistnode and lastnode pointers
137	firstnode.aprev = &firstnode;
138	firstnode.anext = &lastnode;
139	lastnode.anext = &lastnode;
140	lastnode.aprev = &firstnode;
141	acurrentnode = firstnode.anext;
142
143	/* yes ugly hack but assuming that the difference of between
144	RTEList::Node and RTList::Node.data is constant for all
145	elements of the same class seems reasonable to me
146	this is needed because when calling free() the user supplies
147	the pointer to the data T and not to the RTEListNode
148	*/
149	free_offset = (int)(&firstnode.data) - (int)&firstnode;
150	}
151
152	~RTEList() {}
153
154	/**
155	* Returns the first element of the alloclist
156	* NULL if the list is empty (no elements allocated)
157	*/
158	inline T* first() {
159	acurrentnode = firstnode.anext;
160	// if element->anext points to itself it means last element
161	// return NULL to signal end of list
162	if (acurrentnode->anext == acurrentnode) return NULL;
163	return &acurrentnode->data;
164	}
165
166	/**
167	* Returns the last element of the alloclist
168	* NULL if the list is empty (no elements allocated)
169	*/
170	inline T* last() {
171	acurrentnode = lastnode.aprev;
172	// if element->aprev points to itself it means first element
173	// return NULL to signal begin of list
174	if (acurrentnode->aprev == acurrentnode) return NULL;
175	return &acurrentnode->data;
176	}
177
178	/**
179	* Returns the next element of the alloclist
180	* NULL if we reach the end of the list
181	*/
182	inline T* next() {
183	acurrentnode = acurrentnode->anext;
184	// if element->anext points to itself it means last element
185	// return NULL to signal end of list
186	if (acurrentnode->anext == acurrentnode) return NULL;
187	return &acurrentnode->data;
188	}
189
190	/**
191	* Returns the previous element of the alloclist
192	* NULL if we reach the begin of the list
193	*/
194	inline T* prev() {
195	acurrentnode = acurrentnode->aprev;
196	// if element->aprev points to itself it means last element
197	// return NULL to signal begin of list
198	if (acurrentnode->aprev == acurrentnode) return NULL;
199	return &acurrentnode->data;
200	}
201
202	/**
203	* Selects the node in the list respective to the given element;
204	* mandatory for subsequent operations like prev() or next().
205	*
206	* @param element - element to be selected in the list
207	*/
208	inline void set_current(T* element) {
209	char* node = (char*) element;
210	// calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
211	node -= free_offset;
212	// select the node
213	acurrentnode = (RTELNode<T>*) node;
214	}
215
216	/**
217	* Moves current selected element from this list to another list.
218	* The element will be appended to the destination list.
219	*
220	* @param pDstList - destination list
221	* @returns the moved element or NULL on error
222	*/
223	inline T* move(RTEList<T>* pDstList) {
224	// if there's a valid element selected
225	if (acurrentnode != &firstnode && acurrentnode != &lastnode) {
226	RTELNode<T>* pNode = acurrentnode;
227	acurrentnode = acurrentnode->aprev; // select previous element
228	move(pNode, pDstList); // move element's node
229	return &pNode->data;
230	}
231	return NULL;
232	}
233
234	/**
235	* Moves the given element from this list to another list.
236	* The element will be appended to the destination list.
237	*
238	* @param pElement - element to be moved
239	* @param pDstList - destination list
240	*/
241	inline void move(T* pElement, RTEList<T>* pDstList) {
242	char* cNode = (char*) pElement;
243	// calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
244	cNode -= free_offset;
245	RTELNode<T>* pNode = (RTELNode<T>*) cNode;
246
247	// if the node is selected, select previous element
248	if (acurrentnode == pNode) acurrentnode = acurrentnode->aprev;
249
250	// move the element's node
251	move(pNode, pDstList);
252	}
253
254	/**
255	* Returns true if no more element can be allocated from the pool.
256	*/
257	inline bool pool_is_empty() {
258	return pPool->pool_is_empty();
259	}
260
261	/**
262	* Allocate one element from the pool and append it to this list.
263	*
264	* @returns allocated element
265	*/
266	inline T* alloc() {
267	return pPool->alloc_append(this);
268	}
269
270	/**
271	* Allocate one element from the pool, assign given value and
272	* append element to this list.
273	*
274	* @returns allocated element with already assigned value
275	*/
276	inline T* alloc_assign(T data) {
277	T* pData = alloc();
278	if (pData) *pData = data;
279	return pData;
280	}
281
282	/**
283	* Free the given (allocated) element from this list. The element
284	* will be readded to the pool's list of free elements.
285	*/
286	inline void free(T* element) {
287	pPool->free(element);
288	}
289
290	/**
291	* Returns true if the list is empty.
292	*/
293	inline bool is_empty() {
294	return !first();
295	}
296
297	/**
298	* Free all allocated elements in the list. All elements of this list
299	* will be readded to the pool's internal list of free nodes.
300	*
301	* @returns number of freed elements
302	*/
303	inline int clear() {
304	int count = 0;
305	acurrentnode = firstnode.anext;
306	while (acurrentnode != acurrentnode->anext) {
307	pPool->free(&acurrentnode->data); count++;
308	acurrentnode = firstnode.anext;
309	}
310	return count;
311	}
312	};
313
314	template<class T>
315	class RTELMemoryPool : public RTEList<T> {
316	protected:
317	RTELNode<T>* currentnode;
318
319	// array that contains the elements:
320	// each list element is made of list header (prev,next) and the data
321	// of type T
322	RTELNode<T>* memory_pool;
323
324	/**
325	* Allocate one element of the memory pool
326	* if no elements are free return NULL
327	* we find the first element of the list
328	* remove it from the free list and then
329	* return the data associated to the element
330	*/
331	inline T* alloc_append(RTEList<T>* rtelist) {
332	// get the first element
333	currentnode = this->firstnode.next;
334	// element->next points to itself which means last element
335	// return NULL to signal end of list
336	if (currentnode->next == currentnode) return NULL;
337
338	// now remove the element from the freelist
339	RTELNode<T>* prevelem = currentnode->prev;
340	RTELNode<T>* nextelem = currentnode->next;
341	prevelem->next = nextelem;
342	nextelem->prev = prevelem;
343
344	// append the element to the external rtelist
345	RTELNode<T>* el_lastnode = (RTELNode<T>*) &rtelist->lastnode;
346	RTELNode<T>* last = el_lastnode->aprev;
347
348	last->anext = currentnode;
349	currentnode->anext = el_lastnode;
350	el_lastnode->aprev = currentnode;
351	currentnode->aprev = last;
352
353	// finally return the allocated elment
354	//printf("alloc_append returning elem=%d\n",&currentnode->data);
355	return &currentnode->data;
356	}
357
358	/**
359	* same as alloc_append but the element is inserted at the
360	* beginning of the list
361	*/
362	inline T* alloc_prepend(RTEList<T>* rtelist) {
363	RTELNode<T>* prevelem;
364	RTELNode<T>* nextelem;
365	// get the first element
366	currentnode = this->firstnode.next;
367	// element->next points to itself which means last element
368	// return NULL to signal end of list
369	if (currentnode->next == currentnode) return NULL;
370
371	// now remove the element from the freelist
372	prevelem = currentnode->prev;
373	nextelem = currentnode->next;
374	prevelem->next = nextelem;
375	nextelem->prev = prevelem;
376
377	// prepend the element to the external rtelist
378	RTELNode<T>* el_firstnode = (RTELNode<T>*) &rtelist->firstnode;
379	RTELNode<T>* first = el_firstnode->anext;
380
381	currentnode->anext = first;
382	currentnode->aprev = el_firstnode;
383	el_firstnode->anext = currentnode;
384	first->aprev = currentnode;
385
386	// finally return the allocated elment
387	return &currentnode->data;
388	}
389
390	inline void append(RTELNode<T>* elem) {
391	RTELNode<T>* last = this->lastnode.prev;
392
393	last->next = elem;
394	elem->next = &(this->lastnode);
395	this->lastnode.prev = elem;
396	elem->prev = last;
397	}
398
399	inline void prepend(RTELNode<T>* elem) {
400	RTELNode<T>* first = this->firstnode.next;
401
402	elem->next = first;
403	elem->prev = &(this->firstnode);
404	this->firstnode.next = elem;
405	first->prev = elem;
406	}
407
408	friend class RTEList<T>;
409
410	public:
411	/**
412	* Constructor
413	*
414	* @param numelements - number of elements this pool should offer
415	*/
416	RTELMemoryPool(int numelements) : RTEList<T>::RTEList(this) {
417	// initialize freelist listnode and lastnode pointers
418	this->firstnode.prev = &(this->firstnode);
419	this->firstnode.next = &(this->lastnode);
420	this->lastnode.next = &(this->lastnode);
421	this->lastnode.prev = &(this->firstnode);
422
423	currentnode = &(this->lastnode);
424
425	// initialize alloclist listnode and lastnode pointers
426	this->firstnode.aprev = &(this->firstnode);
427	this->firstnode.anext = &(this->lastnode);
428	this->lastnode.anext = &(this->lastnode);
429	this->lastnode.aprev = &(this->firstnode);
430
431
432	memory_pool = new RTELNode<T>[numelements];
433
434	for (int i = 0; i < numelements; i++) {
435	append(&memory_pool[i]);
436	}
437	}
438
439	inline ~RTELMemoryPool() {
440	if (memory_pool) delete[] memory_pool;
441	}
442
443	/**
444	* Returns true if no more element can be allocated.
445	*/
446	inline bool pool_is_empty() {
447	RTELNode<T>* nextnode = this->firstnode.next;
448	return (nextnode->next == nextnode);
449	}
450
451	/**
452	* Allocate one element of the memory pool
453	* if no elements are free return NULL
454	* we find the first element of the list
455	* remove it from the free list and then
456	* return the data associated to the element
457	*/
458	inline T* alloc() {
459	// get the first element
460	currentnode = this->firstnode.next;
461	// element->next points to itself which means last element
462	// return NULL to signal end of list
463	if (currentnode->next == currentnode) return NULL;
464
465	// now remove the element from the freelist
466	RTELNode<T>* prevelem = currentnode->prev;
467	RTELNode<T>* nextelem = currentnode->next;
468	prevelem->next = nextelem;
469	nextelem->prev = prevelem;
470
471	// append the element to the alloc list
472	RTELNode<T>* last = this->lastnode.aprev;
473	last->anext = currentnode;
474	currentnode->anext = &(this->lastnode);
475	this->lastnode.aprev = currentnode;
476	currentnode->aprev = last;
477
478	// finally return the allocated elment
479	return &currentnode->data;
480	}
481
482	/**
483	* Free an allocated element by putting it back to the freelist.
484	*/
485	inline void free(T* element) {
486	RTELNode<T>* prevelem;
487	RTELNode<T>* nextelem;
488	RTELNode<T>* node;
489
490	char* node_to_free = (char*) element;
491	// calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
492	node_to_free -= this->free_offset;
493	// insert the node to the beginning of the freelist
494	node = (RTELNode<T>*) node_to_free;
495	prepend(node);
496
497	// now remove the element from the alloclist
498	prevelem = node->aprev;
499	nextelem = node->anext;
500	prevelem->anext = nextelem;
501	nextelem->aprev = prevelem;
502	//printf("free returning elem=%d\n",&currentnode->data);
503	}
504
505	/**
506	* Frees all allocated elements in the internal allocation list.
507	* This method does not free elements allocated for external lists!
508	* For freeing elements allocated for external lists, use the empty()
509	* method of the respective RTEList object.
510	*
511	* @returns number of freed elements
512	*/
513	inline int clear() {
514	RTELNode<T>* nextnode;
515	RTELNode<T>* prevelem;
516	RTELNode<T>* nextelem;
517
518	int count = 0;
519
520	this->acurrentnode = this->firstnode.anext;
521	if (this->acurrentnode->anext == this->acurrentnode) return 0;
522
523	while (true) {
524	nextnode = this->acurrentnode->anext;
525
526	// prepend (insert at the beginning) the node to the freelist
527	//printf("empty: putting back elem (node) %d to freelist\n",acurrentnode);
528	prepend(this->acurrentnode); count++;
529
530	// now remove the element from the alloclist
531	prevelem = this->acurrentnode->aprev;
532	nextelem = this->acurrentnode->anext;
533	prevelem->anext = nextelem;
534	nextelem->aprev = prevelem;
535
536	if (nextnode->anext == nextnode) return count;
537	this->acurrentnode = nextnode;
538	}
539	}
540	};
541
542
543	#endif