![[BACK]](/icons/back.gif){kind=icon}
Return to tsort.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / tsort|
Return to tsort.c CVS log | Up to [local] / src / usr.bin / tsort |
1.6 ! espie 1: /* $OpenBSD: tsort.c,v 1.5 2001/03/26 22:53:33 espie Exp $ */
1.5 espie 2: /* ex:ts=8 sw=4:
3: */
1.1 deraadt 4:
5: /*
1.5 espie 6: * Copyright (c) 1999-2001 Marc Espie.
1.1 deraadt 7: *
8: * Redistribution and use in source and binary forms, with or without
9: * modification, are permitted provided that the following conditions
10: * are met:
11: * 1. Redistributions of source code must retain the above copyright
12: * notice, this list of conditions and the following disclaimer.
13: * 2. Redistributions in binary form must reproduce the above copyright
14: * notice, this list of conditions and the following disclaimer in the
15: * documentation and/or other materials provided with the distribution.
16: * 3. All advertising materials mentioning features or use of this software
17: * must display the following acknowledgement:
1.5 espie 18: * This product includes software developed by Marc Espie for the OpenBSD
19: * Project.
1.1 deraadt 20: *
1.5 espie 21: * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
22: * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD
25: * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.1 deraadt 32: */
33:
34: #include <sys/types.h>
1.5 espie 35: #include <assert.h>
1.1 deraadt 36: #include <ctype.h>
37: #include <err.h>
1.5 espie 38: #include <limits.h>
39: #include <stddef.h>
40: #include <ohash.h>
1.1 deraadt 41: #include <stdio.h>
42: #include <stdlib.h>
43: #include <string.h>
1.5 espie 44: #include <sysexits.h>
1.1 deraadt 45: #include <unistd.h>
46:
1.5 espie 47: /* The complexity of topological sorting is O(e), where e is the
48: * size of input. While reading input, vertices have to be identified,
49: * thus add the complexity of e keys retrieval among v keys using
50: * an appropriate data structure. This program uses open double hashing
51: * for that purpose. See Knuth for the expected complexity of double
52: * hashing (Brent variation should probably be used if v << e, as a user
53: * option).
54: *
55: * The algorithm used for longest cycle reporting is accurate, but somewhat
56: * expensive. It may need to build all free paths of the graph (a free
57: * path is a path that never goes twice through the same node), whose
58: * number can be as high as O(2^e). Usually, the number of free paths is
59: * much smaller though. This program's author does not believe that a
60: * significantly better worst-case complexity algorithm exists.
61: *
62: * In case of a hints file, the set of minimal nodes is maintained as a
63: * heap. The resulting complexity is O(e+v log v) for the worst case.
64: * The average should actually be near O(e).
65: *
66: * The simple topological sort algorithm detects cycles. This program
67: * goes further, breaking cycles through the use of simple heuristics.
68: * Each cycle break checks the whole set of nodes, hence if c cycles break
69: * are needed, this is an extra cost of O(c v).
1.1 deraadt 70: *
1.5 espie 71: * Possible heuristics are as follows:
72: * - break cycle at node with lowest number of predecessors (default case),
73: * - break longest cycle at node with lowest number of predecessors,
74: * - break cycle at next node from the hints file.
1.1 deraadt 75: *
1.5 espie 76: * Except for the hints file case, which sets an explicit constraint on
77: * which cycle to break, those heuristics locally result in the smallest
78: * number of broken edges.
1.1 deraadt 79: *
1.5 espie 80: * Those are admittedly greedy strategies, as is the selection of the next
81: * node from the hints file amongst equivalent candidates that is used for
82: * `stable' topological sorting.
1.1 deraadt 83: */
1.5 espie 84:
85: #ifdef __GNUC__
86: #define UNUSED __attribute__((unused))
87: #else
88: #define UNUSED
89: #endif
90:
91: struct node;
92:
93: /* The set of arcs from a given node is stored as a linked list. */
94: struct link {
95: struct link *next;
96: struct node *node;
97: };
98:
99: struct node {
100: unsigned int refs; /* Number of arcs left, coming into this node .
101: * Note that nodes with a null count can't
102: * be part of cycles. */
103: struct link *arcs; /* List of forward arcs. */
104:
105: unsigned int order; /* Order of nodes according to a hint file. */
106:
107: /* Cycle detection algorithms build a free path of nodes. */
108: struct node *from; /* Previous node in the current path. */
109:
110: unsigned int mark; /* Mark processed nodes in cycle discovery. */
111: struct link *traverse; /* Next link to traverse when backtracking. */
112: char k[1]; /* Name of this node. */
1.1 deraadt 113: };
114:
1.5 espie 115: #define HASH_START 9
116:
117: struct array {
118: unsigned int entries;
119: struct node **t;
120: };
121:
122: static void nodes_init __P((struct ohash *));
123: static struct node *node_lookup __P((struct ohash *, const char *, const char *));
124: static void usage __P((void));
125: static struct node *new_node __P((const char *, const char *));
126:
127: static void read_pairs __P((FILE *, struct ohash *, int, const char *));
128: static void split_nodes __P((struct ohash *, struct array *, struct array *));
129: static void insert_arc __P((struct node *, struct node *));
130:
131: #ifdef DEBUG
132: static void dump_node __P((struct node *));
133: static void dump_array __P((struct array *));
134: static void dump_hash __P((struct ohash *));
135: #endif
1.6 ! espie 136: static void read_hints __P((FILE *, struct ohash *, int, const char *));
1.5 espie 137: static struct node *find_smallest_node __P((struct array *));
138: static struct node *find_good_cycle_break __P((struct array *));
139: static void print_cycle __P((struct array *));
140: static int find_cycle_with __P((struct node *, struct array *));
141: static struct node *find_predecessor __P((struct array *, struct node *));
142: static unsigned int traverse_node __P((struct node *, unsigned int, struct array *));
143: static struct node *find_longest_cycle __P((struct array *, struct array *));
144:
145: static void heap_down __P((struct array *, unsigned int));
1.6 ! espie 146: static void heapify __P((struct array *, int));
1.5 espie 147: static struct node *dequeue __P((struct array *));
148: static void enqueue __P((struct array *, struct node *));
149:
1.1 deraadt 150:
1.5 espie 151:
152: #define erealloc(n, s) emem(realloc(n, s))
153: static void *hash_alloc __P((size_t, void *));
154: static void hash_free __P((void *, size_t, void *));
155: static void* entry_alloc __P((size_t, void *));
156: static void *emalloc __P((size_t));
157: static void *emem __P((void *));
158: #define DEBUG_TRAVERSE 0
159: static struct ohash_info node_info = {
160: offsetof(struct node, k), NULL, hash_alloc, hash_free, entry_alloc };
161:
162:
163: int main __P((int, char *[]));
164:
165:
166: /***
167: *** Memory handling.
168: ***/
169:
170: static void *
171: emem(p)
172: void *p;
173: {
174: if (p)
175: return p;
176: else
177: errx(EX_SOFTWARE, "Memory exhausted");
178: }
179:
180: static void *
181: hash_alloc(s, u)
182: size_t s;
183: void *u UNUSED;
184: {
185: return emem(calloc(s, 1));
186: }
187:
188: static void
189: hash_free(p, s, u)
190: void *p;
191: size_t s UNUSED;
192: void *u UNUSED;
193: {
194: free(p);
195: }
196:
197: static void *
198: entry_alloc(s, u)
199: size_t s;
200: void *u UNUSED;
201: {
202: return emalloc(s);
203: }
204:
205: static void *
206: emalloc(s)
207: size_t s;
1.1 deraadt 208: {
1.5 espie 209: return emem(malloc(s));
210: }
1.1 deraadt 211:
1.5 espie 212:
213: /***
214: *** Hash table.
215: ***/
216:
217: /* Inserting and finding nodes in the hash structure.
218: * We handle interval strings for efficiency wrt fgetln. */
219: static struct node *
220: new_node(start, end)
221: const char *start;
222: const char *end;
223: {
224: struct node *n;
1.1 deraadt 225:
1.5 espie 226: n = ohash_create_entry(&node_info, start, &end);
227: n->from = NULL;
228: n->arcs = NULL;
229: n->refs = 0;
230: n->mark = 0;
231: n->order = 0;
232: n->traverse = NULL;
233: return n;
234: }
1.1 deraadt 235:
236:
1.5 espie 237: static void
238: nodes_init(h)
239: struct ohash *h;
240: {
241: ohash_init(h, HASH_START, &node_info);
1.1 deraadt 242: }
243:
1.5 espie 244: static struct node *
245: node_lookup(h, start, end)
246: struct ohash *h;
247: const char *start;
248: const char *end;
1.1 deraadt 249: {
1.5 espie 250: unsigned int i;
251: struct node * n;
1.1 deraadt 252:
1.5 espie 253: i = ohash_qlookupi(h, start, &end);
1.1 deraadt 254:
1.5 espie 255: n = ohash_find(h, i);
256: if (n == NULL)
257: n = ohash_insert(h, i, new_node(start, end));
258: return n;
259: }
260:
261: #ifdef DEBUG
262: static void
263: dump_node(n)
264: struct node *n;
265: {
266: struct link *l;
267:
268: if (n->refs == 0)
1.1 deraadt 269: return;
1.5 espie 270: printf("%s (%u): ", n->k, n->refs);
271: for (l = n->arcs; l != NULL; l = l->next)
272: if (n->refs != 0)
273: printf("%s(%u) ", l->node->k, l->node->refs);
274: putchar('\n');
275: }
1.1 deraadt 276:
1.5 espie 277: static void
278: dump_array(a)
279: struct array *a;
280: {
281: unsigned int i;
1.1 deraadt 282:
1.5 espie 283: for (i = 0; i < a->entries; i++)
284: dump_node(a->t[i]);
285: }
286:
287: static void
288: dump_hash(h)
289: struct hash *h;
290: {
291: unsigned int i;
292: struct node *n;
293:
294: for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
295: dump_node(n);
296: }
297: #endif
298:
299:
300: /***
301: *** Reading data.
302: ***/
303:
304: static void
305: insert_arc(a, b)
306: struct node *a, *b;
307: {
308: struct link *l;
309:
310: /* Check that this arc is not already present. */
311: for (l = a->arcs; l != NULL; l = l->next) {
312: if (l->node == b)
1.1 deraadt 313: return;
1.5 espie 314: }
315: b->refs++;
316: l = emalloc(sizeof(struct link));
317: l->node = b;
318: l->next = a->arcs;
319: a->arcs = l;
320: }
1.1 deraadt 321:
1.5 espie 322: static void
323: read_pairs(f, h, reverse, name)
324: FILE *f;
325: struct ohash *h;
326: int reverse;
327: const char *name;
328: {
329: int toggle;
330: struct node *a;
331: size_t size;
332: char *str;
333: unsigned int o;
334:
335: o = 1;
336: toggle = 1;
337: a = NULL;
338:
339: while ((str = fgetln(f, &size)) != NULL) {
340: char *sentinel;
341:
342: sentinel = str + size;
343: for (;;) {
344: char *e;
345:
346: while (isspace(*str) && str < sentinel)
347: str++;
348: if (str == sentinel)
349: break;
350: for (e = str; !isspace(*e) && e < sentinel; e++)
351: continue;
352: if (toggle) {
353: a = node_lookup(h, str, e);
354: if (a->order == 0)
355: a->order = o++;
356: } else {
357: struct node *b;
358:
359: b = node_lookup(h, str, e);
360: assert(a != NULL);
361: if (b != a) {
362: if (reverse)
363: insert_arc(b, a);
364: else
365: insert_arc(a, b);
366: }
367: }
368: toggle = !toggle;
369: str = e;
370: }
371: }
372: if (toggle == 0)
373: errx(EX_DATAERR, "odd number of pairs in %s", name);
374: if (!feof(f))
375: err(EX_IOERR, "error reading %s", name);
376: }
1.1 deraadt 377:
1.5 espie 378: static void
1.6 ! espie 379: read_hints(f, h, quiet, name)
1.5 espie 380: FILE *f;
381: struct ohash *h;
1.6 ! espie 382: int quiet;
1.5 espie 383: const char *name;
384: {
385: char *str;
386: size_t size;
387: unsigned int i;
388:
389: i = 1;
390:
391: while ((str = fgetln(f, &size)) != NULL) {
392: char *sentinel;
393:
394: sentinel = str + size;
395: for (;;) {
396: char *e;
397: struct node *a;
398:
399: while (isspace(*str) && str < sentinel)
400: str++;
401: if (str == sentinel)
402: break;
403: for (e = str; !isspace(*e) && e < sentinel; e++)
404: continue;
405: a = node_lookup(h, str, e);
406: if (a->order != 0)
1.6 ! espie 407: if (!quiet)
! 408: warnx(
1.5 espie 409: "duplicate node %s in hints file %s",
410: a->k, name);
411: else
412: a->order = i++;
413: str = e;
414: }
415: }
416: }
417:
418:
419: /***
420: *** Standard heap handling routines.
421: ***/
422:
423: static void
424: heap_down(h, i)
425: struct array *h;
426: unsigned int i;
427: {
428: unsigned int j;
429: struct node *swap;
430:
431: for (; (j=2*i+1) < h->entries; i = j) {
432: if (j+1 < h->entries && h->t[j+1]->order < h->t[j]->order)
433: j++;
434: if (h->t[i]->order <= h->t[j]->order)
435: break;
436: swap = h->t[i];
437: h->t[i] = h->t[j];
438: h->t[j] = swap;
1.1 deraadt 439: }
1.5 espie 440: }
441:
442: static void
1.6 ! espie 443: heapify(h, verbose)
1.5 espie 444: struct array *h;
1.6 ! espie 445: int verbose;
1.5 espie 446: {
447: unsigned int i;
1.1 deraadt 448:
1.6 ! espie 449: for (i = h->entries; i != 0;) {
! 450: if (h->t[--i]->order == 0 && verbose)
! 451: warnx("node %s absent from hints file", h->t[i]->k);
! 452: heap_down(h, i);
! 453: }
1.5 espie 454: }
455:
456: #define DEQUEUE(h) ( hints_flag ? dequeue(h) : (h)->t[--(h)->entries] )
1.1 deraadt 457:
1.5 espie 458: static struct node *
459: dequeue(h)
460: struct array *h;
461: {
462: struct node *n;
463:
464: if (h->entries == 0)
465: n = NULL;
466: else {
467: n = h->t[0];
468: if (--h->entries != 0) {
469: h->t[0] = h->t[h->entries];
470: heap_down(h, 0);
471: }
472: }
473: return n;
1.1 deraadt 474: }
1.5 espie 475:
476: #define ENQUEUE(h, n) do { \
477: if (hints_flag) \
478: enqueue((h), (n)); \
479: else \
480: (h)->t[(h)->entries++] = (n); \
481: } while(0);
482:
483: static void
484: enqueue(h, n)
485: struct array *h;
486: struct node *n;
487: {
488: unsigned int i, j;
489: struct node *swap;
1.1 deraadt 490:
1.5 espie 491: h->t[h->entries++] = n;
492: for (i = h->entries-1; i > 0; i = j) {
493: j = (i-1)/2;
494: if (h->t[j]->order < h->t[i]->order)
495: break;
496: swap = h->t[j];
497: h->t[j] = h->t[i];
498: h->t[i] = swap;
499: }
500: }
1.1 deraadt 501:
1.5 espie 502:
503: /***
504: *** Search through hash array for nodes.
505: ***/
506:
507: /* Split nodes into unrefed nodes/live nodes. */
508: static void
509: split_nodes(hash, heap, remaining)
510: struct ohash *hash;
511: struct array *heap;
512: struct array *remaining;
1.1 deraadt 513: {
514:
1.5 espie 515: struct node *n;
516: unsigned int i;
517:
518: heap->t = emalloc(sizeof(struct node *) * ohash_entries(hash));
519: remaining->t = emalloc(sizeof(struct node *) * ohash_entries(hash));
520: heap->entries = 0;
521: remaining->entries = 0;
522:
523: for (n = ohash_first(hash, &i); n != NULL; n = ohash_next(hash, &i)) {
524: if (n->refs == 0)
525: heap->t[heap->entries++] = n;
526: else
527: remaining->t[remaining->entries++] = n;
528: }
1.1 deraadt 529: }
530:
1.5 espie 531: /* Good point to break a cycle: live node with as few refs as possible. */
532: static struct node *
533: find_good_cycle_break(h)
534: struct array *h;
535: {
536: unsigned int i;
537: unsigned int best;
538: struct node *u;
539:
540: best = UINT_MAX;
541: u = NULL;
542:
543: assert(h->entries != 0);
544: for (i = 0; i < h->entries; i++) {
545: struct node *n = h->t[i];
546: /* No need to look further. */
547: if (n->refs == 1)
548: return n;
549: if (n->refs != 0 && n->refs < best) {
550: best = n->refs;
551: u = n;
552: }
553: }
554: assert(u != NULL);
555: return u;
556: }
557:
558: /* Retrieve the node with the smallest order. */
559: static struct node *
560: find_smallest_node(h)
561: struct array *h;
562: {
563: unsigned int i;
564: unsigned int best;
565: struct node *u;
566:
567: best = UINT_MAX;
568: u = NULL;
569:
570: assert(h->entries != 0);
571: for (i = 0; i < h->entries; i++) {
572: struct node *n = h->t[i];
573: if (n->refs != 0 && n->order < best) {
574: best = n->order;
575: u = n;
576: }
577: }
578: assert(u != NULL);
579: return u;
580: }
581:
582:
583: /***
584: *** Graph algorithms.
585: ***/
586:
587: /* Explore the nodes reachable from i to find a cycle containing it, store
588: * it in c. This may fail. */
589: static int
590: find_cycle_with(i, c)
591: struct node *i;
592: struct array *c;
593: {
594: struct node *n;
595:
596: n = i;
597: /* XXX Previous cycle findings may have left this pointer non-null. */
598: i->from = NULL;
599:
600: for (;;) {
601: /* Note that all marks are reversed before this code exits. */
602: n->mark = 1;
603: if (n->traverse)
604: n->traverse = n->traverse->next;
605: else
606: n->traverse = n->arcs;
607: /* Skip over dead nodes. */
608: while (n->traverse && n->traverse->node->refs == 0)
609: n->traverse = n->traverse->next;
610: if (n->traverse) {
611: struct node *go = n->traverse->node;
612:
613: if (go->mark) {
614: if (go == i) {
615: c->entries = 0;
616: for (; n != NULL; n = n->from)
617: c->t[c->entries++] = n;
618: return 1;
1.1 deraadt 619: }
1.5 espie 620: } else {
621: go->from = n;
622: n = go;
1.1 deraadt 623: }
1.5 espie 624: } else {
625: n->mark = 0;
626: n = n->from;
627: if (n == NULL)
628: return 0;
629: }
630: }
631: }
1.1 deraadt 632:
1.5 espie 633: /* Find a live predecessor of node n. This is a slow routine, as it needs
634: * to go through the whole array, but it is not needed often.
635: */
636: static struct node *
637: find_predecessor(a, n)
638: struct array *a;
639: struct node *n;
640: {
641: unsigned int i;
642:
643: for (i = 0; i < a->entries; i++) {
644: struct node *m;
1.1 deraadt 645:
1.5 espie 646: m = a->t[i];
647: if (m->refs != 0) {
648: struct link *l;
649:
650: for (l = m->arcs; l != NULL; l = l->next)
651: if (l->node == n)
652: return m;
1.1 deraadt 653: }
1.5 espie 654: }
655: assert(1 == 0);
656: return NULL;
657: }
658:
659: /* Traverse all strongly connected components reachable from node n.
660: Start numbering them at o. Return the maximum order reached.
661: Update the largest cycle found so far.
662: */
663: static unsigned int
664: traverse_node(n, o, c)
665: struct node *n;
666: unsigned int o;
667: struct array *c;
668: {
669: unsigned int min, max;
670:
671: n->from = NULL;
672: min = o;
673: max = ++o;
674:
675: for (;;) {
676: n->mark = o;
677: if (DEBUG_TRAVERSE)
678: printf("%s(%d) ", n->k, n->mark);
679: /* Find next arc to explore. */
680: if (n->traverse)
681: n->traverse = n->traverse->next;
682: else
683: n->traverse = n->arcs;
684: /* Skip over dead nodes. */
685: while (n->traverse && n->traverse->node->refs == 0)
686: n->traverse = n->traverse->next;
687: /* If arc left. */
688: if (n->traverse) {
689: struct node *go;
690:
691: go = n->traverse->node;
692: /* Optimisation: if go->mark < min, we already
693: * visited this strongly-connected component in
694: * a previous pass. Hence, this can yield no new
695: * cycle. */
696:
697: /* Not part of the current path: go for it. */
698: if (go->mark == 0 || go->mark == min) {
699: go->from = n;
700: n = go;
701: o++;
702: if (o > max)
703: max = o;
704: /* Part of the current path: check cycle length. */
705: } else if (go->mark > min) {
706: if (DEBUG_TRAVERSE)
707: printf("%d\n", o - go->mark + 1);
708: if (o - go->mark + 1 > c->entries) {
709: struct node *t;
710: unsigned int i;
711:
712: c->entries = o - go->mark + 1;
713: i = 0;
714: c->t[i++] = go;
715: for (t = n; t != go; t = t->from)
716: c->t[i++] = t;
1.1 deraadt 717: }
1.5 espie 718: }
1.1 deraadt 719:
1.5 espie 720: /* No arc left: backtrack. */
721: } else {
722: n->mark = min;
723: n = n->from;
724: if (!n)
725: return max;
726: o--;
727: }
1.1 deraadt 728: }
729: }
730:
1.5 espie 731: static void
732: print_cycle(c)
733: struct array *c;
734: {
735: unsigned int i;
736:
737: /* Printing in reverse order, since cycle discoveries finds reverse
738: * edges. */
739: for (i = c->entries; i != 0;) {
740: i--;
741: warnx("%s", c->t[i]->k);
742: }
1.1 deraadt 743: }
744:
1.5 espie 745: static struct node *
746: find_longest_cycle(h, c)
747: struct array *h;
748: struct array *c;
749: {
750: unsigned int i;
751: unsigned int o;
752: unsigned int best;
753: struct node *n;
754: static int notfirst = 0;
755:
756: assert(h->entries != 0);
757:
758: /* No cycle found yet. */
759: c->entries = 0;
760:
761: /* Reset the set of marks, except the first time around. */
762: if (notfirst) {
763: for (i = 0; i < h->entries; i++)
764: h->t[i]->mark = 0;
765: } else
766: notfirst = 1;
767:
768: o = 0;
769:
770: /* Traverse the array. Each unmarked, live node heralds a
771: * new set of strongly connected components. */
772: for (i = 0; i < h->entries; i++) {
773: n = h->t[i];
774: if (n->refs != 0 && n->mark == 0) {
775: /* Each call to traverse_node uses a separate
776: * interval of numbers to mark nodes. */
777: o++;
778: o = traverse_node(n, o, c);
779: }
780: }
781:
782: assert(c->entries != 0);
783: n = c->t[0];
784: best = n->refs;
785: for (i = 0; i < c->entries; i++) {
786: if (c->t[i]->refs < best) {
787: n = c->t[i];
788: best = n->refs;
789: }
790: }
791: return n;
792: }
1.1 deraadt 793:
1.5 espie 794:
795: #define plural(n) ((n) > 1 ? "s" : "")
1.1 deraadt 796:
1.5 espie 797: int
798: main(argc, argv)
799: int argc;
800: char *argv[];
801: {
802: struct ohash pairs;
803: int reverse_flag, quiet_flag, long_flag,
804: warn_flag, hints_flag, verbose_flag;
805:
806: reverse_flag = quiet_flag = long_flag =
807: warn_flag = hints_flag = verbose_flag = 0;
808: nodes_init(&pairs);
809:
810: {
811: int c;
812:
813: while ((c = getopt(argc, argv, "h:flqrvw")) != -1) {
814: switch(c) {
815: case 'h': {
816: FILE *f;
817:
818: f = fopen(optarg, "r");
819: if (f == NULL)
820: err(EX_NOINPUT, "Can't open hint file %s",
821: optarg);
1.6 ! espie 822: read_hints(f, &pairs, quiet_flag, optarg);
1.5 espie 823: fclose(f);
824: }
825: /*FALLTHRU*/
826: case 'f':
827: if (hints_flag == 1)
828: usage();
829: hints_flag = 1;
830: break;
831: case 'l':
832: long_flag = 1;
833: break;
834: case 'q':
835: quiet_flag = 1;
836: break;
837: case 'r':
838: reverse_flag = 1;
839: break;
840: case 'v':
841: verbose_flag = 1;
842: break;
843: case 'w':
844: warn_flag = 1;
845: break;
846: default:
847: usage();
848: }
849: }
1.1 deraadt 850:
1.5 espie 851: argc -= optind;
852: argv += optind;
853: }
1.1 deraadt 854:
1.5 espie 855: switch(argc) {
856: case 1: {
857: FILE *f;
858:
859: f = fopen(argv[0], "r");
860: if (f == NULL)
861: err(EX_NOINPUT, "Can't open file %s", argv[1]);
862: read_pairs(f, &pairs, reverse_flag, argv[1]);
863: fclose(f);
864: break;
865: }
866: case 0:
867: read_pairs(stdin, &pairs, reverse_flag, "stdin");
868: break;
869: default:
870: usage();
871: }
1.1 deraadt 872:
1.5 espie 873: {
874: struct array aux; /* Unrefed nodes/cycle reporting. */
875: struct array remaining;
876: unsigned int broken_arcs, broken_cycles;
877: unsigned int left;
878:
879: broken_arcs = 0;
880: broken_cycles = 0;
881:
882: split_nodes(&pairs, &aux, &remaining);
883: ohash_delete(&pairs);
884:
885: if (hints_flag)
1.6 ! espie 886: heapify(&aux, verbose_flag);
1.5 espie 887:
888: left = remaining.entries + aux.entries;
889: while (left != 0) {
890:
891: /* Standard topological sort. */
892: while (aux.entries) {
893: struct link *l;
894: struct node *n;
895:
896: n = DEQUEUE(&aux);
897: printf("%s\n", n->k);
898: left--;
899: /* We can't free nodes, as we don't know which
900: * entry we can remove in the hash table. We
901: * rely on refs == 0 to recognize live nodes.
902: * Decrease ref count of live nodes, enter new
903: * candidates into the unrefed list. */
904: for (l = n->arcs; l != NULL; l = l->next)
905: if (l->node->refs != 0 &&
906: --l->node->refs == 0) {
907: ENQUEUE(&aux, l->node);
908: }
909: }
910: /* There are still cycles to break. */
911: if (left != 0) {
912: struct node *n;
913:
914: broken_cycles++;
915: /* XXX Simple cycle detection and long cycle
916: * detection are mutually exclusive. */
917:
918: if (long_flag) {
919: n = find_longest_cycle(&remaining, &aux);
920: } else {
921: if (hints_flag)
922: n = find_smallest_node(&remaining);
923: else
924: n = find_good_cycle_break(&remaining);
925: if (!quiet_flag) {
926: while (!find_cycle_with(n, &aux))
927: n = find_predecessor(&remaining, n);
928: }
929: }
930:
931: if (!quiet_flag) {
932: warnx("cycle in data");
933: print_cycle(&aux);
934: }
935:
936: if (verbose_flag)
937: warnx("%u edge%s broken", n->refs,
938: plural(n->refs));
939: broken_arcs += n->refs;
940: n->refs = 0;
941: /* Reinitialization, cycle reporting uses aux. */
942: aux.t[0] = n;
943: aux.entries = 1;
944: }
945: }
946: if (verbose_flag && broken_cycles != 0)
947: warnx("%u cycle%s broken, for a total of %u edge%s",
948: broken_cycles, plural(broken_cycles),
949: broken_arcs, plural(broken_arcs));
950: if (warn_flag)
951: exit(broken_cycles < 256 ? broken_cycles : 255);
952: else
953: exit(EX_OK);
1.1 deraadt 954: }
955: }
956:
1.5 espie 957:
958: extern char *__progname;
959:
960: static void
1.1 deraadt 961: usage()
962: {
1.5 espie 963: fprintf(stderr, "Usage: %s [-h file] [-flqrvw] [file]\n", __progname);
964: exit(EX_USAGE);
1.1 deraadt 965: }