Home | History | Annotate | Line # | Download | only in rcorder
rcorder.c revision 1.3
      1  1.3    enami /*	$NetBSD: rcorder.c,v 1.3 2000/05/09 04:21:16 enami Exp $	*/
      2  1.1      mrg 
      3  1.1      mrg /*
      4  1.1      mrg  * Copyright (c) 1998, 1999 Matthew R. Green
      5  1.1      mrg  * All rights reserved.
      6  1.1      mrg  * Copyright (c) 1998
      7  1.1      mrg  * 	Perry E. Metzger.  All rights reserved.
      8  1.1      mrg  *
      9  1.1      mrg  * Redistribution and use in source and binary forms, with or without
     10  1.1      mrg  * modification, are permitted provided that the following conditions
     11  1.1      mrg  * are met:
     12  1.1      mrg  * 1. Redistributions of source code must retain the above copyright
     13  1.1      mrg  *    notice, this list of conditions and the following disclaimer.
     14  1.1      mrg  * 2. Redistributions in binary form must reproduce the above copyright
     15  1.1      mrg  *    notice, this list of conditions and the following disclaimer in the
     16  1.1      mrg  *    documentation and/or other materials provided with the distribution.
     17  1.1      mrg  * 3. All advertising materials mentioning features or use of this software
     18  1.1      mrg  *    must display the following acknowledgement:
     19  1.1      mrg  *	This product includes software developed for the NetBSD Project
     20  1.1      mrg  *	by Perry E. Metzger.
     21  1.1      mrg  * 4. The name of the author may not be used to endorse or promote products
     22  1.1      mrg  *    derived from this software without specific prior written permission.
     23  1.1      mrg  *
     24  1.1      mrg  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     25  1.1      mrg  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     26  1.1      mrg  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     27  1.1      mrg  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     28  1.1      mrg  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     29  1.1      mrg  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     30  1.1      mrg  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     31  1.1      mrg  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     32  1.1      mrg  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     33  1.1      mrg  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     34  1.1      mrg  */
     35  1.1      mrg 
     36  1.1      mrg #include <sys/types.h>
     37  1.3    enami #include <sys/stat.h>
     38  1.1      mrg 
     39  1.1      mrg #include <err.h>
     40  1.1      mrg #include <stdio.h>
     41  1.1      mrg #include <stdlib.h>
     42  1.1      mrg #include <string.h>
     43  1.1      mrg #include <unistd.h>
     44  1.1      mrg #include <util.h>
     45  1.1      mrg 
     46  1.1      mrg #include "ealloc.h"
     47  1.1      mrg #include "sprite.h"
     48  1.1      mrg #include "hash.h"
     49  1.1      mrg 
     50  1.1      mrg #ifdef DEBUG
     51  1.1      mrg int debug = 0;
     52  1.1      mrg # define	DPRINTF(args) if (debug) { fflush(stdout); fprintf args; }
     53  1.1      mrg #else
     54  1.1      mrg # define	DPRINTF(args)
     55  1.1      mrg #endif
     56  1.1      mrg 
     57  1.1      mrg #define REQUIRE_STR	"# REQUIRE:"
     58  1.1      mrg #define REQUIRE_LEN	(sizeof(REQUIRE_STR) - 1)
     59  1.1      mrg #define REQUIRES_STR	"# REQUIRES:"
     60  1.1      mrg #define REQUIRES_LEN	(sizeof(REQUIRES_STR) - 1)
     61  1.1      mrg #define PROVIDE_STR	"# PROVIDE:"
     62  1.1      mrg #define PROVIDE_LEN	(sizeof(PROVIDE_STR) - 1)
     63  1.1      mrg #define PROVIDES_STR	"# PROVIDES:"
     64  1.1      mrg #define PROVIDES_LEN	(sizeof(PROVIDES_STR) - 1)
     65  1.1      mrg #define BEFORE_STR	"# BEFORE:"
     66  1.1      mrg #define BEFORE_LEN	(sizeof(BEFORE_STR) - 1)
     67  1.1      mrg 
     68  1.1      mrg int exit_code;
     69  1.1      mrg int file_count;
     70  1.1      mrg char **file_list;
     71  1.1      mrg 
     72  1.1      mrg typedef int bool;
     73  1.1      mrg #define TRUE 1
     74  1.1      mrg #define FALSE 0
     75  1.1      mrg typedef bool flag;
     76  1.1      mrg #define SET TRUE
     77  1.1      mrg #define RESET FALSE
     78  1.1      mrg 
     79  1.1      mrg Hash_Table provide_hash_s, *provide_hash;
     80  1.1      mrg 
     81  1.1      mrg typedef struct provnode provnode;
     82  1.1      mrg typedef struct filenode filenode;
     83  1.1      mrg typedef struct f_provnode f_provnode;
     84  1.1      mrg typedef struct f_reqnode f_reqnode;
     85  1.1      mrg typedef struct beforelist beforelist;
     86  1.1      mrg 
     87  1.1      mrg struct provnode {
     88  1.1      mrg 	flag		head;
     89  1.1      mrg 	flag		in_progress;
     90  1.1      mrg 	filenode	*fnode;
     91  1.1      mrg 	provnode	*next, *last;
     92  1.1      mrg };
     93  1.1      mrg 
     94  1.1      mrg struct f_provnode {
     95  1.1      mrg 	provnode	*pnode;
     96  1.1      mrg 	f_provnode	*next;
     97  1.1      mrg };
     98  1.1      mrg 
     99  1.1      mrg struct f_reqnode {
    100  1.1      mrg 	Hash_Entry	*entry;
    101  1.1      mrg 	f_reqnode	*next;
    102  1.1      mrg };
    103  1.1      mrg 
    104  1.1      mrg struct filenode {
    105  1.1      mrg 	char		*filename;
    106  1.1      mrg 	flag		in_progress;
    107  1.1      mrg 	filenode	*next, *last;
    108  1.1      mrg 	f_reqnode	*req_list;
    109  1.1      mrg 	f_provnode	*prov_list;
    110  1.1      mrg };
    111  1.1      mrg 
    112  1.1      mrg struct beforelist {
    113  1.1      mrg 	filenode	*node;
    114  1.1      mrg 	char		*s;
    115  1.1      mrg 	beforelist	*next;
    116  1.1      mrg } *bl_list = NULL;
    117  1.1      mrg 
    118  1.1      mrg filenode fn_head_s, *fn_head;
    119  1.1      mrg 
    120  1.1      mrg void do_file __P((filenode *fnode));
    121  1.1      mrg void satisfy_req __P((f_reqnode *rnode, char *filename));
    122  1.1      mrg void crunch_file __P((char *));
    123  1.1      mrg void parse_require __P((filenode *, char *));
    124  1.1      mrg void parse_provide __P((filenode *, char *));
    125  1.1      mrg void parse_before __P((filenode *, char *));
    126  1.1      mrg filenode *filenode_new __P((char *));
    127  1.1      mrg void add_require __P((filenode *, char *));
    128  1.1      mrg void add_provide __P((filenode *, char *));
    129  1.1      mrg void add_before __P((filenode *, char *));
    130  1.1      mrg void insert_before __P((void));
    131  1.1      mrg Hash_Entry *make_fake_provision __P((filenode *));
    132  1.1      mrg void crunch_all_files __P((void));
    133  1.1      mrg void initialize __P((void));
    134  1.1      mrg void generate_ordering __P((void));
    135  1.1      mrg int main __P((int, char *[]));
    136  1.1      mrg 
    137  1.1      mrg int
    138  1.1      mrg main(argc, argv)
    139  1.1      mrg 	int argc;
    140  1.1      mrg 	char *argv[];
    141  1.1      mrg {
    142  1.1      mrg 	int ch;
    143  1.1      mrg 
    144  1.1      mrg 	while ((ch = getopt(argc, argv, "d")) != -1)
    145  1.1      mrg 		switch (ch) {
    146  1.1      mrg 		case 'd':
    147  1.1      mrg #ifdef DEBUG
    148  1.1      mrg 			debug = 1;
    149  1.1      mrg #else
    150  1.1      mrg 			warnx("debugging not compiled in, -d ignored");
    151  1.1      mrg #endif
    152  1.1      mrg 			break;
    153  1.1      mrg 		default:
    154  1.1      mrg 			/* XXX should crunch it? */
    155  1.1      mrg 			break;
    156  1.1      mrg 		}
    157  1.1      mrg 	argc -= optind;
    158  1.1      mrg 	argv += optind;
    159  1.1      mrg 
    160  1.1      mrg 	file_count = argc;
    161  1.1      mrg 	file_list = argv;
    162  1.1      mrg 
    163  1.1      mrg 	DPRINTF((stderr, "parse_args\n"));
    164  1.1      mrg 	initialize();
    165  1.1      mrg 	DPRINTF((stderr, "initialize\n"));
    166  1.1      mrg 	crunch_all_files();
    167  1.1      mrg 	DPRINTF((stderr, "crunch_all_files\n"));
    168  1.1      mrg 	generate_ordering();
    169  1.1      mrg 	DPRINTF((stderr, "generate_ordering\n"));
    170  1.1      mrg 
    171  1.1      mrg 	exit(exit_code);
    172  1.1      mrg }
    173  1.1      mrg 
    174  1.1      mrg /*
    175  1.1      mrg  * initialise various variables.
    176  1.1      mrg  */
    177  1.1      mrg void
    178  1.1      mrg initialize()
    179  1.1      mrg {
    180  1.1      mrg 
    181  1.1      mrg 	fn_head = &fn_head_s;
    182  1.1      mrg 
    183  1.1      mrg 	provide_hash = &provide_hash_s;
    184  1.1      mrg 	Hash_InitTable(provide_hash, file_count);
    185  1.1      mrg }
    186  1.1      mrg 
    187  1.1      mrg /*
    188  1.1      mrg  * below are the functions that deal with creating the lists
    189  1.1      mrg  * from the filename's given and the dependancies and provisions
    190  1.1      mrg  * in each of these files.  no ordering or checking is done here.
    191  1.1      mrg  */
    192  1.1      mrg 
    193  1.1      mrg /*
    194  1.1      mrg  * we have a new filename, create a new filenode structure.
    195  1.1      mrg  * fill in the bits, and put it in the filenode linked list
    196  1.1      mrg  */
    197  1.1      mrg filenode *
    198  1.1      mrg filenode_new(filename)
    199  1.1      mrg 	char *filename;
    200  1.1      mrg {
    201  1.1      mrg 	filenode *temp;
    202  1.1      mrg 
    203  1.1      mrg 	temp = emalloc(sizeof(*temp));
    204  1.1      mrg 	memset(temp, 0, sizeof(*temp));
    205  1.1      mrg 	temp->filename = estrdup(filename);
    206  1.1      mrg 	temp->req_list = NULL;
    207  1.1      mrg 	temp->prov_list = NULL;
    208  1.1      mrg 	temp->in_progress = RESET;
    209  1.1      mrg 	/*
    210  1.1      mrg 	 * link the filenode into the list of filenodes.
    211  1.1      mrg 	 * note that the double linking means we can delete a
    212  1.1      mrg 	 * filenode without searching for where it belongs.
    213  1.1      mrg 	 */
    214  1.1      mrg 	temp->next = fn_head->next;
    215  1.1      mrg 	if (temp->next != NULL)
    216  1.1      mrg 		temp->next->last = temp;
    217  1.1      mrg 	temp->last = fn_head;
    218  1.1      mrg 	fn_head->next = temp;
    219  1.1      mrg 	return (temp);
    220  1.1      mrg }
    221  1.1      mrg 
    222  1.1      mrg /*
    223  1.1      mrg  * add a requirement a filenode.
    224  1.1      mrg  */
    225  1.1      mrg void
    226  1.1      mrg add_require(fnode, s)
    227  1.1      mrg 	filenode *fnode;
    228  1.1      mrg 	char *s;
    229  1.1      mrg {
    230  1.1      mrg 	Hash_Entry *entry;
    231  1.1      mrg 	f_reqnode *rnode;
    232  1.1      mrg 	int new;
    233  1.1      mrg 
    234  1.1      mrg 	entry = Hash_CreateEntry(provide_hash, s, &new);
    235  1.1      mrg 	if (new)
    236  1.1      mrg 		Hash_SetValue(entry, NULL);
    237  1.1      mrg 	rnode = emalloc(sizeof(*rnode));
    238  1.1      mrg 	rnode->entry = entry;
    239  1.1      mrg 	rnode->next = fnode->req_list;
    240  1.1      mrg 	fnode->req_list = rnode;
    241  1.1      mrg }
    242  1.1      mrg 
    243  1.1      mrg /*
    244  1.1      mrg  * add a provision to a filenode.  if this provision doesn't
    245  1.1      mrg  * have a head node, create one here.
    246  1.1      mrg  */
    247  1.1      mrg void
    248  1.1      mrg add_provide(fnode, s)
    249  1.1      mrg 	filenode *fnode;
    250  1.1      mrg 	char *s;
    251  1.1      mrg {
    252  1.1      mrg 	Hash_Entry *entry;
    253  1.1      mrg 	f_provnode *f_pnode;
    254  1.1      mrg 	provnode *pnode, *head;
    255  1.1      mrg 	int new;
    256  1.1      mrg 
    257  1.1      mrg 	entry = Hash_CreateEntry(provide_hash, s, &new);
    258  1.1      mrg 	head = Hash_GetValue(entry);
    259  1.1      mrg 
    260  1.1      mrg 	/* create a head node if necessary. */
    261  1.1      mrg 	if (head == NULL) {
    262  1.1      mrg 		head = emalloc(sizeof(*head));
    263  1.1      mrg 		head->head = SET;
    264  1.1      mrg 		head->in_progress = RESET;
    265  1.1      mrg 		head->fnode = NULL;
    266  1.1      mrg 		head->last = head->next = NULL;
    267  1.1      mrg 		Hash_SetValue(entry, head);
    268  1.2  thorpej 	}
    269  1.2  thorpej #if 0
    270  1.2  thorpej 	/*
    271  1.2  thorpej 	 * Don't warn about this.  We want to be able to support
    272  1.2  thorpej 	 * scripts that do two complex things:
    273  1.2  thorpej 	 *
    274  1.2  thorpej 	 *	- Two independent scripts which both provide the
    275  1.2  thorpej 	 *	  same thing.  Both scripts must be executed in
    276  1.2  thorpej 	 *	  any order to meet the barrier.  An example:
    277  1.2  thorpej 	 *
    278  1.2  thorpej 	 *		Script 1:
    279  1.2  thorpej 	 *
    280  1.2  thorpej 	 *			PROVIDE: mail
    281  1.2  thorpej 	 *			REQUIRE: LOGIN
    282  1.2  thorpej 	 *
    283  1.2  thorpej 	 *		Script 2:
    284  1.2  thorpej 	 *
    285  1.2  thorpej 	 *			PROVIDE: mail
    286  1.2  thorpej 	 *			REQUIRE: LOGIN
    287  1.2  thorpej 	 *
    288  1.2  thorpej 	 * 	- Two interdependent scripts which both provide the
    289  1.2  thorpej 	 *	  same thing.  Both scripts must be executed in
    290  1.2  thorpej 	 *	  graph order to meet the barrier.  An example:
    291  1.2  thorpej 	 *
    292  1.2  thorpej 	 *		Script 1:
    293  1.2  thorpej 	 *
    294  1.2  thorpej 	 *			PROVIDE: nameservice dnscache
    295  1.2  thorpej 	 *			REQUIRE: SERVERS
    296  1.2  thorpej 	 *
    297  1.2  thorpej 	 *		Script 2:
    298  1.2  thorpej 	 *
    299  1.2  thorpej 	 *			PROVIDE: nameservice nscd
    300  1.2  thorpej 	 *			REQUIRE: dnscache
    301  1.2  thorpej 	 */
    302  1.2  thorpej 	else if (new == 0) {
    303  1.1      mrg 		warnx("file `%s' provides `%s'.", fnode->filename, s);
    304  1.2  thorpej 		warnx("\tpreviously seen in `%s'.",
    305  1.2  thorpej 		    head->next->fnode->filename);
    306  1.1      mrg 	}
    307  1.2  thorpej #endif
    308  1.1      mrg 
    309  1.1      mrg 	pnode = emalloc(sizeof(*pnode));
    310  1.1      mrg 	pnode->head = RESET;
    311  1.1      mrg 	pnode->in_progress = RESET;
    312  1.1      mrg 	pnode->fnode = fnode;
    313  1.1      mrg 	pnode->next = head->next;
    314  1.1      mrg 	pnode->last = head;
    315  1.1      mrg 	head->next = pnode;
    316  1.1      mrg 	if (pnode->next != NULL)
    317  1.1      mrg 		pnode->next->last = pnode;
    318  1.1      mrg 
    319  1.1      mrg 	f_pnode = emalloc(sizeof(*f_pnode));
    320  1.1      mrg 	f_pnode->pnode = pnode;
    321  1.1      mrg 	f_pnode->next = fnode->prov_list;
    322  1.1      mrg 	fnode->prov_list = f_pnode;
    323  1.1      mrg }
    324  1.1      mrg 
    325  1.1      mrg /*
    326  1.1      mrg  * put the BEFORE: lines to a list and handle them later.
    327  1.1      mrg  */
    328  1.1      mrg void
    329  1.1      mrg add_before(fnode, s)
    330  1.1      mrg 	filenode *fnode;
    331  1.1      mrg 	char *s;
    332  1.1      mrg {
    333  1.1      mrg 	beforelist *bf_ent;
    334  1.1      mrg 
    335  1.1      mrg 	bf_ent = emalloc(sizeof *bf_ent);
    336  1.1      mrg 	bf_ent->node = fnode;
    337  1.1      mrg 	bf_ent->s = s;
    338  1.1      mrg 	bf_ent->next = bl_list;
    339  1.1      mrg 	bl_list = bf_ent;
    340  1.1      mrg }
    341  1.1      mrg 
    342  1.1      mrg /*
    343  1.1      mrg  * loop over the rest of a REQUIRE line, giving each word to
    344  1.1      mrg  * add_require() to do the real work.
    345  1.1      mrg  */
    346  1.1      mrg void
    347  1.1      mrg parse_require(node, buffer)
    348  1.1      mrg 	filenode *node;
    349  1.1      mrg 	char *buffer;
    350  1.1      mrg {
    351  1.1      mrg 	char *s;
    352  1.1      mrg 
    353  1.1      mrg 	while ((s = strsep(&buffer, " \t\n")) != NULL)
    354  1.1      mrg 		if (*s != '\0')
    355  1.1      mrg 			add_require(node, s);
    356  1.1      mrg }
    357  1.1      mrg 
    358  1.1      mrg /*
    359  1.1      mrg  * loop over the rest of a PROVIDE line, giving each word to
    360  1.1      mrg  * add_provide() to do the real work.
    361  1.1      mrg  */
    362  1.1      mrg void
    363  1.1      mrg parse_provide(node, buffer)
    364  1.1      mrg 	filenode *node;
    365  1.1      mrg 	char *buffer;
    366  1.1      mrg {
    367  1.1      mrg 	char *s;
    368  1.1      mrg 
    369  1.1      mrg 	while ((s = strsep(&buffer, " \t\n")) != NULL)
    370  1.1      mrg 		if (*s != '\0')
    371  1.1      mrg 			add_provide(node, s);
    372  1.1      mrg }
    373  1.1      mrg 
    374  1.1      mrg /*
    375  1.1      mrg  * loop over the rest of a BEFORE line, giving each word to
    376  1.1      mrg  * add_before() to do the real work.
    377  1.1      mrg  */
    378  1.1      mrg void
    379  1.1      mrg parse_before(node, buffer)
    380  1.1      mrg 	filenode *node;
    381  1.1      mrg 	char *buffer;
    382  1.1      mrg {
    383  1.1      mrg 	char *s;
    384  1.1      mrg 
    385  1.1      mrg 	while ((s = strsep(&buffer, " \t\n")) != NULL)
    386  1.1      mrg 		if (*s != '\0')
    387  1.1      mrg 			add_before(node, s);
    388  1.1      mrg }
    389  1.1      mrg 
    390  1.1      mrg /*
    391  1.1      mrg  * given a file name, create a filenode for it, read in lines looking
    392  1.1      mrg  * for provision and requirement lines, building the graphs as needed.
    393  1.1      mrg  */
    394  1.1      mrg void
    395  1.1      mrg crunch_file(filename)
    396  1.1      mrg 	char *filename;
    397  1.1      mrg {
    398  1.1      mrg 	FILE *fp;
    399  1.1      mrg 	char *buf;
    400  1.1      mrg 	int require_flag, provide_flag, before_flag, directive_flag;
    401  1.1      mrg 	filenode *node;
    402  1.1      mrg 	char delims[3] = { '\\', '\\', '\0' };
    403  1.3    enami 	struct stat st;
    404  1.1      mrg 
    405  1.1      mrg 	directive_flag = 0;
    406  1.1      mrg 
    407  1.1      mrg 	if ((fp = fopen(filename, "r")) == NULL) {
    408  1.1      mrg 		warn("could not open %s", filename);
    409  1.3    enami 		return;
    410  1.3    enami 	}
    411  1.3    enami 
    412  1.3    enami 	if (fstat(fileno(fp), &st) == -1) {
    413  1.3    enami 		warn("could not stat %s", filename);
    414  1.3    enami 		return;
    415  1.3    enami 	}
    416  1.3    enami 
    417  1.3    enami 	if (!S_ISREG(st.st_mode)) {
    418  1.3    enami 		warnx("%s is not a file", filename);
    419  1.1      mrg 		return;
    420  1.1      mrg 	}
    421  1.1      mrg 
    422  1.1      mrg 	node = filenode_new(filename);
    423  1.1      mrg 
    424  1.1      mrg 	/*
    425  1.1      mrg 	 * we don't care about length, line number, don't want # for comments,
    426  1.1      mrg 	 * and have no flags.
    427  1.1      mrg 	 */
    428  1.1      mrg 	while ((buf = fparseln(fp, NULL, NULL, delims, 0))) {
    429  1.1      mrg 		require_flag = provide_flag = before_flag = 0;
    430  1.1      mrg 		if (strncmp(REQUIRE_STR, buf, REQUIRE_LEN) == 0)
    431  1.1      mrg 			require_flag = REQUIRE_LEN;
    432  1.1      mrg 		else if (strncmp(REQUIRES_STR, buf, REQUIRES_LEN) == 0)
    433  1.1      mrg 			require_flag = REQUIRES_LEN;
    434  1.1      mrg 		else if (strncmp(PROVIDE_STR, buf, PROVIDE_LEN) == 0)
    435  1.1      mrg 			provide_flag = PROVIDE_LEN;
    436  1.1      mrg 		else if (strncmp(PROVIDES_STR, buf, PROVIDES_LEN) == 0)
    437  1.1      mrg 			provide_flag = PROVIDES_LEN;
    438  1.1      mrg 		else if (strncmp(BEFORE_STR, buf, BEFORE_LEN) == 0)
    439  1.1      mrg 			before_flag = BEFORE_LEN;
    440  1.1      mrg 
    441  1.1      mrg 		if (require_flag)
    442  1.1      mrg 			parse_require(node, buf + require_flag);
    443  1.1      mrg 
    444  1.1      mrg 		if (provide_flag)
    445  1.1      mrg 			parse_provide(node, buf + provide_flag);
    446  1.1      mrg 
    447  1.1      mrg 		if (before_flag)
    448  1.1      mrg 			parse_before(node, buf + before_flag);
    449  1.1      mrg 	}
    450  1.1      mrg 	fclose(fp);
    451  1.1      mrg }
    452  1.1      mrg 
    453  1.1      mrg Hash_Entry *
    454  1.1      mrg make_fake_provision(node)
    455  1.1      mrg 	filenode *node;
    456  1.1      mrg {
    457  1.1      mrg 	Hash_Entry *entry;
    458  1.1      mrg 	f_provnode *f_pnode;
    459  1.1      mrg 	provnode *head, *pnode;
    460  1.1      mrg 	static	int i = 0;
    461  1.1      mrg 	int	new;
    462  1.1      mrg 	char buffer[30];
    463  1.1      mrg 
    464  1.1      mrg 	do {
    465  1.1      mrg 		snprintf(buffer, sizeof buffer, "fake_prov_%08d", i++);
    466  1.1      mrg 		entry = Hash_CreateEntry(provide_hash, buffer, &new);
    467  1.1      mrg 	} while (new == 0);
    468  1.1      mrg 	head = emalloc(sizeof(*head));
    469  1.1      mrg 	head->head = SET;
    470  1.1      mrg 	head->in_progress = RESET;
    471  1.1      mrg 	head->fnode = NULL;
    472  1.1      mrg 	head->last = head->next = NULL;
    473  1.1      mrg 	Hash_SetValue(entry, head);
    474  1.1      mrg 
    475  1.1      mrg 	pnode = emalloc(sizeof(*pnode));
    476  1.1      mrg 	pnode->head = RESET;
    477  1.1      mrg 	pnode->in_progress = RESET;
    478  1.1      mrg 	pnode->fnode = node;
    479  1.1      mrg 	pnode->next = head->next;
    480  1.1      mrg 	pnode->last = head;
    481  1.1      mrg 	head->next = pnode;
    482  1.1      mrg 	if (pnode->next != NULL)
    483  1.1      mrg 		pnode->next->last = pnode;
    484  1.1      mrg 
    485  1.1      mrg 	f_pnode = emalloc(sizeof(*f_pnode));
    486  1.1      mrg 	f_pnode->pnode = pnode;
    487  1.1      mrg 	f_pnode->next = node->prov_list;
    488  1.1      mrg 	node->prov_list = f_pnode;
    489  1.1      mrg 
    490  1.1      mrg 	return (entry);
    491  1.1      mrg }
    492  1.1      mrg 
    493  1.1      mrg /*
    494  1.1      mrg  * go through the BEFORE list, inserting requirements into the graph(s)
    495  1.1      mrg  * as required.  in the before list, for each entry B, we have a file F
    496  1.1      mrg  * and a string S.  we create a "fake" provision (P) that F provides.
    497  1.1      mrg  * for each entry in the provision list for S, add a requirement to
    498  1.1      mrg  * that provisions filenode for P.
    499  1.1      mrg  */
    500  1.1      mrg void
    501  1.1      mrg insert_before()
    502  1.1      mrg {
    503  1.1      mrg 	Hash_Entry *entry, *fake_prov_entry;
    504  1.1      mrg 	provnode *pnode;
    505  1.1      mrg 	f_reqnode *rnode;
    506  1.1      mrg 	beforelist *bl;
    507  1.1      mrg 	int new;
    508  1.1      mrg 
    509  1.1      mrg 	while (bl_list != NULL) {
    510  1.1      mrg 		bl = bl_list->next;
    511  1.1      mrg 
    512  1.1      mrg 		fake_prov_entry = make_fake_provision(bl_list->node);
    513  1.1      mrg 
    514  1.1      mrg 		entry = Hash_CreateEntry(provide_hash, bl_list->s, &new);
    515  1.1      mrg 		if (new == 1)
    516  1.1      mrg 			warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s);
    517  1.1      mrg 
    518  1.1      mrg 		for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) {
    519  1.1      mrg 			if (pnode->head)
    520  1.1      mrg 				continue;
    521  1.1      mrg 
    522  1.1      mrg 			rnode = emalloc(sizeof(*rnode));
    523  1.1      mrg 			rnode->entry = fake_prov_entry;
    524  1.1      mrg 			rnode->next = pnode->fnode->req_list;
    525  1.1      mrg 			pnode->fnode->req_list = rnode;
    526  1.1      mrg 		}
    527  1.1      mrg 
    528  1.1      mrg 		free(bl_list);
    529  1.1      mrg 		bl_list = bl;
    530  1.1      mrg 	}
    531  1.1      mrg }
    532  1.1      mrg 
    533  1.1      mrg /*
    534  1.1      mrg  * loop over all the files calling crunch_file() on them to do the
    535  1.1      mrg  * real work.  after we have built all the nodes, insert the BEFORE:
    536  1.1      mrg  * lines into graph(s).
    537  1.1      mrg  */
    538  1.1      mrg void
    539  1.1      mrg crunch_all_files()
    540  1.1      mrg {
    541  1.1      mrg 	int i;
    542  1.1      mrg 
    543  1.1      mrg 	for (i = 0; i < file_count; i++)
    544  1.1      mrg 		crunch_file(file_list[i]);
    545  1.1      mrg 	insert_before();
    546  1.1      mrg }
    547  1.1      mrg 
    548  1.1      mrg /*
    549  1.1      mrg  * below are the functions that traverse the graphs we have built
    550  1.1      mrg  * finding out the desired ordering, printing each file in turn.
    551  1.1      mrg  * if missing requirements, or cyclic graphs are detected, a
    552  1.1      mrg  * warning will be issued, and we will continue on..
    553  1.1      mrg  */
    554  1.1      mrg 
    555  1.1      mrg /*
    556  1.1      mrg  * given a requirement node (in a filename) we attempt to satisfy it.
    557  1.1      mrg  * we do some sanity checking first, to ensure that we have providers,
    558  1.1      mrg  * aren't already satisfied and aren't already being satisfied (ie,
    559  1.1      mrg  * cyclic).  if we pass all this, we loop over the provision list
    560  1.1      mrg  * calling do_file() (enter recursion) for each filenode in this
    561  1.1      mrg  * provision.
    562  1.1      mrg  */
    563  1.1      mrg void
    564  1.1      mrg satisfy_req(rnode, filename)
    565  1.1      mrg 	f_reqnode *rnode;
    566  1.1      mrg 	char *filename;
    567  1.1      mrg {
    568  1.1      mrg 	Hash_Entry *entry;
    569  1.1      mrg 	provnode *head;
    570  1.1      mrg 
    571  1.1      mrg 	entry = rnode->entry;
    572  1.1      mrg 	head = Hash_GetValue(entry);
    573  1.1      mrg 
    574  1.1      mrg 	if (head == NULL) {
    575  1.1      mrg 		warnx("requirement `%s' in file `%s' has no providers.",
    576  1.1      mrg 		    Hash_GetKey(entry), filename);
    577  1.1      mrg 		exit_code = 1;
    578  1.1      mrg 		return;
    579  1.1      mrg 	}
    580  1.1      mrg 
    581  1.1      mrg 	/* return if the requirement is already satisfied. */
    582  1.1      mrg 	if (head->next == NULL)
    583  1.1      mrg 		return;
    584  1.1      mrg 
    585  1.1      mrg 	/*
    586  1.1      mrg 	 * if list is marked as in progress,
    587  1.1      mrg 	 *	print that there is a circular dependency on it and abort
    588  1.1      mrg 	 */
    589  1.1      mrg 	if (head->in_progress == SET) {
    590  1.1      mrg 		warnx("Circular dependency on provision `%s' in file `%s'.",
    591  1.1      mrg 		    Hash_GetKey(entry), filename);
    592  1.1      mrg 		exit_code = 1;
    593  1.1      mrg 		return;
    594  1.1      mrg 	}
    595  1.1      mrg 
    596  1.1      mrg 	head->in_progress = SET;
    597  1.1      mrg 
    598  1.1      mrg 	/*
    599  1.1      mrg 	 * while provision_list is not empty
    600  1.1      mrg 	 *	do_file(first_member_of(provision_list));
    601  1.1      mrg 	 */
    602  1.1      mrg 	while (head->next != NULL)
    603  1.1      mrg 		do_file(head->next->fnode);
    604  1.1      mrg }
    605  1.1      mrg 
    606  1.1      mrg /*
    607  1.1      mrg  * given a filenode, we ensure we are not a cyclic graph.  if this
    608  1.1      mrg  * is ok, we loop over the filenodes requirements, calling satisfy_req()
    609  1.1      mrg  * for each of them.. once we have done this, remove this filenode
    610  1.1      mrg  * from each provision table, as we are now done.
    611  1.1      mrg  */
    612  1.1      mrg void
    613  1.1      mrg do_file(fnode)
    614  1.1      mrg 	filenode *fnode;
    615  1.1      mrg {
    616  1.1      mrg 	f_reqnode *r, *r_tmp;
    617  1.1      mrg 	f_provnode *p, *p_tmp;
    618  1.1      mrg 	provnode *pnode;
    619  1.1      mrg 	int was_set;
    620  1.1      mrg 
    621  1.1      mrg 	DPRINTF((stderr, "do_file on %s.\n", fnode->filename));
    622  1.1      mrg 
    623  1.1      mrg 	/*
    624  1.1      mrg 	 * if fnode is marked as in progress,
    625  1.1      mrg 	 *	 print that fnode; is circularly depended upon and abort.
    626  1.1      mrg 	 */
    627  1.1      mrg 	if (fnode->in_progress == SET) {
    628  1.1      mrg 		warnx("Circular dependency on file `%s'.",
    629  1.1      mrg 			fnode->filename);
    630  1.1      mrg 		was_set = exit_code = 1;
    631  1.1      mrg 	} else
    632  1.1      mrg 		was_set = 0;
    633  1.1      mrg 
    634  1.1      mrg 	/* mark fnode */
    635  1.1      mrg 	fnode->in_progress = SET;
    636  1.1      mrg 
    637  1.1      mrg 	/*
    638  1.1      mrg 	 * for each requirement of fnode -> r
    639  1.1      mrg 	 *	satisfy_req(r, filename)
    640  1.1      mrg 	 */
    641  1.1      mrg 	r = fnode->req_list;
    642  1.1      mrg 	while (r != NULL) {
    643  1.1      mrg 		r_tmp = r;
    644  1.1      mrg 		satisfy_req(r, fnode->filename);
    645  1.1      mrg 		r = r->next;
    646  1.1      mrg 		free(r_tmp);
    647  1.1      mrg 	}
    648  1.1      mrg 	fnode->req_list = NULL;
    649  1.1      mrg 
    650  1.1      mrg 	/*
    651  1.1      mrg 	 * for each provision of fnode -> p
    652  1.1      mrg 	 *	remove fnode from provision list for p in hash table
    653  1.1      mrg 	 */
    654  1.1      mrg 	p = fnode->prov_list;
    655  1.1      mrg 	while (p != NULL) {
    656  1.1      mrg 		p_tmp = p;
    657  1.1      mrg 		pnode = p->pnode;
    658  1.1      mrg 		if (pnode->next != NULL) {
    659  1.1      mrg 			pnode->next->last = pnode->last;
    660  1.1      mrg 		}
    661  1.1      mrg 		if (pnode->last != NULL) {
    662  1.1      mrg 			pnode->last->next = pnode->next;
    663  1.1      mrg 		}
    664  1.1      mrg 		free(pnode);
    665  1.1      mrg 		p = p->next;
    666  1.1      mrg 		free(p_tmp);
    667  1.1      mrg 	}
    668  1.1      mrg 	fnode->prov_list = NULL;
    669  1.1      mrg 
    670  1.1      mrg 	/* do_it(fnode) */
    671  1.1      mrg 	DPRINTF((stderr, "next do: "));
    672  1.1      mrg 
    673  1.1      mrg 	/* if we were already in progress, don't print again */
    674  1.1      mrg 	if (was_set == 0)
    675  1.1      mrg 		printf("%s\n", fnode->filename);
    676  1.1      mrg 
    677  1.1      mrg 	if (fnode->next != NULL) {
    678  1.1      mrg 		fnode->next->last = fnode->last;
    679  1.1      mrg 	}
    680  1.1      mrg 	if (fnode->last != NULL) {
    681  1.1      mrg 		fnode->last->next = fnode->next;
    682  1.1      mrg 	}
    683  1.1      mrg 
    684  1.1      mrg 	DPRINTF((stderr, "nuking %s\n", fnode->filename));
    685  1.1      mrg 	free(fnode->filename);
    686  1.1      mrg 	free(fnode);
    687  1.1      mrg }
    688  1.1      mrg 
    689  1.1      mrg void
    690  1.1      mrg generate_ordering()
    691  1.1      mrg {
    692  1.1      mrg 
    693  1.1      mrg 	/*
    694  1.1      mrg 	 * while there remain undone files{f},
    695  1.1      mrg 	 *	pick an arbitrary f, and do_file(f)
    696  1.1      mrg 	 * Note that the first file in the file list is perfectly
    697  1.1      mrg 	 * arbitrary, and easy to find, so we use that.
    698  1.1      mrg 	 */
    699  1.1      mrg 
    700  1.1      mrg 	/*
    701  1.1      mrg 	 * N.B.: the file nodes "self delete" after they execute, so
    702  1.1      mrg 	 * after each iteration of the loop, the head will be pointing
    703  1.1      mrg 	 * to something totally different. The loop ends up being
    704  1.1      mrg 	 * executed only once for every strongly connected set of
    705  1.1      mrg 	 * nodes.
    706  1.1      mrg 	 */
    707  1.1      mrg 	while (fn_head->next != NULL) {
    708  1.1      mrg 		DPRINTF((stderr, "generate on %s\n", fn_head->next->filename));
    709  1.1      mrg 		do_file(fn_head->next);
    710  1.1      mrg 	}
    711  1.1      mrg }
    712