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 }