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