/* Free a block of memory allocated by `umalloc'.
   Copyright 1990, 1991, 1992 Free Software Foundation

   Written May 1989 by Mike Haertel.
   Heavily modified Mar 1992 by Fred Fish.  (fnf@cygnus.com)

The GNU C 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.

The GNU C 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 the GNU C Library; see the file COPYING.LIB.  If
not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
Boston, MA 02111-1307, 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. */

#define _UMALLOC_INTERNAL
#include "umprivate.h"

/* Return memory to the heap.
   Like `ufree' but don't call a ufree_hook if there is one.  */

void __umalloc_free(struct mdesc *mdp, void *ptr)
{
    int type, islast;
    blockno_t block, blocks, block_next;
    register blockno_t i;
    struct list *prev, *next;
    uintptr_t block_addr;

    int growsup = MDP_GROWSUP(mdp);

    block = BLOCK_MDP(mdp, ptr);

    type = mdp->heapinfo[block].busy.type;
    switch (type) {
    case 0:
	/* Get as many statistics as early as we can.  */
	mdp->heapstats.chunks_used--;
	mdp->heapstats.bytes_used -=
	    mdp->heapinfo[block].busy.info.size * BLOCKSIZE;
	mdp->heapstats.bytes_free +=
	    mdp->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 = mdp->heapindex;
	if (i > block) {
	    while (i > block) {
		i = mdp->heapinfo[i].free.prev;
	    }
	} else {
	    do {
		i = mdp->heapinfo[i].free.next;
	    }
	    while ((i != 0) && (i < block));
	    i = mdp->heapinfo[i].free.prev;
	}

	blocks = mdp->heapinfo[block].busy.info.size;

	if (!growsup) {

	    /* Determine how to link the block in the freelist's predecessor */
	    if (i != 0 && i == block - blocks) {
		int prev_block = mdp->heapinfo[i].free.prev;
		int next_block = mdp->heapinfo[i].free.next;
		blocks += mdp->heapinfo[i].free.size;
		mdp->heapinfo[block].free.size = blocks;
		mdp->heapinfo[block].free.prev = prev_block;
		mdp->heapinfo[block].free.next = next_block;
		mdp->heapinfo[prev_block].free.next = block;
		mdp->heapinfo[next_block].free.prev = block;
	    }
	    else {
		/* Really link this block back into the free list. */
		mdp->heapinfo[block].free.size = blocks;
		mdp->heapinfo[block].free.next = mdp->heapinfo[i].free.next;
		mdp->heapinfo[block].free.prev = i;
		mdp->heapinfo[i].free.next = block;
		mdp->heapinfo[mdp->heapinfo[block].free.next].free.prev = block;
		mdp->heapstats.chunks_free++;
	    }
	    
	}

	else {
	    /* Determine how to link this block into the free list.  */
	    if (block == i + mdp->heapinfo[i].free.size) {
		/* Coalesce this block with its predecessor.  */
		mdp->heapinfo[i].free.size += mdp->heapinfo[block].busy.info.size;
		block = i;
	    } 
	    else {
		/* Really link this block back into the free list.  */
		mdp->heapinfo[block].free.size = blocks;
		mdp->heapinfo[block].free.next = mdp->heapinfo[i].free.next;
		mdp->heapinfo[block].free.prev = i;
		mdp->heapinfo[i].free.next = block;
		mdp->heapinfo[mdp->heapinfo[block].free.next].free.prev = block;
		mdp->heapstats.chunks_free++;
	    }
	}

	/* SUCCESSOR LINKING:
	 * GrowDown: coalesce if successor free block is adjacent (under block)
	 * GrowUp  : coalesce if successor free block is adjacent (over block)
	 */
	block_next = mdp->heapinfo[block].free.next;

	if (growsup) {
       	  if (block + blocks == block_next) {
	    blocks += mdp->heapinfo[block_next].free.size;
	    mdp->heapinfo[block].free.size = blocks;
	    mdp->heapinfo[block].free.next
		= mdp->heapinfo[block_next].free.next;
	    mdp->heapinfo[mdp->heapinfo[block].free.next].free.prev = block;
	    mdp->heapstats.chunks_free--;
	  }
	}
	else {
	  if (block_next == block + mdp->heapinfo[block_next].free.size) {
	    blocks += mdp->heapinfo[block_next].free.size;
	    mdp->heapinfo[block_next].free.size = blocks;
	    mdp->heapinfo[block_next].free.prev =
		    mdp->heapinfo[block].free.prev;
	    mdp->heapinfo[mdp->heapinfo[block].free.prev].free.next = 
		    block_next;
	    block = block_next;
	    mdp->heapstats.chunks_free--;
	  }
	}

	/* check to see if the block is the final block */
	blocks = mdp->heapinfo[block].free.size;
	if (growsup)
	    islast = block + blocks == mdp->heaplimit &&
		     mdp->morecore(mdp, 0) == ADDRESS_UP(block + blocks);
	else
	    islast = block == mdp->heaplimit &&
		     mdp->morecore(mdp, 0) == ADDRESS_DOWN(block);

	/* Now see if we can return stuff to the system.  */
	if (blocks >= FINAL_FREE_BLOCKS && islast) {
	    register uintptr_t bytes = blocks * BLOCKSIZE;

	    mdp->heaplimit -= blocks;
	    mdp->morecore(mdp, -bytes);
	    mdp->heapinfo[mdp->heapinfo[block].free.prev].free.next
		= mdp->heapinfo[block].free.next;
	    mdp->heapinfo[mdp->heapinfo[block].free.next].free.prev
		= mdp->heapinfo[block].free.prev;
	    block = mdp->heapinfo[block].free.prev;
	    mdp->heapstats.chunks_free--;
	    mdp->heapstats.bytes_free -= bytes;
	}

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

    default:
	/* Do some of the statistics.  */
	mdp->heapstats.chunks_used--;
	mdp->heapstats.bytes_used -= 1 << type;
	mdp->heapstats.chunks_free++;
	mdp->heapstats.bytes_free += 1 << type;

	block_addr = (uintptr_t) ADDRESS_MDP(mdp, block);

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

	if (mdp->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 < (blockno_t) (BLOCKSIZE >> type); ++i) {
		next = next->next;
	    }
	    prev->prev->next = next;
	    if (next != NULL) {
		next->prev = prev->prev;
	    }
	    mdp->heapinfo[block].busy.type = 0;
	    mdp->heapinfo[block].busy.info.size = 1;

	    /* Keep the statistics accurate.  */
	    mdp->heapstats.chunks_used++;
	    mdp->heapstats.bytes_used += BLOCKSIZE;
	    mdp->heapstats.chunks_free -= BLOCKSIZE >> type;
	    mdp->heapstats.bytes_free -= BLOCKSIZE;

	    ufree((void *) mdp, (void *) block_addr);
	} else if (mdp->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;
	    }
	    ++mdp->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;
	    mdp->heapinfo[block].busy.info.frag.nfree = 1;
	    mdp->heapinfo[block].busy.info.frag.first =
		RESIDUAL(ptr, BLOCKSIZE) >> type;

	    prev->next = mdp->fraghead[type].next;
	    prev->prev = &mdp->fraghead[type];
	    prev->prev->next = prev;
	    if (prev->next != NULL) {
		prev->next->prev = prev;
	    }
	}
	break;
    }
}

/* Return memory to the heap.  */

void ufree(umalloc_heap_t *md, void *ptr)
{
    struct mdesc *mdp;
#if 0 /* We no longer use the debugging hooks or umalign */
    void *exact;
#endif

    if (ptr != NULL) {
	mdp = MD_TO_MDP(md);
#if 0 /* We no longer use the debugging hooks or umalign */
        exact = __umalloc_aligned_remove(mdp, ptr);
        if (exact) ptr = exact;
	if (mdp->ufree_hook != NULL) {
	    (*mdp->ufree_hook) (md, ptr);
	} else {
	    __umalloc_free(mdp, ptr);
	}
#else
        __umalloc_free(mdp, ptr);
#endif
    }
}