/*
 * 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_free_area **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; 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;
}