libc/stdlib/malloc/heap_free.c

   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 *
  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 }