1 /* ========================================================================== */
2 /* === Core/cholmod_memory ================================================== */
3 /* ========================================================================== */
4
5 /* -----------------------------------------------------------------------------
6 * CHOLMOD/Core Module. Copyright (C) 2005-2013,
7 * Univ. of Florida. Author: Timothy A. Davis
8 * -------------------------------------------------------------------------- */
9
10 /* Core memory management routines:
11 *
12 * Primary routines:
13 * -----------------
14 * cholmod_malloc malloc wrapper
15 * cholmod_free free wrapper
16 *
17 * Secondary routines:
18 * -------------------
19 * cholmod_calloc calloc wrapper
20 * cholmod_realloc realloc wrapper
21 * cholmod_realloc_multiple realloc wrapper for multiple objects
22 *
23 * The user may make use of these, just like malloc and free. You can even
24 * malloc an object and safely free it with cholmod_free, and visa versa
25 * (except that the memory usage statistics will be corrupted). These routines
26 * do differ from malloc and free. If cholmod_free is given a NULL pointer,
27 * for example, it does nothing (unlike the ANSI free). cholmod_realloc does
28 * not return NULL if given a non-NULL pointer and a nonzero size, even if it
29 * fails (it sets an error code in Common->status instead).
30 *
31 * CHOLMOD keeps track of the amount of memory it has allocated, and so the
32 * cholmod_free routine includes as a parameter the size of the object being
33 * freed. This is only used for memory usage statistics, which are very useful
34 * in finding memory leaks in your program. If you, the user of CHOLMOD, pass
35 * the wrong size, the only consequence is that the memory usage statistics
36 * will be invalid. This will causes assertions to fail if CHOLMOD is
37 * compiled with debugging enabled, but otherwise it will cause no errors.
38 *
39 * The cholmod_free_* routines for each CHOLMOD object keep track of the size
40 * of the blocks they free, so they do not require you to pass their sizes
41 * as a parameter.
42 *
43 * If a block of size zero is requested, these routines allocate a block of
44 * size one instead.
45 */
46
47 #include "cholmod_internal.h"
48 #include "cholmod_core.h"
49
50 /* ========================================================================== */
51 /* === cholmod_add_size_t =================================================== */
52 /* ========================================================================== */
53
54 /* Safely compute a+b, and check for integer overflow. If overflow occurs,
55 * return 0 and set OK to FALSE. Also return 0 if OK is FALSE on input. */
56
CHOLMOD(add_size_t)57 size_t CHOLMOD(add_size_t) (size_t a, size_t b, int *ok)
58 {
59 size_t s = a + b ;
60 (*ok) = (*ok) && (s >= a) ;
61 return ((*ok) ? s : 0) ;
62 }
63
64 /* ========================================================================== */
65 /* === cholmod_mult_size_t ================================================== */
66 /* ========================================================================== */
67
68 /* Safely compute a*k, where k should be small, and check for integer overflow.
69 * If overflow occurs, return 0 and set OK to FALSE. Also return 0 if OK is
70 * FALSE on input. */
71
CHOLMOD(mult_size_t)72 size_t CHOLMOD(mult_size_t) (size_t a, size_t k, int *ok)
73 {
74 size_t p = 0, s ;
75 while (*ok)
76 {
77 if (k % 2)
78 {
79 p = p + a ;
80 (*ok) = (*ok) && (p >= a) ;
81 }
82 k = k / 2 ;
83 if (!k) return (p) ;
84 s = a + a ;
85 (*ok) = (*ok) && (s >= a) ;
86 a = s ;
87 }
88 return (0) ;
89 }
90
91
92 /* ========================================================================== */
93 /* === cholmod_malloc ======================================================= */
94 /* ========================================================================== */
95
96 /* Wrapper around malloc routine. Allocates space of size MAX(1,n)*size, where
97 * size is normally a sizeof (...).
98 *
99 * This routine, cholmod_calloc, and cholmod_realloc do not set Common->status
100 * to CHOLMOD_OK on success, so that a sequence of cholmod_malloc's, _calloc's,
101 * or _realloc's can be used. If any of them fails, the Common->status will
102 * hold the most recent error status.
103 *
104 * Usage, for a pointer to int:
105 *
106 * p = cholmod_malloc (n, sizeof (int), Common)
107 *
108 * Uses a pointer to the malloc routine (or its equivalent) defined in Common.
109 */
110
CHOLMOD(malloc)111 void *CHOLMOD(malloc) /* returns pointer to the newly malloc'd block */
112 (
113 /* ---- input ---- */
114 size_t n, /* number of items */
115 size_t size, /* size of each item */
116 /* --------------- */
117 cholmod_common *Common
118 )
119 {
120 void *p ;
121 size_t s ;
122 /*
123 int ok = TRUE ;
124 */
125
126 RETURN_IF_NULL_COMMON (NULL) ;
127 if (size == 0)
128 {
129 ERROR (CHOLMOD_INVALID, "sizeof(item) must be > 0") ;
130 p = NULL ;
131 }
132 else if (n >= (Size_max / size) || n >= Int_max)
133 {
134 /* object is too big to allocate without causing integer overflow */
135 ERROR (CHOLMOD_TOO_LARGE, "problem too large") ;
136 p = NULL ;
137 }
138 else
139 {
140 /* call malloc, or its equivalent */
141 p = SuiteSparse_malloc (n, size) ;
142
143 if (p == NULL)
144 {
145 /* failure: out of memory */
146 ERROR (CHOLMOD_OUT_OF_MEMORY, "out of memory") ;
147 }
148 else
149 {
150 /* success: increment the count of objects allocated */
151 Common->malloc_count++ ;
152 Common->memory_inuse += (n * size) ;
153 Common->memory_usage =
154 MAX (Common->memory_usage, Common->memory_inuse) ;
155 PRINTM (("cholmod_malloc %p %g cnt: %g inuse %g\n",
156 p, (double) n*size, (double) Common->malloc_count,
157 (double) Common->memory_inuse)) ;
158 }
159 }
160 return (p) ;
161 }
162
163
164 /* ========================================================================== */
165 /* === cholmod_free ========================================================= */
166 /* ========================================================================== */
167
168 /* Wrapper around free routine. Returns NULL, which can be assigned to the
169 * pointer being freed, as in:
170 *
171 * p = cholmod_free (n, sizeof (int), p, Common) ;
172 *
173 * In CHOLMOD, the syntax:
174 *
175 * cholmod_free (n, sizeof (int), p, Common) ;
176 *
177 * is used if p is a local pointer and the routine is returning shortly.
178 * Uses a pointer to the free routine (or its equivalent) defined in Common.
179 * Nothing is freed if the pointer is NULL.
180 */
181
CHOLMOD(free)182 void *CHOLMOD(free) /* always returns NULL */
183 (
184 /* ---- input ---- */
185 size_t n, /* number of items */
186 size_t size, /* size of each item */
187 /* ---- in/out --- */
188 void *p, /* block of memory to free */
189 /* --------------- */
190 cholmod_common *Common
191 )
192 {
193 RETURN_IF_NULL_COMMON (NULL) ;
194 if (p != NULL)
195 {
196 /* only free the object if the pointer is not NULL */
197 /* call free, or its equivalent */
198 SuiteSparse_free (p) ;
199
200 Common->malloc_count-- ;
201 Common->memory_inuse -= (n * size) ;
202 PRINTM (("cholmod_free %p %g cnt: %g inuse %g\n",
203 p, (double) n*size, (double) Common->malloc_count,
204 (double) Common->memory_inuse)) ;
205 /* This assertion will fail if the user calls cholmod_malloc and
206 * cholmod_free with mismatched memory sizes. It shouldn't fail
207 * otherwise. */
208 ASSERT (IMPLIES (Common->malloc_count == 0, Common->memory_inuse == 0));
209 }
210 /* return NULL, and the caller should assign this to p. This avoids
211 * freeing the same pointer twice. */
212 return (NULL) ;
213 }
214
215
216 /* ========================================================================== */
217 /* === cholmod_calloc ======================================================= */
218 /* ========================================================================== */
219
220 /* Wrapper around calloc routine.
221 *
222 * Uses a pointer to the calloc routine (or its equivalent) defined in Common.
223 * This routine is identical to malloc, except that it zeros the newly allocated
224 * block to zero.
225 */
226
CHOLMOD(calloc)227 void *CHOLMOD(calloc) /* returns pointer to the newly calloc'd block */
228 (
229 /* ---- input ---- */
230 size_t n, /* number of items */
231 size_t size, /* size of each item */
232 /* --------------- */
233 cholmod_common *Common
234 )
235 {
236 void *p ;
237
238 RETURN_IF_NULL_COMMON (NULL) ;
239 if (size == 0)
240 {
241 ERROR (CHOLMOD_INVALID, "sizeof(item) must be > 0") ;
242 p = NULL ;
243 }
244 else if (n >= (Size_max / size) || n >= Int_max)
245 {
246 /* object is too big to allocate without causing integer overflow */
247 ERROR (CHOLMOD_TOO_LARGE, "problem too large") ;
248 p = NULL ;
249 }
250 else
251 {
252 /* call calloc, or its equivalent */
253 p = SuiteSparse_calloc (n, size) ;
254
255 if (p == NULL)
256 {
257 /* failure: out of memory */
258 ERROR (CHOLMOD_OUT_OF_MEMORY, "out of memory") ;
259 }
260 else
261 {
262 /* success: increment the count of objects allocated */
263 Common->malloc_count++ ;
264 Common->memory_inuse += (n * size) ;
265 Common->memory_usage =
266 MAX (Common->memory_usage, Common->memory_inuse) ;
267 PRINTM (("cholmod_malloc %p %g cnt: %g inuse %g\n",
268 p, (double) n*size, (double) Common->malloc_count,
269 (double) Common->memory_inuse)) ;
270 }
271 }
272 return (p) ;
273 }
274
275
276 /* ========================================================================== */
277 /* === cholmod_realloc ====================================================== */
278 /* ========================================================================== */
279
280 /* Wrapper around realloc routine. Given a pointer p to a block of size
281 * (*n)*size memory, it changes the size of the block pointed to by p to be
282 * MAX(1,nnew)*size in size. It may return a pointer different than p. This
283 * should be used as (for a pointer to int):
284 *
285 * p = cholmod_realloc (nnew, sizeof (int), p, *n, Common) ;
286 *
287 * If p is NULL, this is the same as p = cholmod_malloc (...).
288 * A size of nnew=0 is treated as nnew=1.
289 *
290 * If the realloc fails, p is returned unchanged and Common->status is set
291 * to CHOLMOD_OUT_OF_MEMORY. If successful, Common->status is not modified,
292 * and p is returned (possibly changed) and pointing to a large block of memory.
293 *
294 * Uses a pointer to the realloc routine (or its equivalent) defined in Common.
295 */
296
CHOLMOD(realloc)297 void *CHOLMOD(realloc) /* returns pointer to reallocated block */
298 (
299 /* ---- input ---- */
300 size_t nnew, /* requested # of items in reallocated block */
301 size_t size, /* size of each item */
302 /* ---- in/out --- */
303 void *p, /* block of memory to realloc */
304 size_t *n, /* current size on input, nnew on output if successful*/
305 /* --------------- */
306 cholmod_common *Common
307 )
308 {
309 size_t nold = (*n) ;
310 void *pnew ;
311 size_t s ;
312 int ok = TRUE ;
313
314 RETURN_IF_NULL_COMMON (NULL) ;
315 if (size == 0)
316 {
317 ERROR (CHOLMOD_INVALID, "sizeof(item) must be > 0") ;
318 p = NULL ;
319 }
320 else if (p == NULL)
321 {
322 /* A fresh object is being allocated. */
323 PRINT1 (("realloc fresh: %d %d\n", nnew, size)) ;
324 p = CHOLMOD(malloc) (nnew, size, Common) ;
325 *n = (p == NULL) ? 0 : nnew ;
326 }
327 else if (nold == nnew)
328 {
329 /* Nothing to do. Do not change p or n. */
330 PRINT1 (("realloc nothing: %d %d\n", nnew, size)) ;
331 }
332 else if (nnew >= (Size_max / size) || nnew >= Int_max)
333 {
334 /* failure: nnew is too big. Do not change p or n. */
335 ERROR (CHOLMOD_TOO_LARGE, "problem too large") ;
336 }
337 else
338 {
339 /* The object exists, and is changing to some other nonzero size. */
340 /* call realloc, or its equivalent */
341 PRINT1 (("realloc : %d to %d, %d\n", nold, nnew, size)) ;
342 pnew = SuiteSparse_realloc (nnew, nold, size, p, &ok) ;
343 if (ok)
344 {
345 /* success: return revised p and change the size of the block */
346 PRINTM (("cholmod_free %p %g cnt: %g inuse %g\n"
347 "cholmod_malloc %p %g cnt: %g inuse %g\n",
348 p, (double) nold*size, (double) Common->malloc_count-1,
349 (double) (Common->memory_inuse - nold*size),
350 pnew, (double) nnew*size, (double) Common->malloc_count,
351 (double) (Common->memory_inuse + (nnew-nold)*size))) ;
352 p = pnew ;
353 *n = nnew ;
354 Common->memory_inuse += ((nnew-nold) * size) ;
355 }
356 else
357 {
358 /* Increasing the size of the block has failed.
359 * Do not change n. */
360 ERROR (CHOLMOD_OUT_OF_MEMORY, "out of memory") ;
361 }
362
363 Common->memory_usage = MAX (Common->memory_usage, Common->memory_inuse);
364 }
365
366 return (p) ;
367 }
368
369
370 /* ========================================================================== */
371 /* === cholmod_realloc_multiple ============================================= */
372 /* ========================================================================== */
373
374 /* reallocate multiple blocks of memory, all of the same size (up to two integer
375 * and two real blocks). Either reallocations all succeed, or all are returned
376 * in the original size (they are freed if the original size is zero). The nnew
377 * blocks are of size 1 or more.
378 */
379
CHOLMOD(realloc_multiple)380 int CHOLMOD(realloc_multiple)
381 (
382 /* ---- input ---- */
383 size_t nnew, /* requested # of items in reallocated blocks */
384 int nint, /* number of int/SuiteSparse_long blocks */
385 int xtype, /* CHOLMOD_PATTERN, _REAL, _COMPLEX, or _ZOMPLEX */
386 /* ---- in/out --- */
387 void **Iblock, /* int or SuiteSparse_long block */
388 void **Jblock, /* int or SuiteSparse_long block */
389 void **Xblock, /* complex or double block */
390 void **Zblock, /* zomplex case only: double block */
391 size_t *nold_p, /* current size of the I,J,X,Z blocks on input,
392 * nnew on output if successful */
393 /* --------------- */
394 cholmod_common *Common
395 )
396 {
397 double *xx, *zz ;
398 size_t i, j, x, z, nold ;
399
400 RETURN_IF_NULL_COMMON (FALSE) ;
401
402 if (xtype < CHOLMOD_PATTERN || xtype > CHOLMOD_ZOMPLEX)
403 {
404 ERROR (CHOLMOD_INVALID, "invalid xtype") ;
405 return (FALSE) ;
406 }
407
408 nold = *nold_p ;
409
410 if (nint < 1 && xtype == CHOLMOD_PATTERN)
411 {
412 /* nothing to do */
413 return (TRUE) ;
414 }
415
416 i = nold ;
417 j = nold ;
418 x = nold ;
419 z = nold ;
420
421 if (nint > 0)
422 {
423 *Iblock = CHOLMOD(realloc) (nnew, sizeof (Int), *Iblock, &i, Common) ;
424 }
425 if (nint > 1)
426 {
427 *Jblock = CHOLMOD(realloc) (nnew, sizeof (Int), *Jblock, &j, Common) ;
428 }
429
430 switch (xtype)
431 {
432 case CHOLMOD_REAL:
433 *Xblock = CHOLMOD(realloc) (nnew, sizeof (double), *Xblock, &x,
434 Common) ;
435 break ;
436
437 case CHOLMOD_COMPLEX:
438 *Xblock = CHOLMOD(realloc) (nnew, 2*sizeof (double), *Xblock, &x,
439 Common) ;
440 break ;
441
442 case CHOLMOD_ZOMPLEX:
443 *Xblock = CHOLMOD(realloc) (nnew, sizeof (double), *Xblock, &x,
444 Common) ;
445 *Zblock = CHOLMOD(realloc) (nnew, sizeof (double), *Zblock, &z,
446 Common) ;
447 break ;
448 }
449
450 if (Common->status < CHOLMOD_OK)
451 {
452 /* one or more realloc's failed. Resize all back down to nold. */
453
454 if (nold == 0)
455 {
456
457 if (nint > 0)
458 {
459 *Iblock = CHOLMOD(free) (i, sizeof (Int), *Iblock, Common) ;
460 }
461 if (nint > 1)
462 {
463 *Jblock = CHOLMOD(free) (j, sizeof (Int), *Jblock, Common) ;
464 }
465
466 switch (xtype)
467 {
468 case CHOLMOD_REAL:
469 *Xblock = CHOLMOD(free) (x, sizeof (double), *Xblock,
470 Common) ;
471 break ;
472
473 case CHOLMOD_COMPLEX:
474 *Xblock = CHOLMOD(free) (x, 2*sizeof (double), *Xblock,
475 Common) ;
476 break ;
477
478 case CHOLMOD_ZOMPLEX:
479 *Xblock = CHOLMOD(free) (x, sizeof (double), *Xblock,
480 Common) ;
481 *Zblock = CHOLMOD(free) (x, sizeof (double), *Zblock,
482 Common) ;
483 break ;
484 }
485
486 }
487 else
488 {
489 if (nint > 0)
490 {
491 *Iblock = CHOLMOD(realloc) (nold, sizeof (Int), *Iblock, &i,
492 Common) ;
493 }
494 if (nint > 1)
495 {
496 *Jblock = CHOLMOD(realloc) (nold, sizeof (Int), *Jblock, &j,
497 Common) ;
498 }
499
500 switch (xtype)
501 {
502 case CHOLMOD_REAL:
503 *Xblock = CHOLMOD(realloc) (nold, sizeof (double),
504 *Xblock, &x, Common) ;
505 break ;
506
507 case CHOLMOD_COMPLEX:
508 *Xblock = CHOLMOD(realloc) (nold, 2*sizeof (double),
509 *Xblock, &x, Common) ;
510 break ;
511
512 case CHOLMOD_ZOMPLEX:
513 *Xblock = CHOLMOD(realloc) (nold, sizeof (double),
514 *Xblock, &x, Common) ;
515 *Zblock = CHOLMOD(realloc) (nold, sizeof (double),
516 *Zblock, &z, Common) ;
517 break ;
518 }
519
520 }
521
522 return (FALSE) ;
523 }
524
525 if (nold == 0)
526 {
527 /* New space was allocated. Clear the first entry so that valgrind
528 * doesn't complain about its access in change_complexity
529 * (Core/cholmod_complex.c). */
530 xx = *Xblock ;
531 zz = *Zblock ;
532 switch (xtype)
533 {
534 case CHOLMOD_REAL:
535 xx [0] = 0 ;
536 break ;
537
538 case CHOLMOD_COMPLEX:
539 xx [0] = 0 ;
540 xx [1] = 0 ;
541 break ;
542
543 case CHOLMOD_ZOMPLEX:
544 xx [0] = 0 ;
545 zz [0] = 0 ;
546 break ;
547 }
548 }
549
550 /* all realloc's succeeded, change size to reflect realloc'ed size. */
551 *nold_p = nnew ;
552 return (TRUE) ;
553 }
554