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