1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
48  *  Topological sort.  Input is a list of pairs of strings separated by
53  *     tsort [-dlq] [inputfile]
54  *  If no input file is specified, standard input is read.
62  *  Michael Rendell, michael@stretch.cs.mun.ca - Feb 26, '90
111 	while ((ch = getopt(argc, argv, "dlq")) != -1)  in main()
126 	argc -= optind;  in main()
141 	for (b = bufs, n = 2; --n >= 0; b++)  in main()
142 		b->b_buf = grow_buf(NULL, b->b_bsize = 1024);  in main()
144 	/* parse input and build the graph */  in main()
153 		bsize = b->b_bsize;  in main()
155 			b->b_buf[nused++] = c;  in main()
157 				b->b_buf = grow_buf(b->b_buf, bsize *= 2);  in main()
161 		b->b_buf[nused] = '\0';  in main()
162 		b->b_bsize = bsize;  in main()
208 	for (i = 0; i < n1->n_narcs; i++)  in add_arc()
209 		if (n1->n_arcs[i] == n2)  in add_arc()
214 	if (n1->n_narcs == n1->n_arcsize) {  in add_arc()
215 		if (!n1->n_arcsize)  in add_arc()
216 			n1->n_arcsize = 10;  in add_arc()
217 		bsize = n1->n_arcsize * sizeof(*n1->n_arcs) * 2;  in add_arc()
218 		n1->n_arcs = grow_buf(n1->n_arcs, bsize);  in add_arc()
219 		n1->n_arcsize = bsize / sizeof(*n1->n_arcs);  in add_arc()
221 	n1->n_arcs[n1->n_narcs++] = n2;  in add_arc()
222 	++n2->n_refcnt;  in add_arc()
239 	switch ((*db->get)(db, &key, &data, 0)) {  in get_node()
246 	case -1:  in get_node()
253 	n->n_narcs = 0;  in get_node()
254 	n->n_arcsize = 0;  in get_node()
255 	n->n_arcs = NULL;  in get_node()
256 	n->n_refcnt = 0;  in get_node()
257 	n->n_flags = 0;  in get_node()
258 	memcpy(n->n_name, name, key.size);  in get_node()
261 	if ((n->n_next = graph) != NULL)  in get_node()
262 		graph->n_prevp = &n->n_next;  in get_node()
263 	n->n_prevp = &graph;  in get_node()
269 	if ((*db->put)(db, &key, &data, 0))  in get_node()
283 	for (n = graph; n != NULL; n = n->n_next)  in clear_cycle()
284 		n->n_flags &= ~NF_NODEST;  in clear_cycle()
302 				next = n->n_next;  in tsort()
303 				if (n->n_refcnt == 0) {  in tsort()
315 			 * Allocate space for two cycle logs - one to be used  in tsort()
319 			for (cnt = 0, n = graph; n != NULL; n = n->n_next)  in tsort()
326 		for (n = graph; n != NULL; n = n->n_next)  in tsort()
327 			if (!(n->n_flags & NF_ACYCLIC)) {  in tsort()
333 							    longest_cycle[i]->n_name);  in tsort()
340 					n->n_flags  |= NF_ACYCLIC;  in tsort()
346 			errx(1, "internal error -- could not find cycle");  in tsort()
357 	(void)printf("%s\n", n->n_name);  in remove_node()
358 	for (np = n->n_arcs, i = n->n_narcs; --i >= 0; np++)  in remove_node()
359 		--(*np)->n_refcnt;  in remove_node()
360 	n->n_narcs = 0;  in remove_node()
361 	*n->n_prevp = n->n_next;  in remove_node()
362 	if (n->n_next)  in remove_node()
363 		n->n_next->n_prevp = n->n_prevp;  in remove_node()
369 find_cycle(NODE *from, NODE *to, int longest_len, int depth)  in find_cycle()  argument
378 	if (from->n_flags & (NF_NODEST|NF_MARK|NF_ACYCLIC))  in find_cycle()
380 	from->n_flags |= NF_MARK;  in find_cycle()
382 	for (np = from->n_arcs, i = from->n_narcs; --i >= 0; np++) {  in find_cycle()
383 		cycle_buf[depth] = *np;  in find_cycle()
385 			if (depth + 1 > longest_len) {  in find_cycle()
386 				longest_len = depth + 1;  in find_cycle()
392 			if ((*np)->n_flags & (NF_MARK|NF_ACYCLIC|NF_NODEST))  in find_cycle()
394 			len = find_cycle(*np, to, longest_len, depth + 1);  in find_cycle()
397 				(void)printf("%*s %s->%s %d\n", depth, "",  in find_cycle()
398 				    from->n_name, to->n_name, len);  in find_cycle()
401 				(*np)->n_flags |= NF_NODEST;  in find_cycle()
410 	from->n_flags &= ~NF_MARK;  in find_cycle()
417 	(void)fprintf(stderr, "usage: tsort [-dlq] [file]\n");  in usage()