Differential D25389 Diff 76759 head/sbin/rcorder/rcorder.c

Changeset View

Standalone View

head/sbin/rcorder/rcorder.c

# if 0		# if 0
/* $NetBSD: rcorder.c,v 1.7 2000/08/04 07:33:55 enami Exp $ */		/* $NetBSD: rcorder.c,v 1.7 2000/08/04 07:33:55 enami Exp $ */
#endif		#endif

/*-		/*-
* SPDX-License-Identifier: BSD-2-Clause-FreeBSD		* SPDX-License-Identifier: BSD-2-Clause-FreeBSD
*		*
* Copyright (c) 1998, 1999 Matthew R. Green		* Copyright (c) 1998, 1999 Matthew R. Green
* All rights reserved.		* All rights reserved.
* Copyright (c) 1998		* Copyright (c) 1998
* Perry E. Metzger. All rights reserved.		* Perry E. Metzger. All rights reserved.
		* Copyright (c) 2020
		* Boris N. Lytochkin. All rights reserved.
*		*
* Redistribution and use in source and binary forms, with or without		* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions		* modification, are permitted provided that the following conditions
* are met:		* are met:
* 1. Redistributions of source code must retain the above copyright		* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.		* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright		* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the		* notice, this list of conditions and the following disclaimer in the
Show All 23 Lines
#include <sys/stat.h>		#include <sys/stat.h>

#include <err.h>		#include <err.h>
#include <stdio.h>		#include <stdio.h>
#include <libutil.h>		#include <libutil.h>
#include <stdlib.h>		#include <stdlib.h>
#include <string.h>		#include <string.h>
#include <unistd.h>		#include <unistd.h>
		#include <libgen.h>
		#include <stdbool.h>

#include "ealloc.h"		#include "ealloc.h"
#include "sprite.h"		#include "sprite.h"
#include "hash.h"		#include "hash.h"

#ifdef DEBUG		#ifdef DEBUG
static int debug = 0;		static int debug = 0;
# define DPRINTF(args) if (debug) { fflush(stdout); fprintf args; }		# define DPRINTF(args) if (debug) { fflush(stdout); fprintf args; }
Show All 11 Lines
#define PROVIDES_LEN (sizeof(PROVIDES_STR) - 1)		#define PROVIDES_LEN (sizeof(PROVIDES_STR) - 1)
#define BEFORE_STR "# BEFORE:"		#define BEFORE_STR "# BEFORE:"
#define BEFORE_LEN (sizeof(BEFORE_STR) - 1)		#define BEFORE_LEN (sizeof(BEFORE_STR) - 1)
#define KEYWORD_STR "# KEYWORD:"		#define KEYWORD_STR "# KEYWORD:"
#define KEYWORD_LEN (sizeof(KEYWORD_STR) - 1)		#define KEYWORD_LEN (sizeof(KEYWORD_STR) - 1)
#define KEYWORDS_STR "# KEYWORDS:"		#define KEYWORDS_STR "# KEYWORDS:"
#define KEYWORDS_LEN (sizeof(KEYWORDS_STR) - 1)		#define KEYWORDS_LEN (sizeof(KEYWORDS_STR) - 1)

		#define FAKE_PROV_NAME "fake_prov_"

static int exit_code;		static int exit_code;
static int file_count;		static int file_count;
static char **file_list;		static char **file_list;

typedef int bool;
#define TRUE 1		#define TRUE 1
#define FALSE 0		#define FALSE 0
typedef bool flag;		typedef bool flag;
#define SET TRUE		#define SET TRUE
#define RESET FALSE		#define RESET FALSE

		static flag do_graphviz = false;
		static flag do_parallel = false;

static Hash_Table provide_hash_s, *provide_hash;		static Hash_Table provide_hash_s, *provide_hash;

typedef struct provnode provnode;		typedef struct provnode provnode;
typedef struct filenode filenode;		typedef struct filenode filenode;
typedef struct f_provnode f_provnode;		typedef struct f_provnode f_provnode;
typedef struct f_reqnode f_reqnode;		typedef struct f_reqnode f_reqnode;
typedef struct strnodelist strnodelist;		typedef struct strnodelist strnodelist;

struct provnode {		struct provnode {
flag head;		flag head;
flag in_progress;		flag in_progress;
		int sequence;
filenode *fnode;		filenode *fnode;
provnode next, last;		provnode next, last;
};		};

struct f_provnode {		struct f_provnode {
provnode *pnode;		provnode *pnode;
		Hash_Entry *entry;
f_provnode *next;		f_provnode *next;
};		};

struct f_reqnode {		struct f_reqnode {
Hash_Entry *entry;		Hash_Entry *entry;
f_reqnode *next;		f_reqnode *next;
};		};

struct strnodelist {		struct strnodelist {
filenode *node;		filenode *node;
strnodelist *next;		strnodelist *next;
char s[1];		char s[1];
};		};

struct filenode {		struct filenode {
char *filename;		char *filename;
flag in_progress;		flag in_progress;
filenode next, last;		filenode next, last;
f_reqnode *req_list;		f_reqnode *req_list;
f_provnode *prov_list;		f_provnode *prov_list;
strnodelist *keyword_list;		strnodelist *keyword_list;
		int issues_count;
		int sequence;
};		};

static filenode fn_head_s, *fn_head;		static filenode fn_head_s, fn_head, *fn_seqlist;
		static int max_sequence = 0;

static strnodelist *bl_list;		static strnodelist *bl_list;
static strnodelist *keep_list;		static strnodelist *keep_list;
static strnodelist *skip_list;		static strnodelist *skip_list;

static void do_file(filenode *fnode);		static void do_file(filenode fnode, strnodelist );
static void strnode_add(strnodelist *, char , filenode *);		static void strnode_add(strnodelist *, char , filenode *);
static int skip_ok(filenode *fnode);		static int skip_ok(filenode *fnode);
static int keep_ok(filenode *fnode);		static int keep_ok(filenode *fnode);
static void satisfy_req(f_reqnode rnode, char filename);		static char generate_loop_for_req(strnodelist , provnode , filenode );
		static void satisfy_req(f_reqnode rnode, filenode fnode, strnodelist *);
static void crunch_file(char *);		static void crunch_file(char *);
static void parse_require(filenode , char );		static void parse_require(filenode , char );
static void parse_provide(filenode , char );		static void parse_provide(filenode , char );
static void parse_before(filenode , char );		static void parse_before(filenode , char );
static void parse_keywords(filenode , char );		static void parse_keywords(filenode , char );
static filenode filenode_new(char );		static filenode filenode_new(char );
static void add_require(filenode , char );		static void add_require(filenode , char );
static void add_provide(filenode , char );		static void add_provide(filenode , char );
static void add_before(filenode , char );		static void add_before(filenode , char );
static void add_keyword(filenode , char );		static void add_keyword(filenode , char );
static void insert_before(void);		static void insert_before(void);
static Hash_Entry make_fake_provision(filenode );		static Hash_Entry make_fake_provision(filenode );
static void crunch_all_files(void);		static void crunch_all_files(void);
static void initialize(void);		static void initialize(void);
		static void generate_graphviz_header(void);
		static void generate_graphviz_footer(void);
		static void generate_graphviz_file_links(Hash_Entry , filenode );
		static void generate_graphviz_providers(void);
		static inline int is_fake_prov(const char *);
		static int sequence_cmp(const void , const void );
static void generate_ordering(void);		static void generate_ordering(void);

int		int
main(int argc, char *argv[])		main(int argc, char *argv[])
{		{
int ch;		int ch;

while ((ch = getopt(argc, argv, "dk:s:")) != -1)		while ((ch = getopt(argc, argv, "dgk:ps:")) != -1)
switch (ch) {		switch (ch) {
case 'd':		case 'd':
#ifdef DEBUG		#ifdef DEBUG
debug = 1;		debug = 1;
#else		#else
warnx("debugging not compiled in, -d ignored");		warnx("debugging not compiled in, -d ignored");
#endif		#endif
break;		break;
		case 'g':
		do_graphviz = true;
		break;
case 'k':		case 'k':
strnode_add(&keep_list, optarg, 0);		strnode_add(&keep_list, optarg, 0);
break;		break;
		case 'p':
		do_parallel = true;
		break;
case 's':		case 's':
strnode_add(&skip_list, optarg, 0);		strnode_add(&skip_list, optarg, 0);
break;		break;
default:		default:
/* XXX should crunch it? */		/* XXX should crunch it? */
break;		break;
}		}
argc -= optind;		argc -= optind;
argv += optind;		argv += optind;

file_count = argc;		file_count = argc;
file_list = argv;		file_list = argv;

DPRINTF((stderr, "parse_args\n"));		DPRINTF((stderr, "parse_args\n"));
initialize();		initialize();
DPRINTF((stderr, "initialize\n"));		DPRINTF((stderr, "initialize\n"));
		generate_graphviz_header();
crunch_all_files();		crunch_all_files();
DPRINTF((stderr, "crunch_all_files\n"));		DPRINTF((stderr, "crunch_all_files\n"));
		generate_graphviz_providers();
generate_ordering();		generate_ordering();
DPRINTF((stderr, "generate_ordering\n"));		DPRINTF((stderr, "generate_ordering\n"));
		generate_graphviz_footer();

exit(exit_code);		exit(exit_code);
}		}

/*		/*
* initialise various variables.		* initialise various variables.
*/		*/
static void		static void
▲ Show 20 Lines • Show All 89 Lines • ▼ Show 20 Lines	add_provide(filenode fnode, char s)
head = Hash_GetValue(entry);		head = Hash_GetValue(entry);

/* create a head node if necessary. */		/* create a head node if necessary. */
if (head == NULL) {		if (head == NULL) {
head = emalloc(sizeof(*head));		head = emalloc(sizeof(*head));
head->head = SET;		head->head = SET;
head->in_progress = RESET;		head->in_progress = RESET;
head->fnode = NULL;		head->fnode = NULL;
		head->sequence = 0;
head->last = head->next = NULL;		head->last = head->next = NULL;
Hash_SetValue(entry, head);		Hash_SetValue(entry, head);
}		}
#if 0		#if 0
/*		/*
* Don't warn about this. We want to be able to support		* Don't warn about this. We want to be able to support
* scripts that do two complex things:		* scripts that do two complex things:
*		*
Show All 39 Lines	#endif
pnode->next = head->next;		pnode->next = head->next;
pnode->last = head;		pnode->last = head;
head->next = pnode;		head->next = pnode;
if (pnode->next != NULL)		if (pnode->next != NULL)
pnode->next->last = pnode;		pnode->next->last = pnode;

f_pnode = emalloc(sizeof(*f_pnode));		f_pnode = emalloc(sizeof(*f_pnode));
f_pnode->pnode = pnode;		f_pnode->pnode = pnode;
		f_pnode->entry = entry;
f_pnode->next = fnode->prov_list;		f_pnode->next = fnode->prov_list;
fnode->prov_list = f_pnode;		fnode->prov_list = f_pnode;
}		}

/*		/*
* put the BEFORE: lines to a list and handle them later.		* put the BEFORE: lines to a list and handle them later.
*/		*/
static void		static void
▲ Show 20 Lines • Show All 156 Lines • ▼ Show 20 Lines	make_fake_provision(filenode *node)
Hash_Entry *entry;		Hash_Entry *entry;
f_provnode *f_pnode;		f_provnode *f_pnode;
provnode head, pnode;		provnode head, pnode;
static int i = 0;		static int i = 0;
int new;		int new;
char buffer[30];		char buffer[30];

do {		do {
snprintf(buffer, sizeof buffer, "fake_prov_%08d", i++);		snprintf(buffer, sizeof buffer, FAKE_PROV_NAME "%08d", i++);
entry = Hash_CreateEntry(provide_hash, buffer, &new);		entry = Hash_CreateEntry(provide_hash, buffer, &new);
} while (new == 0);		} while (new == 0);
head = emalloc(sizeof(*head));		head = emalloc(sizeof(*head));
head->head = SET;		head->head = SET;
head->in_progress = RESET;		head->in_progress = RESET;
head->fnode = NULL;		head->fnode = NULL;
head->last = head->next = NULL;		head->last = head->next = NULL;
Hash_SetValue(entry, head);		Hash_SetValue(entry, head);

pnode = emalloc(sizeof(*pnode));		pnode = emalloc(sizeof(*pnode));
pnode->head = RESET;		pnode->head = RESET;
pnode->in_progress = RESET;		pnode->in_progress = RESET;
pnode->fnode = node;		pnode->fnode = node;
pnode->next = head->next;		pnode->next = head->next;
pnode->last = head;		pnode->last = head;
head->next = pnode;		head->next = pnode;
if (pnode->next != NULL)		if (pnode->next != NULL)
pnode->next->last = pnode;		pnode->next->last = pnode;

f_pnode = emalloc(sizeof(*f_pnode));		f_pnode = emalloc(sizeof(*f_pnode));
		f_pnode->entry = entry;
f_pnode->pnode = pnode;		f_pnode->pnode = pnode;
f_pnode->next = node->prov_list;		f_pnode->next = node->prov_list;
node->prov_list = f_pnode;		node->prov_list = f_pnode;

return (entry);		return (entry);
}		}

/*		/*
Show All 16 Lines	while (bl_list != NULL) {
bl = bl_list->next;		bl = bl_list->next;

fake_prov_entry = make_fake_provision(bl_list->node);		fake_prov_entry = make_fake_provision(bl_list->node);

entry = Hash_CreateEntry(provide_hash, bl_list->s, &new);		entry = Hash_CreateEntry(provide_hash, bl_list->s, &new);
if (new == 1)		if (new == 1)
warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s);		warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s);

		if (new == 1 && do_graphviz == true)
		generate_graphviz_file_links(
		Hash_FindEntry(provide_hash, bl_list->s),
		bl_list->node);

for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) {		for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) {
if (pnode->head)		if (pnode->head)
continue;		continue;

rnode = emalloc(sizeof(*rnode));		rnode = emalloc(sizeof(*rnode));
rnode->entry = fake_prov_entry;		rnode->entry = fake_prov_entry;
rnode->next = pnode->fnode->req_list;		rnode->next = pnode->fnode->req_list;
pnode->fnode->req_list = rnode;		pnode->fnode->req_list = rnode;
Show All 14 Lines
{		{
int i;		int i;

for (i = 0; i < file_count; i++)		for (i = 0; i < file_count; i++)
crunch_file(file_list[i]);		crunch_file(file_list[i]);
insert_before();		insert_before();
}		}

		static inline int
		is_fake_prov(const char *name)
		{

		return (name == strstr(name, FAKE_PROV_NAME));
		}

		/* loop though provide list of vnode drawing all non-fake dependencies */
		static void
		generate_graphviz_file_links(Hash_Entry entry, filenode fnode)
		{
		char dep_name, fname;
		provnode *head;
		f_provnode fpnode, rfpnode;
		int is_before = 0;

		dep_name = Hash_GetKey(entry);
		if (is_fake_prov(dep_name))
		is_before = 1;
		head = Hash_GetValue(entry);

		for (fpnode = fnode->prov_list; fpnode && fpnode->entry;
		fpnode = fpnode->next) {
		fname = Hash_GetKey(fpnode->entry);
		if (is_fake_prov(fname))
		continue;
		rfpnode = NULL;
		do {
		if (rfpnode)
		dep_name = Hash_GetKey(rfpnode->entry);
		else
		dep_name = Hash_GetKey(entry);

		if (!is_fake_prov(dep_name)) {
		printf("\"%s\" -> \"%s\" [%s%s];\n",
		fname, dep_name,
		/* edge style */
		(is_before ? "style=dashed" : "style=solid"),
		/* circular dep? */
		((head == NULL \|\|
		(head->next && head->in_progress == SET)) ?
		", color=red, penwidth=4" : ""));
		if (rfpnode == NULL)
		break;
		}
		/* dependency is solved already */
		if (head == NULL \|\| head->next == NULL)
		break;

		if (rfpnode == NULL)
		rfpnode = head->next->fnode->prov_list;
		else
		rfpnode = rfpnode->next;
		} while (rfpnode);
		}
		}

/*		/*
		* Walk the stack, find the looping point and generate traceback.
		* NULL is returned on failure, otherwize pointer to a buffer holding
		* text representation is returned, caller must run free(3) for the
		* pointer.
		*/
		static char *
		generate_loop_for_req(strnodelist stack_tail, provnode head,
		filenode *fnode)
		{
		provnode *pnode;
		strnodelist stack_ptr, loop_entry;
		char buf, *revstack;
		size_t bufsize;
		int i, stack_depth;

		loop_entry = NULL;
		/* fast forward stack to the component that is required now */
		for (pnode = head->next; pnode; pnode = pnode->next) {
		if (loop_entry)
		break;
		stack_depth = 0;
		for (stack_ptr = stack_tail; stack_ptr;
		stack_ptr = stack_ptr->next) {
		stack_depth++;
		if (stack_ptr->node == pnode->fnode) {
		loop_entry = stack_ptr;
		break;
		}
		}
		}

		if (loop_entry == NULL)
		return (NULL);

		stack_depth += 2; /* fnode + loop_entry */
		revstack = emalloc(sizeof(char ) stack_depth);
		bzero(revstack, (sizeof(char ) stack_depth));

		/* reverse stack and estimate buffer size to allocate */
		bufsize = 1; /* tralining \0 */

		revstack[stack_depth - 1] = loop_entry->node->filename;
		bufsize += strlen(revstack[stack_depth - 1]);

		revstack[stack_depth - 2] = fnode->filename;
		bufsize += strlen(revstack[stack_depth - 2]);
		fnode->issues_count++;

		stack_ptr = stack_tail;
		for (i = stack_depth - 3; i >= 0; i--) {
		revstack[i] = stack_ptr->node->filename;
		stack_ptr->node->issues_count++;
		stack_ptr = stack_ptr->next;
		bufsize += strlen(revstack[i]);
		}
		bufsize += strlen(" -> ") * (stack_depth - 1);

		buf = emalloc(bufsize);
		bzero(buf, bufsize);

		for (i = 0; i < stack_depth; i++) {
		strlcat(buf, revstack[i], bufsize);
		if (i < stack_depth - 1)
		strlcat(buf, " -> ", bufsize);
		}

		free(revstack);
		return (buf);
		}
		/*
* below are the functions that traverse the graphs we have built		* below are the functions that traverse the graphs we have built
* finding out the desired ordering, printing each file in turn.		* finding out the desired ordering, printing each file in turn.
* if missing requirements, or cyclic graphs are detected, a		* if missing requirements, or cyclic graphs are detected, a
* warning will be issued, and we will continue on..		* warning will be issued, and we will continue on..
*/		*/

/*		/*
* given a requirement node (in a filename) we attempt to satisfy it.		* given a requirement node (in a filename) we attempt to satisfy it.
* we do some sanity checking first, to ensure that we have providers,		* we do some sanity checking first, to ensure that we have providers,
* aren't already satisfied and aren't already being satisfied (ie,		* aren't already satisfied and aren't already being satisfied (ie,
* cyclic). if we pass all this, we loop over the provision list		* cyclic). if we pass all this, we loop over the provision list
* calling do_file() (enter recursion) for each filenode in this		* calling do_file() (enter recursion) for each filenode in this
* provision.		* provision.
*/		*/
static void		static void
satisfy_req(f_reqnode rnode, char filename)		satisfy_req(f_reqnode rnode, filenode fnode, strnodelist *stack_ptr)
{		{
Hash_Entry *entry;		Hash_Entry *entry;
provnode *head;		provnode *head;
		strnodelist stack_item;
		char *buf;

entry = rnode->entry;		entry = rnode->entry;
head = Hash_GetValue(entry);		head = Hash_GetValue(entry);

		if (do_graphviz == true)
		generate_graphviz_file_links(entry, fnode);

if (head == NULL) {		if (head == NULL) {
warnx("requirement `%s' in file `%s' has no providers.",		warnx("requirement `%s' in file `%s' has no providers.",
Hash_GetKey(entry), filename);		Hash_GetKey(entry), fnode->filename);
exit_code = 1;		exit_code = 1;
return;		return;
}		}

/* return if the requirement is already satisfied. */		/* return if the requirement is already satisfied. */
if (head->next == NULL)		if (head->next == NULL)
return;		return;

/*		/*
* if list is marked as in progress,		* if list is marked as in progress,
* print that there is a circular dependency on it and abort		* print that there is a circular dependency on it and abort
*/		*/
if (head->in_progress == SET) {		if (head->in_progress == SET) {
warnx("Circular dependency on provision `%s' in file `%s'.",
Hash_GetKey(entry), filename);
exit_code = 1;		exit_code = 1;
		buf = generate_loop_for_req(stack_ptr, head,
		fnode);

		if (buf == NULL) {
		warnx("Circular dependency on provision `%s' in "
		"file `%s' (tracing has failed).",
		Hash_GetKey(entry), fnode->filename);
return;		return;
}		}

		warnx("Circular dependency on provision `%s': %s.",
		Hash_GetKey(entry), buf);
		free(buf);
		return;
		}

head->in_progress = SET;		head->in_progress = SET;

		stack_item.next = stack_ptr;
		stack_item.node = fnode;

/*		/*
* while provision_list is not empty		* while provision_list is not empty
* do_file(first_member_of(provision_list));		* do_file(first_member_of(provision_list));
*/		*/
while (head->next != NULL)		while (head->next != NULL)
do_file(head->next->fnode);		do_file(head->next->fnode, &stack_item);
}		}

static int		static int
skip_ok(filenode *fnode)		skip_ok(filenode *fnode)
{		{
strnodelist *s;		strnodelist *s;
strnodelist *k;		strnodelist *k;

Show All 26 Lines
* for each of them.. once we have done this, remove this filenode		* for each of them.. once we have done this, remove this filenode
* from each provision table, as we are now done.		* from each provision table, as we are now done.
*		*
* NOTE: do_file() is called recursively from several places and cannot		* NOTE: do_file() is called recursively from several places and cannot
* safely free() anything related to items that may be recursed on.		* safely free() anything related to items that may be recursed on.
* Circular dependencies will cause problems if we do.		* Circular dependencies will cause problems if we do.
*/		*/
static void		static void
do_file(filenode *fnode)		do_file(filenode fnode, strnodelist stack_ptr)
{		{
f_reqnode *r;		f_reqnode *r;
f_provnode p, p_tmp;		f_provnode p, p_tmp;
provnode *pnode;		provnode pnode, head;
int was_set;		int was_set;
		char *dep_name;

DPRINTF((stderr, "do_file on %s.\n", fnode->filename));		DPRINTF((stderr, "do_file on %s.\n", fnode->filename));

/*		/*
* if fnode is marked as in progress,		* if fnode is marked as in progress,
* print that fnode; is circularly depended upon and abort.		* print that fnode; is circularly depended upon and abort.
*/		*/
if (fnode->in_progress == SET) {		if (fnode->in_progress == SET) {
warnx("Circular dependency on file `%s'.",		warnx("Circular dependency on file `%s'.",
fnode->filename);		fnode->filename);
was_set = exit_code = 1;		was_set = exit_code = 1;
} else		} else
was_set = 0;		was_set = 0;

/* mark fnode */		/* mark fnode */
fnode->in_progress = SET;		fnode->in_progress = SET;

/*		/*
* for each requirement of fnode -> r		* for each requirement of fnode -> r
* satisfy_req(r, filename)		* satisfy_req(r, filename)
*/		*/
r = fnode->req_list;		r = fnode->req_list;
		fnode->sequence = 0;
while (r != NULL) {		while (r != NULL) {
satisfy_req(r, fnode->filename);		satisfy_req(r, fnode, stack_ptr);
		/* find sequence number where all requirements are satisfied */
		head = Hash_GetValue(r->entry);
		if (head && head->sequence > fnode->sequence)
		fnode->sequence = head->sequence;
r = r->next;		r = r->next;
}		}
fnode->req_list = NULL;		fnode->req_list = NULL;
		fnode->sequence++;

		/* if we've seen issues with this file - put it to the tail */
		if (fnode->issues_count)
		fnode->sequence = max_sequence + 1;

		if (max_sequence < fnode->sequence)
		max_sequence = fnode->sequence;

/*		/*
* for each provision of fnode -> p		* for each provision of fnode -> p
* remove fnode from provision list for p in hash table		* remove fnode from provision list for p in hash table
*/		*/
p = fnode->prov_list;		p = fnode->prov_list;
while (p != NULL) {		while (p != NULL) {
		/* mark all troublemakers on graphviz */
		if (do_graphviz == true && fnode->issues_count) {
		dep_name = Hash_GetKey(p->entry);
		if (!is_fake_prov(dep_name))
		printf("\"%s\" [ color=red, penwidth=4 ];\n",
		dep_name);
		}

		/* update sequence when provided requirements are satisfied */
		head = Hash_GetValue(p->entry);
		if (head->sequence < fnode->sequence)
		head->sequence = fnode->sequence;

p_tmp = p;		p_tmp = p;
pnode = p->pnode;		pnode = p->pnode;
if (pnode->next != NULL) {		if (pnode->next != NULL) {
pnode->next->last = pnode->last;		pnode->next->last = pnode->last;
}		}
if (pnode->last != NULL) {		if (pnode->last != NULL) {
pnode->last->next = pnode->next;		pnode->last->next = pnode->next;
}		}
free(pnode);		free(pnode);
p = p->next;		p = p->next;
free(p_tmp);		free(p_tmp);
}		}
fnode->prov_list = NULL;		fnode->prov_list = NULL;

/* do_it(fnode) */		/* do_it(fnode) */
DPRINTF((stderr, "next do: "));		DPRINTF((stderr, "next do: "));

/* if we were already in progress, don't print again */		/* if we were already in progress, don't print again */
if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode))		if (do_graphviz != true && was_set == 0 && skip_ok(fnode) &&
printf("%s\n", fnode->filename);		keep_ok(fnode)) {
		*fn_seqlist = fnode;
		fn_seqlist++;
		}

if (fnode->next != NULL) {		if (fnode->next != NULL) {
fnode->next->last = fnode->last;		fnode->next->last = fnode->last;
}		}
if (fnode->last != NULL) {		if (fnode->last != NULL) {
fnode->last->next = fnode->next;		fnode->last->next = fnode->next;
}		}

		if (fnode->issues_count)
		warnx("`%s' was seen in circular dependencies for %d times.",
		fnode->filename, fnode->issues_count);

DPRINTF((stderr, "nuking %s\n", fnode->filename));		DPRINTF((stderr, "nuking %s\n", fnode->filename));
#if 0
if (was_set == 0) {
free(fnode->filename);
free(fnode);
}		}
#endif
		static void
		generate_graphviz_header()
		{

		if (do_graphviz != true)
		return;

		printf("digraph rcorder {\n"
		"rankdir=\"BT\";\n"
		"node [style=rounded, shape=record];\n"
		"graph [overlap = false];\n");
}		}

static void		static void
		generate_graphviz_footer()
		{

		if (do_graphviz == true)
		printf("}\n");
		}

		static void
		generate_graphviz_providers()
		{
		Hash_Entry *entry;
		Hash_Search psearch;
		provnode head, pnode;
		char *dep_name;

		if (do_graphviz != true)
		return;

		entry = Hash_EnumFirst(provide_hash, &psearch);
		if (entry == NULL)
		return;

		do {
		dep_name = Hash_GetKey(entry);
		if (is_fake_prov(dep_name))
		continue;
		head = Hash_GetValue(entry);
		/* no providers for this requirement */
		if (head == NULL \|\| head->next == NULL) {
		printf("\"%s\" [label=\"{ %s \| ENOENT }\", "
		"style=\"rounded,filled\", color=red];\n",
		dep_name, dep_name);
		continue;
		}
		/* one PROVIDE word for one file that matches */
		if (head->next->next == NULL &&
		strcmp(dep_name,
		basename(head->next->fnode->filename)) == 0) {
		continue;
		}
		printf("\"%s\" [label=\"{ %s \| ", dep_name, dep_name);
		for (pnode = head->next; pnode; pnode = pnode->next)
		printf("%s\\n", basename(pnode->fnode->filename));

		printf("}\"];\n");
		} while (NULL != (entry = Hash_EnumNext(&psearch)));
		}

		static int
		sequence_cmp(const void a, const void b)
		{
		const filenode fna = ((const filenode * const *)a);
		const filenode fnb = ((const filenode * const *)b);
		int left, right;

		/* push phantom files to the end */
		if (fna == NULL \|\| fnb == NULL)
		return ((fna < fnb) - (fna > fnb));

		left = fna->sequence;
		right = fnb->sequence;

		return ((left > right) - (left < right));
		}

		static void
generate_ordering(void)		generate_ordering(void)
{		{
		filenode seqlist, psl;
		int last_seq = 0;

		/* Prepare order buffer, use an additional one as a list terminator */
		seqlist = emalloc(sizeof(filenode ) (file_count + 1));
		bzero(seqlist, sizeof(filenode ) (file_count + 1));
		fn_seqlist = seqlist;

/*		/*
* while there remain undone files{f},		* while there remain undone files{f},
* pick an arbitrary f, and do_file(f)		* pick an arbitrary f, and do_file(f)
* Note that the first file in the file list is perfectly		* Note that the first file in the file list is perfectly
* arbitrary, and easy to find, so we use that.		* arbitrary, and easy to find, so we use that.
*/		*/

/*		/*
* N.B.: the file nodes "self delete" after they execute, so		* N.B.: the file nodes "self delete" after they execute, so
* after each iteration of the loop, the head will be pointing		* after each iteration of the loop, the head will be pointing
* to something totally different. The loop ends up being		* to something totally different. The loop ends up being
* executed only once for every strongly connected set of		* executed only once for every strongly connected set of
* nodes.		* nodes.
*/		*/
while (fn_head->next != NULL) {		while (fn_head->next != NULL) {
DPRINTF((stderr, "generate on %s\n", fn_head->next->filename));		DPRINTF((stderr, "generate on %s\n", fn_head->next->filename));
do_file(fn_head->next);		do_file(fn_head->next, NULL);
}		}

		/* Sort filenode list based on sequence */
		qsort(seqlist, file_count, sizeof(filenode *), sequence_cmp);

		for (psl = seqlist; *psl; psl++) {
		printf("%s%s",
		(last_seq == 0 ? "" :
		(do_parallel != true \|\| last_seq != (*psl)->sequence) ?
		"\n" : " "),
		(*psl)->filename);
		last_seq = (*psl)->sequence;
		free((*psl)->filename);
		free(*psl);
		}
		if (last_seq)
		printf("\n");

		free(seqlist);
}		}