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