1 /* ========================================================================== */
2 /* === UMF_get_memory ======================================================= */
3 /* ========================================================================== */
4
5 /* -------------------------------------------------------------------------- */
6 /* UMFPACK Copyright (c) Timothy A. Davis, CISE, */
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 /*
12 Reallocate the workspace (Numeric->Memory) and shift elements downwards.
13 needunits: increase in size so that the free space is at least this many
14 Units (to which the tuple lengths is added).
15
16 Return TRUE if successful, FALSE if out of memory.
17 */
18
19 #include "umf_internal.h"
20 #include "umf_get_memory.h"
21 #include "umf_garbage_collection.h"
22 #include "umf_tuple_lengths.h"
23 #include "umf_build_tuples.h"
24 #include "umf_mem_free_tail_block.h"
25 #include "umf_realloc.h"
26
UMF_get_memory(NumericType * Numeric,WorkType * Work,Int needunits,Int r2,Int c2,Int do_Fcpos)27 GLOBAL Int UMF_get_memory
28 (
29 NumericType *Numeric,
30 WorkType *Work,
31 Int needunits,
32 Int r2, /* compact current front to r2-by-c2 */
33 Int c2,
34 Int do_Fcpos
35 )
36 {
37 double nsize, bsize, tsize ;
38 Int i, minsize, newsize, newmem, costly, row, col, *Row_tlen, *Col_tlen,
39 n_row, n_col, *Row_degree, *Col_degree ;
40 Unit *mnew, *p ;
41
42 /* ---------------------------------------------------------------------- */
43 /* get and check parameters */
44 /* ---------------------------------------------------------------------- */
45
46 #ifndef NDEBUG
47 DEBUG1 (("::::GET MEMORY::::\n")) ;
48 UMF_dump_memory (Numeric) ;
49 #endif
50
51 n_row = Work->n_row ;
52 n_col = Work->n_col ;
53 Row_degree = Numeric->Rperm ; /* for NON_PIVOTAL_ROW macro */
54 Col_degree = Numeric->Cperm ; /* for NON_PIVOTAL_COL macro */
55 Row_tlen = Numeric->Uilen ;
56 Col_tlen = Numeric->Lilen ;
57
58 /* ---------------------------------------------------------------------- */
59 /* initialize the tuple list lengths */
60 /* ---------------------------------------------------------------------- */
61
62 for (row = 0 ; row < n_row ; row++)
63 {
64 if (NON_PIVOTAL_ROW (row))
65 {
66 Row_tlen [row] = 0 ;
67 }
68 }
69 for (col = 0 ; col < n_col ; col++)
70 {
71 if (NON_PIVOTAL_COL (col))
72 {
73 Col_tlen [col] = 0 ;
74 }
75 }
76
77 /* ---------------------------------------------------------------------- */
78 /* determine how much memory is needed for the tuples */
79 /* ---------------------------------------------------------------------- */
80
81 nsize = (double) needunits + 2 ;
82 needunits += UMF_tuple_lengths (Numeric, Work, &tsize) ;
83 nsize += tsize ;
84 needunits += 2 ; /* add 2, so that newmem >= 2 is true if realloc'd */
85
86 /* note: Col_tlen and Row_tlen are updated, but the tuple lists */
87 /* themselves are not. Do not attempt to scan the tuple lists. */
88 /* They are now stale, and are about to be destroyed and recreated. */
89
90 /* ---------------------------------------------------------------------- */
91 /* determine the desired new size of memory */
92 /* ---------------------------------------------------------------------- */
93
94 DEBUG0 (("UMF_get_memory: needunits: "ID"\n", needunits)) ;
95
96 minsize = Numeric->size + needunits ;
97 nsize += (double) Numeric->size ;
98
99 bsize = ((double) Int_MAX) / sizeof (Unit) - 1 ;
100
101 newsize = (Int) (UMF_REALLOC_INCREASE * ((double) minsize)) ;
102 nsize *= UMF_REALLOC_INCREASE ;
103 nsize += 1 ;
104
105 if (newsize < 0 || nsize > bsize)
106 {
107 /* :: realloc Numeric->Memory int overflow :: */
108 DEBUGm3 (("Realloc hit integer limit\n")) ;
109 newsize = (Int) bsize ; /* we cannot increase the size beyond bsize */
110 }
111 else
112 {
113 ASSERT (newsize <= nsize) ;
114 newsize = MAX (newsize, minsize) ;
115 }
116 newsize = MAX (newsize, Numeric->size) ;
117
118 DEBUG0 ((
119 "REALLOC MEMORY: needunits "ID" old size: "ID" new size: "ID" Units \n",
120 needunits, Numeric->size, newsize)) ;
121
122 /* Forget where the biggest free block is (we no longer need it) */
123 /* since garbage collection will occur shortly. */
124 Numeric->ibig = EMPTY ;
125
126 DEBUG0 (("Before realloc E [0] "ID"\n", Work->E [0])) ;
127
128 /* ---------------------------------------------------------------------- */
129 /* reallocate the memory, if possible, and make it bigger */
130 /* ---------------------------------------------------------------------- */
131
132 mnew = (Unit *) NULL ;
133 while (!mnew)
134 {
135 mnew = (Unit *) UMF_realloc (Numeric->Memory, newsize, sizeof (Unit)) ;
136 if (!mnew)
137 {
138 if (newsize == minsize) /* last realloc attempt failed */
139 {
140 /* We failed to get the minimum. Just stick with the */
141 /* current allocation and hope that garbage collection */
142 /* can recover enough space. */
143 mnew = Numeric->Memory ; /* no new memory available */
144 newsize = Numeric->size ;
145 }
146 else
147 {
148 /* otherwise, reduce the request and keep trying */
149 newsize = (Int) (UMF_REALLOC_REDUCTION * ((double) newsize)) ;
150 newsize = MAX (minsize, newsize) ;
151 }
152 }
153 }
154 ASSERT (mnew != (Unit *) NULL) ;
155
156 /* see if realloc had to copy, rather than just extend memory */
157 costly = (mnew != Numeric->Memory) ;
158
159 /* ---------------------------------------------------------------------- */
160 /* extend the tail portion of memory downwards */
161 /* ---------------------------------------------------------------------- */
162
163 Numeric->Memory = mnew ;
164 if (Work->E [0])
165 {
166 Int nb, dr, dc ;
167 nb = Work->nb ;
168 dr = Work->fnr_curr ;
169 dc = Work->fnc_curr ;
170 Work->Flublock = (Entry *) (Numeric->Memory + Work->E [0]) ;
171 Work->Flblock = Work->Flublock + nb * nb ;
172 Work->Fublock = Work->Flblock + dr * nb ;
173 Work->Fcblock = Work->Fublock + nb * dc ;
174 DEBUG0 (("after realloc E [0] "ID"\n", Work->E [0])) ;
175 }
176 ASSERT (IMPLIES (!(Work->E [0]), Work->Flublock == (Entry *) NULL)) ;
177
178 newmem = newsize - Numeric->size ;
179 ASSERT (newmem == 0 || newmem >= 2) ;
180
181 if (newmem >= 2)
182 {
183 /* reallocation succeeded */
184
185 /* point to the old tail marker block of size 1 + header */
186 p = Numeric->Memory + Numeric->size - 2 ;
187
188 /* create a new block out of the newly extended memory */
189 p->header.size = newmem - 1 ;
190 i = Numeric->size - 1 ;
191 p += newmem ;
192
193 /* create a new tail marker block */
194 p->header.prevsize = newmem - 1 ;
195 p->header.size = 1 ;
196
197 Numeric->size = newsize ;
198
199 /* free the new block */
200 UMF_mem_free_tail_block (Numeric, i) ;
201
202 Numeric->nrealloc++ ;
203
204 if (costly)
205 {
206 Numeric->ncostly++ ;
207 }
208
209 }
210 DEBUG1 (("Done with realloc memory\n")) ;
211
212 /* ---------------------------------------------------------------------- */
213 /* garbage collection on the tail of Numeric->memory (destroys tuples) */
214 /* ---------------------------------------------------------------------- */
215
216 UMF_garbage_collection (Numeric, Work, r2, c2, do_Fcpos) ;
217
218 /* ---------------------------------------------------------------------- */
219 /* rebuild the tuples */
220 /* ---------------------------------------------------------------------- */
221
222 return (UMF_build_tuples (Numeric, Work)) ;
223 }
224