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:

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

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

// 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			RTEList (void) {
92			// initialize alloclist fistnode and lastnode pointers
93			firstnode.aprev=&firstnode;
94			firstnode.anext=&lastnode;
95			lastnode.anext=&lastnode;
96			lastnode.aprev=&firstnode;
97			acurrentnode=firstnode.anext;
98			}
99			~RTEList (void) {
100			}
101
102			/* returns the first element of the alloclist
103			NULL if the list is empty (no elements allocated)
104			*/
105			inline T *first(void) {
106			acurrentnode=firstnode.anext;
107			// if element->anext points to itself it means last element
108			// return NULL to signal end of list
109			if(acurrentnode->anext == acurrentnode) return(NULL);
110			return(&acurrentnode->data);
111			}
112
113			/* returns the last element of the alloclist
114			NULL if the list is empty (no elements allocated)
115			*/
116			inline T *last(void) {
117			acurrentnode=lastnode.aprev;
118			// if element->aprev points to itself it means first element
119			// return NULL to signal begin of list
120			if(acurrentnode->aprev == acurrentnode) return(NULL);
121			return(&acurrentnode->data);
122			}
123
124			/* returns the next element of the alloclist
125			NULL if we reach the end of the list
126			*/
127			inline T *next(void) {
128			acurrentnode=acurrentnode->anext;
129			// if element->anext points to itself it means last element
130			// return NULL to signal end of list
131			if(acurrentnode->anext == acurrentnode) return(NULL);
132			return(&acurrentnode->data);
133			}
134
135			/* returns the previous element of the alloclist
136			NULL if we reach the begin of the list
137			*/
138			inline T *prev(void) {
139			acurrentnode=acurrentnode->aprev;
140			// if element->aprev points to itself it means last element
141			// return NULL to signal begin of list
142			if(acurrentnode->aprev == acurrentnode) return(NULL);
143			return(&acurrentnode->data);
144			}
145
146			RTEListNode firstnode;
147			RTEListNode lastnode;
148			RTEListNode *acurrentnode;
149
150			};
151
152			template<class T>
153			class RTELMemoryPool
154			{
155
156
157
158			/*
159			RTEListNode contains the next and prev pointers needed to manage
160			the free element list, and anext,aprev needed to manage the list
161			of allocated elements. This list is handy for the routines that make
162			use of RTELMemoryPool because the list of elements can be traversed without
163			building a separate list outside RTELMemoryPool
164			*/
165
166			typedef struct _RTEListNode {
167			struct _RTEListNode *next;
168			struct _RTEListNode *prev;
169			struct _RTEListNode *anext;
170			struct _RTEListNode *aprev;
171			T data;
172			} RTEListNode;
173
174			public:
175
176			inline RTELMemoryPool (int numelements) {
177
178
179			// initialize freelist fistnode and lastnode pointers
180			firstnode.prev=&firstnode;
181			firstnode.next=&lastnode;
182			lastnode.next=&lastnode;
183			lastnode.prev=&firstnode;
184
185			currentnode=&lastnode;
186
187			// initialize alloclist fistnode and lastnode pointers
188			firstnode.aprev=&firstnode;
189			firstnode.anext=&lastnode;
190			lastnode.anext=&lastnode;
191			lastnode.aprev=&firstnode;
192
193
194			memory_pool=new RTEListNode[numelements];
195
196			for(int i=0; i < numelements; i++) {
197			append(&memory_pool[i]);
198			}
199			/* yes ugly hack but assuming that the difference of between
200			RTEListNode and RTListNode.data is constant for all
201			elements of the same class seems reasonable to me
202			this is needed because when calling free() the user supplies
203			the pointer to the data T and not to the RTEListNode
204			*/
205			free_offset=(int)(&firstnode.data)-(int)&firstnode;
206			}
207			inline ~RTELMemoryPool() {
208			delete[] memory_pool;
209			}
210
211			/* returns the first element of the alloclist
212			NULL if the list is empty (no elements allocated)
213			*/
214			inline T *first(void) {
215			acurrentnode=firstnode.anext;
216			// if element->anext points to itself it means last element
217			// return NULL to signal end of list
218			if(acurrentnode->anext == acurrentnode) return(NULL);
219			return(&acurrentnode->data);
220			}
221
222			/* returns the last element of the alloclist
223			NULL if the list is empty (no elements allocated)
224			*/
225			inline T *last(void) {
226			acurrentnode=lastnode.aprev;
227			// if element->aprev points to itself it means first element
228			// return NULL to signal begin of list
229			if(acurrentnode->aprev == acurrentnode) return(NULL);
230			return(&acurrentnode->data);
231			}
232
233			/* returns the next element of the alloclist
234			NULL if we reach the end of the list
235			*/
236			inline T *next(void) {
237			acurrentnode=acurrentnode->anext;
238			// if element->anext points to itself it means last element
239			// return NULL to signal end of list
240			if(acurrentnode->anext == acurrentnode) return(NULL);
241			return(&acurrentnode->data);
242			}
243
244			/* returns the previous element of the alloclist
245			NULL if we reach the begin of the list
246			*/
247			inline T *prev(void) {
248			acurrentnode=acurrentnode->aprev;
249			// if element->aprev points to itself it means last element
250			// return NULL to signal begin of list
251			if(acurrentnode->aprev == acurrentnode) return(NULL);
252			return(&acurrentnode->data);
253			}
254
255			inline void append(RTEListNode *elem) {
256
257			RTEListNode *last=lastnode.prev;
258
259			last->next=elem;
260			elem->next=&lastnode;
261			lastnode.prev=elem;
262			elem->prev=last;
263
264			}
265
266			inline void prepend(RTEListNode *elem) {
267
268			RTEListNode *first=firstnode.next;
269
270			elem->next=first;
271			elem->prev=&firstnode;
272			firstnode.next=elem;
273			first->prev=elem;
274			}
275
276
277
278			/* alloc_append:
279			allocate one element of the memory pool
280			if no elements are free return NULL
281			we find the first element of the list
282			remove it from the free list and then
283			return the data associated to the element
284			*/
285
286			inline T alloc_append(RTEList<T> rtelist) {
287			RTEListNode *prevelem;
288			RTEListNode *nextelem;
289			// get the first element
290			currentnode=firstnode.next;
291			// element->next points to itself which means last element
292			// return NULL to signal end of list
293			if(currentnode->next == currentnode) return(NULL);
294
295			// now remove the element from the freelist
296			prevelem=currentnode->prev;
297			nextelem=currentnode->next;
298			prevelem->next=nextelem;
299			nextelem->prev=prevelem;
300
301			// append the element to the external rtelist
302			RTEListNode el_lastnode=(RTEListNode )&rtelist->lastnode;
303			RTEListNode *last=el_lastnode->aprev;
304
305			last->anext=currentnode;
306			currentnode->anext=el_lastnode;
307			el_lastnode->aprev=currentnode;
308			currentnode->aprev=last;
309
310			// finally return the allocated elment
311			//printf("alloc_append returning elem=%d\n",&currentnode->data);
312			return(&currentnode->data);
313			}
314			/* same as alloc_append but the element is inserted at the
315			beginning of the list
316			*/
317			inline T alloc_prepend(RTEList<T> rtelist) {
318			RTEListNode *prevelem;
319			RTEListNode *nextelem;
320			// get the first element
321			currentnode=firstnode.next;
322			// element->next points to itself which means last element
323			// return NULL to signal end of list
324			if(currentnode->next == currentnode) return(NULL);
325
326			// now remove the element from the freelist
327			prevelem=currentnode->prev;
328			nextelem=currentnode->next;
329			prevelem->next=nextelem;
330			nextelem->prev=prevelem;
331
332			// prepend the element to the external rtelist
333			RTEListNode el_firstnode=(RTEListNode )&rtelist->firstnode;
334			RTEListNode *first=el_firstnode->anext;
335
336			currentnode->anext=first;
337			currentnode->aprev=el_firstnode;
338			el_firstnode->anext=currentnode;
339			first->aprev=currentnode;
340
341			// finally return the allocated elment
342			return(&currentnode->data);
343			}
344
345
346
347			// allocate one element of the memory pool
348			// if no elements are free return NULL
349			// we find the first element of the list
350			// remove it from the free list and then
351			// return the data associated to the element
352			inline T *alloc(void) {
353
354			RTEListNode *prevelem;
355			RTEListNode *nextelem;
356			RTEListNode *last;
357
358			// get the first element
359			currentnode=firstnode.next;
360			// element->next points to itself which means last element
361			// return NULL to signal end of list
362			if(currentnode->next == currentnode) return(NULL);
363
364			// now remove the element from the freelist
365			prevelem=currentnode->prev;
366			nextelem=currentnode->next;
367			prevelem->next=nextelem;
368			nextelem->prev=prevelem;
369
370			// append the element to the alloc list
371			last=lastnode.aprev;
372			last->anext=currentnode;
373			currentnode->anext=&lastnode;
374			lastnode.aprev=currentnode;
375			currentnode->aprev=last;
376
377			// finally return the allocated elment
378			return(&currentnode->data);
379			}
380
381
382			// free an allocated element by putting it back to the freelist
383			inline void free(T *element) {
384			RTEListNode *prevelem;
385			RTEListNode *nextelem;
386			RTEListNode *node;
387
388			char node_to_free=(char )element;
389			// calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
390			node_to_free -= free_offset;
391			// insert the node to the beginning of the freelist
392			node=(RTEListNode *)node_to_free;
393			prepend(node);
394
395			// now remove the element from the alloclist
396			prevelem=node->aprev;
397			nextelem=node->anext;
398			prevelem->anext=nextelem;
399			nextelem->aprev=prevelem;
400			//printf("free returning elem=%d\n",&currentnode->data);
401			}
402
403			// empty the whole list
404			inline void empty(void) {
405
406			RTEListNode *nextnode;
407			RTEListNode *prevelem;
408			RTEListNode *nextelem;
409
410			acurrentnode=firstnode.anext;
411			if(acurrentnode->anext == acurrentnode) return;
412
413			while(1) {
414			nextnode=acurrentnode->anext;
415
416			// prepend (insert at the beginning) the node to the freelist
417			//printf("empty: putting back elem (node) %d to freelist\n",acurrentnode);
418			prepend(acurrentnode);
419
420			// now remove the element from the alloclist
421			prevelem=acurrentnode->aprev;
422			nextelem=acurrentnode->anext;
423			prevelem->anext=nextelem;
424			nextelem->aprev=prevelem;
425
426			if(nextnode->anext == nextnode) return;
427			acurrentnode=nextnode;
428			}
429			}
430
431
432			int free_offset;
433
434
435			RTEListNode firstnode;
436			RTEListNode lastnode;
437			RTEListNode *currentnode;
438
439			RTEListNode *acurrentnode;
440
441			// array that contains the elements:
442			// each list element is made of list header (prev,next) and the data
443			// of type T
444			RTEListNode *memory_pool;
445
446
447			};
448
449
450			#endif