/[svn]/linuxsampler/trunk/src/rtelmemorypool.h
ViewVC logotype

Contents of /linuxsampler/trunk/src/rtelmemorypool.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 15 - (show annotations) (download) (as text)
Sun Nov 23 21:16:49 2003 UTC (20 years, 4 months ago) by schoenebeck
File MIME type: text/x-c++hdr
File size: 14086 byte(s)
* rewrote sustain pedal handling: instead of just queuing the note-offs I
  added a sustain pointer for each midi key which starts to point to the
  first active voice on the respective key and increments to the next voice
  on the key when a note-off arrived, the release velocity value will
  immediately be stored in the respective voice object (this also fixes the
  segmentation fault issue when the sustain pool was full)

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 typedef RTEListNode* NodeHandle;
92
93 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 /// 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 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
408 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 /// 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 // 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

  ViewVC Help
Powered by ViewVC