Blame view
fvn_sparse/UMFPACK/Source/umf_mem_alloc_tail_block.c
4 KB
422234dc3
git-svn-id: https...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
/* ========================================================================== */
/* === UMF_mem_alloc_tail_block ============================================= */
/* ========================================================================== */
/* -------------------------------------------------------------------------- */
/* 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 */
/* -------------------------------------------------------------------------- */
/* The UMF_mem_* routines manage the Numeric->Memory memory space. */
#include "umf_internal.h"
/* allocate nunits from tail of Numeric->Memory */
/* (requires nunits+1, for header). */
/* Returns the index into Numeric->Memory if successful, or 0 on failure. */
GLOBAL Int UMF_mem_alloc_tail_block
(
NumericType *Numeric,
Int nunits
)
{
Int bigsize, usage ;
Unit *p, *pnext, *pbig ;
ASSERT (Numeric != (NumericType *) NULL) ;
ASSERT (Numeric->Memory != (Unit *) NULL) ;
#ifndef NDEBUG
if (UMF_allocfail)
{
/* pretend to fail, to test garbage_collection */
DEBUGm2 (("UMF_mem_alloc_tail_block: pretend to fail
")) ;
UMF_allocfail = FALSE ; /* don't fail the next time */
return (0) ;
}
DEBUG2 (("UMF_mem_alloc_tail_block, size: "ID" + 1 = "ID": ",
nunits, nunits+1)) ;
#endif
bigsize = 0 ;
pbig = (Unit *) NULL ;
ASSERT (nunits > 0) ; /* size must be positive */
if (Numeric->ibig != EMPTY)
{
ASSERT (Numeric->ibig > Numeric->itail) ;
ASSERT (Numeric->ibig < Numeric->size) ;
pbig = Numeric->Memory + Numeric->ibig ;
bigsize = -pbig->header.size ;
ASSERT (bigsize > 0) ; /* Numeric->ibig is free */
ASSERT (pbig->header.prevsize >= 0) ; /* prev. is not free */
}
if (pbig && bigsize >= nunits)
{
/* use the biggest block, somewhere in middle of memory */
p = pbig ;
pnext = p + 1 + bigsize ;
/* next is in range */
ASSERT (pnext < Numeric->Memory + Numeric->size) ;
/* prevsize of next = this size */
ASSERT (pnext->header.prevsize == bigsize) ;
/* next is not free */
ASSERT (pnext->header.size > 0) ;
bigsize -= nunits + 1 ;
if (bigsize < 4)
{
/* internal fragmentation would be too small */
/* allocate the entire free block */
p->header.size = -p->header.size ;
DEBUG2 (("GET BLOCK: p: "ID" size: "ID", all of big: "ID" size: "
ID"
", (Int) (p-Numeric->Memory), nunits, Numeric->ibig,
p->header.size)) ;
/* no more biggest block */
Numeric->ibig = EMPTY ;
}
else
{
/* allocate just the first nunits Units of the free block */
p->header.size = nunits ;
/* make a new free block */
Numeric->ibig += nunits + 1 ;
pbig = Numeric->Memory + Numeric->ibig ;
pbig->header.size = -bigsize ;
pbig->header.prevsize = nunits ;
pnext->header.prevsize = bigsize ;
DEBUG2 (("GET BLOCK: p: "ID" size: "ID", some of big: "ID" left: "
ID"
", (Int) (p-Numeric->Memory), nunits, Numeric->ibig,
bigsize)) ;
}
}
else
{
/* allocate from the top of tail */
pnext = Numeric->Memory + Numeric->itail ;
DEBUG2 (("GET BLOCK: from tail ")) ;
if ((nunits + 1) > (Numeric->itail - Numeric->ihead))
{
DEBUG2 (("
")) ;
return (0) ;
}
Numeric->itail -= (nunits + 1) ;
p = Numeric->Memory + Numeric->itail ;
p->header.size = nunits ;
p->header.prevsize = 0 ;
pnext->header.prevsize = nunits ;
DEBUG2 (("p: "ID" size: "ID", new tail "ID"
",
(Int) (p-Numeric->Memory), nunits, Numeric->itail)) ;
}
Numeric->tail_usage += p->header.size + 1 ;
usage = Numeric->ihead + Numeric->tail_usage ;
Numeric->max_usage = MAX (Numeric->max_usage, usage) ;
#ifndef NDEBUG
UMF_debug -= 10 ;
UMF_dump_memory (Numeric) ;
UMF_debug += 10 ;
#endif
/* p points to the header. Add one to point to the usable block itself. */
/* return the offset into Numeric->Memory */
return ((p - Numeric->Memory) + 1) ;
}
|