/* ========================================================================== */
/* === UMF_mem_free_tail_block ============================================== */
/* ========================================================================== */

/* -------------------------------------------------------------------------- */
/* UMFPACK Version 4.4, Copyright (c) 2005 by Timothy A. Davis.  CISE Dept,   */
/* Univ. of Florida.  All Rights Reserved.  See ../Doc/License for License.   */
/* web: http://www.cise.ufl.edu/research/sparse/umfpack                       */
/* -------------------------------------------------------------------------- */

/* The UMF_mem_* routines manage the Numeric->Memory memory space. */

/* free a block from the tail of Numeric->memory */

#include "umf_internal.h"

GLOBAL void UMF_mem_free_tail_block
(
    NumericType *Numeric,
    Int i
)
{
    Unit *pprev, *pnext, *p, *pbig ;
    Int sprev ;

    ASSERT (Numeric != (NumericType *) NULL) ;
    ASSERT (Numeric->Memory != (Unit *) NULL) ;
    if (i == EMPTY || i == 0) return ;	/* already deallocated */

    /* ---------------------------------------------------------------------- */
    /* get the block */
    /* ---------------------------------------------------------------------- */

    p = Numeric->Memory + i ;

    p-- ;	/* get the corresponding header */
    DEBUG2 (("free block: p: "ID, (Int) (p-Numeric->Memory))) ;
    ASSERT (p >= Numeric->Memory + Numeric->itail) ;
    ASSERT (p < Numeric->Memory + Numeric->size) ;
    ASSERT (p->header.size > 0) ;		/* block not already free */
    ASSERT (p->header.prevsize >= 0) ;

    Numeric->tail_usage -= p->header.size + 1 ;

    /* ---------------------------------------------------------------------- */
    /* merge with next free block, if any */
    /* ---------------------------------------------------------------------- */

    pnext = p + 1 + p->header.size ;
    DEBUG2 (("size: "ID" next: "ID" ", p->header.size,
	(Int) (pnext-Numeric->Memory))) ;
    ASSERT (pnext < Numeric->Memory + Numeric->size) ;
    ASSERT (pnext->header.prevsize == p->header.size) ;
    ASSERT (pnext->header.size != 0) ;

    if (pnext->header.size < 0)
    {
	/* next block is also free - merge with current block */
	p->header.size += (-(pnext->header.size)) + 1 ;
	DEBUG2 ((" NEXT FREE ")) ;
    }

    /* ---------------------------------------------------------------------- */
    /* merge with previous free block, if any */
    /* ---------------------------------------------------------------------- */

#ifndef NDEBUG
    if (p == Numeric->Memory + Numeric->itail)
    {
	DEBUG2 ((" at top of tail ")) ;
	ASSERT (p->header.prevsize == 0) ;
    }
#endif

    if (p > Numeric->Memory + Numeric->itail)
    {
	ASSERT (p->header.prevsize > 0) ;
	pprev = p - 1 - p->header.prevsize ;
	DEBUG2 ((" prev: "ID" ", (Int) (pprev-Numeric->Memory))) ;
	ASSERT (pprev >= Numeric->Memory + Numeric->itail) ;
	sprev = pprev->header.size ;
	if (sprev < 0)
	{
	    /* previous block is also free - merge it with current block */
	    ASSERT (p->header.prevsize == -sprev) ;
	    pprev->header.size = p->header.size + (-sprev) + 1 ;
	    p = pprev ;
	    DEBUG2 ((" PREV FREE ")) ;
	    /* note that p may now point to Numeric->itail */
	}
#ifndef NDEBUG
	else
	{
	    ASSERT (p->header.prevsize == sprev) ;
	}
#endif
    }

    /* ---------------------------------------------------------------------- */
    /* free the block, p */
    /* ---------------------------------------------------------------------- */

    pnext = p + 1 + p->header.size ;
    ASSERT (pnext < Numeric->Memory + Numeric->size) ;

    if (p == Numeric->Memory + Numeric->itail)
    {
	/* top block in list is freed */
	Numeric->itail = pnext - Numeric->Memory ;
	pnext->header.prevsize = 0 ;
	DEBUG2 ((" NEW TAIL : "ID" ", Numeric->itail)) ;
	ASSERT (pnext->header.size > 0) ;
	if (Numeric->ibig != EMPTY && Numeric->ibig <= Numeric->itail)
	{
	    /* the big free block is now above the tail */
	    Numeric->ibig = EMPTY ;
	}
    }
    else
    {
	/* keep track of the biggest free block seen */
	if (Numeric->ibig == EMPTY)
	{
	    Numeric->ibig = p - Numeric->Memory ;
	}
	else
	{
	    pbig = Numeric->Memory + Numeric->ibig ;
	    if (-(pbig->header.size) < p->header.size)
	    {
		Numeric->ibig = p - Numeric->Memory ;
	    }
	}
	/* flag the block as free, somewhere in the middle of the tail */
	pnext->header.prevsize = p->header.size ;
	p->header.size = -(p->header.size) ;
    }

    DEBUG2 (("new p: "ID" freesize: "ID"\n", (Int) (p-Numeric->Memory),
	-(p->header.size))) ;

}