/[svn]/linuxsampler/trunk/src/common/RTELMemoryPool.h
ViewVC logotype

Contents of /linuxsampler/trunk/src/common/RTELMemoryPool.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 248 - (show annotations) (download) (as text)
Mon Sep 20 00:20:13 2004 UTC (16 years ago) by schoenebeck
File MIME type: text/x-c++hdr
File size: 19032 byte(s)
added pool_is_empty() methods

1 /*
2 Copyright (C) 2003, 2004 by Benno Senoner ( benno@gardena.net )
3 http://www.linuxaudiodev.org
4
5 For questions, suggestions, improvements contact me via E-Mail.
6
7 LICENSE:
8
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22
23 DESCRIPTION:
24
25 This C++ class is an fast Real Time memory allocator suitable
26 for elements of constant size.
27 This is often needed in real time audio applications and I wrote
28 this allocator because of my frustration of still seeing
29 real time audio applications that call new,delete malloc() and free()
30 within the real time loop !
31
32 The allocappend(), allocprepend() and free() methods take only a few machine cycles providing
33 deterministic execution times.
34
35 the class is designed to provide element allocation which can
36 be put in an external list ( RTEList<T>) which can be traversed
37 forwards and backwards using
38 for(elem=rtelist->first(); elem; elem=rtelist->next() ) { .... }
39 or: for(elem=rtelist->last(); elem; elem=rtelist->prev() ) { .... }
40
41
42 USAGE:
43
44 //TODO: update usage documentation here to the new interface, means things below don't work anymore!
45
46 creation of the memory pool:
47
48 RTELMemoryPool *mypool=RTLMemoryPool<my_datatype>(number_of_elements);
49
50 the above constructor creates a memory pool which contains
51 number_of_elements elements that can be allocated and freed
52 efficienty without calling system functions like new, delete malloc(),free()
53 which cause non-deterministic behaviour in Real Time applications that
54 need deterministic execution time.
55
56 allocation of an element:
57
58 RTEList<T> *rtelist;
59 rtelist=new RTEList<T>;
60 my_datatype *element;
61 // append the allocated element to rtelist
62 element=mypool->allocappend(rtelist);
63 // prepend (insert at first position) the allocated element to rtelist
64 element=mypool->allocprepend(rtelist);
65
66 if there is no space left in the array alloc() returns NULL
67
68 freeing of an element:
69
70 mypool->free(element);
71
72
73 THAT'S ALL FOLKS !
74
75
76 */
77
78
79 #ifndef RTELMEMORYPOOL_H
80 #define RTELMEMORYPOOL_H
81
82 template<class T> class RTELMemoryPool;
83
84 template<class T>
85 class RTEList {
86 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
111 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
118 // 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
126 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
142 /* 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
151 ~RTEList() {}
152
153 /**
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
165 /**
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
177 /**
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
189 /**
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
201 /**
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
215 /**
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
233 /**
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
246 // if the node is selected, select previous element
247 if (acurrentnode == pNode) acurrentnode = acurrentnode->aprev;
248
249 // move the element's node
250 move(pNode, pDstList);
251 }
252
253 /**
254 * Returns true if no more element can be allocated from the pool.
255 */
256 inline bool pool_is_empty() {
257 return pPool->pool_is_empty();
258 }
259
260 /**
261 * Allocate one element from the pool and append it to this list.
262 *
263 * @returns allocated element
264 */
265 inline T* alloc() {
266 return pPool->alloc_append(this);
267 }
268
269 /**
270 * Allocate one element from the pool, assign given value and
271 * append element to this list.
272 *
273 * @returns allocated element with already assigned value
274 */
275 inline T* alloc_assign(T data) {
276 T* pData = alloc();
277 if (pData) *pData = data;
278 return pData;
279 }
280
281 /**
282 * Free the given (allocated) element from this list. The element
283 * will be readded to the pool's list of free elements.
284 */
285 inline void free(T* element) {
286 pPool->free(element);
287 }
288
289 /**
290 * Returns true if the list is empty.
291 */
292 inline bool is_empty() {
293 return !first();
294 }
295
296 /**
297 * Free all allocated elements in the list. All elements of this list
298 * will be readded to the pool's internal list of free nodes.
299 *
300 * @returns number of freed elements
301 */
302 inline int clear() {
303 int count = 0;
304 acurrentnode = firstnode.anext;
305 while (acurrentnode != acurrentnode->anext) {
306 pPool->free(&acurrentnode->data); count++;
307 acurrentnode = firstnode.anext;
308 }
309 return count;
310 }
311 };
312
313 template<class T>
314 class RTELMemoryPool : public RTEList<T> {
315 protected:
316 RTEList<T>::Node<T>* currentnode;
317
318 // array that contains the elements:
319 // each list element is made of list header (prev,next) and the data
320 // of type T
321 RTEList<T>::Node<T>* memory_pool;
322
323 /**
324 * Allocate one element of the memory pool
325 * if no elements are free return NULL
326 * we find the first element of the list
327 * remove it from the free list and then
328 * return the data associated to the element
329 */
330 inline T* alloc_append(RTEList<T>* rtelist) {
331 // get the first element
332 currentnode = firstnode.next;
333 // element->next points to itself which means last element
334 // return NULL to signal end of list
335 if (currentnode->next == currentnode) return NULL;
336
337 // now remove the element from the freelist
338 RTEList<T>::Node<T>* prevelem = currentnode->prev;
339 RTEList<T>::Node<T>* nextelem = currentnode->next;
340 prevelem->next = nextelem;
341 nextelem->prev = prevelem;
342
343 // append the element to the external rtelist
344 RTEList<T>::Node<T>* el_lastnode = (RTEList<T>::Node<T>*) &rtelist->lastnode;
345 RTEList<T>::Node<T>* last = el_lastnode->aprev;
346
347 last->anext = currentnode;
348 currentnode->anext = el_lastnode;
349 el_lastnode->aprev = currentnode;
350 currentnode->aprev = last;
351
352 // finally return the allocated elment
353 //printf("alloc_append returning elem=%d\n",&currentnode->data);
354 return &currentnode->data;
355 }
356
357 /**
358 * same as alloc_append but the element is inserted at the
359 * beginning of the list
360 */
361 inline T* alloc_prepend(RTEList<T>* rtelist) {
362 RTEList<T>::Node<T>* prevelem;
363 RTEList<T>::Node<T>* nextelem;
364 // get the first element
365 currentnode = firstnode.next;
366 // element->next points to itself which means last element
367 // return NULL to signal end of list
368 if (currentnode->next == currentnode) return NULL;
369
370 // now remove the element from the freelist
371 prevelem = currentnode->prev;
372 nextelem = currentnode->next;
373 prevelem->next = nextelem;
374 nextelem->prev = prevelem;
375
376 // prepend the element to the external rtelist
377 RTEList<T>::Node<T>* el_firstnode = (RTEList<T>::Node<T>*) &rtelist->firstnode;
378 RTEList<T>::Node<T>* first = el_firstnode->anext;
379
380 currentnode->anext = first;
381 currentnode->aprev = el_firstnode;
382 el_firstnode->anext = currentnode;
383 first->aprev = currentnode;
384
385 // finally return the allocated elment
386 return &currentnode->data;
387 }
388
389 inline void append(RTEList<T>::Node<T>* elem) {
390 RTEList<T>::Node<T>* last = lastnode.prev;
391
392 last->next = elem;
393 elem->next = &lastnode;
394 lastnode.prev = elem;
395 elem->prev = last;
396 }
397
398 inline void prepend(RTEList<T>::Node<T>* elem) {
399 RTEList<T>::Node<T>* first = firstnode.next;
400
401 elem->next = first;
402 elem->prev = &firstnode;
403 firstnode.next = elem;
404 first->prev = elem;
405 }
406
407 friend class RTEList<T>;
408
409 public:
410 /**
411 * Constructor
412 *
413 * @param numelements - number of elements this pool should offer
414 */
415 RTELMemoryPool(int numelements) : RTEList<T>::RTEList(this) {
416 // initialize freelist listnode and lastnode pointers
417 firstnode.prev = &firstnode;
418 firstnode.next = &lastnode;
419 lastnode.next = &lastnode;
420 lastnode.prev = &firstnode;
421
422 currentnode = &lastnode;
423
424 // initialize alloclist listnode and lastnode pointers
425 firstnode.aprev = &firstnode;
426 firstnode.anext = &lastnode;
427 lastnode.anext = &lastnode;
428 lastnode.aprev = &firstnode;
429
430
431 memory_pool = new RTEList<T>::Node<T>[numelements];
432
433 for (int i = 0; i < numelements; i++) {
434 append(&memory_pool[i]);
435 }
436 }
437
438 inline ~RTELMemoryPool() {
439 if (memory_pool) delete[] memory_pool;
440 }
441
442 /**
443 * Returns true if no more element can be allocated.
444 */
445 inline bool pool_is_empty() {
446 RTEList<T>::Node<T>* nextnode = firstnode.next;
447 return (nextnode->next == nextnode);
448 }
449
450 /**
451 * Allocate one element of the memory pool
452 * if no elements are free return NULL
453 * we find the first element of the list
454 * remove it from the free list and then
455 * return the data associated to the element
456 */
457 inline T* alloc() {
458 // get the first element
459 currentnode = firstnode.next;
460 // element->next points to itself which means last element
461 // return NULL to signal end of list
462 if (currentnode->next == currentnode) return NULL;
463
464 // now remove the element from the freelist
465 RTEList<T>::Node<T>* prevelem = currentnode->prev;
466 RTEList<T>::Node<T>* nextelem = currentnode->next;
467 prevelem->next = nextelem;
468 nextelem->prev = prevelem;
469
470 // append the element to the alloc list
471 RTEList<T>::Node<T>* last = lastnode.aprev;
472 last->anext = currentnode;
473 currentnode->anext = &lastnode;
474 lastnode.aprev = currentnode;
475 currentnode->aprev = last;
476
477 // finally return the allocated elment
478 return &currentnode->data;
479 }
480
481 /**
482 * Free an allocated element by putting it back to the freelist.
483 */
484 inline void free(T* element) {
485 RTEList<T>::Node<T>* prevelem;
486 RTEList<T>::Node<T>* nextelem;
487 RTEList<T>::Node<T>* node;
488
489 char* node_to_free = (char*) element;
490 // calculate the offset of the RTEListNode (see free_offset calculation in the constructor)
491 node_to_free -= free_offset;
492 // insert the node to the beginning of the freelist
493 node = (RTEList<T>::Node<T>*) node_to_free;
494 prepend(node);
495
496 // now remove the element from the alloclist
497 prevelem = node->aprev;
498 nextelem = node->anext;
499 prevelem->anext = nextelem;
500 nextelem->aprev = prevelem;
501 //printf("free returning elem=%d\n",&currentnode->data);
502 }
503
504 /**
505 * Frees all allocated elements in the internal allocation list.
506 * This method does not free elements allocated for external lists!
507 * For freeing elements allocated for external lists, use the empty()
508 * method of the respective RTEList object.
509 *
510 * @returns number of freed elements
511 */
512 inline int clear() {
513 RTEList<T>::Node<T>* nextnode;
514 RTEList<T>::Node<T>* prevelem;
515 RTEList<T>::Node<T>* nextelem;
516
517 int count = 0;
518
519 acurrentnode = firstnode.anext;
520 if (acurrentnode->anext == acurrentnode) return 0;
521
522 while (true) {
523 nextnode = acurrentnode->anext;
524
525 // prepend (insert at the beginning) the node to the freelist
526 //printf("empty: putting back elem (node) %d to freelist\n",acurrentnode);
527 prepend(acurrentnode); count++;
528
529 // now remove the element from the alloclist
530 prevelem = acurrentnode->aprev;
531 nextelem = acurrentnode->anext;
532 prevelem->anext = nextelem;
533 nextelem->aprev = prevelem;
534
535 if (nextnode->anext == nextnode) return count;
536 acurrentnode = nextnode;
537 }
538 }
539 };
540
541
542 #endif

  ViewVC Help
Powered by ViewVC