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