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