/* ========================================================================== */
  /* === UMF_get_memory ======================================================= */
  /* ========================================================================== */
  
  /* -------------------------------------------------------------------------- */
  /* UMFPACK Copyright (c) Timothy A. Davis, CISE,                              */
  /* Univ. of Florida.  All Rights Reserved.  See ../Doc/License for License.   */
  /* web: http://www.cise.ufl.edu/research/sparse/umfpack                       */
  /* -------------------------------------------------------------------------- */
  
  /*
      Reallocate the workspace (Numeric->Memory) and shift elements downwards.
      needunits: increase in size so that the free space is at least this many
      Units (to which the tuple lengths is added).
  
      Return TRUE if successful, FALSE if out of memory.
  */
  
  #include "umf_internal.h"
  #include "umf_garbage_collection.h"
  #include "umf_tuple_lengths.h"
  #include "umf_build_tuples.h"
  #include "umf_mem_free_tail_block.h"
  #include "umf_realloc.h"
  
  GLOBAL Int UMF_get_memory
  (
      NumericType *Numeric,
      WorkType *Work,
      Int needunits,
      Int r2,		/* compact current front to r2-by-c2 */
      Int c2,
      Int do_Fcpos
  )
  {
      double nsize, bsize, tsize ;
      Int i, minsize, newsize, newmem, costly, row, col, *Row_tlen, *Col_tlen,
  	n_row, n_col, *Row_degree, *Col_degree ;
      Unit *mnew, *p ;
  
      /* ---------------------------------------------------------------------- */
      /* get and check parameters */
      /* ---------------------------------------------------------------------- */
  
  #ifndef NDEBUG
      DEBUG1 (("::::GET MEMORY::::
  ")) ;
      UMF_dump_memory (Numeric) ;
  #endif
  
      n_row = Work->n_row ;
      n_col = Work->n_col ;
      Row_degree = Numeric->Rperm ;	/* for NON_PIVOTAL_ROW macro */
      Col_degree = Numeric->Cperm ;	/* for NON_PIVOTAL_COL macro */
      Row_tlen   = Numeric->Uilen ;
      Col_tlen   = Numeric->Lilen ;
  
      /* ---------------------------------------------------------------------- */
      /* initialize the tuple list lengths */
      /* ---------------------------------------------------------------------- */
  
      for (row = 0 ; row < n_row ; row++)
      {
  	if (NON_PIVOTAL_ROW (row))
  	{
  	    Row_tlen [row] = 0 ;
  	}
      }
      for (col = 0 ; col < n_col ; col++)
      {
  	if (NON_PIVOTAL_COL (col))
  	{
  	    Col_tlen [col] = 0 ;
  	}
      }
  
      /* ---------------------------------------------------------------------- */
      /* determine how much memory is needed for the tuples */
      /* ---------------------------------------------------------------------- */
  
      nsize = (double) needunits + 2 ;
      needunits += UMF_tuple_lengths (Numeric, Work, &tsize) ;
      nsize += tsize ;
      needunits += 2 ;	/* add 2, so that newmem >= 2 is true if realloc'd */
  
      /* note: Col_tlen and Row_tlen are updated, but the tuple lists */
      /* themselves are not.  Do not attempt to scan the tuple lists. */
      /* They are now stale, and are about to be destroyed and recreated. */
  
      /* ---------------------------------------------------------------------- */
      /* determine the desired new size of memory */
      /* ---------------------------------------------------------------------- */
  
      DEBUG0 (("UMF_get_memory: needunits: "ID"
  ", needunits)) ;
  
      minsize = Numeric->size + needunits ;
      nsize += (double) Numeric->size ;
  
      bsize = ((double) Int_MAX) / sizeof (Unit) - 1 ;
  
      newsize = (Int) (UMF_REALLOC_INCREASE * ((double) minsize)) ;
      nsize *= UMF_REALLOC_INCREASE ;
      nsize += 1 ;
  
      if (newsize < 0 || nsize > bsize)
      {
  	/* :: realloc Numeric->Memory int overflow :: */
  	DEBUGm3 (("Realloc hit integer limit
  ")) ;
  	newsize = (Int) bsize ;	/* we cannot increase the size beyond bsize */
      }
      else
      {
  	ASSERT (newsize <= nsize) ;
  	newsize = MAX (newsize, minsize) ;
      }
      newsize = MAX (newsize, Numeric->size) ;
  
      DEBUG0 ((
      "REALLOC MEMORY: needunits "ID" old size: "ID" new size: "ID" Units 
  ",
  	needunits, Numeric->size, newsize)) ;
  
      /* Forget where the biggest free block is (we no longer need it) */
      /* since garbage collection will occur shortly. */
      Numeric->ibig = EMPTY ;
  
      DEBUG0 (("Before realloc E [0] "ID"
  ", Work->E [0])) ;
  
      /* ---------------------------------------------------------------------- */
      /* reallocate the memory, if possible, and make it bigger */
      /* ---------------------------------------------------------------------- */
  
      mnew = (Unit *) NULL ;
      while (!mnew)
      {
  	mnew = (Unit *) UMF_realloc (Numeric->Memory, newsize, sizeof (Unit)) ;
  	if (!mnew)
  	{
  	    if (newsize == minsize)	/* last realloc attempt failed */
  	    {
  		/* We failed to get the minimum.  Just stick with the */
  		/* current allocation and hope that garbage collection */
  		/* can recover enough space. */
  		mnew = Numeric->Memory ;	/* no new memory available */
  		newsize = Numeric->size ;
  	    }
  	    else
  	    {
  		/* otherwise, reduce the request and keep trying */
  		newsize = (Int) (UMF_REALLOC_REDUCTION * ((double) newsize)) ;
  		newsize = MAX (minsize, newsize) ;
  	    }
  	}
      }
      ASSERT (mnew != (Unit *) NULL) ;
  
      /* see if realloc had to copy, rather than just extend memory */
      costly = (mnew != Numeric->Memory) ;
  
      /* ---------------------------------------------------------------------- */
      /* extend the tail portion of memory downwards */
      /* ---------------------------------------------------------------------- */
  
      Numeric->Memory = mnew ;
      if (Work->E [0])
      {
  	Int nb, dr, dc ;
  	nb = Work->nb ;
  	dr = Work->fnr_curr ;
  	dc = Work->fnc_curr ;
  	Work->Flublock = (Entry *) (Numeric->Memory + Work->E [0]) ;
  	Work->Flblock  = Work->Flublock + nb * nb ;
  	Work->Fublock  = Work->Flblock  + dr * nb ;
  	Work->Fcblock  = Work->Fublock  + nb * dc ;
  	DEBUG0 (("after realloc E [0] "ID"
  ", Work->E [0])) ;
      }
      ASSERT (IMPLIES (!(Work->E [0]), Work->Flublock == (Entry *) NULL)) ;
  
      newmem = newsize - Numeric->size ;
      ASSERT (newmem == 0 || newmem >= 2) ;
  
      if (newmem >= 2)
      {
  	/* reallocation succeeded */
  
  	/* point to the old tail marker block of size 1 + header */
  	p = Numeric->Memory + Numeric->size - 2 ;
  
  	/* create a new block out of the newly extended memory */
  	p->header.size = newmem - 1 ;
  	i = Numeric->size - 1 ;
  	p += newmem ;
  
  	/* create a new tail marker block */
  	p->header.prevsize = newmem - 1 ;
  	p->header.size = 1 ;
  
  	Numeric->size = newsize ;
  
  	/* free the new block */
  	UMF_mem_free_tail_block (Numeric, i) ;
  
  	Numeric->nrealloc++ ;
  
  	if (costly)
  	{
  	    Numeric->ncostly++ ;
  	}
  
      }
      DEBUG1 (("Done with realloc memory
  ")) ;
  
      /* ---------------------------------------------------------------------- */
      /* garbage collection on the tail of Numeric->memory (destroys tuples) */
      /* ---------------------------------------------------------------------- */
  
      UMF_garbage_collection (Numeric, Work, r2, c2, do_Fcpos) ;
  
      /* ---------------------------------------------------------------------- */
      /* rebuild the tuples */
      /* ---------------------------------------------------------------------- */
  
      return (UMF_build_tuples (Numeric, Work)) ;
  }