Annotation of src/usr.bin/tsort/tsort.c, Revision 1.1
1.1 ! deraadt 1: /* $NetBSD: tsort.c,v 1.10 1995/08/31 22:06:22 jtc Exp $ */
! 2:
! 3: /*
! 4: * Copyright (c) 1989, 1993, 1994
! 5: * The Regents of the University of California. All rights reserved.
! 6: *
! 7: * This code is derived from software contributed to Berkeley by
! 8: * Michael Rendell of Memorial University of Newfoundland.
! 9: *
! 10: * Redistribution and use in source and binary forms, with or without
! 11: * modification, are permitted provided that the following conditions
! 12: * are met:
! 13: * 1. Redistributions of source code must retain the above copyright
! 14: * notice, this list of conditions and the following disclaimer.
! 15: * 2. Redistributions in binary form must reproduce the above copyright
! 16: * notice, this list of conditions and the following disclaimer in the
! 17: * documentation and/or other materials provided with the distribution.
! 18: * 3. All advertising materials mentioning features or use of this software
! 19: * must display the following acknowledgement:
! 20: * This product includes software developed by the University of
! 21: * California, Berkeley and its contributors.
! 22: * 4. Neither the name of the University nor the names of its contributors
! 23: * may be used to endorse or promote products derived from this software
! 24: * without specific prior written permission.
! 25: *
! 26: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
! 27: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
! 28: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
! 29: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
! 30: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
! 31: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
! 32: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
! 33: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
! 34: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
! 35: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
! 36: * SUCH DAMAGE.
! 37: */
! 38:
! 39: #ifndef lint
! 40: static char copyright[] =
! 41: "@(#) Copyright (c) 1989, 1993, 1994\n\
! 42: The Regents of the University of California. All rights reserved.\n";
! 43: #endif /* not lint */
! 44:
! 45: #ifndef lint
! 46: #if 0
! 47: static char sccsid[] = "@(#)tsort.c 8.3 (Berkeley) 5/4/95";
! 48: #endif
! 49: static char rcsid[] = "$NetBSD: tsort.c,v 1.10 1995/08/31 22:06:22 jtc Exp $";
! 50: #endif /* not lint */
! 51:
! 52: #include <sys/types.h>
! 53:
! 54: #include <ctype.h>
! 55: #include <db.h>
! 56: #include <err.h>
! 57: #include <errno.h>
! 58: #include <fcntl.h>
! 59: #include <stdio.h>
! 60: #include <stdlib.h>
! 61: #include <string.h>
! 62: #include <unistd.h>
! 63:
! 64: /*
! 65: * Topological sort. Input is a list of pairs of strings separated by
! 66: * white space (spaces, tabs, and/or newlines); strings are written to
! 67: * standard output in sorted order, one per line.
! 68: *
! 69: * usage:
! 70: * tsort [-l] [inputfile]
! 71: * If no input file is specified, standard input is read.
! 72: *
! 73: * Should be compatable with AT&T tsort HOWEVER the output is not identical
! 74: * (i.e. for most graphs there is more than one sorted order, and this tsort
! 75: * usually generates a different one then the AT&T tsort). Also, cycle
! 76: * reporting seems to be more accurate in this version (the AT&T tsort
! 77: * sometimes says a node is in a cycle when it isn't).
! 78: *
! 79: * Michael Rendell, michael@stretch.cs.mun.ca - Feb 26, '90
! 80: */
! 81: #define HASHSIZE 53 /* doesn't need to be big */
! 82: #define NF_MARK 0x1 /* marker for cycle detection */
! 83: #define NF_ACYCLIC 0x2 /* this node is cycle free */
! 84: #define NF_NODEST 0x4 /* Unreachable */
! 85:
! 86: typedef struct node_str NODE;
! 87:
! 88: struct node_str {
! 89: NODE **n_prevp; /* pointer to previous node's n_next */
! 90: NODE *n_next; /* next node in graph */
! 91: NODE **n_arcs; /* array of arcs to other nodes */
! 92: int n_narcs; /* number of arcs in n_arcs[] */
! 93: int n_arcsize; /* size of n_arcs[] array */
! 94: int n_refcnt; /* # of arcs pointing to this node */
! 95: int n_flags; /* NF_* */
! 96: char n_name[1]; /* name of this node */
! 97: };
! 98:
! 99: typedef struct _buf {
! 100: char *b_buf;
! 101: int b_bsize;
! 102: } BUF;
! 103:
! 104: DB *db;
! 105: NODE *graph, **cycle_buf, **longest_cycle;
! 106: int debug, longest;
! 107:
! 108: void add_arc __P((char *, char *));
! 109: int find_cycle __P((NODE *, NODE *, int, int));
! 110: NODE *get_node __P((char *));
! 111: void *grow_buf __P((void *, int));
! 112: void remove_node __P((NODE *));
! 113: void tsort __P((void));
! 114: void usage __P((void));
! 115:
! 116: int
! 117: main(argc, argv)
! 118: int argc;
! 119: char *argv[];
! 120: {
! 121: register BUF *b;
! 122: register int c, n;
! 123: FILE *fp;
! 124: int bsize, ch, nused;
! 125: BUF bufs[2];
! 126:
! 127: while ((ch = getopt(argc, argv, "dl")) != EOF)
! 128: switch (ch) {
! 129: case 'd':
! 130: debug = 1;
! 131: break;
! 132: case 'l':
! 133: longest = 1;
! 134: break;
! 135: case '?':
! 136: default:
! 137: usage();
! 138: }
! 139: argc -= optind;
! 140: argv += optind;
! 141:
! 142: switch (argc) {
! 143: case 0:
! 144: fp = stdin;
! 145: break;
! 146: case 1:
! 147: if ((fp = fopen(*argv, "r")) == NULL)
! 148: err(1, "%s", *argv);
! 149: break;
! 150: default:
! 151: usage();
! 152: }
! 153:
! 154: for (b = bufs, n = 2; --n >= 0; b++)
! 155: b->b_buf = grow_buf(NULL, b->b_bsize = 1024);
! 156:
! 157: /* parse input and build the graph */
! 158: for (n = 0, c = getc(fp);;) {
! 159: while (c != EOF && isspace(c))
! 160: c = getc(fp);
! 161: if (c == EOF)
! 162: break;
! 163:
! 164: nused = 0;
! 165: b = &bufs[n];
! 166: bsize = b->b_bsize;
! 167: do {
! 168: b->b_buf[nused++] = c;
! 169: if (nused == bsize)
! 170: b->b_buf = grow_buf(b->b_buf, bsize *= 2);
! 171: c = getc(fp);
! 172: } while (c != EOF && !isspace(c));
! 173:
! 174: b->b_buf[nused] = '\0';
! 175: b->b_bsize = bsize;
! 176: if (n)
! 177: add_arc(bufs[0].b_buf, bufs[1].b_buf);
! 178: n = !n;
! 179: }
! 180: (void)fclose(fp);
! 181: if (n)
! 182: errx(1, "odd data count");
! 183:
! 184: /* do the sort */
! 185: tsort();
! 186: exit(0);
! 187: }
! 188:
! 189: /* double the size of oldbuf and return a pointer to the new buffer. */
! 190: void *
! 191: grow_buf(bp, size)
! 192: void *bp;
! 193: int size;
! 194: {
! 195: if ((bp = realloc(bp, (u_int)size)) == NULL)
! 196: err(1, NULL);
! 197: return (bp);
! 198: }
! 199:
! 200: /*
! 201: * add an arc from node s1 to node s2 in the graph. If s1 or s2 are not in
! 202: * the graph, then add them.
! 203: */
! 204: void
! 205: add_arc(s1, s2)
! 206: char *s1, *s2;
! 207: {
! 208: register NODE *n1;
! 209: NODE *n2;
! 210: int bsize, i;
! 211:
! 212: n1 = get_node(s1);
! 213:
! 214: if (!strcmp(s1, s2))
! 215: return;
! 216:
! 217: n2 = get_node(s2);
! 218:
! 219: /*
! 220: * Check if this arc is already here.
! 221: */
! 222: for (i = 0; i < n1->n_narcs; i++)
! 223: if (n1->n_arcs[i] == n2)
! 224: return;
! 225: /*
! 226: * Add it.
! 227: */
! 228: if (n1->n_narcs == n1->n_arcsize) {
! 229: if (!n1->n_arcsize)
! 230: n1->n_arcsize = 10;
! 231: bsize = n1->n_arcsize * sizeof(*n1->n_arcs) * 2;
! 232: n1->n_arcs = grow_buf(n1->n_arcs, bsize);
! 233: n1->n_arcsize = bsize / sizeof(*n1->n_arcs);
! 234: }
! 235: n1->n_arcs[n1->n_narcs++] = n2;
! 236: ++n2->n_refcnt;
! 237: }
! 238:
! 239: /* Find a node in the graph (insert if not found) and return a pointer to it. */
! 240: NODE *
! 241: get_node(name)
! 242: char *name;
! 243: {
! 244: DBT data, key;
! 245: NODE *n;
! 246:
! 247: if (db == NULL &&
! 248: (db = dbopen(NULL, O_RDWR, 0, DB_HASH, NULL)) == NULL)
! 249: err(1, "db: %s", name);
! 250:
! 251: key.data = name;
! 252: key.size = strlen(name) + 1;
! 253:
! 254: switch ((*db->get)(db, &key, &data, 0)) {
! 255: case 0:
! 256: bcopy(data.data, &n, sizeof(n));
! 257: return (n);
! 258: case 1:
! 259: break;
! 260: default:
! 261: case -1:
! 262: err(1, "db: %s", name);
! 263: }
! 264:
! 265: if ((n = malloc(sizeof(NODE) + key.size)) == NULL)
! 266: err(1, NULL);
! 267:
! 268: n->n_narcs = 0;
! 269: n->n_arcsize = 0;
! 270: n->n_arcs = NULL;
! 271: n->n_refcnt = 0;
! 272: n->n_flags = 0;
! 273: bcopy(name, n->n_name, key.size);
! 274:
! 275: /* Add to linked list. */
! 276: if ((n->n_next = graph) != NULL)
! 277: graph->n_prevp = &n->n_next;
! 278: n->n_prevp = &graph;
! 279: graph = n;
! 280:
! 281: /* Add to hash table. */
! 282: data.data = &n;
! 283: data.size = sizeof(n);
! 284: if ((*db->put)(db, &key, &data, 0))
! 285: err(1, "db: %s", name);
! 286: return (n);
! 287: }
! 288:
! 289:
! 290: /*
! 291: * Clear the NODEST flag from all nodes.
! 292: */
! 293: void
! 294: clear_cycle()
! 295: {
! 296: NODE *n;
! 297:
! 298: for (n = graph; n != NULL; n = n->n_next)
! 299: n->n_flags &= ~NF_NODEST;
! 300: }
! 301:
! 302: /* do topological sort on graph */
! 303: void
! 304: tsort()
! 305: {
! 306: register NODE *n, *next;
! 307: register int cnt, i;
! 308:
! 309: while (graph != NULL) {
! 310: /*
! 311: * Keep getting rid of simple cases until there are none left,
! 312: * if there are any nodes still in the graph, then there is
! 313: * a cycle in it.
! 314: */
! 315: do {
! 316: for (cnt = 0, n = graph; n != NULL; n = next) {
! 317: next = n->n_next;
! 318: if (n->n_refcnt == 0) {
! 319: remove_node(n);
! 320: ++cnt;
! 321: }
! 322: }
! 323: } while (graph != NULL && cnt);
! 324:
! 325: if (graph == NULL)
! 326: break;
! 327:
! 328: if (!cycle_buf) {
! 329: /*
! 330: * Allocate space for two cycle logs - one to be used
! 331: * as scratch space, the other to save the longest
! 332: * cycle.
! 333: */
! 334: for (cnt = 0, n = graph; n != NULL; n = n->n_next)
! 335: ++cnt;
! 336: cycle_buf = malloc((u_int)sizeof(NODE *) * cnt);
! 337: longest_cycle = malloc((u_int)sizeof(NODE *) * cnt);
! 338: if (cycle_buf == NULL || longest_cycle == NULL)
! 339: err(1, NULL);
! 340: }
! 341: for (n = graph; n != NULL; n = n->n_next)
! 342: if (!(n->n_flags & NF_ACYCLIC))
! 343: if (cnt = find_cycle(n, n, 0, 0)) {
! 344: warnx("cycle in data");
! 345: for (i = 0; i < cnt; i++)
! 346: warnx("%s",
! 347: longest_cycle[i]->n_name);
! 348: remove_node(n);
! 349: clear_cycle();
! 350: break;
! 351: } else {
! 352: /* to avoid further checks */
! 353: n->n_flags |= NF_ACYCLIC;
! 354: clear_cycle();
! 355: }
! 356:
! 357: if (n == NULL)
! 358: errx(1, "internal error -- could not find cycle");
! 359: }
! 360: }
! 361:
! 362: /* print node and remove from graph (does not actually free node) */
! 363: void
! 364: remove_node(n)
! 365: register NODE *n;
! 366: {
! 367: register NODE **np;
! 368: register int i;
! 369:
! 370: (void)printf("%s\n", n->n_name);
! 371: for (np = n->n_arcs, i = n->n_narcs; --i >= 0; np++)
! 372: --(*np)->n_refcnt;
! 373: n->n_narcs = 0;
! 374: *n->n_prevp = n->n_next;
! 375: if (n->n_next)
! 376: n->n_next->n_prevp = n->n_prevp;
! 377: }
! 378:
! 379:
! 380: /* look for the longest? cycle from node from to node to. */
! 381: int
! 382: find_cycle(from, to, longest_len, depth)
! 383: NODE *from, *to;
! 384: int depth, longest_len;
! 385: {
! 386: register NODE **np;
! 387: register int i, len;
! 388:
! 389: /*
! 390: * avoid infinite loops and ignore portions of the graph known
! 391: * to be acyclic
! 392: */
! 393: if (from->n_flags & (NF_NODEST|NF_MARK|NF_ACYCLIC))
! 394: return (0);
! 395: from->n_flags |= NF_MARK;
! 396:
! 397: for (np = from->n_arcs, i = from->n_narcs; --i >= 0; np++) {
! 398: cycle_buf[depth] = *np;
! 399: if (*np == to) {
! 400: if (depth + 1 > longest_len) {
! 401: longest_len = depth + 1;
! 402: (void)memcpy((char *)longest_cycle,
! 403: (char *)cycle_buf,
! 404: longest_len * sizeof(NODE *));
! 405: }
! 406: } else {
! 407: if ((*np)->n_flags & (NF_MARK|NF_ACYCLIC|NF_NODEST))
! 408: continue;
! 409: len = find_cycle(*np, to, longest_len, depth + 1);
! 410:
! 411: if (debug)
! 412: (void)printf("%*s %s->%s %d\n", depth, "",
! 413: from->n_name, to->n_name, len);
! 414:
! 415: if (len == 0)
! 416: (*np)->n_flags |= NF_NODEST;
! 417:
! 418: if (len > longest_len)
! 419: longest_len = len;
! 420:
! 421: if (len > 0 && !longest)
! 422: break;
! 423: }
! 424: }
! 425: from->n_flags &= ~NF_MARK;
! 426: return (longest_len);
! 427: }
! 428:
! 429: void
! 430: usage()
! 431: {
! 432: (void)fprintf(stderr, "usage: tsort [-l] [file]\n");
! 433: exit(1);
! 434: }
![[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