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