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