v0_1_0/src/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	senoner	10	/*
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	schoenebeck	32	//TODO: update usage documentation here to the new interface, means things below don't work anymore!
45
46	senoner	10	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	schoenebeck	32
76	senoner	10	*/
77
78
79			#ifndef RTELMEMORYPOOL_H
80			#define RTELMEMORYPOOL_H
81
82	schoenebeck	32	template<class T> class RTELMemoryPool;
83
84	senoner	10	template<class T>
85			class RTEList {
86	schoenebeck	32	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	senoner	10
111	schoenebeck	32	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	schoenebeck	15
118	schoenebeck	32	// 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	senoner	10
126	schoenebeck	32	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	senoner	10
142	schoenebeck	32	/* 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	senoner	10
151	schoenebeck	32	~RTEList() {}
152	senoner	10
153	schoenebeck	32	/**
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	senoner	10
165	schoenebeck	32	/**
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	schoenebeck	15
177	schoenebeck	32	/**
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	schoenebeck	15
189	schoenebeck	32	/**
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	schoenebeck	15
201	schoenebeck	32	/**
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	senoner	10
215	schoenebeck	32	/**
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	senoner	10
233	schoenebeck	32	/**
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	senoner	10
246	schoenebeck	32	// if the node is selected, select previous element
247			if (acurrentnode == pNode) acurrentnode = acurrentnode->aprev;
248	senoner	10
249	schoenebeck	32	// move the element's node
250			move(pNode, pDstList);
251			}
252	senoner	10
253	schoenebeck	32	/**
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	senoner	10
262	schoenebeck	32	/**
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	senoner	10
274	schoenebeck	32	/**
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	senoner	10
282	schoenebeck	32	/**
283			* Returns true if the list is empty.
284			*/
285			inline bool is_empty() {
286			return !first();
287			}
288	senoner	10
289	schoenebeck	32	/**
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	senoner	10
306	schoenebeck	32	template<class T>
307			class RTELMemoryPool : public RTEList<T> {
308			protected:
309			RTEList<T>::Node<T>* currentnode;
310	senoner	10
311	schoenebeck	32	// 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	senoner	10
316	schoenebeck	32	/**
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	senoner	10
330	schoenebeck	32	// 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	senoner	10
336	schoenebeck	32	// 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	senoner	10
340	schoenebeck	32	last->anext = currentnode;
341			currentnode->anext = el_lastnode;
342			el_lastnode->aprev = currentnode;
343			currentnode->aprev = last;
344	senoner	10
345	schoenebeck	32	// finally return the allocated elment
346			//printf("alloc_append returning elem=%d\n",&currentnode->data);
347			return &currentnode->data;
348			}
349	senoner	10
350	schoenebeck	32	/**
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	senoner	10
363	schoenebeck	32	// now remove the element from the freelist
364			prevelem = currentnode->prev;
365			nextelem = currentnode->next;
366			prevelem->next = nextelem;
367			nextelem->prev = prevelem;
368	senoner	10
369	schoenebeck	32	// 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	senoner	10
373	schoenebeck	32	currentnode->anext = first;
374			currentnode->aprev = el_firstnode;
375			el_firstnode->anext = currentnode;
376			first->aprev = currentnode;
377	senoner	10
378	schoenebeck	32	// finally return the allocated elment
379			return &currentnode->data;
380			}
381	senoner	10
382	schoenebeck	32	inline void append(RTEList<T>::Node<T>* elem) {
383			RTEList<T>::Node<T>* last = lastnode.prev;
384	senoner	10
385	schoenebeck	32	last->next = elem;
386			elem->next = &lastnode;
387			lastnode.prev = elem;
388			elem->prev = last;
389			}
390	senoner	10
391	schoenebeck	32	inline void prepend(RTEList<T>::Node<T>* elem) {
392			RTEList<T>::Node<T>* first = firstnode.next;
393	senoner	10
394	schoenebeck	32	elem->next = first;
395			elem->prev = &firstnode;
396			firstnode.next = elem;
397			first->prev = elem;
398			}
399	senoner	10
400	schoenebeck	32	friend class RTEList<T>;
401	senoner	10
402	schoenebeck	32	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	senoner	10
415	schoenebeck	32	currentnode = &lastnode;
416	senoner	10
417	schoenebeck	32	// initialize alloclist listnode and lastnode pointers
418			firstnode.aprev = &firstnode;
419			firstnode.anext = &lastnode;
420			lastnode.anext = &lastnode;
421			lastnode.aprev = &firstnode;
422	senoner	10
423
424	schoenebeck	32	memory_pool = new RTEList<T>::Node<T>[numelements];
425	senoner	10
426	schoenebeck	32	for (int i = 0; i < numelements; i++) {
427			append(&memory_pool[i]);
428			}
429			}
430	senoner	10
431	schoenebeck	32	inline ~RTELMemoryPool() {
432			if (memory_pool) delete[] memory_pool;
433			}
434	senoner	10
435	schoenebeck	32	/**
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	senoner	10
449	schoenebeck	32	// 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	senoner	10
455	schoenebeck	32	// 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	senoner	10
462	schoenebeck	32	// finally return the allocated elment
463			return &currentnode->data;
464			}
465	senoner	10
466	schoenebeck	32	/**
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	senoner	10
474	schoenebeck	32	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	senoner	10
481	schoenebeck	32	// 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	senoner	10
489	schoenebeck	32	/**
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	senoner	10
502	schoenebeck	32	int count = 0;
503	senoner	10
504	schoenebeck	32	acurrentnode = firstnode.anext;
505			if (acurrentnode->anext == acurrentnode) return 0;
506	senoner	10
507	schoenebeck	32	while (true) {
508			nextnode = acurrentnode->anext;
509	senoner	10
510	schoenebeck	32	// 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	senoner	10
514	schoenebeck	32	// now remove the element from the alloclist
515			prevelem = acurrentnode->aprev;
516			nextelem = acurrentnode->anext;
517			prevelem->anext = nextelem;
518			nextelem->aprev = prevelem;
519	senoner	10
520	schoenebeck	32	if (nextnode->anext == nextnode) return count;
521			acurrentnode = nextnode;
522			}
523			}
524	senoner	10	};
525
526
527			#endif