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