Mercurial > octave-nkf
comparison liboctave/UMFPACK/UMFPACK/Source/umf_mem_free_tail_block.c @ 5164:57077d0ddc8e
[project @ 2005-02-25 19:55:24 by jwe]
author | jwe |
---|---|
date | Fri, 25 Feb 2005 19:55:28 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
5163:9f3299378193 | 5164:57077d0ddc8e |
---|---|
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 } |