Branch data Line data Source code
1 : : /**
2 : : * \file This holds all stufff related our memory managent.
3 : : * I try the best as far as I can to reduce memory fragmentation
4 : : * and unneccessary calls to alloc and free.
5 : : *
6 : : * To achive this I try an approach described here as "Quick Fit".
7 : : * http://www.flounder.com/memory_allocation.htm
8 : : *
9 : : * The basic idea is to keep allocated memory segments and don't free
10 : : * them again. Instead I will put them in a tree indexed by their size.
11 : : * To get new memory I first have a look in the tree if there is
12 : : * a fitting memory segment. Fitting mean, larger or exactly the size
13 : : * I need. If there is one, use it. If not create a new one using
14 : : * usual malloc approach.
15 : : * I won't split the reagions at all because most likely they will be
16 : : * free soon again. This way I might waste some memory, so I have to
17 : : * keep an eye on this.
18 : : *
19 : : * Right now I don't build an upper limit for allocation. The limit
20 : : * still is the system memory itself.
21 : : *
22 : : * This is not implemented as a class because it will be used in the
23 : : * process of object creation.
24 : : *
25 : : * The data structure is a balanced tree with size as key.
26 : : * Under the size key is a list of elements of the same size.
27 : : *
28 : : * \author Georg Hopp
29 : : *
30 : : * \copyright
31 : : * Copyright © 2012 Georg Hopp
32 : : *
33 : : * This program is free software: you can redistribute it and/or modify
34 : : * it under the terms of the GNU General Public License as published by
35 : : * the Free Software Foundation, either version 3 of the License, or
36 : : * (at your option) any later version.
37 : : *
38 : : * This program is distributed in the hope that it will be useful,
39 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
40 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
41 : : * GNU General Public License for more details.
42 : : *
43 : : * You should have received a copy of the GNU General Public License
44 : : * along with this program. If not, see <http://www.gnu.org/licenses/>.
45 : : */
46 : :
47 : : #define _GNU_SOURCE
48 : :
49 : : #include <stdio.h>
50 : :
51 : : #include <stdlib.h>
52 : : #include <string.h>
53 : : #include <search.h>
54 : : #include <unistd.h>
55 : :
56 : : #include "utils/memory.h"
57 : : #include "tree.h"
58 : :
59 : :
60 : : struct memSegment
61 : : {
62 : : size_t ref_count;
63 : : size_t size;
64 : : void * ptr;
65 : :
66 : : enum rbColor color;
67 : :
68 : : struct memSegment * next;
69 : : struct memSegment * last;
70 : :
71 : : struct memSegment * parent;
72 : : struct memSegment * left;
73 : : struct memSegment * right;
74 : : };
75 : :
76 : : struct memSegment *
77 : 23 : newElement(size_t size)
78 : : {
79 : 23 : struct memSegment * element = malloc(size);
80 : :
81 : 23 : element->ref_count = 1;
82 : 23 : element->size = size;
83 : 23 : element->ptr = (void*)element + sizeof(struct memSegment);
84 : :
85 : 23 : element->next = NULL;
86 : 23 : element->last = NULL;
87 : :
88 : 23 : element->color = rbRed;
89 : 23 : element->parent = NULL;
90 : 23 : element->left = NULL;
91 : 23 : element->right = NULL;
92 : :
93 : 23 : return element;
94 : : }
95 : :
96 : : /**
97 : : * find element in tree
98 : : */
99 : : struct memSegment *
100 : 36 : findElement(struct memSegment * tree, size_t size)
101 : : {
102 : 36 : struct memSegment * fitting = NULL;
103 : :
104 : 78 : while (NULL != tree) {
105 : 17 : if (tree->size == size) {
106 : 11 : fitting = tree;
107 : 11 : break;
108 : : }
109 : :
110 : 6 : if (size > tree->size) {
111 : 2 : tree = tree->right;
112 : : } else {
113 : 4 : fitting = tree;
114 : 4 : tree = tree->left;
115 : : }
116 : : }
117 : :
118 : 36 : return fitting;
119 : : }
120 : :
121 : : /*
122 : : * function to get specific elements needed for
123 : : * rb handling, grandparent, uncle and sibbling
124 : : */
125 : : struct memSegment *
126 : 17 : grandparent(struct memSegment * node)
127 : : {
128 : 17 : if (NULL != node && NULL != node->parent) {
129 : 17 : return node->parent->parent;
130 : : }
131 : :
132 : 0 : return NULL;
133 : : }
134 : :
135 : : struct memSegment *
136 : 7 : uncle(struct memSegment * node)
137 : : {
138 : 7 : struct memSegment * gp = grandparent(node);
139 : :
140 : 7 : if (NULL == gp) {
141 : 0 : return NULL;
142 : : }
143 : :
144 : 7 : if (node->parent == gp->left) {
145 : 2 : return gp->right;
146 : : }
147 : :
148 : 5 : return gp->left;
149 : : }
150 : :
151 : : struct memSegment *
152 : 0 : sibling(struct memSegment * node)
153 : : {
154 : 0 : if (NULL == node) {
155 : 0 : return NULL;
156 : : }
157 : :
158 : 0 : if (NULL == node->parent->left || node == node->parent->left) {
159 : 0 : return node->parent->right;
160 : : } else {
161 : 0 : return node->parent->left;
162 : : }
163 : : }
164 : :
165 : : /*
166 : : * tree modifications...needed for rb handling.
167 : : */
168 : : void
169 : 3 : rotateLeft(struct memSegment ** tree, struct memSegment * node)
170 : : {
171 : 3 : struct memSegment * rightChild = node->right;
172 : 3 : struct memSegment * rcLeftSub = node->right->left;
173 : :
174 : 3 : rightChild->left = node;
175 : 3 : rightChild->parent = node->parent;
176 : 3 : node->right = rcLeftSub;
177 : 3 : if (NULL != rcLeftSub) {
178 : 0 : rcLeftSub->parent = node;
179 : : }
180 : :
181 : 3 : if (node->parent) {
182 : 2 : if (node->parent->left == node) {
183 : 1 : node->parent->left = rightChild;
184 : : } else {
185 : 1 : node->parent->right = rightChild;
186 : : }
187 : : } else {
188 : 1 : *tree = rightChild;
189 : : }
190 : :
191 : 3 : node->parent = rightChild;
192 : 3 : }
193 : :
194 : : void
195 : 0 : rotateRight(struct memSegment ** tree, struct memSegment * node)
196 : : {
197 : 0 : struct memSegment * leftChild = node->left;
198 : 0 : struct memSegment * lcRightSub = node->left->right;
199 : :
200 : 0 : leftChild->right = node;
201 : 0 : leftChild->parent = node->parent;
202 : 0 : node->left = lcRightSub;
203 : 0 : if (NULL != lcRightSub) {
204 : 0 : lcRightSub->parent = node;
205 : : }
206 : :
207 : 0 : if (node->parent) {
208 : 0 : if (node->parent->left == node) {
209 : 0 : node->parent->left = leftChild;
210 : : } else {
211 : 0 : node->parent->right = leftChild;
212 : : }
213 : : } else {
214 : 0 : *tree = leftChild;
215 : : }
216 : :
217 : 0 : node->parent = leftChild;
218 : 0 : }
219 : :
220 : : void
221 : 13 : replaceNode(
222 : : struct memSegment ** tree,
223 : : struct memSegment * node1,
224 : : struct memSegment * node2)
225 : : {
226 : 13 : if (NULL != node1->parent) {
227 : 2 : if (node1 == node1->parent->left) {
228 : 2 : node1->parent->left = node2;
229 : : } else {
230 : 0 : node1->parent->right = node2;
231 : : }
232 : : } else {
233 : 11 : *tree = node2;
234 : : }
235 : :
236 : 13 : if (NULL != node2) {
237 : 2 : node2->parent = node1->parent;
238 : : }
239 : 13 : }
240 : :
241 : :
242 : : /**
243 : : * insert element in tree
244 : : */
245 : : struct memSegment *
246 : 45 : insertElement(struct memSegment ** tree, struct memSegment * element)
247 : : {
248 : 45 : struct memSegment * node = *tree;
249 : 45 : struct memSegment * new_node = NULL;
250 : : struct memSegment * u;
251 : : struct memSegment * g;
252 : :
253 : 45 : element->next = NULL;
254 : 45 : element->last = NULL;
255 : :
256 : 45 : element->color = rbRed;
257 : 45 : element->parent = NULL;
258 : 45 : element->left = NULL;
259 : 45 : element->right = NULL;
260 : :
261 : : // if tree is empty it's simple... :)
262 : 45 : if (NULL == node) {
263 : 15 : *tree = node = new_node = element;
264 : : } else {
265 : : // normal binary tree add....
266 : 79 : while (NULL != node) {
267 : 49 : if (element->size < node->size) {
268 : 18 : if (NULL == node->left) {
269 : 7 : node->left = element;
270 : 7 : node->left->parent = node;
271 : 7 : new_node = node = node->left;
272 : 7 : break;
273 : : } else {
274 : 11 : node = node->left;
275 : : }
276 : 31 : } else if (element->size > node->size) {
277 : 18 : if (NULL == node->right) {
278 : 10 : node->right = element;
279 : 10 : node->right->parent = node;
280 : 10 : new_node = node = node->right;
281 : 10 : break;
282 : : } else {
283 : 8 : node = node->right;
284 : : }
285 : : } else {
286 : 13 : if (NULL == node->next) {
287 : 7 : node->next = element;
288 : 7 : node->last = element;
289 : : } else {
290 : 6 : node->last->next = element;
291 : 6 : node->last = element;
292 : : }
293 : 13 : return node;
294 : : }
295 : : }
296 : : }
297 : :
298 : 32 : if (NULL != new_node) {
299 : : /*
300 : : * handle reballancing rb style
301 : : */
302 : : while (1) {
303 : : // case 1
304 : 36 : if (node->parent == NULL) {
305 : 17 : node->color = rbBlack;
306 : : // we're done.... :)
307 : 17 : break;
308 : : }
309 : :
310 : : // case 2
311 : 19 : if (node->parent->color == rbBlack) {
312 : : // Tree is still valid ... wow, again we're done... :)
313 : 12 : break;
314 : : }
315 : :
316 : : // case 3
317 : 7 : u = uncle(node);
318 : 7 : g = grandparent(node);
319 : :
320 : 7 : if (u != NULL && u->color == rbRed) {
321 : 4 : node->parent->color = rbBlack;
322 : 4 : u->color = rbBlack;
323 : 4 : g->color = rbRed;
324 : :
325 : 4 : node = g;
326 : 4 : continue;
327 : : }
328 : :
329 : : // case 4
330 : 3 : if (node == node->parent->right && node->parent == g->left) {
331 : 0 : rotateLeft(tree, node->parent);
332 : 0 : node = node->left;
333 : 3 : } else if (node == node->parent->left && node->parent == g->right) {
334 : :
335 : 0 : rotateRight(tree, node->parent);
336 : 0 : node = node->right;
337 : : }
338 : :
339 : : // case 5
340 : 3 : g = grandparent(node);
341 : :
342 : 3 : node->parent->color = rbBlack;
343 : 3 : g->color = rbRed;
344 : :
345 : 3 : if (node == node->parent->left) {
346 : 0 : rotateRight(tree, g);
347 : : } else {
348 : 3 : rotateLeft(tree, g);
349 : : }
350 : :
351 : : // we're done..
352 : 3 : break;
353 : 4 : }
354 : : }
355 : :
356 : 32 : return new_node;
357 : : }
358 : :
359 : : /**
360 : : * delete element from tree
361 : : * here multiple functions are involved....
362 : : * =======================================================================
363 : : */
364 : : /**
365 : : * find minimum of the right subtree aka leftmost leaf of right subtree
366 : : * aka left in-order successor.
367 : : * We return the parent of the element in the out argument parent.
368 : : * This can be NULL wenn calling.
369 : : *
370 : : * 2: *successor = {size = 80, ptr = 0x603ae0, color = rbRed, parent = 0x603160,
371 : : * left = 0x0, right = 0x0}
372 : : * 1: *node = {size = 70, ptr = 0x603a60, color = rbBlack, parent = 0x603070,
373 : : * left = 0x6030e0, right = 0x6031e0}
374 : : *
375 : : */
376 : : struct memSegment *
377 : 0 : findInOrderSuccessor(struct memSegment * tree)
378 : : {
379 : 0 : struct memSegment * node = tree->right;
380 : :
381 : 0 : while (NULL != node->left) {
382 : 0 : node = node->left;
383 : : }
384 : :
385 : 0 : return node;
386 : : }
387 : :
388 : : struct memSegment *
389 : 13 : deleteElement(struct memSegment ** tree, struct memSegment * element)
390 : : {
391 : 13 : struct memSegment * node = *tree;
392 : : struct memSegment * del_node;
393 : : struct memSegment * child;
394 : : struct memSegment * s;
395 : :
396 : : // find the relevant node and it's parent
397 : 28 : while (NULL != node) {
398 : :
399 : 15 : if (element->size < node->size) {
400 : 2 : node = node->left;
401 : 13 : } else if (element->size > node->size) {
402 : 0 : node = node->right;
403 : : } else {
404 : 13 : if (NULL != node->next) {
405 : 0 : if (NULL != node->parent) {
406 : 0 : if (node == node->parent->left) {
407 : 0 : node->parent->left = node->next;
408 : : } else {
409 : 0 : node->parent->right = node->next;
410 : : }
411 : : } else {
412 : 0 : *tree = node->next;
413 : : }
414 : :
415 : 0 : if (NULL != node->left) {
416 : 0 : node->left->parent = node->next;
417 : : }
418 : :
419 : 0 : if (NULL != node->right) {
420 : 0 : node->right->parent = node->next;
421 : : }
422 : :
423 : 0 : node->next->last = node->last;
424 : 0 : node->next->color = node->color;
425 : 0 : node->next->parent = node->parent;
426 : 0 : node->next->left = node->left;
427 : 0 : node->next->right = node->right;
428 : :
429 : 0 : return node;
430 : : }
431 : 13 : break;
432 : : }
433 : : }
434 : :
435 : : // element not found
436 : 13 : if (NULL == node) {
437 : 0 : return node;
438 : : }
439 : :
440 : 13 : del_node = node;
441 : :
442 : : // now our cases follows...the first one is the same as with
443 : : // simple binary search trees. Two non null children.
444 : :
445 : : // case 1: two children
446 : 13 : if (NULL != node->left && NULL != node->right) {
447 : 0 : struct memSegment * successor = findInOrderSuccessor(node);
448 : :
449 : 0 : enum rbColor tmpcolor = successor->color;
450 : 0 : struct memSegment * tmpparent = successor->parent;
451 : 0 : struct memSegment * tmpleft = successor->left;
452 : 0 : struct memSegment * tmpright = successor->right;
453 : :
454 : 0 : replaceNode(tree, node, successor);
455 : :
456 : 0 : successor->color = node->color;
457 : 0 : successor->left = node->left;
458 : 0 : successor->left->parent = successor;
459 : : // the right one might be successor...
460 : 0 : if (node->right == successor) {
461 : 0 : successor->right = node;
462 : 0 : node->parent = successor;
463 : : } else {
464 : 0 : successor->right = node->right;
465 : 0 : node->right->parent = successor;
466 : 0 : node->parent = tmpparent;
467 : 0 : tmpparent->left = node;
468 : : }
469 : :
470 : 0 : node->color = tmpcolor;
471 : 0 : node->left = tmpleft;
472 : 0 : node->right = tmpright;
473 : : }
474 : :
475 : : // Precondition: n has at most one non-null child.
476 : 13 : child = (NULL == node->right) ? node->left : node->right;
477 : 13 : replaceNode(tree, node, child);
478 : :
479 : : // delete one child case
480 : : // TODO this is overly complex as simply derived from the function...
481 : : // maybe this can be simplified. Maybe not...check.
482 : 13 : if (node->color == rbBlack) {
483 : 11 : if (NULL != child && child->color == rbRed) {
484 : 2 : child->color = rbBlack;
485 : : // done despite modifying tree itself if neccessary..
486 : 2 : return del_node;
487 : : } else {
488 : 9 : if (NULL != child) {
489 : 0 : node = child;
490 : : } else {
491 : 9 : node->color = rbBlack;
492 : 9 : node->left = NULL;
493 : 9 : node->right = NULL;
494 : : }
495 : : }
496 : : } else {
497 : 2 : return del_node;
498 : : }
499 : :
500 : : // delete and rb rebalance...
501 : : while(1) {
502 : : // case 1
503 : 9 : if (NULL == node->parent) {
504 : : // done again
505 : 9 : break;
506 : : }
507 : :
508 : : // case 2
509 : 0 : s = sibling(node);
510 : :
511 : 0 : if (NULL != s && s->color == rbRed) {
512 : 0 : node->parent->color = rbRed;
513 : 0 : s->color = rbBlack;
514 : :
515 : : /*
516 : : * detect which child we are...assumption
517 : : * if we are not parent->right and parent->right is not
518 : : * null we must be left, even if its set to NULL previously
519 : : */
520 : 0 : if (NULL != node->parent->right && node != node->parent->right) {
521 : 0 : rotateLeft(tree, node->parent);
522 : : } else {
523 : 0 : rotateRight(tree, node->parent);
524 : : }
525 : : }
526 : :
527 : 0 : s = sibling(node);
528 : : // case 3 / 4
529 : 0 : if (NULL == s || ((s->color == rbBlack) &&
530 : 0 : (NULL == s->left || s->left->color == rbBlack) &&
531 : 0 : (NULL == s->right || s->right->color == rbBlack))) {
532 : :
533 : 0 : if (NULL != s) {
534 : 0 : s->color = rbRed;
535 : : }
536 : :
537 : 0 : if (node->parent->color == rbBlack) {
538 : : // case 3
539 : 0 : node = node->parent;
540 : 0 : continue;
541 : : } else {
542 : : // case 4
543 : 0 : node->parent->color = rbBlack;
544 : : // and done again...
545 : 0 : break;
546 : : }
547 : : }
548 : :
549 : : // case 5
550 : 0 : if (NULL != s && s->color == rbBlack) {
551 : : // this if statement is trivial,
552 : : // due to case 2 (even though case 2 changed the sibling to a
553 : : // sibling's child,
554 : : // the sibling's child can't be red, since no red parent can
555 : : // have a red child).
556 : : //
557 : : // the following statements just force the red to be on the
558 : : // left of the left of the parent,
559 : : // or right of the right, so case 6 will rotate correctly.
560 : 0 : if ((node == node->parent->left) &&
561 : 0 : (NULL == s->right || s->right->color == rbBlack) &&
562 : 0 : (NULL != s->left && s->left->color == rbRed)) {
563 : :
564 : : // this last test is trivial too due to cases 2-4.
565 : 0 : s->color = rbRed;
566 : 0 : s->left->color = rbBlack;
567 : :
568 : 0 : rotateRight(tree, s);
569 : 0 : } else if ((node == node->parent->right) &&
570 : 0 : (NULL == s->left || s->left->color == rbBlack) &&
571 : 0 : (NULL != s->right && s->right->color == rbRed)) {
572 : : // this last test is trivial too due to cases 2-4.
573 : 0 : s->color = rbRed;
574 : 0 : s->right->color = rbBlack;
575 : :
576 : 0 : rotateLeft(tree, s);
577 : : }
578 : : }
579 : :
580 : 0 : s = sibling(node);
581 : : // case 6
582 : 0 : if (NULL != s) {
583 : 0 : s->color = node->parent->color;
584 : : }
585 : :
586 : 0 : if (NULL != node && NULL != node->parent) {
587 : 0 : node->parent->color = rbBlack;
588 : :
589 : : /*
590 : : * detect which child we are...assumption
591 : : * if we are not parent->right and parent->right is not
592 : : * null we must be left, even if its set to NULL previously
593 : : */
594 : 0 : if (NULL != node->parent->right && node != node->parent->right) {
595 : 0 : if (NULL != s->right) {
596 : 0 : s->right->color = rbBlack;
597 : : }
598 : 0 : rotateLeft(tree, node->parent);
599 : : } else {
600 : 0 : if (NULL != s->left) {
601 : 0 : s->left->color = rbBlack;
602 : : }
603 : 0 : rotateRight(tree, node->parent);
604 : : }
605 : : }
606 : :
607 : : // done...
608 : 0 : break;
609 : 0 : }
610 : :
611 : 9 : return del_node;
612 : : }
613 : :
614 : :
615 : : void
616 : 0 : traverse(struct memSegment * tree, void (*cb)(struct memSegment *, int))
617 : : {
618 : 0 : struct memSegment * previous = tree;
619 : 0 : struct memSegment * node = tree;
620 : 0 : int depth = 1;
621 : :
622 : : /*
623 : : * I think this has something like O(n+log(n)) on a ballanced
624 : : * tree because I have to traverse back the rightmost leaf to
625 : : * the root to get a break condition.
626 : : */
627 : 0 : while (node) {
628 : : /*
629 : : * If we come from the right so nothing and go to our
630 : : * next parent.
631 : : */
632 : 0 : if (previous == node->right) {
633 : 0 : previous = node;
634 : 0 : node = node->parent;
635 : 0 : depth--;
636 : 0 : continue;
637 : : }
638 : :
639 : 0 : if ((NULL == node->left || previous == node->left)) {
640 : : /*
641 : : * If there are no more elements to the left or we
642 : : * came from the left, process data.
643 : : */
644 : 0 : cb(node, depth);
645 : 0 : previous = node;
646 : :
647 : 0 : if (NULL != node->right) {
648 : 0 : node = node->right;
649 : 0 : depth++;
650 : : } else {
651 : 0 : node = node->parent;
652 : 0 : depth--;
653 : : }
654 : : } else {
655 : : /*
656 : : * if there are more elements to the left go there.
657 : : */
658 : 0 : previous = node;
659 : 0 : node = node->left;
660 : 0 : depth++;
661 : : }
662 : : }
663 : 0 : }
664 : :
665 : : void
666 : 0 : post(struct memSegment * tree, void (*cb)(struct memSegment *, int))
667 : : {
668 : 0 : struct memSegment * previous = tree;
669 : 0 : struct memSegment * node = tree;
670 : 0 : int depth = 1;
671 : :
672 : : /*
673 : : * I think this has something like O(n+log(n)) on a ballanced
674 : : * tree because I have to traverse back the rightmost leaf to
675 : : * the root to get a break condition.
676 : : */
677 : 0 : while (node) {
678 : : /*
679 : : * If we come from the right so nothing and go to our
680 : : * next parent.
681 : : */
682 : 0 : if (((NULL == node->left || previous == node->left)
683 : 0 : && NULL == node->right)
684 : 0 : || previous == node->right) {
685 : :
686 : 0 : struct memSegment * parent = node->parent;
687 : :
688 : 0 : cb(node, depth);
689 : :
690 : 0 : previous = node;
691 : 0 : node = parent;
692 : 0 : depth--;
693 : 0 : continue;
694 : : }
695 : :
696 : 0 : if ((NULL == node->left || previous == node->left)) {
697 : : /*
698 : : * If there are no more elements to the left or we
699 : : * came from the left, process data.
700 : : */
701 : 0 : previous = node;
702 : :
703 : 0 : if (NULL != node->right) {
704 : 0 : node = node->right;
705 : 0 : depth++;
706 : : } else {
707 : 0 : node = node->parent;
708 : 0 : depth--;
709 : : }
710 : : } else {
711 : : /*
712 : : * if there are more elements to the left go there.
713 : : */
714 : 0 : previous = node;
715 : 0 : node = node->left;
716 : 0 : depth++;
717 : : }
718 : : }
719 : 0 : }
720 : :
721 : 0 : void printElement(struct memSegment * node, int depth)
722 : : {
723 : : int i;
724 : :
725 : 0 : printf("%s %010zu:%p(%02d)",
726 : 0 : (node->color==rbRed)?"R":"B",
727 : : node->size,
728 : : node->ptr,
729 : : depth);
730 : 0 : for (i=0; i<depth; i++) printf("-");
731 : 0 : puts("");
732 : :
733 : 0 : node = node->next;
734 : 0 : while (NULL != node) {
735 : 0 : printf(" %s %010zu:%p(%02d)",
736 : 0 : (node->color==rbRed)?"R":"B",
737 : : node->size,
738 : : node->ptr,
739 : : depth);
740 : 0 : for (i=0; i<depth; i++) printf("-");
741 : 0 : puts("");
742 : 0 : node = node->next;
743 : : }
744 : 0 : }
745 : :
746 : : void
747 : 0 : cleanup(struct memSegment * node, int depth)
748 : : {
749 : 0 : while (NULL != node) {
750 : 0 : struct memSegment * next = node->next;
751 : 0 : free(node);
752 : 0 : node = next;
753 : : }
754 : 0 : }
755 : :
756 : : struct memSegment * segments = NULL;
757 : :
758 : : static
759 : : void
760 : 0 : segmentFree(struct memSegment * segment, int depth)
761 : : {
762 : 0 : while (NULL != segment) {
763 : 0 : struct memSegment * next = segment->next;
764 : 0 : free(segment);
765 : 0 : segment = next;
766 : : }
767 : 0 : }
768 : :
769 : : void *
770 : 0 : memNewRef(void * mem)
771 : : {
772 : 0 : struct memSegment * seg = (mem - sizeof(struct memSegment));
773 : :
774 : 0 : seg->ref_count++;
775 : :
776 : 0 : return mem;
777 : : }
778 : :
779 : : /*
780 : : * This will always allocate a multiple of PAGESIZE
781 : : */
782 : : void *
783 : 36 : memMalloc(size_t size)
784 : : {
785 : 36 : struct memSegment * seg = NULL;
786 : : //long psize = sysconf(_SC_PAGESIZE);
787 : 36 : long psize = 64;
788 : :
789 : 36 : size += sizeof(struct memSegment);
790 : :
791 : : /* allocate only blocks of a multiple of pagesize, similar to cbuf */
792 : 36 : size = (0>=size)?1:(0!=size%psize)?(size/psize)+1:size/psize;
793 : 36 : size *= psize;
794 : :
795 : : #ifdef MEM_OPT
796 : 36 : seg = findElement(segments, size);
797 : : #endif
798 : :
799 : 36 : if (NULL == seg) {
800 : 23 : seg = newElement(size);
801 : : } else {
802 : : // remove the found one from the tree as we use it now.
803 : 13 : seg = deleteElement(&segments, seg);
804 : : }
805 : :
806 : 36 : return seg->ptr;
807 : : }
808 : :
809 : : /**
810 : : * this is a really memory wasting solution....just to be able to
811 : : * use calloc, which might be faster then malloc/memset solution.
812 : : *
813 : : * Maybe this is a bad idea, as we need to memset the buffer anyway
814 : : * if it comes from our tree, which hopefully should be the majority
815 : : * of cases.
816 : : */
817 : : void *
818 : 26 : memCalloc(size_t nmemb, size_t size)
819 : : {
820 : 26 : size_t _size = nmemb * size;
821 : 26 : void * mem = memMalloc(_size);
822 : :
823 : 26 : memset(mem, 0, _size);
824 : :
825 : 26 : return mem;
826 : : }
827 : :
828 : : void
829 : 45 : memFree(void ** mem)
830 : : {
831 : 45 : if (NULL != *mem) {
832 : 45 : struct memSegment * seg = (*mem - sizeof(struct memSegment));
833 : :
834 : 45 : if (1 < seg->ref_count) {
835 : 0 : seg->ref_count--;
836 : : } else {
837 : : #ifdef MEM_OPT
838 : 45 : insertElement(&segments, seg);
839 : : #else
840 : : free(seg);
841 : : #endif
842 : : }
843 : :
844 : 45 : *mem = NULL;
845 : : }
846 : 45 : }
847 : :
848 : : size_t
849 : 0 : memGetSize(void * mem)
850 : : {
851 : : struct memSegment * segment;
852 : :
853 : 0 : if (NULL == mem) {
854 : 0 : return 0;
855 : : }
856 : :
857 : 0 : segment = (struct memSegment *)(mem - sizeof(struct memSegment));
858 : 0 : return segment->size;
859 : : }
860 : :
861 : : void
862 : 0 : memCleanup()
863 : : {
864 : : #ifdef MEM_OPT
865 : 0 : post(segments, segmentFree);
866 : : #endif
867 : 0 : }
868 : :
869 : : // vim: set ts=4 sw=4:
|