* 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 "heap.h"
-/* Return the memory area MEM of size SIZE to HEAP. */
-void
+/* 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 *prev_fa, *fa, *new_fa;
+ struct heap_free_area *fa, *prev_fa;
void *end = (char *)mem + size;
- __heap_lock (heap);
-
HEAP_DEBUG (heap, "before __heap_free");
- /* Find an adjacent free-list entry. */
+ /* 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;
- void *fa_end = HEAP_FREE_AREA_END (fa);
- void *fa_mem = HEAP_FREE_AREA_START (fa);
+ size_t fa_size = fa->size + size;
- if (fa_mem == end)
- /* FA is just after MEM, grow down to encompass it. */
+ if (HEAP_FREE_AREA_START (fa) == end)
+ /* FA is just after the new block, 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))
+ if (prev_fa && mem == 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;
+ __heap_link_free_area_after (heap, fa, prev_fa->prev);
}
-
- fa->size = fa_size;
-
- goto done;
}
- else if (fa_end == mem)
- /* FA is just before MEM, expand to encompass it. */
+ else
+ /* FA is just before the new block, 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))
+ if (next_fa && end == HEAP_FREE_AREA_START (next_fa))
+ /* Yup; merge FA's info into 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;
+ __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. */
{
- 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;
+ /* 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;
-
- 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;
+ fa->size = fa_size;
+ }
else
- heap->free_areas = new_fa;
- if (fa)
- fa->prev = new_fa;
+ /* Make the new block into a separate free-list entry. */
+ fa = __heap_add_free_area (heap, mem, size, prev_fa, fa);
- done:
HEAP_DEBUG (heap, "after __heap_free");
- __heap_unlock (heap);
+ return fa;
}
OSDN Git Service
