![[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.7 ! espie 1: /* $OpenBSD: tsort.c,v 1.6 2001/04/07 14:17:38 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:
1.7 ! espie 99: #define NO_ORDER UINT_MAX
! 100:
1.5 espie 101: struct node {
102: unsigned int refs; /* Number of arcs left, coming into this node .
103: * Note that nodes with a null count can't
104: * be part of cycles. */
105: struct link *arcs; /* List of forward arcs. */
106:
107: unsigned int order; /* Order of nodes according to a hint file. */
108:
109: /* Cycle detection algorithms build a free path of nodes. */
110: struct node *from; /* Previous node in the current path. */
111:
112: unsigned int mark; /* Mark processed nodes in cycle discovery. */
113: struct link *traverse; /* Next link to traverse when backtracking. */
114: char k[1]; /* Name of this node. */
1.1 deraadt 115: };
116:
1.5 espie 117: #define HASH_START 9
118:
119: struct array {
120: unsigned int entries;
121: struct node **t;
122: };
123:
124: static void nodes_init __P((struct ohash *));
125: static struct node *node_lookup __P((struct ohash *, const char *, const char *));
126: static void usage __P((void));
127: static struct node *new_node __P((const char *, const char *));
128:
1.7 ! espie 129: static unsigned int read_pairs __P((FILE *, struct ohash *, int,
! 130: const char *, unsigned int));
1.5 espie 131: static void split_nodes __P((struct ohash *, struct array *, struct array *));
132: static void insert_arc __P((struct node *, struct node *));
133:
134: #ifdef DEBUG
135: static void dump_node __P((struct node *));
136: static void dump_array __P((struct array *));
137: static void dump_hash __P((struct ohash *));
138: #endif
1.7 ! espie 139: static unsigned int read_hints __P((FILE *, struct ohash *, int,
! 140: const char *, unsigned int));
1.5 espie 141: static struct node *find_smallest_node __P((struct array *));
142: static struct node *find_good_cycle_break __P((struct array *));
143: static void print_cycle __P((struct array *));
144: static int find_cycle_with __P((struct node *, struct array *));
145: static struct node *find_predecessor __P((struct array *, struct node *));
146: static unsigned int traverse_node __P((struct node *, unsigned int, struct array *));
147: static struct node *find_longest_cycle __P((struct array *, struct array *));
148:
149: static void heap_down __P((struct array *, unsigned int));
1.6 espie 150: static void heapify __P((struct array *, int));
1.5 espie 151: static struct node *dequeue __P((struct array *));
152: static void enqueue __P((struct array *, struct node *));
153:
1.1 deraadt 154:
1.5 espie 155:
156: #define erealloc(n, s) emem(realloc(n, s))
157: static void *hash_alloc __P((size_t, void *));
158: static void hash_free __P((void *, size_t, void *));
159: static void* entry_alloc __P((size_t, void *));
160: static void *emalloc __P((size_t));
161: static void *emem __P((void *));
162: #define DEBUG_TRAVERSE 0
163: static struct ohash_info node_info = {
164: offsetof(struct node, k), NULL, hash_alloc, hash_free, entry_alloc };
165:
166:
167: int main __P((int, char *[]));
168:
169:
170: /***
171: *** Memory handling.
172: ***/
173:
174: static void *
175: emem(p)
176: void *p;
177: {
178: if (p)
179: return p;
180: else
181: errx(EX_SOFTWARE, "Memory exhausted");
182: }
183:
184: static void *
185: hash_alloc(s, u)
186: size_t s;
187: void *u UNUSED;
188: {
189: return emem(calloc(s, 1));
190: }
191:
192: static void
193: hash_free(p, s, u)
194: void *p;
195: size_t s UNUSED;
196: void *u UNUSED;
197: {
198: free(p);
199: }
200:
201: static void *
202: entry_alloc(s, u)
203: size_t s;
204: void *u UNUSED;
205: {
206: return emalloc(s);
207: }
208:
209: static void *
210: emalloc(s)
211: size_t s;
1.1 deraadt 212: {
1.5 espie 213: return emem(malloc(s));
214: }
1.1 deraadt 215:
1.5 espie 216:
217: /***
218: *** Hash table.
219: ***/
220:
221: /* Inserting and finding nodes in the hash structure.
222: * We handle interval strings for efficiency wrt fgetln. */
223: static struct node *
224: new_node(start, end)
225: const char *start;
226: const char *end;
227: {
228: struct node *n;
1.1 deraadt 229:
1.5 espie 230: n = ohash_create_entry(&node_info, start, &end);
231: n->from = NULL;
232: n->arcs = NULL;
233: n->refs = 0;
234: n->mark = 0;
1.7 ! espie 235: n->order = NO_ORDER;
1.5 espie 236: n->traverse = NULL;
237: return n;
238: }
1.1 deraadt 239:
240:
1.5 espie 241: static void
242: nodes_init(h)
243: struct ohash *h;
244: {
245: ohash_init(h, HASH_START, &node_info);
1.1 deraadt 246: }
247:
1.5 espie 248: static struct node *
249: node_lookup(h, start, end)
250: struct ohash *h;
251: const char *start;
252: const char *end;
1.1 deraadt 253: {
1.5 espie 254: unsigned int i;
255: struct node * n;
1.1 deraadt 256:
1.5 espie 257: i = ohash_qlookupi(h, start, &end);
1.1 deraadt 258:
1.5 espie 259: n = ohash_find(h, i);
260: if (n == NULL)
261: n = ohash_insert(h, i, new_node(start, end));
262: return n;
263: }
264:
265: #ifdef DEBUG
266: static void
267: dump_node(n)
268: struct node *n;
269: {
270: struct link *l;
271:
272: if (n->refs == 0)
1.1 deraadt 273: return;
1.5 espie 274: printf("%s (%u): ", n->k, n->refs);
275: for (l = n->arcs; l != NULL; l = l->next)
276: if (n->refs != 0)
277: printf("%s(%u) ", l->node->k, l->node->refs);
278: putchar('\n');
279: }
1.1 deraadt 280:
1.5 espie 281: static void
282: dump_array(a)
283: struct array *a;
284: {
285: unsigned int i;
1.1 deraadt 286:
1.5 espie 287: for (i = 0; i < a->entries; i++)
288: dump_node(a->t[i]);
289: }
290:
291: static void
292: dump_hash(h)
293: struct hash *h;
294: {
295: unsigned int i;
296: struct node *n;
297:
298: for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
299: dump_node(n);
300: }
301: #endif
302:
303:
304: /***
305: *** Reading data.
306: ***/
307:
308: static void
309: insert_arc(a, b)
310: struct node *a, *b;
311: {
312: struct link *l;
313:
314: /* Check that this arc is not already present. */
315: for (l = a->arcs; l != NULL; l = l->next) {
316: if (l->node == b)
1.1 deraadt 317: return;
1.5 espie 318: }
319: b->refs++;
320: l = emalloc(sizeof(struct link));
321: l->node = b;
322: l->next = a->arcs;
323: a->arcs = l;
324: }
1.1 deraadt 325:
1.7 ! espie 326: static unsigned int
! 327: read_pairs(f, h, reverse, name, order)
1.5 espie 328: FILE *f;
329: struct ohash *h;
330: int reverse;
331: const char *name;
1.7 ! espie 332: unsigned int order;
1.5 espie 333: {
334: int toggle;
335: struct node *a;
336: size_t size;
337: char *str;
338:
339: toggle = 1;
340: a = NULL;
341:
342: while ((str = fgetln(f, &size)) != NULL) {
343: char *sentinel;
344:
345: sentinel = str + size;
346: for (;;) {
347: char *e;
348:
349: while (isspace(*str) && str < sentinel)
350: str++;
351: if (str == sentinel)
352: break;
353: for (e = str; !isspace(*e) && e < sentinel; e++)
354: continue;
355: if (toggle) {
356: a = node_lookup(h, str, e);
1.7 ! espie 357: if (a->order == NO_ORDER)
! 358: a->order = order++;
1.5 espie 359: } else {
360: struct node *b;
361:
362: b = node_lookup(h, str, e);
363: assert(a != NULL);
364: if (b != a) {
365: if (reverse)
366: insert_arc(b, a);
367: else
368: insert_arc(a, b);
369: }
370: }
371: toggle = !toggle;
372: str = e;
373: }
374: }
375: if (toggle == 0)
376: errx(EX_DATAERR, "odd number of pairs in %s", name);
377: if (!feof(f))
378: err(EX_IOERR, "error reading %s", name);
1.7 ! espie 379: return order;
1.5 espie 380: }
1.1 deraadt 381:
1.7 ! espie 382: static unsigned int
! 383: read_hints(f, h, quiet, name, order)
1.5 espie 384: FILE *f;
385: struct ohash *h;
1.6 espie 386: int quiet;
1.5 espie 387: const char *name;
1.7 ! espie 388: unsigned int order;
1.5 espie 389: {
390: char *str;
391: size_t size;
392:
393: while ((str = fgetln(f, &size)) != NULL) {
394: char *sentinel;
395:
396: sentinel = str + size;
397: for (;;) {
398: char *e;
399: struct node *a;
400:
401: while (isspace(*str) && str < sentinel)
402: str++;
403: if (str == sentinel)
404: break;
405: for (e = str; !isspace(*e) && e < sentinel; e++)
406: continue;
407: a = node_lookup(h, str, e);
1.7 ! espie 408: if (a->order != NO_ORDER) {
1.6 espie 409: if (!quiet)
410: warnx(
1.5 espie 411: "duplicate node %s in hints file %s",
412: a->k, name);
1.7 ! espie 413: } else
! 414: a->order = order++;
1.5 espie 415: str = e;
416: }
417: }
1.7 ! espie 418: return order;
1.5 espie 419: }
420:
421:
422: /***
423: *** Standard heap handling routines.
424: ***/
425:
426: static void
427: heap_down(h, i)
428: struct array *h;
429: unsigned int i;
430: {
431: unsigned int j;
432: struct node *swap;
433:
434: for (; (j=2*i+1) < h->entries; i = j) {
435: if (j+1 < h->entries && h->t[j+1]->order < h->t[j]->order)
436: j++;
437: if (h->t[i]->order <= h->t[j]->order)
438: break;
439: swap = h->t[i];
440: h->t[i] = h->t[j];
441: h->t[j] = swap;
1.1 deraadt 442: }
1.5 espie 443: }
444:
445: static void
1.6 espie 446: heapify(h, verbose)
1.5 espie 447: struct array *h;
1.6 espie 448: int verbose;
1.5 espie 449: {
450: unsigned int i;
1.1 deraadt 451:
1.6 espie 452: for (i = h->entries; i != 0;) {
453: if (h->t[--i]->order == 0 && verbose)
454: warnx("node %s absent from hints file", h->t[i]->k);
455: heap_down(h, i);
456: }
1.5 espie 457: }
458:
459: #define DEQUEUE(h) ( hints_flag ? dequeue(h) : (h)->t[--(h)->entries] )
1.1 deraadt 460:
1.5 espie 461: static struct node *
462: dequeue(h)
463: struct array *h;
464: {
465: struct node *n;
466:
467: if (h->entries == 0)
468: n = NULL;
469: else {
470: n = h->t[0];
471: if (--h->entries != 0) {
472: h->t[0] = h->t[h->entries];
473: heap_down(h, 0);
474: }
475: }
476: return n;
1.1 deraadt 477: }
1.5 espie 478:
479: #define ENQUEUE(h, n) do { \
480: if (hints_flag) \
481: enqueue((h), (n)); \
482: else \
483: (h)->t[(h)->entries++] = (n); \
484: } while(0);
485:
486: static void
487: enqueue(h, n)
488: struct array *h;
489: struct node *n;
490: {
491: unsigned int i, j;
492: struct node *swap;
1.1 deraadt 493:
1.5 espie 494: h->t[h->entries++] = n;
495: for (i = h->entries-1; i > 0; i = j) {
496: j = (i-1)/2;
497: if (h->t[j]->order < h->t[i]->order)
498: break;
499: swap = h->t[j];
500: h->t[j] = h->t[i];
501: h->t[i] = swap;
502: }
503: }
1.1 deraadt 504:
1.5 espie 505:
506: /***
507: *** Search through hash array for nodes.
508: ***/
509:
510: /* Split nodes into unrefed nodes/live nodes. */
511: static void
512: split_nodes(hash, heap, remaining)
513: struct ohash *hash;
514: struct array *heap;
515: struct array *remaining;
1.1 deraadt 516: {
517:
1.5 espie 518: struct node *n;
519: unsigned int i;
520:
521: heap->t = emalloc(sizeof(struct node *) * ohash_entries(hash));
522: remaining->t = emalloc(sizeof(struct node *) * ohash_entries(hash));
523: heap->entries = 0;
524: remaining->entries = 0;
525:
526: for (n = ohash_first(hash, &i); n != NULL; n = ohash_next(hash, &i)) {
527: if (n->refs == 0)
528: heap->t[heap->entries++] = n;
529: else
530: remaining->t[remaining->entries++] = n;
531: }
1.1 deraadt 532: }
533:
1.5 espie 534: /* Good point to break a cycle: live node with as few refs as possible. */
535: static struct node *
536: find_good_cycle_break(h)
537: struct array *h;
538: {
539: unsigned int i;
540: unsigned int best;
541: struct node *u;
542:
543: best = UINT_MAX;
544: u = NULL;
545:
546: assert(h->entries != 0);
547: for (i = 0; i < h->entries; i++) {
548: struct node *n = h->t[i];
549: /* No need to look further. */
550: if (n->refs == 1)
551: return n;
552: if (n->refs != 0 && n->refs < best) {
553: best = n->refs;
554: u = n;
555: }
556: }
557: assert(u != NULL);
558: return u;
559: }
560:
561: /* Retrieve the node with the smallest order. */
562: static struct node *
563: find_smallest_node(h)
564: struct array *h;
565: {
566: unsigned int i;
567: unsigned int best;
568: struct node *u;
569:
570: best = UINT_MAX;
571: u = NULL;
572:
573: assert(h->entries != 0);
574: for (i = 0; i < h->entries; i++) {
575: struct node *n = h->t[i];
576: if (n->refs != 0 && n->order < best) {
577: best = n->order;
578: u = n;
579: }
580: }
581: assert(u != NULL);
582: return u;
583: }
584:
585:
586: /***
587: *** Graph algorithms.
588: ***/
589:
590: /* Explore the nodes reachable from i to find a cycle containing it, store
591: * it in c. This may fail. */
592: static int
593: find_cycle_with(i, c)
594: struct node *i;
595: struct array *c;
596: {
597: struct node *n;
598:
599: n = i;
600: /* XXX Previous cycle findings may have left this pointer non-null. */
601: i->from = NULL;
602:
603: for (;;) {
604: /* Note that all marks are reversed before this code exits. */
605: n->mark = 1;
606: if (n->traverse)
607: n->traverse = n->traverse->next;
608: else
609: n->traverse = n->arcs;
610: /* Skip over dead nodes. */
611: while (n->traverse && n->traverse->node->refs == 0)
612: n->traverse = n->traverse->next;
613: if (n->traverse) {
614: struct node *go = n->traverse->node;
615:
616: if (go->mark) {
617: if (go == i) {
618: c->entries = 0;
619: for (; n != NULL; n = n->from)
620: c->t[c->entries++] = n;
621: return 1;
1.1 deraadt 622: }
1.5 espie 623: } else {
624: go->from = n;
625: n = go;
1.1 deraadt 626: }
1.5 espie 627: } else {
628: n->mark = 0;
629: n = n->from;
630: if (n == NULL)
631: return 0;
632: }
633: }
634: }
1.1 deraadt 635:
1.5 espie 636: /* Find a live predecessor of node n. This is a slow routine, as it needs
637: * to go through the whole array, but it is not needed often.
638: */
639: static struct node *
640: find_predecessor(a, n)
641: struct array *a;
642: struct node *n;
643: {
644: unsigned int i;
645:
646: for (i = 0; i < a->entries; i++) {
647: struct node *m;
1.1 deraadt 648:
1.5 espie 649: m = a->t[i];
650: if (m->refs != 0) {
651: struct link *l;
652:
653: for (l = m->arcs; l != NULL; l = l->next)
654: if (l->node == n)
655: return m;
1.1 deraadt 656: }
1.5 espie 657: }
658: assert(1 == 0);
659: return NULL;
660: }
661:
662: /* Traverse all strongly connected components reachable from node n.
663: Start numbering them at o. Return the maximum order reached.
664: Update the largest cycle found so far.
665: */
666: static unsigned int
667: traverse_node(n, o, c)
668: struct node *n;
669: unsigned int o;
670: struct array *c;
671: {
672: unsigned int min, max;
673:
674: n->from = NULL;
675: min = o;
676: max = ++o;
677:
678: for (;;) {
679: n->mark = o;
680: if (DEBUG_TRAVERSE)
681: printf("%s(%d) ", n->k, n->mark);
682: /* Find next arc to explore. */
683: if (n->traverse)
684: n->traverse = n->traverse->next;
685: else
686: n->traverse = n->arcs;
687: /* Skip over dead nodes. */
688: while (n->traverse && n->traverse->node->refs == 0)
689: n->traverse = n->traverse->next;
690: /* If arc left. */
691: if (n->traverse) {
692: struct node *go;
693:
694: go = n->traverse->node;
695: /* Optimisation: if go->mark < min, we already
696: * visited this strongly-connected component in
697: * a previous pass. Hence, this can yield no new
698: * cycle. */
699:
700: /* Not part of the current path: go for it. */
701: if (go->mark == 0 || go->mark == min) {
702: go->from = n;
703: n = go;
704: o++;
705: if (o > max)
706: max = o;
707: /* Part of the current path: check cycle length. */
708: } else if (go->mark > min) {
709: if (DEBUG_TRAVERSE)
710: printf("%d\n", o - go->mark + 1);
711: if (o - go->mark + 1 > c->entries) {
712: struct node *t;
713: unsigned int i;
714:
715: c->entries = o - go->mark + 1;
716: i = 0;
717: c->t[i++] = go;
718: for (t = n; t != go; t = t->from)
719: c->t[i++] = t;
1.1 deraadt 720: }
1.5 espie 721: }
1.1 deraadt 722:
1.5 espie 723: /* No arc left: backtrack. */
724: } else {
725: n->mark = min;
726: n = n->from;
727: if (!n)
728: return max;
729: o--;
730: }
1.1 deraadt 731: }
732: }
733:
1.5 espie 734: static void
735: print_cycle(c)
736: struct array *c;
737: {
738: unsigned int i;
739:
740: /* Printing in reverse order, since cycle discoveries finds reverse
741: * edges. */
742: for (i = c->entries; i != 0;) {
743: i--;
744: warnx("%s", c->t[i]->k);
745: }
1.1 deraadt 746: }
747:
1.5 espie 748: static struct node *
749: find_longest_cycle(h, c)
750: struct array *h;
751: struct array *c;
752: {
753: unsigned int i;
754: unsigned int o;
755: unsigned int best;
756: struct node *n;
757: static int notfirst = 0;
758:
759: assert(h->entries != 0);
760:
761: /* No cycle found yet. */
762: c->entries = 0;
763:
764: /* Reset the set of marks, except the first time around. */
765: if (notfirst) {
766: for (i = 0; i < h->entries; i++)
767: h->t[i]->mark = 0;
768: } else
769: notfirst = 1;
770:
771: o = 0;
772:
773: /* Traverse the array. Each unmarked, live node heralds a
774: * new set of strongly connected components. */
775: for (i = 0; i < h->entries; i++) {
776: n = h->t[i];
777: if (n->refs != 0 && n->mark == 0) {
778: /* Each call to traverse_node uses a separate
779: * interval of numbers to mark nodes. */
780: o++;
781: o = traverse_node(n, o, c);
782: }
783: }
784:
785: assert(c->entries != 0);
786: n = c->t[0];
787: best = n->refs;
788: for (i = 0; i < c->entries; i++) {
789: if (c->t[i]->refs < best) {
790: n = c->t[i];
791: best = n->refs;
792: }
793: }
794: return n;
795: }
1.1 deraadt 796:
1.5 espie 797:
798: #define plural(n) ((n) > 1 ? "s" : "")
1.1 deraadt 799:
1.5 espie 800: int
801: main(argc, argv)
802: int argc;
803: char *argv[];
804: {
805: struct ohash pairs;
806: int reverse_flag, quiet_flag, long_flag,
807: warn_flag, hints_flag, verbose_flag;
1.7 ! espie 808: unsigned int order;
! 809:
! 810: order = 1;
1.5 espie 811:
812: reverse_flag = quiet_flag = long_flag =
813: warn_flag = hints_flag = verbose_flag = 0;
814: nodes_init(&pairs);
815:
816: {
817: int c;
818:
819: while ((c = getopt(argc, argv, "h:flqrvw")) != -1) {
820: switch(c) {
821: case 'h': {
822: FILE *f;
823:
824: f = fopen(optarg, "r");
825: if (f == NULL)
826: err(EX_NOINPUT, "Can't open hint file %s",
827: optarg);
1.7 ! espie 828: order = read_hints(f, &pairs, quiet_flag,
! 829: optarg, order);
1.5 espie 830: fclose(f);
831: }
832: /*FALLTHRU*/
833: case 'f':
834: if (hints_flag == 1)
835: usage();
836: hints_flag = 1;
837: break;
838: case 'l':
839: long_flag = 1;
840: break;
841: case 'q':
842: quiet_flag = 1;
843: break;
844: case 'r':
845: reverse_flag = 1;
846: break;
847: case 'v':
848: verbose_flag = 1;
849: break;
850: case 'w':
851: warn_flag = 1;
852: break;
853: default:
854: usage();
855: }
856: }
1.1 deraadt 857:
1.5 espie 858: argc -= optind;
859: argv += optind;
860: }
1.1 deraadt 861:
1.5 espie 862: switch(argc) {
863: case 1: {
864: FILE *f;
865:
866: f = fopen(argv[0], "r");
867: if (f == NULL)
868: err(EX_NOINPUT, "Can't open file %s", argv[1]);
1.7 ! espie 869: order = read_pairs(f, &pairs, reverse_flag, argv[1], order);
1.5 espie 870: fclose(f);
871: break;
872: }
873: case 0:
1.7 ! espie 874: order = read_pairs(stdin, &pairs, reverse_flag, "stdin", order);
1.5 espie 875: break;
876: default:
877: usage();
878: }
1.1 deraadt 879:
1.5 espie 880: {
881: struct array aux; /* Unrefed nodes/cycle reporting. */
882: struct array remaining;
883: unsigned int broken_arcs, broken_cycles;
884: unsigned int left;
885:
886: broken_arcs = 0;
887: broken_cycles = 0;
888:
889: split_nodes(&pairs, &aux, &remaining);
890: ohash_delete(&pairs);
891:
892: if (hints_flag)
1.6 espie 893: heapify(&aux, verbose_flag);
1.5 espie 894:
895: left = remaining.entries + aux.entries;
896: while (left != 0) {
897:
898: /* Standard topological sort. */
899: while (aux.entries) {
900: struct link *l;
901: struct node *n;
902:
903: n = DEQUEUE(&aux);
904: printf("%s\n", n->k);
905: left--;
906: /* We can't free nodes, as we don't know which
907: * entry we can remove in the hash table. We
908: * rely on refs == 0 to recognize live nodes.
909: * Decrease ref count of live nodes, enter new
910: * candidates into the unrefed list. */
911: for (l = n->arcs; l != NULL; l = l->next)
912: if (l->node->refs != 0 &&
913: --l->node->refs == 0) {
914: ENQUEUE(&aux, l->node);
915: }
916: }
917: /* There are still cycles to break. */
918: if (left != 0) {
919: struct node *n;
920:
921: broken_cycles++;
922: /* XXX Simple cycle detection and long cycle
923: * detection are mutually exclusive. */
924:
925: if (long_flag) {
926: n = find_longest_cycle(&remaining, &aux);
927: } else {
928: if (hints_flag)
929: n = find_smallest_node(&remaining);
930: else
931: n = find_good_cycle_break(&remaining);
932: if (!quiet_flag) {
933: while (!find_cycle_with(n, &aux))
934: n = find_predecessor(&remaining, n);
935: }
936: }
937:
938: if (!quiet_flag) {
939: warnx("cycle in data");
940: print_cycle(&aux);
941: }
942:
943: if (verbose_flag)
944: warnx("%u edge%s broken", n->refs,
945: plural(n->refs));
946: broken_arcs += n->refs;
947: n->refs = 0;
948: /* Reinitialization, cycle reporting uses aux. */
949: aux.t[0] = n;
950: aux.entries = 1;
951: }
952: }
953: if (verbose_flag && broken_cycles != 0)
954: warnx("%u cycle%s broken, for a total of %u edge%s",
955: broken_cycles, plural(broken_cycles),
956: broken_arcs, plural(broken_arcs));
957: if (warn_flag)
958: exit(broken_cycles < 256 ? broken_cycles : 255);
959: else
960: exit(EX_OK);
1.1 deraadt 961: }
962: }
963:
1.5 espie 964:
965: extern char *__progname;
966:
967: static void
1.1 deraadt 968: usage()
969: {
1.5 espie 970: fprintf(stderr, "Usage: %s [-h file] [-flqrvw] [file]\n", __progname);
971: exit(EX_USAGE);
1.1 deraadt 972: }