--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/liboctave/UMFPACK/UMFPACK/Source/umf_mem_free_tail_block.c	Fri Feb 25 19:55:28 2005 +0000
@@ -0,0 +1,142 @@
+/* ========================================================================== */
+/* === 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))) ;
+
+}