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