trunk/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:

  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 RTEList {
typedef struct _RTEListNode {
                 struct _RTEListNode *next;
                 struct _RTEListNode *prev;
                 struct _RTEListNode *anext;
                 struct _RTEListNode *aprev;
                 T data;
               } RTEListNode;

public:
  typedef RTEListNode* NodeHandle;

  RTEList (void) {
    // initialize alloclist fistnode and lastnode pointers
    firstnode.aprev=&firstnode;
    firstnode.anext=&lastnode;
    lastnode.anext=&lastnode;
    lastnode.aprev=&firstnode;
    acurrentnode=firstnode.anext;
  }
  ~RTEList (void) {
  }

/* returns the first element of the alloclist
   NULL if the list is empty (no elements allocated)
 */
inline T *first(void) {
    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(void) {
    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(void) {
    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(void) {
    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);
}

/// Returns a handle for the currently selected node or NULL if the list is empty.
inline NodeHandle current(void) {
    if (acurrentnode->anext == acurrentnode) return NULL;
    return acurrentnode;
}

/// Selects the node in the list respective to the node handle and returns it's data.
inline T* set_current(NodeHandle hNode) {
    acurrentnode = (RTEListNode*) hNode;
    return &acurrentnode->data;
    //FIXME: there should be a check if the node could be selected and a return value of NULL if failed
}

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

  RTEListNode firstnode;
  RTEListNode lastnode;
  RTEListNode *acurrentnode;

};

template<class T>
class RTELMemoryPool
{


/*
   RTEListNode 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
*/

typedef struct _RTEListNode { 
                 struct _RTEListNode *next;
                 struct _RTEListNode *prev;
                 struct _RTEListNode *anext; 
                 struct _RTEListNode *aprev; 
                 T data;
               } RTEListNode;

public:

inline RTELMemoryPool (int numelements) {


    // initialize freelist fistnode and lastnode pointers
    firstnode.prev=&firstnode;
    firstnode.next=&lastnode;
    lastnode.next=&lastnode;
    lastnode.prev=&firstnode;

    currentnode=&lastnode;

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


    memory_pool=new RTEListNode[numelements];

    for(int i=0; i < numelements; i++) {
      append(&memory_pool[i]);
    }
    /* yes ugly hack but assuming that the difference of between
       RTEListNode and RTListNode.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;
  }
inline  ~RTELMemoryPool() {
    delete[] memory_pool;
  }

/* returns the first element of the alloclist
   NULL if the list is empty (no elements allocated)
 */
inline T *first(void) {
    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(void) {
    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(void) {
    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(void) {
    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);
}

inline  void append(RTEListNode *elem) {

    RTEListNode *last=lastnode.prev;

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

inline  void prepend(RTEListNode *elem) {

    RTEListNode *first=firstnode.next;

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


/* alloc_append:
   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) {
    RTEListNode *prevelem;
    RTEListNode *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;

    // append the element to the external rtelist
    RTEListNode *el_lastnode=(RTEListNode *)&rtelist->lastnode;
    RTEListNode *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) {
    RTEListNode *prevelem;
    RTEListNode *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
    RTEListNode *el_firstnode=(RTEListNode *)&rtelist->firstnode;
    RTEListNode *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);
}


  // 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(void) {

    RTEListNode *prevelem;
    RTEListNode *nextelem;
    RTEListNode *last;

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

    // append the element to the alloc list
    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) {
    RTEListNode *prevelem;
    RTEListNode *nextelem;
    RTEListNode *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=(RTEListNode *)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);
  }

/// Selects the current element node by providing the pointer to the sought
/// element's data.
inline void set_current(T* element) {
    char* node    = (char*) element;
    node         -= free_offset;  // calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
    acurrentnode  = (RTEListNode*) node;
    //FIXME: there should be a check if the element could be selected and a respective return value
}

/// Returns true if there's no allocated element.
inline bool is_empty() {
    return !first();
}

// empty the whole list
inline void empty(void) {

    RTEListNode *nextnode;
    RTEListNode *prevelem;
    RTEListNode *nextelem;

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

    while(1) {
      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);

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

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


  int free_offset;


  RTEListNode firstnode;
  RTEListNode lastnode;
  RTEListNode *currentnode;

  RTEListNode *acurrentnode;

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


};


#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			creation of the memory pool:
45
46			RTELMemoryPool *mypool=RTLMemoryPool<my_datatype>(number_of_elements);
47
48			the above constructor creates a memory pool which contains
49			number_of_elements elements that can be allocated and freed
50			efficienty without calling system functions like new, delete malloc(),free()
51			which cause non-deterministic behaviour in Real Time applications that
52			need deterministic execution time.
53
54			allocation of an element:
55
56			RTEList<T> *rtelist;
57			rtelist=new RTEList<T>;
58			my_datatype *element;
59			// append the allocated element to rtelist
60			element=mypool->allocappend(rtelist);
61			// prepend (insert at first position) the allocated element to rtelist
62			element=mypool->allocprepend(rtelist);
63
64			if there is no space left in the array alloc() returns NULL
65
66			freeing of an element:
67
68			mypool->free(element);
69
70
71			THAT'S ALL FOLKS !
72
73
74			*/
75
76
77			#ifndef RTELMEMORYPOOL_H
78			#define RTELMEMORYPOOL_H
79
80			template<class T>
81			class RTEList {
82			typedef struct _RTEListNode {
83			struct _RTEListNode *next;
84			struct _RTEListNode *prev;
85			struct _RTEListNode *anext;
86			struct _RTEListNode *aprev;
87			T data;
88			} RTEListNode;
89
90			public:
91	schoenebeck	15	typedef RTEListNode* NodeHandle;
92
93	senoner	10	RTEList (void) {
94			// initialize alloclist fistnode and lastnode pointers
95			firstnode.aprev=&firstnode;
96			firstnode.anext=&lastnode;
97			lastnode.anext=&lastnode;
98			lastnode.aprev=&firstnode;
99			acurrentnode=firstnode.anext;
100			}
101			~RTEList (void) {
102			}
103
104			/* returns the first element of the alloclist
105			NULL if the list is empty (no elements allocated)
106			*/
107			inline T *first(void) {
108			acurrentnode=firstnode.anext;
109			// if element->anext points to itself it means last element
110			// return NULL to signal end of list
111			if(acurrentnode->anext == acurrentnode) return(NULL);
112			return(&acurrentnode->data);
113			}
114
115			/* returns the last element of the alloclist
116			NULL if the list is empty (no elements allocated)
117			*/
118			inline T *last(void) {
119			acurrentnode=lastnode.aprev;
120			// if element->aprev points to itself it means first element
121			// return NULL to signal begin of list
122			if(acurrentnode->aprev == acurrentnode) return(NULL);
123			return(&acurrentnode->data);
124			}
125
126			/* returns the next element of the alloclist
127			NULL if we reach the end of the list
128			*/
129			inline T *next(void) {
130			acurrentnode=acurrentnode->anext;
131			// if element->anext points to itself it means last element
132			// return NULL to signal end of list
133			if(acurrentnode->anext == acurrentnode) return(NULL);
134			return(&acurrentnode->data);
135			}
136
137			/* returns the previous element of the alloclist
138			NULL if we reach the begin of the list
139			*/
140			inline T *prev(void) {
141			acurrentnode=acurrentnode->aprev;
142			// if element->aprev points to itself it means last element
143			// return NULL to signal begin of list
144			if(acurrentnode->aprev == acurrentnode) return(NULL);
145			return(&acurrentnode->data);
146			}
147
148	schoenebeck	15	/// Returns a handle for the currently selected node or NULL if the list is empty.
149			inline NodeHandle current(void) {
150			if (acurrentnode->anext == acurrentnode) return NULL;
151			return acurrentnode;
152			}
153
154			/// Selects the node in the list respective to the node handle and returns it's data.
155			inline T* set_current(NodeHandle hNode) {
156			acurrentnode = (RTEListNode*) hNode;
157			return &acurrentnode->data;
158			//FIXME: there should be a check if the node could be selected and a return value of NULL if failed
159			}
160
161			/// Returns true if the list is empty.
162			inline bool is_empty() {
163			return !first();
164			}
165
166	senoner	10	RTEListNode firstnode;
167			RTEListNode lastnode;
168			RTEListNode *acurrentnode;
169
170			};
171
172			template<class T>
173			class RTELMemoryPool
174			{
175
176
177
178			/*
179			RTEListNode contains the next and prev pointers needed to manage
180			the free element list, and anext,aprev needed to manage the list
181			of allocated elements. This list is handy for the routines that make
182			use of RTELMemoryPool because the list of elements can be traversed without
183			building a separate list outside RTELMemoryPool
184			*/
185
186			typedef struct _RTEListNode {
187			struct _RTEListNode *next;
188			struct _RTEListNode *prev;
189			struct _RTEListNode *anext;
190			struct _RTEListNode *aprev;
191			T data;
192			} RTEListNode;
193
194			public:
195
196			inline RTELMemoryPool (int numelements) {
197
198
199			// initialize freelist fistnode and lastnode pointers
200			firstnode.prev=&firstnode;
201			firstnode.next=&lastnode;
202			lastnode.next=&lastnode;
203			lastnode.prev=&firstnode;
204
205			currentnode=&lastnode;
206
207			// initialize alloclist fistnode and lastnode pointers
208			firstnode.aprev=&firstnode;
209			firstnode.anext=&lastnode;
210			lastnode.anext=&lastnode;
211			lastnode.aprev=&firstnode;
212
213
214			memory_pool=new RTEListNode[numelements];
215
216			for(int i=0; i < numelements; i++) {
217			append(&memory_pool[i]);
218			}
219			/* yes ugly hack but assuming that the difference of between
220			RTEListNode and RTListNode.data is constant for all
221			elements of the same class seems reasonable to me
222			this is needed because when calling free() the user supplies
223			the pointer to the data T and not to the RTEListNode
224			*/
225			free_offset=(int)(&firstnode.data)-(int)&firstnode;
226			}
227			inline ~RTELMemoryPool() {
228			delete[] memory_pool;
229			}
230
231			/* returns the first element of the alloclist
232			NULL if the list is empty (no elements allocated)
233			*/
234			inline T *first(void) {
235			acurrentnode=firstnode.anext;
236			// if element->anext points to itself it means last element
237			// return NULL to signal end of list
238			if(acurrentnode->anext == acurrentnode) return(NULL);
239			return(&acurrentnode->data);
240			}
241
242			/* returns the last element of the alloclist
243			NULL if the list is empty (no elements allocated)
244			*/
245			inline T *last(void) {
246			acurrentnode=lastnode.aprev;
247			// if element->aprev points to itself it means first element
248			// return NULL to signal begin of list
249			if(acurrentnode->aprev == acurrentnode) return(NULL);
250			return(&acurrentnode->data);
251			}
252
253			/* returns the next element of the alloclist
254			NULL if we reach the end of the list
255			*/
256			inline T *next(void) {
257			acurrentnode=acurrentnode->anext;
258			// if element->anext points to itself it means last element
259			// return NULL to signal end of list
260			if(acurrentnode->anext == acurrentnode) return(NULL);
261			return(&acurrentnode->data);
262			}
263
264			/* returns the previous element of the alloclist
265			NULL if we reach the begin of the list
266			*/
267			inline T *prev(void) {
268			acurrentnode=acurrentnode->aprev;
269			// if element->aprev points to itself it means last element
270			// return NULL to signal begin of list
271			if(acurrentnode->aprev == acurrentnode) return(NULL);
272			return(&acurrentnode->data);
273			}
274
275			inline void append(RTEListNode *elem) {
276
277			RTEListNode *last=lastnode.prev;
278
279			last->next=elem;
280			elem->next=&lastnode;
281			lastnode.prev=elem;
282			elem->prev=last;
283
284			}
285
286			inline void prepend(RTEListNode *elem) {
287
288			RTEListNode *first=firstnode.next;
289
290			elem->next=first;
291			elem->prev=&firstnode;
292			firstnode.next=elem;
293			first->prev=elem;
294			}
295
296
297
298			/* alloc_append:
299			allocate one element of the memory pool
300			if no elements are free return NULL
301			we find the first element of the list
302			remove it from the free list and then
303			return the data associated to the element
304			*/
305
306			inline T alloc_append(RTEList<T> rtelist) {
307			RTEListNode *prevelem;
308			RTEListNode *nextelem;
309			// get the first element
310			currentnode=firstnode.next;
311			// element->next points to itself which means last element
312			// return NULL to signal end of list
313			if(currentnode->next == currentnode) return(NULL);
314
315			// now remove the element from the freelist
316			prevelem=currentnode->prev;
317			nextelem=currentnode->next;
318			prevelem->next=nextelem;
319			nextelem->prev=prevelem;
320
321			// append the element to the external rtelist
322			RTEListNode el_lastnode=(RTEListNode )&rtelist->lastnode;
323			RTEListNode *last=el_lastnode->aprev;
324
325			last->anext=currentnode;
326			currentnode->anext=el_lastnode;
327			el_lastnode->aprev=currentnode;
328			currentnode->aprev=last;
329
330			// finally return the allocated elment
331			//printf("alloc_append returning elem=%d\n",&currentnode->data);
332			return(&currentnode->data);
333			}
334			/* same as alloc_append but the element is inserted at the
335			beginning of the list
336			*/
337			inline T alloc_prepend(RTEList<T> rtelist) {
338			RTEListNode *prevelem;
339			RTEListNode *nextelem;
340			// get the first element
341			currentnode=firstnode.next;
342			// element->next points to itself which means last element
343			// return NULL to signal end of list
344			if(currentnode->next == currentnode) return(NULL);
345
346			// now remove the element from the freelist
347			prevelem=currentnode->prev;
348			nextelem=currentnode->next;
349			prevelem->next=nextelem;
350			nextelem->prev=prevelem;
351
352			// prepend the element to the external rtelist
353			RTEListNode el_firstnode=(RTEListNode )&rtelist->firstnode;
354			RTEListNode *first=el_firstnode->anext;
355
356			currentnode->anext=first;
357			currentnode->aprev=el_firstnode;
358			el_firstnode->anext=currentnode;
359			first->aprev=currentnode;
360
361			// finally return the allocated elment
362			return(&currentnode->data);
363			}
364
365
366
367			// allocate one element of the memory pool
368			// if no elements are free return NULL
369			// we find the first element of the list
370			// remove it from the free list and then
371			// return the data associated to the element
372			inline T *alloc(void) {
373
374			RTEListNode *prevelem;
375			RTEListNode *nextelem;
376			RTEListNode *last;
377
378			// get the first element
379			currentnode=firstnode.next;
380			// element->next points to itself which means last element
381			// return NULL to signal end of list
382			if(currentnode->next == currentnode) return(NULL);
383
384			// now remove the element from the freelist
385			prevelem=currentnode->prev;
386			nextelem=currentnode->next;
387			prevelem->next=nextelem;
388			nextelem->prev=prevelem;
389
390			// append the element to the alloc list
391			last=lastnode.aprev;
392			last->anext=currentnode;
393			currentnode->anext=&lastnode;
394			lastnode.aprev=currentnode;
395			currentnode->aprev=last;
396
397			// finally return the allocated elment
398			return(&currentnode->data);
399			}
400
401
402			// free an allocated element by putting it back to the freelist
403			inline void free(T *element) {
404			RTEListNode *prevelem;
405			RTEListNode *nextelem;
406			RTEListNode *node;
407	schoenebeck	15
408	senoner	10	char node_to_free=(char )element;
409			// calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
410			node_to_free -= free_offset;
411			// insert the node to the beginning of the freelist
412			node=(RTEListNode *)node_to_free;
413			prepend(node);
414
415			// now remove the element from the alloclist
416			prevelem=node->aprev;
417			nextelem=node->anext;
418			prevelem->anext=nextelem;
419			nextelem->aprev=prevelem;
420			//printf("free returning elem=%d\n",&currentnode->data);
421			}
422
423	schoenebeck	15	/// Selects the current element node by providing the pointer to the sought
424			/// element's data.
425			inline void set_current(T* element) {
426			char* node = (char*) element;
427			node -= free_offset; // calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
428			acurrentnode = (RTEListNode*) node;
429			//FIXME: there should be a check if the element could be selected and a respective return value
430			}
431
432			/// Returns true if there's no allocated element.
433			inline bool is_empty() {
434			return !first();
435			}
436
437	senoner	10	// empty the whole list
438			inline void empty(void) {
439
440			RTEListNode *nextnode;
441			RTEListNode *prevelem;
442			RTEListNode *nextelem;
443
444			acurrentnode=firstnode.anext;
445			if(acurrentnode->anext == acurrentnode) return;
446
447			while(1) {
448			nextnode=acurrentnode->anext;
449
450			// prepend (insert at the beginning) the node to the freelist
451			//printf("empty: putting back elem (node) %d to freelist\n",acurrentnode);
452			prepend(acurrentnode);
453
454			// now remove the element from the alloclist
455			prevelem=acurrentnode->aprev;
456			nextelem=acurrentnode->anext;
457			prevelem->anext=nextelem;
458			nextelem->aprev=prevelem;
459
460			if(nextnode->anext == nextnode) return;
461			acurrentnode=nextnode;
462			}
463			}
464
465
466			int free_offset;
467
468
469			RTEListNode firstnode;
470			RTEListNode lastnode;
471			RTEListNode *currentnode;
472
473			RTEListNode *acurrentnode;
474
475			// array that contains the elements:
476			// each list element is made of list header (prev,next) and the data
477			// of type T
478			RTEListNode *memory_pool;
479
480
481			};
482
483
484			#endif