blob: ac7e00be3a12d2dedd46b42c05c31c6b3a01a855 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
/*
* libc/stdlib/malloc/heap_free.c -- return memory to a heap
*
* Copyright (C) 2002 NEC Corporation
* Copyright (C) 2002 Miles Bader <miles@gnu.org>
*
* This file is subject to the terms and conditions of the GNU Lesser
* General Public License. See the file COPYING.LIB in the main
* directory of this archive for more details.
*
* Written by Miles Bader <miles@gnu.org>
*/
#include <stdlib.h>
#include "heap.h"
/* Return the memory area MEM of size SIZE to HEAP. */
struct heap_free_area *
__heap_free (struct heap *heap, void *mem, size_t size)
{
struct heap_free_area *prev_fa, *fa, *new_fa;
void *end = (char *)mem + size;
__heap_lock (heap);
HEAP_DEBUG (heap, "before __heap_free");
/* Find an adjacent free-list entry. */
for (prev_fa = 0, fa = heap->free_areas; fa; prev_fa = fa, fa = fa->next)
{
size_t fa_size = fa->size;
void *fa_end = HEAP_FREE_AREA_END (fa);
void *fa_mem = HEAP_FREE_AREA_START (fa);
if (fa_mem == end)
/* FA is just after MEM, grow down to encompass it. */
{
fa_size += size;
/* See if FA can now be merged with its predecessor. */
if (prev_fa && fa_mem - size == HEAP_FREE_AREA_END (prev_fa))
/* Yup; merge PREV_FA's info into FA. */
{
struct heap_free_area *pp = prev_fa->prev;
fa_size += prev_fa->size;
if (pp)
pp->next = fa;
else
heap->free_areas = fa;
fa->prev = pp;
}
fa->size = fa_size;
goto done;
}
else if (fa_end == mem)
/* FA is just before MEM, expand to encompass it. */
{
struct heap_free_area *next_fa = fa->next;
fa_size += size;
/* See if FA can now be merged with its successor. */
if (next_fa && fa_end + size == HEAP_FREE_AREA_START (next_fa))
{
/* Yup; merge FA's info into NEXT_FA. */
fa_size += next_fa->size;
if (prev_fa)
prev_fa->next = next_fa;
else
heap->free_areas = next_fa;
next_fa->prev = prev_fa;
fa = next_fa;
}
else
/* FA can't be merged; move the descriptor for it to the tail-end
of the memory block. */
{
new_fa = (struct heap_free_area *)((char *)fa + size);
/* Update surrounding free-areas to point to FA's new address. */
if (prev_fa)
prev_fa->next = new_fa;
else
heap->free_areas = new_fa;
if (next_fa)
next_fa->prev = new_fa;
/* Fill in the moved descriptor. */
new_fa->prev = prev_fa;
new_fa->next = next_fa;
fa = new_fa;
}
fa->size = fa_size;
goto done;
}
else if (fa_mem > mem)
/* We've reached the right spot in the free-list without finding an
adjacent free-area, so add a new free area to hold MEM. */
break;
}
/* Make a new free-list entry. */
/* NEW_FA initially holds only MEM. */
new_fa = (struct heap_free_area *)
((char *)mem + size - sizeof (struct heap_free_area));
new_fa->size = size;
new_fa->next = fa;
new_fa->prev = prev_fa;
/* Insert NEW_FA in the free-list between PREV_FA and FA. */
if (prev_fa)
prev_fa->next = new_fa;
else
heap->free_areas = new_fa;
if (fa)
fa->prev = new_fa;
fa = new_fa;
done:
HEAP_DEBUG (heap, "after __heap_free");
__heap_unlock (heap);
return fa;
}
|
