1
2 #include <stdio.h>
3 #include <ctype.h>
4 #include "string.h"
5 #include <errno.h>
6
7 #include "viz.h"
8
9 extern errno;
10
11 extern char *malloc();
12
13 void
printlist(level,list)14 printlist(level, list)
15 int level;
16 MEMBER *list;
17 {
18 MEMBER *p;
19
20 if (level > 0)
21 (void) fprintf(stderr, "%*.*s ", level*4, level*4, " ");
22
23 for (p = list; p != NIL; p = p->next) {
24
25 if (p->count == UPTO_EOF)
26 (void) fprintf(stderr, "<inf>");
27 else if (p->count < 0)
28 (void) fprintf(stderr, "$%c", - p->count);
29 else
30 (void) fprintf(stderr, "%d", p->count);
31
32 if (p->type == T_LISTHEAD) {
33
34 (void) fprintf(stderr, "(sublist) ");
35
36 } else if (p->type == T_COPYOUT) {
37
38 (void) fprintf(stderr, "[%s] ", p->u.copyout);
39
40 } else if (p->type == T_SEEK) {
41
42 (void) fprintf(stderr, "%l!%d ", p->u.seek.count,
43 p->u.seek.direction);
44
45 } else if (p->type == T_MATH) {
46
47 (void) fprintf(stderr, "$%c%c%d ",
48 p->u.math.reg_no, p->u.math.operator, p->u.math.operand);
49
50 } else if (p->type == T_NEWLINE) {
51
52 (void) fputs("\\n ", stderr);
53
54 } else {
55
56 (void) fprintf(stderr, "(%c,%c,%d",
57 p->u.iospec.ichar, p->u.iospec.ochar, p->u.iospec.size);
58 if (p->u.iospec.reg_no > 0)
59 (void) fprintf(stderr, ">%c", p->u.iospec.reg_no);
60 (void) fprintf(stderr, ") ");
61 }
62 }
63 (void) fprintf(stderr, "\n");
64
65 for (p = list; p != NIL; p = p->next) {
66 if (p->type == T_LISTHEAD)
67 printlist(level+1, p->u.sublist);
68 }
69 }
70
71 /* Create a new list with mem its first member.
72 * Do this by
73 * - allocating a T_LISTHEAD member that points to mem as its sublist;
74 * - give the listhead a repeat count of 1;
75 * - give the listhead a NIL next field.
76 * Return ptr to the listhead.
77 */
78 MEMBER *
newlist(mem)79 newlist(mem)
80 MEMBER *mem;
81 {
82 MEMBER *p;
83
84 p = (MEMBER *) malloc(sizeof(MEMBER));
85 if (p != NIL) {
86 p->next = NIL;
87 p->type = T_LISTHEAD;
88 p->count = 1;
89 p->u.sublist = mem;
90 }
91 return p;
92 }
93
94 /* Add a member to a list; returns 1st arg */
addmember(list,member)95 MEMBER *addmember(list, member)
96 MEMBER *list; /* listhead member */
97 MEMBER *member;
98 {
99 MEMBER *p;
100
101 p = list->u.sublist;
102 while (p->next)
103 p = p->next;
104
105 p->next = member;
106 member->next = NIL;
107
108 return list;
109 }
110
111 /* Makes the core of an iospec -- everything except for a reg_no is
112 * filled in (fmt is NULL, but is implied by the ichar/ochar setting).
113 */
114 IOSPEC
makecore(ichar,ochar)115 makecore(ichar, ochar)
116 int ichar;
117 int ochar;
118 {
119 IOSPEC io;
120 int defaultichar();
121 int defaultochar();
122
123 if (ichar == 0 && ochar == 0) {
124 ichar = 'C';
125 ochar = 'a';
126 } else if (ichar == 0) {
127 ichar = defaultichar(ochar);
128 } else if (ochar == 0) {
129 ochar = defaultochar(ichar);
130 }
131
132 io.size = getsize(ichar);
133 io.ichar = ichar;
134 io.ochar = ochar;
135 io.fmt = NULL;
136 io.reg_no = 0;
137
138 return io;
139 }
140
141 /* Makes the core of an iospec when a printf-style outform is given */
142 IOSPEC
makecorepct(ichar,fmt)143 makecorepct(ichar, fmt)
144 int ichar;
145 char *fmt;
146 {
147 IOSPEC io;
148
149 if (ichar == 0) {
150 io.ichar = 'C';
151 io.ochar = 'a';
152 } else {
153 io.ichar = ichar;
154 io.ochar = defaultochar(ichar);
155 }
156
157 io.size = getsize(ichar);
158 io.fmt = fmt;
159 io.reg_no = 0;
160
161 return io;
162 }
163
164 /* Condenses a list.
165 * Returns the total number of changes made to the list.
166
167 * condenselist() does the following:
168 * - combines similar adjacent members into single members;
169 * - combines similar adjacent sublists into single sublists;
170 * - merges sublists that have unit repeat count or are of
171 * unit length into the body of the list;
172 */
173 int
condenselist(list)174 condenselist(list)
175 MEMBER *list; /* pointer to a listhead member */
176 {
177 /* Work over each member of list. Each pass is recursive on
178 * sublists, so that all sublists are completely processed before
179 * a current list is processed.
180
181 * Combining duplicates is done first, so that sublists can be
182 * merged into the current list, if at all possible. However,
183 * once a list has been merged, there may be a new duplicate
184 * at the merge point. Therefore, if there are any merged sublists,
185 * we have to repeat the member-combining passes.
186
187 * Pass 1: comb_dup_nl()
188 * Combine adjacent duplicate non-lists into single members.
189
190 * Pass 2: comb_dup_list()
191 * Combine adjacent duplicate lists into single lists.
192
193 * Pass 3: merge_sublist()
194 * Merge sublists that have unit repeat counts or are one
195 * element long into current list.
196
197 */
198 int nmerge;
199 int nchange = 0;
200
201 do {
202 nchange += comb_dup_nl(list);
203 nchange += comb_dup_list(list);
204 nmerge = merge_sublist(list);
205 nchange += nmerge;
206 } while (nmerge > 0);
207 return nchange;
208 }
209
210
211 int
comb_dup_nl(list)212 comb_dup_nl(list)
213 MEMBER *list; /* Pointer to a member of list; can be listhead or otherwise */
214 {
215 register MEMBER *p, *q;
216
217 /* Combine adjacent duplicate non-list members into single members. */
218
219 int nchange = 0;
220
221 /* Process sublists first */
222 for (p = list; p != NIL; p = p->next) {
223 if (p->type == T_LISTHEAD)
224 nchange += comb_dup_nl(p->u.sublist);
225 }
226
227 /* Now process duplicate non-list members */
228 p = list;
229 while ( (q = p->next) != NIL) {
230 if (p->type == q->type) {
231 if (
232 (p->type == T_IOSPEC &&
233 (p->count == UPTO_EOF || p->count >= 0) &&
234 (q->count == UPTO_EOF || q->count >= 0) &&
235 p->u.iospec.reg_no == q->u.iospec.reg_no &&
236 p->u.iospec.size == q->u.iospec.size &&
237 p->u.iospec.ichar == q->u.iospec.ichar &&
238 p->u.iospec.ochar == q->u.iospec.ochar &&
239 p->u.iospec.fmt == q->u.iospec.fmt) ||
240 (p->type == T_MATH &&
241 p->u.math.reg_no == q->u.math.reg_no &&
242 p->u.math.operator == q->u.math.operator &&
243 p->u.math.operand == q->u.math.operand) ||
244 (p->type == T_COPYOUT &&
245 (strcmp(p->u.copyout, q->u.copyout) == 0)) ||
246 (p->type == T_NEWLINE)
247 ) {
248 /* Two successive non-list members do the same thing;
249 * join them.
250 */
251 nchange++;
252 if (p->count == UPTO_EOF || q->count == UPTO_EOF)
253 p->count = UPTO_EOF;
254 else
255 p->count += q->count;
256 p->next = q->next;
257 /* Don't advance member pointer p; that way, we'll
258 * compare the combined member to next one.
259 */
260 } else {
261 /* Can't reduce these members; advance to next member */
262 p = q;
263 }
264 } else {
265 /* Can't reduce these members; advance to next member */
266 p = q;
267 }
268 }
269 return nchange;
270 }
271
272 int
comb_dup_list(list)273 comb_dup_list(list)
274 MEMBER *list; /* Pointer to a member of list; can be listhead or otherwise */
275 {
276 register MEMBER *p, *q;
277 int nchange;
278
279 /* Combine adjacent duplicate lists into single lists. */
280
281 for (nchange = 0, p=list; p != NIL; ) {
282
283 if (p->type != T_LISTHEAD) {
284 /* Not a list */
285 p = p->next;
286 continue;
287 }
288 nchange += comb_dup_list(p->u.sublist);
289
290 q = p->next;
291 if (q == NIL)
292 return nchange;
293
294 if (q->type != T_LISTHEAD) {
295 /* Not a sublist */
296 p = q->next;
297 continue;
298 }
299
300 if (((p->count > 0 && q->count > 0) ||
301 (p->count == UPTO_EOF && q->count == UPTO_EOF)) &&
302 duplicates(p->u.sublist, q->u.sublist)) {
303 /* Two successive lists do the same thing; join them. */
304 nchange++;
305 if (p->count == UPTO_EOF || q->count == UPTO_EOF)
306 p->count = UPTO_EOF;
307 else
308 p->count += q->count;
309 p->next = q->next;
310
311 /* Don't advance member pointer p; that way, we'll
312 * compare the combined member to next one.
313 */
314 } else {
315 /* Can't reduce these members; advance to next member */
316 p = q;
317 }
318 }
319 return nchange;
320 }
321
322 int
merge_sublist(list)323 merge_sublist(list)
324 MEMBER *list; /* Pointer to a member of list; can be listhead or otherwise */
325 {
326 /* Merge sublists of list that have unit repeat counts or are one
327 * element long into list.
328
329 * Return resulting list length.
330 */
331
332 register MEMBER *p, *end;
333 int nchange;
334 long test;
335
336 for (nchange=0, p=list; p != NIL; p = p->next) {
337
338 /* p points to successive members of list */
339
340 if (p->type != T_LISTHEAD) {
341 /* Not a listhead; nothing to merge here */
342 continue;
343 }
344
345 /* First, merge p's sublists into it. */
346 nchange += merge_sublist(p->u.sublist);
347
348
349 /* In following line, note that a single-member sublist
350 * has the value p->u.sublist->next == NIL.
351 */
352
353 if ( (p->count < 0 && p->count != UPTO_EOF) ||
354 (p->count > 1 && p->u.sublist->next != NIL)) {
355 /* Can't merge sublist into current list:
356 * either a count comes from a register, or
357 * sublist has multiple members and our repeat count > 1.
358 */
359 continue;
360 }
361
362 /* Get here if the sublist is repeated once or if it's
363 * got just 1 member. Merge the sublist into current list.
364 */
365 nchange++;
366 if (p->count == UPTO_EOF || p->count > 1) {
367 /* Sublist must have only one member. Fold the repeat
368 * counts together, so that the listhead member contains
369 * a count of 1, and it can then be discarded.
370 */
371
372 /* If either count is UPTO_EOF, use that as total count.
373 * Otherwise, don't merge unless the product of the two
374 * values can still fit into a long.
375 */
376 if (p->count == UPTO_EOF || p->u.sublist->count == UPTO_EOF) {
377 p->u.sublist->count = UPTO_EOF;
378 } else {
379 test = p->u.sublist->count * p->count;
380 if (test / p->count != p->u.sublist->count)
381 continue;
382 else
383 p->u.sublist->count = test;
384 }
385 }
386 /* The listhead now has a repeat count of one. Replace it with
387 * the sublist. Find end of list, and connect it to successor
388 * of current listhead.
389 */
390 end = p->u.sublist;
391 while (end->next)
392 end = end->next;
393 end->next = p->next;
394
395 /* Copy the first member of the sublist onto the
396 * listhead member.
397
398 * [[ It would be better to just discard the listhead member
399 * and insert the sublist member, but since the lists are
400 * singly-linked, we don't easily know who is pointing to
401 * the listhead, so we can't adjust their pointers.
402 * An alternative would be to make the listhead member
403 * into a no-op that points to the former first member
404 * of the sublist, and optionally remove the no-op on
405 * a second pass. But since the list member structures
406 * are small and discarded listheads will probably be
407 * only occasional, copying is cheaper than a ton of compares
408 * on a second pass. ]]
409 */
410 *p = *(p->u.sublist);
411 }
412 return nchange;
413 }
414
duplicates(list1,list2)415 duplicates(list1, list2)
416 MEMBER *list1, *list2; /* listhead or other list member */
417 {
418 /* Returns non-zero if two lists are the same, including their
419 * count fields. However, if either count field is < 0, the two
420 * lists will automatically compare unequal, so that we don't have to
421 * try to determine if the count registers will necessarily contain
422 * the same value at execution time.
423
424 * Note that if you want to compare the xxx and yyy in the
425 * lists 3(xxx) and 14(yyy), you should pass pointers to the first
426 * members of xxx and yyy, so that you don't compare the repeat
427 * counts "3" and "14", which will of course compare unequal.
428
429 */
430
431 for (; list1 != NIL && list2 != NIL;
432 list1 = list1->next, list2 = list2->next) {
433
434 if (list1->type != list2->type)
435 return 0;
436
437 if (list1->count < 0 || list2->count < 0 ||
438 list1->count != list2->count)
439 return 0;
440
441 switch (list1->type) {
442
443 case T_COPYOUT:
444
445 if (strcmp(list1->u.copyout, list2->u.copyout) != 0)
446 return 0;
447 break;
448
449 case T_MATH:
450
451 if (list1->u.math.reg_no != list2->u.math.reg_no ||
452 list1->u.math.operator != list2->u.math.operator ||
453 list1->u.math.operand != list2->u.math.operand)
454 return 0;
455 break;
456
457 case T_IOSPEC:
458
459 if (list1->u.iospec.size != list2->u.iospec.size ||
460 list1->u.iospec.ichar != list2->u.iospec.ichar ||
461 list1->u.iospec.ochar != list2->u.iospec.ochar ||
462 list1->u.iospec.fmt != list2->u.iospec.fmt ||
463 list1->u.iospec.reg_no != list2->u.iospec.reg_no)
464 return 0;
465 break;
466
467 case T_LISTHEAD:
468
469 if (duplicates(list1->u.sublist, list2->u.sublist) == 0)
470 return 0;
471
472 break;
473
474 default:
475 (void) fprintf(stderr,
476 "%s: unknown type %d in duplicates()\n", prog, list1->type);
477 }
478 }
479 if (list1 != NIL || list2 != NIL)
480 return 0; /* list lengths differ */
481 else
482 return 1;
483
484 /* NOTREACHED */
485 }
486
487 /* Returns the number of members of a sublist; returns 0 if list is
488 * not a listhead.
489 */
listlen(list)490 listlen(list)
491 MEMBER *list; /* Points to a listhead */
492 {
493 int n;
494 if (list->type != T_LISTHEAD)
495 return 0;
496
497 for (n=0, list = list->u.sublist; list != NIL; n++, list = list->next)
498 ;
499 return n;
500 }
501