|
5164
|
1 /* ========================================================================== */ |
|
|
2 /* === UMF_mem_free_tail_block ============================================== */ |
|
|
3 /* ========================================================================== */ |
|
|
4 |
|
|
5 /* -------------------------------------------------------------------------- */ |
|
|
6 /* UMFPACK Version 4.4, Copyright (c) 2005 by Timothy A. Davis. CISE Dept, */ |
|
|
7 /* Univ. of Florida. All Rights Reserved. See ../Doc/License for License. */ |
|
|
8 /* web: http://www.cise.ufl.edu/research/sparse/umfpack */ |
|
|
9 /* -------------------------------------------------------------------------- */ |
|
|
10 |
|
|
11 /* The UMF_mem_* routines manage the Numeric->Memory memory space. */ |
|
|
12 |
|
|
13 /* free a block from the tail of Numeric->memory */ |
|
|
14 |
|
|
15 #include "umf_internal.h" |
|
|
16 |
|
|
17 GLOBAL void UMF_mem_free_tail_block |
|
|
18 ( |
|
|
19 NumericType *Numeric, |
|
|
20 Int i |
|
|
21 ) |
|
|
22 { |
|
|
23 Unit *pprev, *pnext, *p, *pbig ; |
|
|
24 Int sprev ; |
|
|
25 |
|
|
26 ASSERT (Numeric != (NumericType *) NULL) ; |
|
|
27 ASSERT (Numeric->Memory != (Unit *) NULL) ; |
|
|
28 if (i == EMPTY || i == 0) return ; /* already deallocated */ |
|
|
29 |
|
|
30 /* ---------------------------------------------------------------------- */ |
|
|
31 /* get the block */ |
|
|
32 /* ---------------------------------------------------------------------- */ |
|
|
33 |
|
|
34 p = Numeric->Memory + i ; |
|
|
35 |
|
|
36 p-- ; /* get the corresponding header */ |
|
|
37 DEBUG2 (("free block: p: "ID, (Int) (p-Numeric->Memory))) ; |
|
|
38 ASSERT (p >= Numeric->Memory + Numeric->itail) ; |
|
|
39 ASSERT (p < Numeric->Memory + Numeric->size) ; |
|
|
40 ASSERT (p->header.size > 0) ; /* block not already free */ |
|
|
41 ASSERT (p->header.prevsize >= 0) ; |
|
|
42 |
|
|
43 Numeric->tail_usage -= p->header.size + 1 ; |
|
|
44 |
|
|
45 /* ---------------------------------------------------------------------- */ |
|
|
46 /* merge with next free block, if any */ |
|
|
47 /* ---------------------------------------------------------------------- */ |
|
|
48 |
|
|
49 pnext = p + 1 + p->header.size ; |
|
|
50 DEBUG2 (("size: "ID" next: "ID" ", p->header.size, |
|
|
51 (Int) (pnext-Numeric->Memory))) ; |
|
|
52 ASSERT (pnext < Numeric->Memory + Numeric->size) ; |
|
|
53 ASSERT (pnext->header.prevsize == p->header.size) ; |
|
|
54 ASSERT (pnext->header.size != 0) ; |
|
|
55 |
|
|
56 if (pnext->header.size < 0) |
|
|
57 { |
|
|
58 /* next block is also free - merge with current block */ |
|
|
59 p->header.size += (-(pnext->header.size)) + 1 ; |
|
|
60 DEBUG2 ((" NEXT FREE ")) ; |
|
|
61 } |
|
|
62 |
|
|
63 /* ---------------------------------------------------------------------- */ |
|
|
64 /* merge with previous free block, if any */ |
|
|
65 /* ---------------------------------------------------------------------- */ |
|
|
66 |
|
|
67 #ifndef NDEBUG |
|
|
68 if (p == Numeric->Memory + Numeric->itail) |
|
|
69 { |
|
|
70 DEBUG2 ((" at top of tail ")) ; |
|
|
71 ASSERT (p->header.prevsize == 0) ; |
|
|
72 } |
|
|
73 #endif |
|
|
74 |
|
|
75 if (p > Numeric->Memory + Numeric->itail) |
|
|
76 { |
|
|
77 ASSERT (p->header.prevsize > 0) ; |
|
|
78 pprev = p - 1 - p->header.prevsize ; |
|
|
79 DEBUG2 ((" prev: "ID" ", (Int) (pprev-Numeric->Memory))) ; |
|
|
80 ASSERT (pprev >= Numeric->Memory + Numeric->itail) ; |
|
|
81 sprev = pprev->header.size ; |
|
|
82 if (sprev < 0) |
|
|
83 { |
|
|
84 /* previous block is also free - merge it with current block */ |
|
|
85 ASSERT (p->header.prevsize == -sprev) ; |
|
|
86 pprev->header.size = p->header.size + (-sprev) + 1 ; |
|
|
87 p = pprev ; |
|
|
88 DEBUG2 ((" PREV FREE ")) ; |
|
|
89 /* note that p may now point to Numeric->itail */ |
|
|
90 } |
|
|
91 #ifndef NDEBUG |
|
|
92 else |
|
|
93 { |
|
|
94 ASSERT (p->header.prevsize == sprev) ; |
|
|
95 } |
|
|
96 #endif |
|
|
97 } |
|
|
98 |
|
|
99 /* ---------------------------------------------------------------------- */ |
|
|
100 /* free the block, p */ |
|
|
101 /* ---------------------------------------------------------------------- */ |
|
|
102 |
|
|
103 pnext = p + 1 + p->header.size ; |
|
|
104 ASSERT (pnext < Numeric->Memory + Numeric->size) ; |
|
|
105 |
|
|
106 if (p == Numeric->Memory + Numeric->itail) |
|
|
107 { |
|
|
108 /* top block in list is freed */ |
|
|
109 Numeric->itail = pnext - Numeric->Memory ; |
|
|
110 pnext->header.prevsize = 0 ; |
|
|
111 DEBUG2 ((" NEW TAIL : "ID" ", Numeric->itail)) ; |
|
|
112 ASSERT (pnext->header.size > 0) ; |
|
|
113 if (Numeric->ibig != EMPTY && Numeric->ibig <= Numeric->itail) |
|
|
114 { |
|
|
115 /* the big free block is now above the tail */ |
|
|
116 Numeric->ibig = EMPTY ; |
|
|
117 } |
|
|
118 } |
|
|
119 else |
|
|
120 { |
|
|
121 /* keep track of the biggest free block seen */ |
|
|
122 if (Numeric->ibig == EMPTY) |
|
|
123 { |
|
|
124 Numeric->ibig = p - Numeric->Memory ; |
|
|
125 } |
|
|
126 else |
|
|
127 { |
|
|
128 pbig = Numeric->Memory + Numeric->ibig ; |
|
|
129 if (-(pbig->header.size) < p->header.size) |
|
|
130 { |
|
|
131 Numeric->ibig = p - Numeric->Memory ; |
|
|
132 } |
|
|
133 } |
|
|
134 /* flag the block as free, somewhere in the middle of the tail */ |
|
|
135 pnext->header.prevsize = p->header.size ; |
|
|
136 p->header.size = -(p->header.size) ; |
|
|
137 } |
|
|
138 |
|
|
139 DEBUG2 (("new p: "ID" freesize: "ID"\n", (Int) (p-Numeric->Memory), |
|
|
140 -(p->header.size))) ; |
|
|
141 |
|
|
142 } |
