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