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
|
/*
* 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 block of memory at MEM, of size SIZE, to HEAP. */
struct heap_free_area *
__heap_free (struct heap *heap, void *mem, size_t size)
{
struct heap_free_area *fa, *prev_fa;
void *end = (char *)mem + size;
HEAP_DEBUG (heap, "before __heap_free");
/* Find the right position in the free-list entry to place the new block.
This is the most speed critical loop in this malloc implementation:
since we use a simple linked-list for the free-list, and we keep it in
address-sorted order, it can become very expensive to insert something
in the free-list when it becomes fragmented and long. [A better
implemention would use a balanced tree or something for the free-list,
though that bloats the code-size and complexity quite a bit.] */
for (prev_fa = 0, fa = heap->free_areas; fa; prev_fa = fa, fa = fa->next)
if (unlikely (HEAP_FREE_AREA_END (fa) >= mem))
break;
if (fa && HEAP_FREE_AREA_START (fa) <= end)
/* The free-area FA is adjacent to the new block, merge them. */
{
size_t fa_size = fa->size + size;
if (HEAP_FREE_AREA_START (fa) == end)
/* FA is just after the new block, grow down to encompass it. */
{
/* See if FA can now be merged with its predecessor. */
if (prev_fa && mem == HEAP_FREE_AREA_END (prev_fa))
/* Yup; merge PREV_FA's info into FA. */
{
fa_size += prev_fa->size;
__heap_link_free_area_after (heap, fa, prev_fa->prev);
}
}
else
/* FA is just before the new block, expand to encompass it. */
{
struct heap_free_area *next_fa = fa->next;
/* See if FA can now be merged with its successor. */
if (next_fa && end == HEAP_FREE_AREA_START (next_fa))
/* Yup; merge FA's info into NEXT_FA. */
{
fa_size += next_fa->size;
__heap_link_free_area_after (heap, next_fa, prev_fa);
fa = next_fa;
}
else
/* FA can't be merged; move the descriptor for it to the tail-end
of the memory block. */
{
/* The new descriptor is at the end of the extended block,
SIZE bytes later than the old descriptor. */
fa = (struct heap_free_area *)((char *)fa + size);
/* Update links with the neighbors in the list. */
__heap_link_free_area (heap, fa, prev_fa, next_fa);
}
}
fa->size = fa_size;
}
else
/* Make the new block into a separate free-list entry. */
fa = __heap_add_free_area (heap, mem, size, prev_fa, fa);
HEAP_DEBUG (heap, "after __heap_free");
return fa;
}
|
