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 /*
18 * allocate a new col vector
19 */
20 sm_col *
sm_col_alloc()21 sm_col_alloc()
22 {
23 register sm_col *pcol;
24
25 #ifdef FAST_AND_LOOSE
26 if (sm_col_freelist == NIL(sm_col)) {
27 pcol = ALLOC(sm_col, 1);
28 } else {
29 pcol = sm_col_freelist;
30 sm_col_freelist = pcol->next_col;
31 }
32 #else
33 pcol = ALLOC(sm_col, 1);
34 #endif
35
36 pcol->col_num = 0;
37 pcol->length = 0;
38 pcol->first_row = pcol->last_row = NIL(sm_element);
39 pcol->next_col = pcol->prev_col = NIL(sm_col);
40 pcol->flag = 0;
41 pcol->user_word = NIL(char); /* for our user ... */
42 return pcol;
43 }
44
45
46 /*
47 * free a col vector -- for FAST_AND_LOOSE, this is real cheap for cols;
48 * however, freeing a rowumn must still walk down the rowumn discarding
49 * the elements one-by-one; that is the only use for the extra '-DCOLS'
50 * compile flag ...
51 */
52 void
sm_col_free(pcol)53 sm_col_free(pcol)
54 register sm_col *pcol;
55 {
56 #if defined(FAST_AND_LOOSE) && ! defined(COLS)
57 if (pcol->first_row != NIL(sm_element)) {
58 /* Add the linked list of col items to the free list */
59 pcol->last_row->next_row = sm_element_freelist;
60 sm_element_freelist = pcol->first_row;
61 }
62
63 /* Add the col to the free list of cols */
64 pcol->next_col = sm_col_freelist;
65 sm_col_freelist = pcol;
66 #else
67 register sm_element *p, *pnext;
68
69 for(p = pcol->first_row; p != 0; p = pnext) {
70 pnext = p->next_row;
71 sm_element_free(p);
72 }
73 FREE(pcol);
74 #endif
75 }
76
77
78 /*
79 * duplicate an existing col
80 */
81 sm_col *
sm_col_dup(pcol)82 sm_col_dup(pcol)
83 register sm_col *pcol;
84 {
85 register sm_col *pnew;
86 register sm_element *p;
87
88 pnew = sm_col_alloc();
89 for(p = pcol->first_row; p != 0; p = p->next_row) {
90 (void) sm_col_insert(pnew, p->row_num);
91 }
92 return pnew;
93 }
94
95
96 /*
97 * insert an element into a col vector
98 */
99 sm_element *
sm_col_insert(pcol,row)100 sm_col_insert(pcol, row)
101 register sm_col *pcol;
102 register int row;
103 {
104 register sm_element *test, *element;
105
106 /* get a new item, save its address */
107 sm_element_alloc(element);
108 test = element;
109 sorted_insert(sm_element, pcol->first_row, pcol->last_row, pcol->length,
110 next_row, prev_row, row_num, row, test);
111
112 /* if item was not used, free it */
113 if (element != test) {
114 sm_element_free(element);
115 }
116
117 /* either way, return the current new value */
118 return test;
119 }
120
121
122 /*
123 * remove an element from a col vector
124 */
125 void
sm_col_remove(pcol,row)126 sm_col_remove(pcol, row)
127 register sm_col *pcol;
128 register int row;
129 {
130 register sm_element *p;
131
132 for(p = pcol->first_row; p != 0 && p->row_num < row; p = p->next_row)
133 ;
134 if (p != 0 && p->row_num == row) {
135 dll_unlink(p, pcol->first_row, pcol->last_row,
136 next_row, prev_row, pcol->length);
137 sm_element_free(p);
138 }
139 }
140
141
142 /*
143 * find an element (if it is in the col vector)
144 */
145 sm_element *
sm_col_find(pcol,row)146 sm_col_find(pcol, row)
147 sm_col *pcol;
148 int row;
149 {
150 register sm_element *p;
151
152 for(p = pcol->first_row; p != 0 && p->row_num < row; p = p->next_row)
153 ;
154 if (p != 0 && p->row_num == row) {
155 return p;
156 } else {
157 return NIL(sm_element);
158 }
159 }
160
161 /*
162 * return 1 if col p2 contains col p1; 0 otherwise
163 */
164 int
sm_col_contains(p1,p2)165 sm_col_contains(p1, p2)
166 sm_col *p1, *p2;
167 {
168 register sm_element *q1, *q2;
169
170 q1 = p1->first_row;
171 q2 = p2->first_row;
172 while (q1 != 0) {
173 if (q2 == 0 || q1->row_num < q2->row_num) {
174 return 0;
175 } else if (q1->row_num == q2->row_num) {
176 q1 = q1->next_row;
177 q2 = q2->next_row;
178 } else {
179 q2 = q2->next_row;
180 }
181 }
182 return 1;
183 }
184
185
186 /*
187 * return 1 if col p1 and col p2 share an element in common
188 */
189 int
sm_col_intersects(p1,p2)190 sm_col_intersects(p1, p2)
191 sm_col *p1, *p2;
192 {
193 register sm_element *q1, *q2;
194
195 q1 = p1->first_row;
196 q2 = p2->first_row;
197 if (q1 == 0 || q2 == 0) return 0;
198 for(;;) {
199 if (q1->row_num < q2->row_num) {
200 if ((q1 = q1->next_row) == 0) {
201 return 0;
202 }
203 } else if (q1->row_num > q2->row_num) {
204 if ((q2 = q2->next_row) == 0) {
205 return 0;
206 }
207 } else {
208 return 1;
209 }
210 }
211 }
212
213
214 /*
215 * compare two cols, lexical ordering
216 */
217 int
sm_col_compare(p1,p2)218 sm_col_compare(p1, p2)
219 sm_col *p1, *p2;
220 {
221 register sm_element *q1, *q2;
222
223 q1 = p1->first_row;
224 q2 = p2->first_row;
225 while(q1 != 0 && q2 != 0) {
226 if (q1->row_num != q2->row_num) {
227 return q1->row_num - q2->row_num;
228 }
229 q1 = q1->next_row;
230 q2 = q2->next_row;
231 }
232
233 if (q1 != 0) {
234 return 1;
235 } else if (q2 != 0) {
236 return -1;
237 } else {
238 return 0;
239 }
240 }
241
242
243 /*
244 * return the intersection
245 */
246 sm_col *
sm_col_and(p1,p2)247 sm_col_and(p1, p2)
248 sm_col *p1, *p2;
249 {
250 register sm_element *q1, *q2;
251 register sm_col *result;
252
253 result = sm_col_alloc();
254 q1 = p1->first_row;
255 q2 = p2->first_row;
256 if (q1 == 0 || q2 == 0) return result;
257 for(;;) {
258 if (q1->row_num < q2->row_num) {
259 if ((q1 = q1->next_row) == 0) {
260 return result;
261 }
262 } else if (q1->row_num > q2->row_num) {
263 if ((q2 = q2->next_row) == 0) {
264 return result;
265 }
266 } else {
267 (void) sm_col_insert(result, q1->row_num);
268 if ((q1 = q1->next_row) == 0) {
269 return result;
270 }
271 if ((q2 = q2->next_row) == 0) {
272 return result;
273 }
274 }
275 }
276 }
277
278 int
sm_col_hash(pcol,modulus)279 sm_col_hash(pcol, modulus)
280 sm_col *pcol;
281 int modulus;
282 {
283 register int sum;
284 register sm_element *p;
285
286 sum = 0;
287 for(p = pcol->first_row; p != 0; p = p->next_row) {
288 sum = (sum*17 + p->row_num) % modulus;
289 }
290 return sum;
291 }
292
293 /*
294 * remove an element from a col vector (given a pointer to the element)
295 */
296 void
sm_col_remove_element(pcol,p)297 sm_col_remove_element(pcol, p)
298 register sm_col *pcol;
299 register sm_element *p;
300 {
301 dll_unlink(p, pcol->first_row, pcol->last_row,
302 next_row, prev_row, pcol->length);
303 sm_element_free(p);
304 }
305
306
307 void
sm_col_print(fp,pcol)308 sm_col_print(fp, pcol)
309 FILE *fp;
310 sm_col *pcol;
311 {
312 sm_element *p;
313
314 for(p = pcol->first_row; p != 0; p = p->next_row) {
315 (void) fprintf(fp, " %d", p->row_num);
316 }
317 }
318 ABC_NAMESPACE_IMPL_END
319
320