umf_mem_alloc_tail_block.c
4 KB
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
/* ========================================================================== */
/* === 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\n")) ;
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"\n", (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"\n", (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 (("\n")) ;
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"\n",
(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) ;
}