1 /*
2 * libc/stdlib/malloc/heap_free.c -- return memory to a heap
3 *
4 * Copyright (C) 2002 NEC Corporation
5 * Copyright (C) 2002 Miles Bader <miles@gnu.org>
6 *
7 * This file is subject to the terms and conditions of the GNU Lesser
8 * General Public License. See the file COPYING.LIB in the main
9 * directory of this archive for more details.
10 *
11 * Written by Miles Bader <miles@gnu.org>
12 */
13
14 #include <stdlib.h>
15
16 #include "heap.h"
17
18
19 /* Return the block of memory at MEM, of size SIZE, to HEAP. */
20 struct heap_free_area *
__heap_free(struct heap_free_area ** heap,void * mem,size_t size)21 __heap_free (struct heap_free_area **heap, void *mem, size_t size)
22 {
23 struct heap_free_area *fa, *prev_fa;
24 void *end = (char *)mem + size;
25
26 HEAP_DEBUG (*heap, "before __heap_free");
27
28 /* Find the right position in the free-list entry to place the new block.
29 This is the most speed critical loop in this malloc implementation:
30 since we use a simple linked-list for the free-list, and we keep it in
31 address-sorted order, it can become very expensive to insert something
32 in the free-list when it becomes fragmented and long. [A better
33 implemention would use a balanced tree or something for the free-list,
34 though that bloats the code-size and complexity quite a bit.] */
35 for (prev_fa = 0, fa = *heap; fa; prev_fa = fa, fa = fa->next)
36 if (unlikely (HEAP_FREE_AREA_END (fa) >= mem))
37 break;
38
39 if (fa && HEAP_FREE_AREA_START (fa) <= end)
40 /* The free-area FA is adjacent to the new block, merge them. */
41 {
42 size_t fa_size = fa->size + size;
43
44 if (HEAP_FREE_AREA_START (fa) == end)
45 /* FA is just after the new block, grow down to encompass it. */
46 {
47 /* See if FA can now be merged with its predecessor. */
48 if (prev_fa && mem == HEAP_FREE_AREA_END (prev_fa))
49 /* Yup; merge PREV_FA's info into FA. */
50 {
51 fa_size += prev_fa->size;
52 __heap_link_free_area_after (heap, fa, prev_fa->prev);
53 }
54 }
55 else
56 /* FA is just before the new block, expand to encompass it. */
57 {
58 struct heap_free_area *next_fa = fa->next;
59
60 /* See if FA can now be merged with its successor. */
61 if (next_fa && end == HEAP_FREE_AREA_START (next_fa))
62 /* Yup; merge FA's info into NEXT_FA. */
63 {
64 fa_size += next_fa->size;
65 __heap_link_free_area_after (heap, next_fa, prev_fa);
66 fa = next_fa;
67 }
68 else
69 /* FA can't be merged; move the descriptor for it to the tail-end
70 of the memory block. */
71 {
72 /* The new descriptor is at the end of the extended block,
73 SIZE bytes later than the old descriptor. */
74 fa = (struct heap_free_area *)((char *)fa + size);
75 /* Update links with the neighbors in the list. */
76 __heap_link_free_area (heap, fa, prev_fa, next_fa);
77 }
78 }
79
80 fa->size = fa_size;
81 }
82 else
83 /* Make the new block into a separate free-list entry. */
84 fa = __heap_add_free_area (heap, mem, size, prev_fa, fa);
85
86 HEAP_DEBUG (*heap, "after __heap_free");
87
88 return fa;
89 }
90