/* Free a block of memory allocated by `malloc'.
   Copyright 1990, 1991, 1992, 1994 Free Software Foundation, Inc.
		  Written May 1989 by Mike Haertel.

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Library General Public License for more details.

You should have received a copy of the GNU Library General Public
License along with this library; see the file COPYING.LIB.  If
not, write to the Free Software Foundation, Inc., 675 Mass Ave,
Cambridge, MA 02139, USA.

   The author may be reached (Email) at the address mike@ai.mit.edu,
   or (US mail) as Mike Haertel c/o Free Software Foundation.  */

#ifndef	_MALLOC_INTERNAL
#define _MALLOC_INTERNAL
#include "malloc.h"
#endif
#include <priv_syscalls.h>

#define	RNDPAGEDWN(i)	((char *)((uint)(i) & ~0xfff))
#define RNDPAGEUP(i)	((char *)(((uint)(i) + 0xfff) & ~0xfff))

void _gnu_free (void *ptr, malloc_state *ms, malloc_funcs *mf);

/* Return memory to the heap.
   Like `free' but don't call a __free_hook if there is one.  */
void
_free_internal (void *ptr, malloc_state *ms, malloc_funcs *mf)
{
  int type;
  size_t block, blocks;
  register size_t i;
  struct list *prev, *next;
  char *s, *e;
  size_t n;

  block = BLOCK (ptr);
  
  type = ms->_heapinfo[block].busy.type;
  switch (type)
    {
    case 0:
      /* Get as many statistics as early as we can.  */
      --ms->_chunks_used;
      ms->_bytes_used -= ms->_heapinfo[block].busy.info.size * BLOCKSIZE;
      ms->_bytes_free += ms->_heapinfo[block].busy.info.size * BLOCKSIZE;

      /* Find the free cluster previous to this one in the free list.
	 Start searching at the last block referenced; this may benefit
	 programs with locality of allocation.  */
      i = ms->_heapindex;
      if (i > block)
	while (i > block)
	  i = ms->_heapinfo[i].free.prev;
      else
	{
	  do
	    i = ms->_heapinfo[i].free.next;
	  while (i > 0 && i < block);
	  i = ms->_heapinfo[i].free.prev;
	}

	s = RNDPAGEUP((char *)ptr);
	e = RNDPAGEDWN((char *)ptr + ms->_heapinfo[block].busy.info.size * BLOCKSIZE);

      /* Determine how to link this block into the free list.  */
      if (block == i + ms->_heapinfo[i].free.size)
	{
	  if (RNDPAGEDWN((char *)ADDRESS(i)) !=
	  RNDPAGEDWN((char *)ADDRESS(i) + ms->_heapinfo[i].free.size * BLOCKSIZE))
		s = RNDPAGEDWN((char *)ADDRESS(i) + ms->_heapinfo[i].free.size * BLOCKSIZE);

	  /* Coalesce this block with its predecessor.  */
	  ms->_heapinfo[i].free.size += ms->_heapinfo[block].busy.info.size;
	  block = i;
	}
      else
	{
	  /* Really link this block back into the free list.  */
	  ms->_heapinfo[block].free.size = ms->_heapinfo[block].busy.info.size;
	  ms->_heapinfo[block].free.next = ms->_heapinfo[i].free.next;
	  ms->_heapinfo[block].free.prev = i;
	  ms->_heapinfo[i].free.next = block;
	  ms->_heapinfo[ms->_heapinfo[block].free.next].free.prev = block;
	  ++ms->_chunks_free;
	}

      /* Now that the block is linked in, see if we can coalesce it
	 with its successor (by deleting its successor from the list
	 and adding in its size).  */
      if (block + ms->_heapinfo[block].free.size == ms->_heapinfo[block].free.next)
	{
	  n = ms->_heapinfo[block].free.next;
	  if (RNDPAGEDWN((char *)ADDRESS(n)) !=
	  RNDPAGEDWN((char *)ADDRESS(n) + ms->_heapinfo[n].free.size * BLOCKSIZE))
			e = RNDPAGEUP((char *)ADDRESS(n));

	  ms->_heapinfo[block].free.size
	    += ms->_heapinfo[ms->_heapinfo[block].free.next].free.size;
	  ms->_heapinfo[block].free.next
	    = ms->_heapinfo[ms->_heapinfo[block].free.next].free.next;
	  ms->_heapinfo[ms->_heapinfo[block].free.next].free.prev = block;
	  --ms->_chunks_free;

	}

	  if (mf->free_memory && (e > s))
		(*mf->free_memory)(s, e-s);

      /* Now see if we can return stuff to the system.  */
      blocks = ms->_heapinfo[block].free.size;
      if (blocks >= FINAL_FREE_BLOCKS && block + blocks == ms->_heaplimit
	  && (*mf->morecore) (0, ms) == ADDRESS (block + blocks))
	{
	  register size_t bytes = blocks * BLOCKSIZE;
	  ms->_heaplimit -= blocks;
	  (*mf->morecore) (-bytes, ms);
	  ms->_heapinfo[ms->_heapinfo[block].free.prev].free.next
	    = ms->_heapinfo[block].free.next;
	  ms->_heapinfo[ms->_heapinfo[block].free.next].free.prev
	    = ms->_heapinfo[block].free.prev;
	  block = ms->_heapinfo[block].free.prev;
	  --ms->_chunks_free;
	  ms->_bytes_free -= bytes;
	}

      /* Set the next search to begin at this block.  */
      ms->_heapindex = block;
      break;

    default:
      /* Do some of the statistics.  */
      --ms->_chunks_used;
      ms->_bytes_used -= 1 << type;
      ++ms->_chunks_free;
      ms->_bytes_free += 1 << type;

      /* Get the address of the first free fragment in this block.  */
      prev = (struct list *) ((char *) ADDRESS (block) +
			   (ms->_heapinfo[block].busy.info.frag.first << type));

      if (ms->_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1)
	{
	  /* If all fragments of this block are free, remove them
	     from the fragment list and free the whole block.  */
	  next = prev;
	  for (i = 1; i < (size_t) (BLOCKSIZE >> type); ++i)
	    next = next->next;
	  prev->prev->next = next;
	  if (next != NULL)
	    next->prev = prev->prev;
	  ms->_heapinfo[block].busy.type = 0;
	  ms->_heapinfo[block].busy.info.size = 1;

	  /* Keep the statistics accurate.  */
	  ++ms->_chunks_used;
	  ms->_bytes_used += BLOCKSIZE;
	  ms->_chunks_free -= BLOCKSIZE >> type;
	  ms->_bytes_free -= BLOCKSIZE;

	  _gnu_free (ADDRESS (block), ms, mf);
	}
      else if (ms->_heapinfo[block].busy.info.frag.nfree != 0)
	{
	  /* If some fragments of this block are free, link this
	     fragment into the fragment list after the first free
	     fragment of this block. */
	  next = (struct list *) ptr;
	  next->next = prev->next;
	  next->prev = prev;
	  prev->next = next;
	  if (next->next != NULL)
	    next->next->prev = next;
	  ++ms->_heapinfo[block].busy.info.frag.nfree;
	}
      else
	{
	  /* No fragments of this block are free, so link this
	     fragment into the fragment list and announce that
	     it is the first free fragment of this block. */
	  prev = (struct list *) ptr;
	  ms->_heapinfo[block].busy.info.frag.nfree = 1;
	  ms->_heapinfo[block].busy.info.frag.first = (unsigned long int)
	    ((unsigned long int) ((char *) ptr - (char *) NULL)
	     % BLOCKSIZE >> type);
	  prev->next = ms->_fraghead[type].next;
	  prev->prev = &ms->_fraghead[type];
	  prev->prev->next = prev;
	  if (prev->next != NULL)
	    prev->next->prev = prev;
	}
      break;
    }
}

/* Return memory to the heap.  */
void
_gnu_free (void *ptr, malloc_state *ms, malloc_funcs *mf)
{
  register struct alignlist *l;

  if (ptr == NULL)
    return;

  for (l = ms->_aligned_blocks; l != NULL; l = l->next)
    if (l->aligned == ptr)
      {
	l->aligned = NULL;	/* Mark the slot in the list as free.  */
	ptr = l->exact;
	break;
      }

  _free_internal (ptr, ms, mf);
}


void
_free (void *ptr, malloc_state *ms, malloc_funcs *mf)
{
    _m_acquire_sem(ms);
    _gnu_free(ptr, ms, mf);
    _m_release_sem(ms);
}
