| 1 |
1325 |
phoenix |
/*
|
| 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 *
|
| 21 |
|
|
__heap_free (struct heap *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->free_areas; 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 |
|
|
}
|
