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