1 /* ========================================================================== */
2 /* === UMF_mem_free_tail_block ============================================== */
3 /* ========================================================================== */
4
5 /* -------------------------------------------------------------------------- */
6 /* Copyright (c) 2005-2012 by Timothy A. Davis, http://www.suitesparse.com. */
7 /* All Rights Reserved. See ../Doc/License.txt for License. */
8 /* -------------------------------------------------------------------------- */
9
10 /* The UMF_mem_* routines manage the Numeric->Memory memory space. */
11
12 /* free a block from the tail of Numeric->memory */
13
14 #include "umf_internal.h"
15 #include "umf_mem_free_tail_block.h"
16
UMF_mem_free_tail_block(NumericType * Numeric,Int i)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 }
143