1 /* ========================================================================== */
2 /* === UMF_garbage_collection =============================================== */
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 Compress the elements at the tail of Numeric->Memory, and delete the tuples.
12 Elements are renumbered. The new numbering space is compressed, and
13 in the order of element creation (original elements of A first, followed
14 by the new elements in the order that they were formed).
15
16 Only called by UMF_get_memory.
17
18 There are 5 ways in which garbage collection can be performed:
19
20 Allocate a new working array for the current frontal matrix. In this
21 case, there are never any pivot rows/columns in the current frontal
22 matrix (fnpiv = 0), and the old working array for the current frontal
23 matrix can always be fully compacted, to fnrows-by-fncols.
24
25 UMF_kernel : UMF_extend : UMF_grow_front : UMF_get_memory
26 UMF_kernel : UMF_init_front : UMF_grow_front : UMF_get_memory
27 UMF_kernel : UMF_start_front : UMF_grow_front : UMF_get_memory
28
29 Allocate a new element. In this case, UMF_grow_front may or may not
30 be subsequently called, depending on Work->do_grow. There are never
31 any pivot rows/columns in the current frontal matrix (fnpiv=0), but one
32 may be added if UMF_init_front is to be called just after
33 UMF_create_element. If do_grow is true, then the current front can be
34 fully compacted, to fnrows-by-fncols. Otherwise, it can only be
35 partially compacted, to MAX (fnrows, fnrows_new + 1) -by-
36 MAX (fncols, fncols_new + 1).
37
38 UMF_kernel : UMF_create_element : UMF_get_memory
39
40 Allocate rows of L and columns of U. In this case, the current
41 frontal matrix is only partially compacted, to (fnrows_new + 1)-by-
42 (fncols_new + 1). There are pivots in the frontal matrix (fnpiv > 0).
43
44 UMF_kernel : UMF_store_lu : UMF_get_memory
45 */
46
47 #include "umf_internal.h"
48 #include "umf_garbage_collection.h"
49
UMF_garbage_collection(NumericType * Numeric,WorkType * Work,Int drnew,Int dcnew,Int do_Fcpos)50 GLOBAL void UMF_garbage_collection
51 (
52 NumericType *Numeric,
53 WorkType *Work,
54 Int drnew, /* compact current front to drnew-by-dcnew */
55 Int dcnew,
56 Int do_Fcpos
57 )
58 {
59 /* ---------------------------------------------------------------------- */
60 /* local variables */
61 /* ---------------------------------------------------------------------- */
62
63 Int size, e, n_row, n_col, nrows, ncols, nrowsleft, ncolsleft, prevsize,
64 csize, size2, i2, j2, i, j, cdeg, rdeg, *E, row, col,
65 *Rows, *Cols, *Rows2, *Cols2, nel, e2, *Row_tuples, *Col_tuples,
66 *Row_degree, *Col_degree ;
67 Entry *C, *C1, *C3, *C2 ;
68 Unit *psrc, *pdest, *p, *pnext ;
69 Element *epsrc, *epdest ;
70
71 #ifndef NDEBUG
72 Int nmark ;
73 #endif
74
75 /* ---------------------------------------------------------------------- */
76 /* get parameters */
77 /* ---------------------------------------------------------------------- */
78
79 Col_degree = Numeric->Cperm ; /* for NON_PIVOTAL_COL macro */
80 Row_degree = Numeric->Rperm ; /* for NON_PIVOTAL_ROW macro */
81 Row_tuples = Numeric->Uip ;
82 Col_tuples = Numeric->Lip ;
83 E = Work->E ;
84 n_row = Work->n_row ;
85 n_col = Work->n_col ;
86
87 /* note that the tuple lengths (Col_tlen and Row_tlen) are updated, but */
88 /* the tuple lists themselves are stale and are about to be destroyed */
89 /* and recreated. Do not attempt to scan them until they are recreated. */
90
91 #ifndef NDEBUG
92 DEBUGm1 (("::::GARBAGE COLLECTION::::\n")) ;
93 UMF_dump_memory (Numeric) ;
94 #endif
95
96 Numeric->ngarbage++ ;
97
98 /* ---------------------------------------------------------------------- */
99 /* delete the tuple lists by marking the blocks as free */
100 /* ---------------------------------------------------------------------- */
101
102 /* do not modify Row_tlen and Col_tlen */
103 /* those are needed for UMF_build_tuples */
104
105 for (row = 0 ; row < n_row ; row++)
106 {
107 if (NON_PIVOTAL_ROW (row) && Row_tuples [row])
108 {
109 DEBUG2 (("row "ID" tuples "ID"\n", row, Row_tuples [row])) ;
110 p = Numeric->Memory + Row_tuples [row] - 1 ;
111 DEBUG2 (("Freeing tuple list row "ID", p-S "ID", size "ID"\n",
112 row, (Int) (p-Numeric->Memory), p->header.size)) ;
113 ASSERT (p->header.size > 0) ;
114 ASSERT (p >= Numeric->Memory + Numeric->itail) ;
115 ASSERT (p < Numeric->Memory + Numeric->size) ;
116 p->header.size = -p->header.size ;
117 Row_tuples [row] = 0 ;
118 }
119 }
120
121 for (col = 0 ; col < n_col ; col++)
122 {
123 if (NON_PIVOTAL_COL (col) && Col_tuples [col])
124 {
125 DEBUG2 (("col "ID" tuples "ID"\n", col, Col_tuples [col])) ;
126 p = Numeric->Memory + Col_tuples [col] - 1 ;
127 DEBUG2 (("Freeing tuple list col "ID", p-S "ID", size "ID"\n",
128 col, (Int) (p-Numeric->Memory), p->header.size)) ;
129 ASSERT (p->header.size > 0) ;
130 ASSERT (p >= Numeric->Memory + Numeric->itail) ;
131 ASSERT (p < Numeric->Memory + Numeric->size) ;
132 p->header.size = -p->header.size ;
133 Col_tuples [col] = 0 ;
134 }
135 }
136
137 /* ---------------------------------------------------------------------- */
138 /* mark the elements, and compress the name space */
139 /* ---------------------------------------------------------------------- */
140
141 nel = Work->nel ;
142 ASSERT (nel < Work->elen) ;
143
144 #ifndef NDEBUG
145 nmark = 0 ;
146 UMF_dump_current_front (Numeric, Work, FALSE) ;
147 DEBUGm1 (("E [0] "ID" \n", E [0])) ;
148 ASSERT (IMPLIES (E [0],
149 Work->Flublock == (Entry *) (Numeric->Memory + E [0]))) ;
150 ASSERT (IMPLIES (Work->Flublock,
151 Work->Flublock == (Entry *) (Numeric->Memory + E [0]))) ;
152 ASSERT ((E [0] != 0) == (Work->Flublock != (Entry *) NULL)) ;
153 #endif
154
155 e2 = 0 ;
156
157 for (e = 0 ; e <= nel ; e++) /* for all elements in order of creation */
158 {
159 if (E [e])
160 {
161 psrc = Numeric->Memory + E [e] ;
162 psrc-- ; /* get the header of this block */
163 if (e > 0)
164 {
165 e2++ ; /* do not renumber element zero */
166 }
167 ASSERT (psrc->header.size > 0) ;
168 psrc->header.size = e2 ; /* store the new name in the header */
169 #ifndef NDEBUG
170 nmark++ ;
171 #endif
172 DEBUG7 ((ID":: Mark e "ID" at psrc-S "ID", new e "ID"\n",
173 nmark, e, (Int) (psrc-Numeric->Memory), e2)) ;
174 E [e] = 0 ;
175 if (e == Work->prior_element)
176 {
177 Work->prior_element = e2 ;
178 }
179 }
180 }
181
182 /* all 1..e2 are now in use (element zero may or may not be in use) */
183 Work->nel = e2 ;
184 nel = Work->nel ;
185
186 #ifndef NDEBUG
187 for (e = 0 ; e < Work->elen ; e++)
188 {
189 ASSERT (!E [e]) ;
190 }
191 #endif
192
193 /* ---------------------------------------------------------------------- */
194 /* compress the elements */
195 /* ---------------------------------------------------------------------- */
196
197 /* point to tail marker block of size 1 + header */
198 psrc = Numeric->Memory + Numeric->size - 2 ;
199 pdest = psrc ;
200 prevsize = psrc->header.prevsize ;
201 DEBUG7 (("Starting the compression:\n")) ;
202
203 while (prevsize > 0)
204 {
205
206 /* ------------------------------------------------------------------ */
207 /* move up to the next element above the current header, and */
208 /* get the element name and size */
209 /* (if it is an element, the name will be positive) */
210 /* ------------------------------------------------------------------ */
211
212 size = prevsize ;
213 psrc -= (size + 1) ;
214 e = psrc->header.size ;
215 prevsize = psrc->header.prevsize ;
216 /* top block at tail has prevsize of 0 */
217
218 /* a free block will have a negative size, so skip it */
219 /* otherwise, if size >= 0, it holds the element name, not the size */
220
221 DEBUG8 (("psrc-S: "ID" prevsize: "ID" size: "ID,
222 (Int) (psrc-Numeric->Memory), prevsize, size)) ;
223
224 if (e == 0)
225 {
226 /* -------------------------------------------------------------- */
227 /* this is the current frontal matrix */
228 /* -------------------------------------------------------------- */
229
230 Entry *F1, *F2, *Fsrc, *Fdst ;
231 Int c, r, k, dr, dc, gap, gap1, gap2, nb ;
232
233 /* shift the frontal matrix down */
234 F1 = (Entry *) (psrc + 1) ;
235
236 /* get the size of the current front. r and c could be zero */
237 k = Work->fnpiv ;
238 dr = Work->fnr_curr ;
239 dc = Work->fnc_curr ;
240 r = Work->fnrows ;
241 c = Work->fncols ;
242 nb = Work->nb ;
243
244 ASSERT ((dr >= 0 && (dr % 2) == 1) || dr == 0) ;
245 ASSERT (drnew >= 0) ;
246 if (drnew % 2 == 0)
247 {
248 /* make sure leading frontal matrix dimension is always odd */
249 drnew++ ;
250 }
251 drnew = MIN (dr, drnew) ;
252 ASSERT ((drnew >= 0 && (drnew % 2) == 1) || drnew == 0) ;
253
254 pnext = pdest ;
255
256 #ifndef NDEBUG
257 DEBUGm2 (("move front: dr "ID" dc "ID" r "ID" drnew "ID" c "ID
258 " dcnew " ID" k "ID"\n", dr, dc, r, drnew, c, dcnew, k)) ;
259 DEBUG7 (("\n")) ;
260 DEBUG7 ((ID":: Move current frontal matrix from: psrc-S: "ID" \n",
261 nmark, (Int) (psrc-Numeric->Memory))) ;
262 nmark-- ;
263 ASSERT (E [e] == 0) ;
264 ASSERT (Work->Flublock == F1) ;
265 ASSERT (Work->Flblock == Work->Flublock + nb*nb) ;
266 ASSERT (Work->Fublock == Work->Flblock + dr*nb) ;
267 ASSERT (Work->Fcblock == Work->Fublock + nb*dc) ;
268 DEBUG7 (("C block: ")) ;
269 UMF_dump_dense (Work->Fcblock, dr, r, c) ;
270 DEBUG7 (("L block: ")) ;
271 UMF_dump_dense (Work->Flblock, dr, r, k);
272 DEBUG7 (("U' block: ")) ;
273 UMF_dump_dense (Work->Fublock, dc, c, k) ;
274 DEBUG7 (("LU block: ")) ;
275 UMF_dump_dense (Work->Flublock, nb, k, k) ;
276 ASSERT (r <= drnew && c <= dcnew && drnew <= dr && dcnew <= dc) ;
277 #endif
278
279 /* compact frontal matrix to drnew-by-dcnew before moving it */
280
281 /* do not compact the LU block (nb-by-nb) */
282
283 /* compact the columns of L (from dr-by-nb to drnew-by-nb) */
284 Fsrc = Work->Flblock ;
285 Fdst = Work->Flblock ;
286 ASSERT (Fdst == F1 + nb*nb) ;
287 gap1 = dr - r ;
288 gap2 = drnew - r ;
289 ASSERT (gap1 >= 0) ;
290 for (j = 0 ; j < k ; j++)
291 {
292 for (i = 0 ; i < r ; i++)
293 {
294 *Fdst++ = *Fsrc++ ;
295 }
296 Fsrc += gap1 ;
297 Fdst += gap2 ;
298 }
299 ASSERT (Fdst == F1 + nb*nb + drnew*k) ;
300 Fdst += drnew * (nb - k) ;
301
302 /* compact the rows of U (U' from dc-by-nb to dcnew-by-nb) */
303 Fsrc = Work->Fublock ;
304 ASSERT (Fdst == F1 + nb*nb + drnew*nb) ;
305 gap1 = dc - c ;
306 gap2 = dcnew - c ;
307 for (i = 0 ; i < k ; i++)
308 {
309 for (j = 0 ; j < c ; j++)
310 {
311 *Fdst++ = *Fsrc++ ;
312 }
313 Fsrc += gap1 ;
314 Fdst += gap2 ;
315 }
316 ASSERT (Fdst == F1 + nb*nb + drnew*nb + dcnew*k) ;
317 Fdst += dcnew * (nb - k) ;
318
319 /* compact the columns of C (from dr-by-dc to drnew-by-dcnew) */
320 Fsrc = Work->Fcblock ;
321 ASSERT (Fdst == F1 + nb*nb + drnew*nb + nb*dcnew) ;
322 gap1 = dr - r ;
323 gap2 = drnew - r ;
324 for (j = 0 ; j < c ; j++)
325 {
326 for (i = 0 ; i < r ; i++)
327 {
328 *Fdst++ = *Fsrc++ ;
329 }
330 Fsrc += gap1 ;
331 Fdst += gap2 ;
332 }
333 ASSERT (Fdst == F1 + nb*nb + drnew*nb + nb*dcnew + drnew*c) ;
334
335 /* recompute Fcpos, if necessary */
336 if (do_Fcpos)
337 {
338 Int *Fcols, *Fcpos ;
339 Fcols = Work->Fcols ;
340 Fcpos = Work->Fcpos ;
341 for (j = 0 ; j < c ; j++)
342 {
343 col = Fcols [j] ;
344 ASSERT (col >= 0 && col < Work->n_col) ;
345 ASSERT (Fcpos [col] == j * dr) ;
346 Fcpos [col] = j * drnew ;
347 }
348 #ifndef NDEBUG
349 {
350 Int cnt = 0 ;
351 for (j = 0 ; j < Work->n_col ; j++)
352 {
353 if (Fcpos [j] != EMPTY) cnt++ ;
354 }
355 DEBUGm2 (("Recompute Fcpos cnt "ID" c "ID"\n", cnt, c)) ;
356 ASSERT (cnt == c) ;
357 }
358 #endif
359 }
360
361 #ifndef NDEBUG
362 DEBUGm2 (("Compacted front, drnew "ID" dcnew "ID"\n", drnew, dcnew)) ;
363 DEBUG7 (("C block: ")) ;
364 UMF_dump_dense (F1 + nb*nb + drnew*nb + nb*dcnew, drnew, r, c) ;
365 DEBUG7 (("L block: ")) ;
366 UMF_dump_dense (F1 + nb*nb, drnew, r, k) ;
367 DEBUG7 (("U block: ")) ;
368 UMF_dump_dense (F1 + nb*nb + drnew*nb, nb, k, c) ;
369 DEBUG7 (("LU block: ")) ;
370 UMF_dump_dense (F1, nb, k, k) ;
371 #endif
372
373 /* Compacted dimensions of the new frontal matrix. */
374 Work->fnr_curr = drnew ;
375 Work->fnc_curr = dcnew ;
376 Work->fcurr_size = (drnew + nb) * (dcnew + nb) ;
377 size = UNITS (Entry, Work->fcurr_size) ;
378
379 /* make sure the object doesn't evaporate. The front can have
380 * zero size (Work->fcurr_size = 0), but the size of the memory
381 * block containing it cannot have zero size. */
382 size = MAX (1, size) ;
383
384 /* get the destination of frontal matrix */
385 pnext->header.prevsize = size ;
386 pdest -= (size + 1) ;
387 F2 = (Entry *) (pdest + 1) ;
388
389 ASSERT ((unsigned Int) psrc + 1 + size <= (unsigned Int) pnext) ;
390 ASSERT (psrc <= pdest) ;
391 ASSERT (F1 <= F2) ;
392
393 /* move the C block first */
394 Fsrc = F1 + nb*nb + drnew*nb + nb*dcnew + drnew*c ;
395 Fdst = F2 + nb*nb + drnew*nb + nb*dcnew + drnew*c ;
396 gap = drnew - r ;
397 for (j = c-1 ; j >= 0 ; j--)
398 {
399 Fsrc -= gap ;
400 Fdst -= gap ;
401 /* move column j of C */
402 for (i = r-1 ; i >= 0 ; i--)
403 {
404 *--Fdst = *--Fsrc ;
405 }
406 }
407 ASSERT (Fsrc == F1 + nb*nb + drnew*nb + nb*dcnew) ;
408 ASSERT (Fdst == F2 + nb*nb + drnew*nb + nb*dcnew) ;
409
410 /* move the U block */
411 Fsrc -= dcnew * (nb - k) ;
412 Fdst -= dcnew * (nb - k) ;
413 ASSERT (Fsrc == F1 + nb*nb + drnew*nb + dcnew*k) ;
414 ASSERT (Fdst == F2 + nb*nb + drnew*nb + dcnew*k) ;
415 gap = dcnew - c ;
416 for (i = k-1 ; i >= 0 ; i--)
417 {
418 Fsrc -= gap ;
419 Fdst -= gap ;
420 for (j = c-1 ; j >= 0 ; j--)
421 {
422 *--Fdst = *--Fsrc ;
423 }
424 }
425 ASSERT (Fsrc == F1 + nb*nb + drnew*nb) ;
426 ASSERT (Fdst == F2 + nb*nb + drnew*nb) ;
427
428 /* move the L block */
429 Fsrc -= drnew * (nb - k) ;
430 Fdst -= drnew * (nb - k) ;
431 ASSERT (Fsrc == F1 + nb*nb + drnew*k) ;
432 ASSERT (Fdst == F2 + nb*nb + drnew*k) ;
433 gap = drnew - r ;
434 for (j = k-1 ; j >= 0 ; j--)
435 {
436 Fsrc -= gap ;
437 Fdst -= gap ;
438 for (i = r-1 ; i >= 0 ; i--)
439 {
440 *--Fdst = *--Fsrc ;
441 }
442 }
443 ASSERT (Fsrc == F1 + nb*nb) ;
444 ASSERT (Fdst == F2 + nb*nb) ;
445
446 /* move the LU block */
447 Fsrc -= nb * (nb - k) ;
448 Fdst -= nb * (nb - k) ;
449 ASSERT (Fsrc == F1 + nb*k) ;
450 ASSERT (Fdst == F2 + nb*k) ;
451 gap = nb - k ;
452 for (j = k-1 ; j >= 0 ; j--)
453 {
454 Fsrc -= gap ;
455 Fdst -= gap ;
456 for (i = k-1 ; i >= 0 ; i--)
457 {
458 *--Fdst = *--Fsrc ;
459 }
460 }
461 ASSERT (Fsrc == F1) ;
462 ASSERT (Fdst == F2) ;
463
464 E [0] = (pdest + 1) - Numeric->Memory ;
465
466 Work->Flublock = (Entry *) (Numeric->Memory + E [0]) ;
467 ASSERT (Work->Flublock == F2) ;
468 Work->Flblock = Work->Flublock + nb * nb ;
469 Work->Fublock = Work->Flblock + drnew * nb ;
470 Work->Fcblock = Work->Fublock + nb * dcnew ;
471
472 pdest->header.prevsize = 0 ;
473 pdest->header.size = size ;
474
475 #ifndef NDEBUG
476 DEBUG7 (("After moving compressed current frontal matrix:\n")) ;
477 DEBUG7 (("C block: ")) ;
478 UMF_dump_dense (Work->Fcblock, drnew, r, c) ;
479 DEBUG7 (("L block: ")) ;
480 UMF_dump_dense (Work->Flblock, drnew, r, k);
481 DEBUG7 (("U' block: ")) ;
482 UMF_dump_dense (Work->Fublock, dcnew, c, k) ;
483 DEBUG7 (("LU block: ")) ;
484 UMF_dump_dense (Work->Flublock, nb, k, k) ;
485 #endif
486
487 }
488 else if (e > 0)
489 {
490
491 /* -------------------------------------------------------------- */
492 /* this is an element, compress and move from psrc down to pdest */
493 /* -------------------------------------------------------------- */
494
495 #ifndef NDEBUG
496 DEBUG7 (("\n")) ;
497 DEBUG7 ((ID":: Move element "ID": from: "ID" \n",
498 nmark, e, (Int) (psrc-Numeric->Memory))) ;
499 nmark-- ;
500 ASSERT (e <= nel) ;
501 ASSERT (E [e] == 0) ;
502 #endif
503
504 /* -------------------------------------------------------------- */
505 /* get the element scalars, and pointers to C, Rows, and Cols: */
506 /* -------------------------------------------------------------- */
507
508 p = psrc + 1 ;
509 GET_ELEMENT (epsrc, p, Cols, Rows, ncols, nrows, C) ;
510 nrowsleft = epsrc->nrowsleft ;
511 ncolsleft = epsrc->ncolsleft ;
512 cdeg = epsrc->cdeg ;
513 rdeg = epsrc->rdeg ;
514
515 #ifndef NDEBUG
516 DEBUG7 ((" nrows "ID" nrowsleft "ID"\n", nrows, nrowsleft)) ;
517 DEBUG7 ((" ncols "ID" ncolsleft "ID"\n", ncols, ncolsleft)) ;
518 DEBUG8 ((" Rows:")) ;
519 for (i = 0 ; i < nrows ; i++) DEBUG8 ((" "ID, Rows [i])) ;
520 DEBUG8 (("\n Cols:")) ;
521 for (j = 0 ; j < ncols ; j++) DEBUG8 ((" "ID, Cols [j])) ;
522 DEBUG8 (("\n")) ;
523 #endif
524
525 /* -------------------------------------------------------------- */
526 /* determine the layout of the new element */
527 /* -------------------------------------------------------------- */
528
529 csize = nrowsleft * ncolsleft ;
530 size2 = UNITS (Element, 1)
531 + UNITS (Int, nrowsleft + ncolsleft)
532 + UNITS (Entry, csize) ;
533
534 DEBUG7 (("Old size "ID" New size "ID"\n", size, size2)) ;
535
536 pnext = pdest ;
537 pnext->header.prevsize = size2 ;
538 pdest -= (size2 + 1) ;
539
540 ASSERT (size2 <= size) ;
541 ASSERT ((unsigned Int) psrc + 1 + size <= (unsigned Int) pnext) ;
542 ASSERT (psrc <= pdest) ;
543
544 p = pdest + 1 ;
545 epdest = (Element *) p ;
546 p += UNITS (Element, 1) ;
547 Cols2 = (Int *) p ;
548 Rows2 = Cols2 + ncolsleft ;
549 p += UNITS (Int, nrowsleft + ncolsleft) ;
550 C2 = (Entry *) p ;
551
552 ASSERT (epdest >= epsrc) ;
553 ASSERT (Rows2 >= Rows) ;
554 ASSERT (Cols2 >= Cols) ;
555 ASSERT (C2 >= C) ;
556 ASSERT (p + UNITS (Entry, csize) == pnext) ;
557
558 /* -------------------------------------------------------------- */
559 /* move the contribution block */
560 /* -------------------------------------------------------------- */
561
562 /* overlap = psrc + size + 1 > pdest ; */
563
564 if (nrowsleft < nrows || ncolsleft < ncols)
565 {
566
567 /* ---------------------------------------------------------- */
568 /* compress contribution block in place prior to moving it */
569 /* ---------------------------------------------------------- */
570
571 DEBUG7 (("Compress C in place prior to move:\n"));
572 #ifndef NDEBUG
573 UMF_dump_dense (C, nrows, nrows, ncols) ;
574 #endif
575 C1 = C ;
576 C3 = C ;
577 for (j = 0 ; j < ncols ; j++)
578 {
579 if (Cols [j] >= 0)
580 {
581 for (i = 0 ; i < nrows ; i++)
582 {
583 if (Rows [i] >= 0)
584 {
585 *C3++ = C1 [i] ;
586 }
587 }
588 }
589 C1 += nrows ;
590 }
591 ASSERT (C3-C == csize) ;
592 DEBUG8 (("Newly compressed contrib. block (all in use):\n")) ;
593 #ifndef NDEBUG
594 UMF_dump_dense (C, nrowsleft, nrowsleft, ncolsleft) ;
595 #endif
596 }
597
598 /* shift the contribution block down */
599 C += csize ;
600 C2 += csize ;
601 for (i = 0 ; i < csize ; i++)
602 {
603 *--C2 = *--C ;
604 }
605
606 /* -------------------------------------------------------------- */
607 /* move the row indices */
608 /* -------------------------------------------------------------- */
609
610 i2 = nrowsleft ;
611 for (i = nrows - 1 ; i >= 0 ; i--)
612 {
613 ASSERT (Rows2+i2 >= Rows+i) ;
614 if (Rows [i] >= 0)
615 {
616 Rows2 [--i2] = Rows [i] ;
617 }
618 }
619 ASSERT (i2 == 0) ;
620
621 j2 = ncolsleft ;
622 for (j = ncols - 1 ; j >= 0 ; j--)
623 {
624 ASSERT (Cols2+j2 >= Cols+j) ;
625 if (Cols [j] >= 0)
626 {
627 Cols2 [--j2] = Cols [j] ;
628 }
629 }
630 ASSERT (j2 == 0) ;
631
632 /* -------------------------------------------------------------- */
633 /* construct the new header */
634 /* -------------------------------------------------------------- */
635
636 /* E [0...e] is now valid */
637 E [e] = (pdest + 1) - Numeric->Memory ;
638 epdest = (Element *) (pdest + 1) ;
639
640 epdest->next = EMPTY ; /* destroys the son list */
641 epdest->ncols = ncolsleft ;
642 epdest->nrows = nrowsleft ;
643 epdest->ncolsleft = ncolsleft ;
644 epdest->nrowsleft = nrowsleft ;
645 epdest->rdeg = rdeg ;
646 epdest->cdeg = cdeg ;
647
648 ASSERT (size2 <= size) ;
649 pdest->header.prevsize = 0 ;
650 pdest->header.size = size2 ;
651
652 DEBUG7 (("After moving it:\n")) ;
653 #ifndef NDEBUG
654 UMF_dump_element (Numeric, Work, e, FALSE) ;
655 #endif
656 }
657
658 #ifndef NDEBUG
659 else
660 {
661 DEBUG8 ((" free\n")) ;
662 }
663 #endif
664 DEBUG7 (("psrc "ID" tail "ID"\n",
665 (Int) (psrc-Numeric->Memory), Numeric->itail)) ;
666 }
667
668 ASSERT (psrc == Numeric->Memory + Numeric->itail) ;
669 ASSERT (nmark == 0) ;
670
671 /* ---------------------------------------------------------------------- */
672 /* final tail pointer */
673 /* ---------------------------------------------------------------------- */
674
675 ASSERT (pdest >= Numeric->Memory + Numeric->itail) ;
676 Numeric->itail = pdest - Numeric->Memory ;
677 pdest->header.prevsize = 0 ;
678 Numeric->ibig = EMPTY ;
679 Numeric->tail_usage = Numeric->size - Numeric->itail ;
680
681 /* ---------------------------------------------------------------------- */
682 /* clear the unused E [nel+1 .. Work->elen - 1] */
683 /* ---------------------------------------------------------------------- */
684
685 for (e = nel+1 ; e < Work->elen ; e++)
686 {
687 E [e] = 0 ;
688 }
689
690 #ifndef NDEBUG
691 UMF_dump_packed_memory (Numeric, Work) ;
692 #endif
693
694 DEBUG8 (("::::GARBAGE COLLECTION DONE::::\n")) ;
695 }
696