1 /*
2 * Revision Control Information
3 *
4 * $Source$
5 * $Author$
6 * $Revision$
7 * $Date$
8 *
9 */
10 //#include "port.h"
11 #include "sparse_int.h"
12
13 ABC_NAMESPACE_IMPL_START
14
15
16 /*
17 * free-lists are only used if 'FAST_AND_LOOSE' is set; this is because
18 * we lose the debugging capability of libmm_t which trashes objects when
19 * they are free'd. However, FAST_AND_LOOSE is much faster if matrices
20 * are created and freed frequently.
21 */
22
23 #ifdef FAST_AND_LOOSE
24 sm_element *sm_element_freelist;
25 sm_row *sm_row_freelist;
26 sm_col *sm_col_freelist;
27 #endif
28
29
30 sm_matrix *
sm_alloc()31 sm_alloc()
32 {
33 register sm_matrix *A;
34
35 A = ALLOC(sm_matrix, 1);
36 A->rows = NIL(sm_row *);
37 A->cols = NIL(sm_col *);
38 A->nrows = A->ncols = 0;
39 A->rows_size = A->cols_size = 0;
40 A->first_row = A->last_row = NIL(sm_row);
41 A->first_col = A->last_col = NIL(sm_col);
42 A->user_word = NIL(char); /* for our user ... */
43 return A;
44 }
45
46
47 sm_matrix *
sm_alloc_size(row,col)48 sm_alloc_size(row, col)
49 int row, col;
50 {
51 register sm_matrix *A;
52
53 A = sm_alloc();
54 sm_resize(A, row, col);
55 return A;
56 }
57
58
59 void
sm_free(A)60 sm_free(A)
61 sm_matrix *A;
62 {
63 #ifdef FAST_AND_LOOSE
64 register sm_row *prow;
65
66 if (A->first_row != 0) {
67 for(prow = A->first_row; prow != 0; prow = prow->next_row) {
68 /* add the elements to the free list of elements */
69 prow->last_col->next_col = sm_element_freelist;
70 sm_element_freelist = prow->first_col;
71 }
72
73 /* Add the linked list of rows to the row-free-list */
74 A->last_row->next_row = sm_row_freelist;
75 sm_row_freelist = A->first_row;
76
77 /* Add the linked list of cols to the col-free-list */
78 A->last_col->next_col = sm_col_freelist;
79 sm_col_freelist = A->first_col;
80 }
81 #else
82 register sm_row *prow, *pnext_row;
83 register sm_col *pcol, *pnext_col;
84
85 for(prow = A->first_row; prow != 0; prow = pnext_row) {
86 pnext_row = prow->next_row;
87 sm_row_free(prow);
88 }
89 for(pcol = A->first_col; pcol != 0; pcol = pnext_col) {
90 pnext_col = pcol->next_col;
91 pcol->first_row = pcol->last_row = NIL(sm_element);
92 sm_col_free(pcol);
93 }
94 #endif
95
96 /* Free the arrays to map row/col numbers into pointers */
97 FREE(A->rows);
98 FREE(A->cols);
99 FREE(A);
100 }
101
102
103 sm_matrix *
sm_dup(A)104 sm_dup(A)
105 sm_matrix *A;
106 {
107 register sm_row *prow;
108 register sm_element *p;
109 register sm_matrix *B;
110
111 B = sm_alloc();
112 if (A->last_row != 0) {
113 sm_resize(B, A->last_row->row_num, A->last_col->col_num);
114 for(prow = A->first_row; prow != 0; prow = prow->next_row) {
115 for(p = prow->first_col; p != 0; p = p->next_col) {
116 (void) sm_insert(B, p->row_num, p->col_num);
117 }
118 }
119 }
120 return B;
121 }
122
123
124 void
sm_resize(A,row,col)125 sm_resize(A, row, col)
126 register sm_matrix *A;
127 int row, col;
128 {
129 register int i, new_size;
130
131 if (row >= A->rows_size) {
132 new_size = MAX(A->rows_size*2, row+1);
133 A->rows = REALLOC(sm_row *, A->rows, new_size);
134 for(i = A->rows_size; i < new_size; i++) {
135 A->rows[i] = NIL(sm_row);
136 }
137 A->rows_size = new_size;
138 }
139
140 if (col >= A->cols_size) {
141 new_size = MAX(A->cols_size*2, col+1);
142 A->cols = REALLOC(sm_col *, A->cols, new_size);
143 for(i = A->cols_size; i < new_size; i++) {
144 A->cols[i] = NIL(sm_col);
145 }
146 A->cols_size = new_size;
147 }
148 }
149
150
151 /*
152 * insert -- insert a value into the matrix
153 */
154 sm_element *
sm_insert(A,row,col)155 sm_insert(A, row, col)
156 register sm_matrix *A;
157 register int row, col;
158 {
159 register sm_row *prow;
160 register sm_col *pcol;
161 register sm_element *element;
162 sm_element *save_element;
163
164 if (row >= A->rows_size || col >= A->cols_size) {
165 sm_resize(A, row, col);
166 }
167
168 prow = A->rows[row];
169 if (prow == NIL(sm_row)) {
170 prow = A->rows[row] = sm_row_alloc();
171 prow->row_num = row;
172 sorted_insert(sm_row, A->first_row, A->last_row, A->nrows,
173 next_row, prev_row, row_num, row, prow);
174 }
175
176 pcol = A->cols[col];
177 if (pcol == NIL(sm_col)) {
178 pcol = A->cols[col] = sm_col_alloc();
179 pcol->col_num = col;
180 sorted_insert(sm_col, A->first_col, A->last_col, A->ncols,
181 next_col, prev_col, col_num, col, pcol);
182 }
183
184 /* get a new item, save its address */
185 sm_element_alloc(element);
186 save_element = element;
187
188 /* insert it into the row list */
189 sorted_insert(sm_element, prow->first_col, prow->last_col,
190 prow->length, next_col, prev_col, col_num, col, element);
191
192 /* if it was used, also insert it into the column list */
193 if (element == save_element) {
194 sorted_insert(sm_element, pcol->first_row, pcol->last_row,
195 pcol->length, next_row, prev_row, row_num, row, element);
196 } else {
197 /* otherwise, it was already in matrix -- free element we allocated */
198 sm_element_free(save_element);
199 }
200 return element;
201 }
202
203
204 sm_element *
sm_find(A,rownum,colnum)205 sm_find(A, rownum, colnum)
206 sm_matrix *A;
207 int rownum, colnum;
208 {
209 sm_row *prow;
210 sm_col *pcol;
211
212 prow = sm_get_row(A, rownum);
213 if (prow == NIL(sm_row)) {
214 return NIL(sm_element);
215 } else {
216 pcol = sm_get_col(A, colnum);
217 if (pcol == NIL(sm_col)) {
218 return NIL(sm_element);
219 }
220 if (prow->length < pcol->length) {
221 return sm_row_find(prow, colnum);
222 } else {
223 return sm_col_find(pcol, rownum);
224 }
225 }
226 }
227
228
229 void
sm_remove(A,rownum,colnum)230 sm_remove(A, rownum, colnum)
231 sm_matrix *A;
232 int rownum, colnum;
233 {
234 sm_remove_element(A, sm_find(A, rownum, colnum));
235 }
236
237
238
239 void
sm_remove_element(A,p)240 sm_remove_element(A, p)
241 register sm_matrix *A;
242 register sm_element *p;
243 {
244 register sm_row *prow;
245 register sm_col *pcol;
246
247 if (p == 0) return;
248
249 /* Unlink the element from its row */
250 prow = sm_get_row(A, p->row_num);
251 dll_unlink(p, prow->first_col, prow->last_col,
252 next_col, prev_col, prow->length);
253
254 /* if no more elements in the row, discard the row header */
255 if (prow->first_col == NIL(sm_element)) {
256 sm_delrow(A, p->row_num);
257 }
258
259 /* Unlink the element from its column */
260 pcol = sm_get_col(A, p->col_num);
261 dll_unlink(p, pcol->first_row, pcol->last_row,
262 next_row, prev_row, pcol->length);
263
264 /* if no more elements in the column, discard the column header */
265 if (pcol->first_row == NIL(sm_element)) {
266 sm_delcol(A, p->col_num);
267 }
268
269 sm_element_free(p);
270 }
271
272 void
sm_delrow(A,i)273 sm_delrow(A, i)
274 sm_matrix *A;
275 int i;
276 {
277 register sm_element *p, *pnext;
278 sm_col *pcol;
279 sm_row *prow;
280
281 prow = sm_get_row(A, i);
282 if (prow != NIL(sm_row)) {
283 /* walk across the row */
284 for(p = prow->first_col; p != 0; p = pnext) {
285 pnext = p->next_col;
286
287 /* unlink the item from the column (and delete it) */
288 pcol = sm_get_col(A, p->col_num);
289 sm_col_remove_element(pcol, p);
290
291 /* discard the column if it is now empty */
292 if (pcol->first_row == NIL(sm_element)) {
293 sm_delcol(A, pcol->col_num);
294 }
295 }
296
297 /* discard the row -- we already threw away the elements */
298 A->rows[i] = NIL(sm_row);
299 dll_unlink(prow, A->first_row, A->last_row,
300 next_row, prev_row, A->nrows);
301 prow->first_col = prow->last_col = NIL(sm_element);
302 sm_row_free(prow);
303 }
304 }
305
306 void
sm_delcol(A,i)307 sm_delcol(A, i)
308 sm_matrix *A;
309 int i;
310 {
311 register sm_element *p, *pnext;
312 sm_row *prow;
313 sm_col *pcol;
314
315 pcol = sm_get_col(A, i);
316 if (pcol != NIL(sm_col)) {
317 /* walk down the column */
318 for(p = pcol->first_row; p != 0; p = pnext) {
319 pnext = p->next_row;
320
321 /* unlink the element from the row (and delete it) */
322 prow = sm_get_row(A, p->row_num);
323 sm_row_remove_element(prow, p);
324
325 /* discard the row if it is now empty */
326 if (prow->first_col == NIL(sm_element)) {
327 sm_delrow(A, prow->row_num);
328 }
329 }
330
331 /* discard the column -- we already threw away the elements */
332 A->cols[i] = NIL(sm_col);
333 dll_unlink(pcol, A->first_col, A->last_col,
334 next_col, prev_col, A->ncols);
335 pcol->first_row = pcol->last_row = NIL(sm_element);
336 sm_col_free(pcol);
337 }
338 }
339
340 void
sm_copy_row(dest,dest_row,prow)341 sm_copy_row(dest, dest_row, prow)
342 register sm_matrix *dest;
343 int dest_row;
344 sm_row *prow;
345 {
346 register sm_element *p;
347
348 for(p = prow->first_col; p != 0; p = p->next_col) {
349 (void) sm_insert(dest, dest_row, p->col_num);
350 }
351 }
352
353
354 void
sm_copy_col(dest,dest_col,pcol)355 sm_copy_col(dest, dest_col, pcol)
356 register sm_matrix *dest;
357 int dest_col;
358 sm_col *pcol;
359 {
360 register sm_element *p;
361
362 for(p = pcol->first_row; p != 0; p = p->next_row) {
363 (void) sm_insert(dest, dest_col, p->row_num);
364 }
365 }
366
367
368 sm_row *
sm_longest_row(A)369 sm_longest_row(A)
370 sm_matrix *A;
371 {
372 register sm_row *large_row, *prow;
373 register int max_length;
374
375 max_length = 0;
376 large_row = NIL(sm_row);
377 for(prow = A->first_row; prow != 0; prow = prow->next_row) {
378 if (prow->length > max_length) {
379 max_length = prow->length;
380 large_row = prow;
381 }
382 }
383 return large_row;
384 }
385
386
387 sm_col *
sm_longest_col(A)388 sm_longest_col(A)
389 sm_matrix *A;
390 {
391 register sm_col *large_col, *pcol;
392 register int max_length;
393
394 max_length = 0;
395 large_col = NIL(sm_col);
396 for(pcol = A->first_col; pcol != 0; pcol = pcol->next_col) {
397 if (pcol->length > max_length) {
398 max_length = pcol->length;
399 large_col = pcol;
400 }
401 }
402 return large_col;
403 }
404
405 int
sm_num_elements(A)406 sm_num_elements(A)
407 sm_matrix *A;
408 {
409 register sm_row *prow;
410 register int num;
411
412 num = 0;
413 sm_foreach_row(A, prow) {
414 num += prow->length;
415 }
416 return num;
417 }
418
419 int
sm_read(fp,A)420 sm_read(fp, A)
421 FILE *fp;
422 sm_matrix **A;
423 {
424 int i, j, err;
425
426 *A = sm_alloc();
427 while (! feof(fp)) {
428 err = fscanf(fp, "%d %d", &i, &j);
429 if (err == EOF) {
430 return 1;
431 } else if (err != 2) {
432 return 0;
433 }
434 (void) sm_insert(*A, i, j);
435 }
436 return 1;
437 }
438
439
440 int
sm_read_compressed(fp,A)441 sm_read_compressed(fp, A)
442 FILE *fp;
443 sm_matrix **A;
444 {
445 int i, j, k, nrows, ncols;
446 unsigned long x;
447
448 *A = sm_alloc();
449 if (fscanf(fp, "%d %d", &nrows, &ncols) != 2) {
450 return 0;
451 }
452 sm_resize(*A, nrows, ncols);
453
454 for(i = 0; i < nrows; i++) {
455 if (fscanf(fp, "%lx", &x) != 1) {
456 return 0;
457 }
458 for(j = 0; j < ncols; j += 32) {
459 if (fscanf(fp, "%lx", &x) != 1) {
460 return 0;
461 }
462 for(k = j; x != 0; x >>= 1, k++) {
463 if (x & 1) {
464 (void) sm_insert(*A, i, k);
465 }
466 }
467 }
468 }
469 return 1;
470 }
471
472
473 void
sm_write(fp,A)474 sm_write(fp, A)
475 FILE *fp;
476 sm_matrix *A;
477 {
478 register sm_row *prow;
479 register sm_element *p;
480
481 for(prow = A->first_row; prow != 0; prow = prow->next_row) {
482 for(p = prow->first_col; p != 0; p = p->next_col) {
483 (void) fprintf(fp, "%d %d\n", p->row_num, p->col_num);
484 }
485 }
486 }
487
488 void
sm_print(fp,A)489 sm_print(fp, A)
490 FILE *fp;
491 sm_matrix *A;
492 {
493 register sm_row *prow;
494 register sm_col *pcol;
495 int c;
496
497 if (A->last_col->col_num >= 100) {
498 (void) fprintf(fp, " ");
499 for(pcol = A->first_col; pcol != 0; pcol = pcol->next_col) {
500 (void) fprintf(fp, "%d", (pcol->col_num / 100)%10);
501 }
502 putc('\n', fp);
503 }
504
505 if (A->last_col->col_num >= 10) {
506 (void) fprintf(fp, " ");
507 for(pcol = A->first_col; pcol != 0; pcol = pcol->next_col) {
508 (void) fprintf(fp, "%d", (pcol->col_num / 10)%10);
509 }
510 putc('\n', fp);
511 }
512
513 (void) fprintf(fp, " ");
514 for(pcol = A->first_col; pcol != 0; pcol = pcol->next_col) {
515 (void) fprintf(fp, "%d", pcol->col_num % 10);
516 }
517 putc('\n', fp);
518
519 (void) fprintf(fp, " ");
520 for(pcol = A->first_col; pcol != 0; pcol = pcol->next_col) {
521 (void) fprintf(fp, "-");
522 }
523 putc('\n', fp);
524
525 for(prow = A->first_row; prow != 0; prow = prow->next_row) {
526 (void) fprintf(fp, "%3d:", prow->row_num);
527
528 for(pcol = A->first_col; pcol != 0; pcol = pcol->next_col) {
529 c = sm_row_find(prow, pcol->col_num) ? '1' : '.';
530 putc(c, fp);
531 }
532 putc('\n', fp);
533 }
534 }
535
536
537 void
sm_dump(A,s,max)538 sm_dump(A, s, max)
539 sm_matrix *A;
540 char *s;
541 int max;
542 {
543 FILE *fp = stdout;
544
545 (void) fprintf(fp, "%s %d rows by %d cols\n", s, A->nrows, A->ncols);
546 if (A->nrows < max) {
547 sm_print(fp, A);
548 }
549 }
550
551 void
sm_cleanup()552 sm_cleanup()
553 {
554 #ifdef FAST_AND_LOOSE
555 register sm_element *p, *pnext;
556 register sm_row *prow, *pnextrow;
557 register sm_col *pcol, *pnextcol;
558
559 for(p = sm_element_freelist; p != 0; p = pnext) {
560 pnext = p->next_col;
561 FREE(p);
562 }
563 sm_element_freelist = 0;
564
565 for(prow = sm_row_freelist; prow != 0; prow = pnextrow) {
566 pnextrow = prow->next_row;
567 FREE(prow);
568 }
569 sm_row_freelist = 0;
570
571 for(pcol = sm_col_freelist; pcol != 0; pcol = pnextcol) {
572 pnextcol = pcol->next_col;
573 FREE(pcol);
574 }
575 sm_col_freelist = 0;
576 #endif
577 }
578 ABC_NAMESPACE_IMPL_END
579
580