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