1 /* ========================================================================== */
2 /* === UMF_build_tuples ===================================================== */
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 Construct the tuple lists from a set of packed elements (no holes in
12 elements, no internal or external fragmentation, and a packed (0..Work->nel)
13 element name space). Assume no tuple lists are currently allocated, but
14 that the tuple lengths have been initialized by UMF_tuple_lengths.
15
16 Returns TRUE if successful, FALSE if not enough memory.
17 */
18
19 #include "umf_internal.h"
20 #include "umf_build_tuples.h"
21 #include "umf_mem_alloc_tail_block.h"
22
UMF_build_tuples(NumericType * Numeric,WorkType * Work)23 GLOBAL Int UMF_build_tuples
24 (
25 NumericType *Numeric,
26 WorkType *Work
27 )
28 {
29 /* ---------------------------------------------------------------------- */
30 /* local variables */
31 /* ---------------------------------------------------------------------- */
32
33 Int e, nrows, ncols, nel, *Rows, *Cols, row, col, n_row, n_col, *E,
34 *Row_tuples, *Row_degree, *Row_tlen,
35 *Col_tuples, *Col_degree, *Col_tlen, n1 ;
36 Element *ep ;
37 Unit *p ;
38 Tuple tuple, *tp ;
39
40 /* ---------------------------------------------------------------------- */
41 /* get parameters */
42 /* ---------------------------------------------------------------------- */
43
44 E = Work->E ;
45 Col_degree = Numeric->Cperm ; /* for NON_PIVOTAL_COL macro */
46 Row_degree = Numeric->Rperm ; /* for NON_PIVOTAL_ROW macro */
47 Row_tuples = Numeric->Uip ;
48 Row_tlen = Numeric->Uilen ;
49 Col_tuples = Numeric->Lip ;
50 Col_tlen = Numeric->Lilen ;
51 n_row = Work->n_row ;
52 n_col = Work->n_col ;
53 nel = Work->nel ;
54 n1 = Work->n1 ;
55
56 DEBUG3 (("BUILD_TUPLES: n_row "ID" n_col "ID" nel "ID"\n",
57 n_row, n_col, nel)) ;
58
59 /* ---------------------------------------------------------------------- */
60 /* allocate space for the tuple lists */
61 /* ---------------------------------------------------------------------- */
62
63 /* Garbage collection and memory reallocation have already attempted to */
64 /* ensure that there is enough memory for all the tuple lists. If */
65 /* memory allocation fails here, then there is nothing more to be done. */
66
67 for (row = n1 ; row < n_row ; row++)
68 {
69 if (NON_PIVOTAL_ROW (row))
70 {
71 Row_tuples [row] = UMF_mem_alloc_tail_block (Numeric,
72 UNITS (Tuple, TUPLES (Row_tlen [row]))) ;
73 if (!Row_tuples [row])
74 {
75 /* :: out of memory for row tuples :: */
76 DEBUGm4 (("out of memory: build row tuples\n")) ;
77 return (FALSE) ; /* out of memory for row tuples */
78 }
79 Row_tlen [row] = 0 ;
80 }
81 }
82
83 /* push on stack in reverse order, so column tuples are in the order */
84 /* that they will be deleted. */
85 for (col = n_col-1 ; col >= n1 ; col--)
86 {
87 if (NON_PIVOTAL_COL (col))
88 {
89 Col_tuples [col] = UMF_mem_alloc_tail_block (Numeric,
90 UNITS (Tuple, TUPLES (Col_tlen [col]))) ;
91 if (!Col_tuples [col])
92 {
93 /* :: out of memory for col tuples :: */
94 DEBUGm4 (("out of memory: build col tuples\n")) ;
95 return (FALSE) ; /* out of memory for col tuples */
96 }
97 Col_tlen [col] = 0 ;
98 }
99 }
100
101 #ifndef NDEBUG
102 UMF_dump_memory (Numeric) ;
103 #endif
104
105 /* ---------------------------------------------------------------------- */
106 /* create the tuple lists (exclude element 0) */
107 /* ---------------------------------------------------------------------- */
108
109 /* for all elements, in order of creation */
110 for (e = 1 ; e <= nel ; e++)
111 {
112 DEBUG9 (("Adding tuples for element: "ID" at "ID"\n", e, E [e])) ;
113 ASSERT (E [e]) ; /* no external fragmentation */
114 p = Numeric->Memory + E [e] ;
115 GET_ELEMENT_PATTERN (ep, p, Cols, Rows, ncols) ;
116 nrows = ep->nrows ;
117 ASSERT (e != 0) ;
118 ASSERT (e == 0 || nrows == ep->nrowsleft) ;
119 ASSERT (e == 0 || ncols == ep->ncolsleft) ;
120 tuple.e = e ;
121 for (tuple.f = 0 ; tuple.f < ncols ; tuple.f++)
122 {
123 col = Cols [tuple.f] ;
124 ASSERT (col >= n1 && col < n_col) ;
125 ASSERT (NON_PIVOTAL_COL (col)) ;
126 ASSERT (Col_tuples [col]) ;
127 tp = ((Tuple *) (Numeric->Memory + Col_tuples [col]))
128 + Col_tlen [col]++ ;
129 *tp = tuple ;
130 #ifndef NDEBUG
131 UMF_dump_rowcol (1, Numeric, Work, col, FALSE) ;
132 #endif
133 }
134 for (tuple.f = 0 ; tuple.f < nrows ; tuple.f++)
135 {
136 row = Rows [tuple.f] ;
137 ASSERT (row >= n1 && row < n_row) ;
138 ASSERT (NON_PIVOTAL_COL (col)) ;
139 ASSERT (Row_tuples [row]) ;
140 tp = ((Tuple *) (Numeric->Memory + Row_tuples [row]))
141 + Row_tlen [row]++ ;
142 *tp = tuple ;
143 #ifndef NDEBUG
144 UMF_dump_rowcol (0, Numeric, Work, row, FALSE) ;
145 #endif
146 }
147 }
148
149 /* ---------------------------------------------------------------------- */
150 /* the tuple lists are now valid, and can be scanned */
151 /* ---------------------------------------------------------------------- */
152
153 #ifndef NDEBUG
154 UMF_dump_memory (Numeric) ;
155 UMF_dump_matrix (Numeric, Work, FALSE) ;
156 #endif
157 DEBUG3 (("BUILD_TUPLES: done\n")) ;
158 return (TRUE) ;
159 }
160