summaryrefslogtreecommitdiff
path: root/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/pdbox/dbestfit-3.3/bmalloc.c')
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bmalloc.c740
1 files changed, 740 insertions, 0 deletions
diff --git a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c
new file mode 100644
index 0000000000..f95b4f6125
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c
@@ -0,0 +1,740 @@
1/*****************************************************************************
2 *
3 * Big (best-fit) Memory Allocation
4 *
5 * Author: Daniel Stenberg
6 * Date: March 5, 1997
7 * Version: 2.0
8 * Email: Daniel.Stenberg@sth.frontec.se
9 *
10 *
11 * Read 'thoughts' for theories and details in implementation.
12 *
13 * Routines meant to replace the most low level functions of an Operting
14 * System
15 *
16 * v2.0
17 * - Made all size-routines get moved out from this file. This way, the size
18 * functions can much more easily get replaced.
19 * - Improved how new memory blocks get added to the size-sorted list. When
20 * not adding new pools, there should never ever be any list traversing
21 * since all information is dynamically gathered.
22 *
23 ****************************************************************************/
24
25#include <stdio.h>
26#include <stdlib.h>
27
28#include "bysize.h"
29
30#ifndef TRUE
31#define TRUE 1
32#endif
33#ifndef FALSE
34#define FALSE 0
35#endif
36
37/* #define DEBUG */
38
39#define BMEM_ALIGN 64 /* resolution */
40
41#define BMEMERR_TOOSMALL -1
42
43/* this struct will be stored in all CHUNKS and AREAS */
44struct BlockInfo {
45 struct BlockInfo *lower; /* previous block in memory (lower address) */
46 struct BlockInfo *higher; /* next block in memory (higher address) */
47 unsigned long info; /* 31 bits size: 1 bit free boolean */
48#define INFO_FREE 1
49#define INFO_SIZE (~ INFO_FREE) /* inverted FREE bit pattern */
50
51 /* FREE+SIZE Could be written to use ordinary bitfields if using a smart
52 (like gcc) compiler in a manner like:
53 int size:31;
54 int free:1;
55
56 The 'higher' pointer COULD be removed completely if the size is used as
57 an index to the higher one. This would then REQUIRE the entire memory
58 pool to be contiguous and it needs a 'terminating' "node" or an extra
59 flag that informs about the end of the list.
60 */
61};
62
63/* the BLOCK list should be sorted in a lower to higher address order */
64struct BlockInfo *blockHead=NULL; /* nothing from the start */
65
66void print_lists(void);
67
68
69/***********************************************************************
70 *
71 * remove_block()
72 *
73 * Remove the block from the address-sorted list.
74 *
75 ***********************************************************************/
76
77void remove_block(struct BlockInfo *block)
78{
79 if(block->lower)
80 block->lower->higher = block->higher;
81 else
82 blockHead = block->higher;
83 if(block->higher)
84 block->higher->lower = block->lower;
85}
86
87/****************************************************************************
88 *
89 * add_blocktolists()
90 *
91 * Adds the specified block at the specified place in the address-sorted
92 * list and at the appropriate place in the size-sorted.
93 *
94 ***************************************************************************/
95void add_blocktolists(struct BlockInfo *block,
96 struct BlockInfo *newblock,
97 size_t newsize)
98{
99 struct BlockInfo *temp; /* temporary storage variable */
100 if(block) {
101 /* `block' is now a lower address than 'newblock' */
102
103 /*
104 * Check if the new CHUNK is wall-to-wall with the lower addressed
105 * one (if *that* is free)
106 */
107 if(block->info&INFO_FREE) {
108 if((char *)block + (block->info&INFO_SIZE) == (char *)newblock) {
109 /* yes sir, this is our lower address neighbour, enlarge that one
110 pick it out from the list and recursively add that chunk and
111 then we escape */
112
113 /* remove from size-sorted list: */
114 remove_chunksize((char*)block+sizeof(struct BlockInfo));
115
116 block->info += newsize; /* newsize is an even number and thus the FREE
117 bit is untouched */
118
119 remove_block(block); /* unlink the block address-wise */
120
121 /* recursively check our lower friend(s) */
122 add_blocktolists(block->lower, block, block->info&INFO_SIZE);
123 return;
124 }
125 }
126
127 temp = block->higher;
128
129 block->higher = newblock;
130 newblock->lower = block;
131 newblock->higher = temp;
132 if(newblock->higher)
133 newblock->higher->lower = newblock;
134 }
135 else {
136 /* this block should preceed the heading one */
137 temp = blockHead;
138
139 /* check if this is our higher addressed neighbour */
140 if((char *)newblock + newsize == (char *)temp) {
141
142 /* yes, we are wall-to-wall with the higher CHUNK */
143 if(temp->info&INFO_FREE) {
144 /* and the neighbour is even free, remove that one and enlarge
145 ourselves, call add_pool() recursively and then escape */
146
147 remove_block(temp); /* unlink 'temp' from list */
148
149 /* remove from size-sorted list: */
150 remove_chunksize((char*)temp+sizeof(struct BlockInfo) );
151
152 /* add the upper block's size on ourselves */
153 newsize += temp->info&INFO_SIZE;
154
155 /* add the new, bigger block */
156 add_blocktolists(block, newblock, newsize);
157 return;
158 }
159 }
160
161 blockHead = newblock;
162 newblock->higher = temp;
163 newblock->lower = NULL; /* there is no lower one */
164 if(newblock->higher)
165 newblock->higher->lower = newblock;
166 }
167
168 newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the
169 FREE bit */
170 insert_bysize((char *)newblock+sizeof(struct BlockInfo), newsize);
171}
172
173/***********************************************************************
174 *
175 * findblockbyaddr()
176 *
177 * Find the block that is just before the input block in memory. Returns NULL
178 * if none is.
179 *
180 ***********************************************************************/
181
182static struct BlockInfo *findblockbyaddr(struct BlockInfo *block)
183{
184 struct BlockInfo *test = blockHead;
185 struct BlockInfo *lower = NULL;
186
187 while(test && (test < block)) {
188 lower = test;
189 test = test->higher;
190 }
191 return lower;
192}
193
194/***********************************************************************
195 *
196 * add_pool()
197 *
198 * This function should be the absolutely first function to call. It sets up
199 * the memory bounds of the [first] CHUNK(s). It should be possible to call
200 * this function several times to add more CHUNKs to the pool of free
201 * memory. This allows the bmalloc system to deal with a non-contigous memory
202 * area.
203 *
204 * Returns non-zero if an error occured. The memory was not added then.
205 *
206 ***********************************************************************/
207
208int add_pool(void *start,
209 size_t size)
210{
211 struct BlockInfo *newblock = (struct BlockInfo *)start;
212 struct BlockInfo *block;
213
214 if(size < BMEM_ALIGN)
215 return BMEMERR_TOOSMALL;
216
217 block = findblockbyaddr( newblock );
218 /* `block' is now a lower address than 'newblock' or NULL */
219
220 if(size&1)
221 size--; /* only add even sizes */
222
223 add_blocktolists(block, newblock, size);
224
225 return 0;
226}
227
228
229#ifdef DEBUG
230static void bmalloc_failed(size_t size)
231{
232 printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
233 print_lists();
234}
235#else
236#define bmalloc_failed(x)
237#endif
238
239void print_lists()
240{
241 struct BlockInfo *block = blockHead;
242#if 1
243 printf("List of BLOCKS (in address order):\n");
244 while(block) {
245 printf(" START %p END %p SIZE %ld FLAG %s\n",
246 (char *)block,
247 (char *)block+(block->info&INFO_SIZE), block->info&INFO_SIZE,
248 (block->info&INFO_FREE)?"free":"used");
249 block = block->higher;
250 }
251 printf("End of BLOCKS:\n");
252#endif
253 print_sizes();
254}
255
256void *bmalloc(size_t size)
257{
258 void *mem;
259
260#ifdef DEBUG
261 {
262 static int count=0;
263 int realsize = size + sizeof(struct BlockInfo);
264 if(realsize%4096)
265 realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN;
266 printf("%d bmalloc(%d) [%d]\n", count++, size, realsize);
267 }
268#endif
269
270 size += sizeof(struct BlockInfo); /* add memory for our header */
271
272 if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be
273 changed if the BLOCKSIZE is not 2^X ! */
274 size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */
275
276 /* get a CHUNK from the list with this size */
277 mem = obtainbysize ( size );
278 if(mem) {
279 /* the memory block we have got is the "best-fit" and it is already
280 un-linked from the free list */
281
282 /* now do the math to get the proper block pointer */
283 struct BlockInfo *block= (struct BlockInfo *)
284 ((char *)mem - sizeof(struct BlockInfo));
285
286 block->info &= ~INFO_FREE;
287 /* not free anymore */
288
289 if( size != (block->info&INFO_SIZE)) {
290 /* split this chunk into two pieces and return the one that fits us */
291 size_t othersize = (block->info&INFO_SIZE) - size;
292
293 if(othersize > BMEM_ALIGN) {
294 /* prevent losing small pieces of memory due to weird alignments
295 of the memory pool */
296
297 block->info = size; /* set new size (leave FREE bit cleared) */
298
299 /* Add the new chunk to the lists: */
300 add_blocktolists(block,
301 (struct BlockInfo *)((char *)block + size),
302 othersize );
303 }
304 }
305
306 /* Return the memory our parent may use: */
307 return (char *)block+sizeof(struct BlockInfo);
308 }
309 else {
310 bmalloc_failed(size);
311 return NULL; /* can't find any memory, fail hard */
312 }
313 return NULL;
314}
315
316void bfree(void *ptr)
317{
318 struct BlockInfo *block = (struct BlockInfo *)
319 ((char *)ptr - sizeof(struct BlockInfo));
320 size_t size;
321
322 /* setup our initial higher and lower pointers */
323 struct BlockInfo *lower = block->lower;
324 struct BlockInfo *higher = block->higher;
325
326#ifdef DEBUG
327 static int freecount=0;
328 printf("%d bfree(%p)\n", freecount++, ptr);
329#endif
330
331 /* bind together lower addressed FREE CHUNKS */
332 if(lower && (lower->info&INFO_FREE) &&
333 ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) {
334 size = block->info&INFO_SIZE; /* original size */
335
336 /* remove from size-link: */
337 remove_chunksize((char *)lower+sizeof(struct BlockInfo));
338
339 remove_block(block); /* unlink from address list */
340 block = lower; /* new base area pointer */
341 block->info += size; /* append the new size (the FREE bit
342 will remain untouched) */
343
344 lower = lower->lower; /* new lower pointer */
345 }
346 /* bind together higher addressed FREE CHUNKS */
347 if(higher && (higher->info&INFO_FREE) &&
348 ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) {
349 /* append higher size, the FREE bit won't be affected */
350 block->info += (higher->info&INFO_SIZE);
351
352 /* unlink from size list: */
353 remove_chunksize((char *)higher+sizeof(struct BlockInfo));
354 remove_block(higher); /* unlink from address list */
355 higher = higher->higher; /* the new higher link */
356 block->higher = higher; /* new higher link */
357 }
358 block->info |= INFO_FREE; /* consider this FREE! */
359
360 block->lower = lower;
361 block->higher = higher;
362
363 insert_bysize((char *)block+sizeof(struct BlockInfo), block->info&INFO_SIZE);
364
365#ifdef DEBUG
366 print_lists();
367#endif
368
369}
370
371/*****************************************************************************
372 *
373 * Big (best-fit) Memory Allocation
374 *
375 * Author: Daniel Stenberg
376 * Date: March 5, 1997
377 * Version: 2.0
378 * Email: Daniel.Stenberg@sth.frontec.se
379 *
380 *
381 * Read 'thoughts' for theories and details in implementation.
382 *
383 * Routines meant to replace the most low level functions of an Operting
384 * System
385 *
386 * v2.0
387 * - Made all size-routines get moved out from this file. This way, the size
388 * functions can much more easily get replaced.
389 * - Improved how new memory blocks get added to the size-sorted list. When
390 * not adding new pools, there should never ever be any list traversing
391 * since all information is dynamically gathered.
392 *
393 ****************************************************************************/
394
395#include <stdio.h>
396#include <stdlib.h>
397
398#include "bysize.h"
399
400#ifndef TRUE
401#define TRUE 1
402#endif
403#ifndef FALSE
404#define FALSE 0
405#endif
406
407/* #define DEBUG */
408
409#define BMEM_ALIGN 64 /* resolution */
410
411#define BMEMERR_TOOSMALL -1
412
413/* this struct will be stored in all CHUNKS and AREAS */
414struct BlockInfo {
415 struct BlockInfo *lower; /* previous block in memory (lower address) */
416 struct BlockInfo *higher; /* next block in memory (higher address) */
417 unsigned long info; /* 31 bits size: 1 bit free boolean */
418#define INFO_FREE 1
419#define INFO_SIZE (~ INFO_FREE) /* inverted FREE bit pattern */
420
421 /* FREE+SIZE Could be written to use ordinary bitfields if using a smart
422 (like gcc) compiler in a manner like:
423 int size:31;
424 int free:1;
425
426 The 'higher' pointer COULD be removed completely if the size is used as
427 an index to the higher one. This would then REQUIRE the entire memory
428 pool to be contiguous and it needs a 'terminating' "node" or an extra
429 flag that informs about the end of the list.
430 */
431};
432
433/* the BLOCK list should be sorted in a lower to higher address order */
434struct BlockInfo *blockHead=NULL; /* nothing from the start */
435
436void print_lists(void);
437
438
439/***********************************************************************
440 *
441 * remove_block()
442 *
443 * Remove the block from the address-sorted list.
444 *
445 ***********************************************************************/
446
447void remove_block(struct BlockInfo *block)
448{
449 if(block->lower)
450 block->lower->higher = block->higher;
451 else
452 blockHead = block->higher;
453 if(block->higher)
454 block->higher->lower = block->lower;
455}
456
457/****************************************************************************
458 *
459 * add_blocktolists()
460 *
461 * Adds the specified block at the specified place in the address-sorted
462 * list and at the appropriate place in the size-sorted.
463 *
464 ***************************************************************************/
465void add_blocktolists(struct BlockInfo *block,
466 struct BlockInfo *newblock,
467 size_t newsize)
468{
469 struct BlockInfo *temp; /* temporary storage variable */
470 if(block) {
471 /* `block' is now a lower address than 'newblock' */
472
473 /*
474 * Check if the new CHUNK is wall-to-wall with the lower addressed
475 * one (if *that* is free)
476 */
477 if(block->info&INFO_FREE) {
478 if((char *)block + (block->info&INFO_SIZE) == (char *)newblock) {
479 /* yes sir, this is our lower address neighbour, enlarge that one
480 pick it out from the list and recursively add that chunk and
481 then we escape */
482
483 /* remove from size-sorted list: */
484 remove_chunksize((char*)block+sizeof(struct BlockInfo));
485
486 block->info += newsize; /* newsize is an even number and thus the FREE
487 bit is untouched */
488
489 remove_block(block); /* unlink the block address-wise */
490
491 /* recursively check our lower friend(s) */
492 add_blocktolists(block->lower, block, block->info&INFO_SIZE);
493 return;
494 }
495 }
496
497 temp = block->higher;
498
499 block->higher = newblock;
500 newblock->lower = block;
501 newblock->higher = temp;
502 if(newblock->higher)
503 newblock->higher->lower = newblock;
504 }
505 else {
506 /* this block should preceed the heading one */
507 temp = blockHead;
508
509 /* check if this is our higher addressed neighbour */
510 if((char *)newblock + newsize == (char *)temp) {
511
512 /* yes, we are wall-to-wall with the higher CHUNK */
513 if(temp->info&INFO_FREE) {
514 /* and the neighbour is even free, remove that one and enlarge
515 ourselves, call add_pool() recursively and then escape */
516
517 remove_block(temp); /* unlink 'temp' from list */
518
519 /* remove from size-sorted list: */
520 remove_chunksize((char*)temp+sizeof(struct BlockInfo) );
521
522 /* add the upper block's size on ourselves */
523 newsize += temp->info&INFO_SIZE;
524
525 /* add the new, bigger block */
526 add_blocktolists(block, newblock, newsize);
527 return;
528 }
529 }
530
531 blockHead = newblock;
532 newblock->higher = temp;
533 newblock->lower = NULL; /* there is no lower one */
534 if(newblock->higher)
535 newblock->higher->lower = newblock;
536 }
537
538 newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the
539 FREE bit */
540 insert_bysize((char *)newblock+sizeof(struct BlockInfo), newsize);
541}
542
543/***********************************************************************
544 *
545 * findblockbyaddr()
546 *
547 * Find the block that is just before the input block in memory. Returns NULL
548 * if none is.
549 *
550 ***********************************************************************/
551
552static struct BlockInfo *findblockbyaddr(struct BlockInfo *block)
553{
554 struct BlockInfo *test = blockHead;
555 struct BlockInfo *lower = NULL;
556
557 while(test && (test < block)) {
558 lower = test;
559 test = test->higher;
560 }
561 return lower;
562}
563
564/***********************************************************************
565 *
566 * add_pool()
567 *
568 * This function should be the absolutely first function to call. It sets up
569 * the memory bounds of the [first] CHUNK(s). It should be possible to call
570 * this function several times to add more CHUNKs to the pool of free
571 * memory. This allows the bmalloc system to deal with a non-contigous memory
572 * area.
573 *
574 * Returns non-zero if an error occured. The memory was not added then.
575 *
576 ***********************************************************************/
577
578int add_pool(void *start,
579 size_t size)
580{
581 struct BlockInfo *newblock = (struct BlockInfo *)start;
582 struct BlockInfo *block;
583
584 if(size < BMEM_ALIGN)
585 return BMEMERR_TOOSMALL;
586
587 block = findblockbyaddr( newblock );
588 /* `block' is now a lower address than 'newblock' or NULL */
589
590 if(size&1)
591 size--; /* only add even sizes */
592
593 add_blocktolists(block, newblock, size);
594
595 return 0;
596}
597
598
599#ifdef DEBUG
600static void bmalloc_failed(size_t size)
601{
602 printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
603 print_lists();
604}
605#else
606#define bmalloc_failed(x)
607#endif
608
609void print_lists()
610{
611 struct BlockInfo *block = blockHead;
612#if 1
613 printf("List of BLOCKS (in address order):\n");
614 while(block) {
615 printf(" START %p END %p SIZE %ld FLAG %s\n",
616 (char *)block,
617 (char *)block+(block->info&INFO_SIZE), block->info&INFO_SIZE,
618 (block->info&INFO_FREE)?"free":"used");
619 block = block->higher;
620 }
621 printf("End of BLOCKS:\n");
622#endif
623 print_sizes();
624}
625
626void *bmalloc(size_t size)
627{
628 void *mem;
629
630#ifdef DEBUG
631 {
632 static int count=0;
633 int realsize = size + sizeof(struct BlockInfo);
634 if(realsize%4096)
635 realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN;
636 printf("%d bmalloc(%d) [%d]\n", count++, size, realsize);
637 }
638#endif
639
640 size += sizeof(struct BlockInfo); /* add memory for our header */
641
642 if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be
643 changed if the BLOCKSIZE is not 2^X ! */
644 size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */
645
646 /* get a CHUNK from the list with this size */
647 mem = obtainbysize ( size );
648 if(mem) {
649 /* the memory block we have got is the "best-fit" and it is already
650 un-linked from the free list */
651
652 /* now do the math to get the proper block pointer */
653 struct BlockInfo *block= (struct BlockInfo *)
654 ((char *)mem - sizeof(struct BlockInfo));
655
656 block->info &= ~INFO_FREE;
657 /* not free anymore */
658
659 if( size != (block->info&INFO_SIZE)) {
660 /* split this chunk into two pieces and return the one that fits us */
661 size_t othersize = (block->info&INFO_SIZE) - size;
662
663 if(othersize > BMEM_ALIGN) {
664 /* prevent losing small pieces of memory due to weird alignments
665 of the memory pool */
666
667 block->info = size; /* set new size (leave FREE bit cleared) */
668
669 /* Add the new chunk to the lists: */
670 add_blocktolists(block,
671 (struct BlockInfo *)((char *)block + size),
672 othersize );
673 }
674 }
675
676 /* Return the memory our parent may use: */
677 return (char *)block+sizeof(struct BlockInfo);
678 }
679 else {
680 bmalloc_failed(size);
681 return NULL; /* can't find any memory, fail hard */
682 }
683 return NULL;
684}
685
686void bfree(void *ptr)
687{
688 struct BlockInfo *block = (struct BlockInfo *)
689 ((char *)ptr - sizeof(struct BlockInfo));
690 size_t size;
691
692 /* setup our initial higher and lower pointers */
693 struct BlockInfo *lower = block->lower;
694 struct BlockInfo *higher = block->higher;
695
696#ifdef DEBUG
697 static int freecount=0;
698 printf("%d bfree(%p)\n", freecount++, ptr);
699#endif
700
701 /* bind together lower addressed FREE CHUNKS */
702 if(lower && (lower->info&INFO_FREE) &&
703 ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) {
704 size = block->info&INFO_SIZE; /* original size */
705
706 /* remove from size-link: */
707 remove_chunksize((char *)lower+sizeof(struct BlockInfo));
708
709 remove_block(block); /* unlink from address list */
710 block = lower; /* new base area pointer */
711 block->info += size; /* append the new size (the FREE bit
712 will remain untouched) */
713
714 lower = lower->lower; /* new lower pointer */
715 }
716 /* bind together higher addressed FREE CHUNKS */
717 if(higher && (higher->info&INFO_FREE) &&
718 ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) {
719 /* append higher size, the FREE bit won't be affected */
720 block->info += (higher->info&INFO_SIZE);
721
722 /* unlink from size list: */
723 remove_chunksize((char *)higher+sizeof(struct BlockInfo));
724 remove_block(higher); /* unlink from address list */
725 higher = higher->higher; /* the new higher link */
726 block->higher = higher; /* new higher link */
727 }
728 block->info |= INFO_FREE; /* consider this FREE! */
729
730 block->lower = lower;
731 block->higher = higher;
732
733 insert_bysize((char *)block+sizeof(struct BlockInfo), block->info&INFO_SIZE);
734
735#ifdef DEBUG
736 print_lists();
737#endif
738
739}
740
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-12 17:47:26 +0000