rcorder.c revision 296736
131921Sbrian# if 0 231921Sbrian/* $NetBSD: rcorder.c,v 1.7 2000/08/04 07:33:55 enami Exp $ */ 331921Sbrian#endif 431921Sbrian 531921Sbrian/* 631921Sbrian * Copyright (c) 1998, 1999 Matthew R. Green 730715Sbrian * All rights reserved. 831921Sbrian * Copyright (c) 1998 931921Sbrian * Perry E. Metzger. All rights reserved. 1031921Sbrian * 1131921Sbrian * Redistribution and use in source and binary forms, with or without 1231921Sbrian * modification, are permitted provided that the following conditions 1331921Sbrian * are met: 1431921Sbrian * 1. Redistributions of source code must retain the above copyright 1531921Sbrian * notice, this list of conditions and the following disclaimer. 1630715Sbrian * 2. Redistributions in binary form must reproduce the above copyright 1731921Sbrian * notice, this list of conditions and the following disclaimer in the 1831921Sbrian * documentation and/or other materials provided with the distribution. 1931921Sbrian * 3. All advertising materials mentioning features or use of this software 2031921Sbrian * must display the following acknowledgement: 2131921Sbrian * This product includes software developed for the NetBSD Project 2231921Sbrian * by Perry E. Metzger. 2331921Sbrian * 4. The name of the author may not be used to endorse or promote products 2431921Sbrian * derived from this software without specific prior written permission. 2531921Sbrian * 2631921Sbrian * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 2731921Sbrian * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 2831921Sbrian * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2950479Speter * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 306059Samurai * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 316059Samurai * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3236285Sbrian * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3330715Sbrian * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3431514Sbrian * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 3530715Sbrian * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3646686Sbrian */ 3730715Sbrian 3838174Sbrian#include <sys/types.h> 3946686Sbrian__FBSDID("$FreeBSD: stable/10/sbin/rcorder/rcorder.c 296736 2016-03-12 18:40:51Z ngie $"); 4030715Sbrian 4130715Sbrian#include <sys/stat.h> 4230715Sbrian 4330715Sbrian#include <err.h> 4436285Sbrian#include <stdio.h> 4530715Sbrian#include <libutil.h> 4631514Sbrian#include <stdlib.h> 4730715Sbrian#include <string.h> 4844650Sbrian#include <unistd.h> 4944650Sbrian 5030715Sbrian#include "ealloc.h" 5130715Sbrian#include "sprite.h" 526059Samurai#include "hash.h" 536059Samurai 546059Samurai#ifdef DEBUG 556059Samuraistatic int debug = 0; 566059Samurai# define DPRINTF(args) if (debug) { fflush(stdout); fprintf args; } 576059Samurai#else 5836285Sbrian# define DPRINTF(args) 5931514Sbrian#endif 606059Samurai 6136285Sbrian#define REQUIRE_STR "# REQUIRE:" 6236285Sbrian#define REQUIRE_LEN (sizeof(REQUIRE_STR) - 1) 6336285Sbrian#define REQUIRES_STR "# REQUIRES:" 6436285Sbrian#define REQUIRES_LEN (sizeof(REQUIRES_STR) - 1) 656059Samurai#define PROVIDE_STR "# PROVIDE:" 666059Samurai#define PROVIDE_LEN (sizeof(PROVIDE_STR) - 1) 6736285Sbrian#define PROVIDES_STR "# PROVIDES:" 686059Samurai#define PROVIDES_LEN (sizeof(PROVIDES_STR) - 1) 6928679Sbrian#define BEFORE_STR "# BEFORE:" 7028679Sbrian#define BEFORE_LEN (sizeof(BEFORE_STR) - 1) 716059Samurai#define KEYWORD_STR "# KEYWORD:" 7228679Sbrian#define KEYWORD_LEN (sizeof(KEYWORD_STR) - 1) 7328679Sbrian#define KEYWORDS_STR "# KEYWORDS:" 7428679Sbrian#define KEYWORDS_LEN (sizeof(KEYWORDS_STR) - 1) 7528679Sbrian 7628679Sbrianstatic int exit_code; 7736285Sbrianstatic int file_count; 7828679Sbrianstatic char **file_list; 7928679Sbrian 8036285Sbriantypedef int bool; 8128679Sbrian#define TRUE 1 8228679Sbrian#define FALSE 0 8336285Sbriantypedef bool flag; 8428679Sbrian#define SET TRUE 856059Samurai#define RESET FALSE 8628679Sbrian 8728679Sbrianstatic Hash_Table provide_hash_s, *provide_hash; 8828679Sbrian 896059Samuraitypedef struct provnode provnode; 906059Samuraitypedef struct filenode filenode; 916059Samuraitypedef struct f_provnode f_provnode; 9244792Sbriantypedef struct f_reqnode f_reqnode; 936059Samuraitypedef struct strnodelist strnodelist; 9428679Sbrian 9544792Sbrianstruct provnode { 9644792Sbrian flag head; 9728679Sbrian flag in_progress; 986059Samurai filenode *fnode; 996059Samurai provnode *next, *last; 1006059Samurai}; 10144792Sbrian 1026059Samuraistruct f_provnode { 10328679Sbrian provnode *pnode; 10428679Sbrian f_provnode *next; 1056059Samurai}; 10628679Sbrian 10728679Sbrianstruct f_reqnode { 10828679Sbrian Hash_Entry *entry; 10928679Sbrian f_reqnode *next; 11028679Sbrian}; 11128679Sbrian 11236285Sbrianstruct strnodelist { 11328679Sbrian filenode *node; 11428679Sbrian strnodelist *next; 11528679Sbrian char s[1]; 11636285Sbrian}; 11728679Sbrian 11828679Sbrianstruct filenode { 11928679Sbrian char *filename; 12036285Sbrian flag in_progress; 1216059Samurai filenode *next, *last; 12228679Sbrian f_reqnode *req_list; 12328679Sbrian f_provnode *prov_list; 1246059Samurai strnodelist *keyword_list; 1256059Samurai}; 12631514Sbrian 12736285Sbrianstatic filenode fn_head_s, *fn_head; 1286059Samurai 12936285Sbrianstatic strnodelist *bl_list; 13036285Sbrianstatic strnodelist *keep_list; 13131514Sbrianstatic strnodelist *skip_list; 13231514Sbrian 13331514Sbrianstatic void do_file(filenode *fnode); 13436285Sbrianstatic void strnode_add(strnodelist **, char *, filenode *); 13531514Sbrianstatic int skip_ok(filenode *fnode); 13636285Sbrianstatic int keep_ok(filenode *fnode); 13736285Sbrianstatic void satisfy_req(f_reqnode *rnode, char *filename); 13836285Sbrianstatic void crunch_file(char *); 13936285Sbrianstatic void parse_require(filenode *, char *); 1406059Samuraistatic void parse_provide(filenode *, char *); 1416059Samuraistatic void parse_before(filenode *, char *); 14231514Sbrianstatic void parse_keywords(filenode *, char *); 14336285Sbrianstatic filenode *filenode_new(char *); 14431514Sbrianstatic void add_require(filenode *, char *); 14536285Sbrianstatic void add_provide(filenode *, char *); 14636285Sbrianstatic void add_before(filenode *, char *); 14736285Sbrianstatic void add_keyword(filenode *, char *); 14836285Sbrianstatic void insert_before(void); 14931514Sbrianstatic Hash_Entry *make_fake_provision(filenode *); 15031514Sbrianstatic void crunch_all_files(void); 15136285Sbrianstatic void initialize(void); 15236285Sbrianstatic void generate_ordering(void); 15331514Sbrian 15436285Sbrianint 15536285Sbrianmain(int argc, char *argv[]) 15636285Sbrian{ 15736285Sbrian int ch; 15836285Sbrian 15931514Sbrian while ((ch = getopt(argc, argv, "dk:s:")) != -1) 16031514Sbrian switch (ch) { 16136285Sbrian case 'd': 16236285Sbrian#ifdef DEBUG 16331514Sbrian debug = 1; 16436285Sbrian#else 16536285Sbrian warnx("debugging not compiled in, -d ignored"); 16636285Sbrian#endif 16736285Sbrian break; 16836285Sbrian case 'k': 16931514Sbrian strnode_add(&keep_list, optarg, 0); 17031514Sbrian break; 17146686Sbrian case 's': 17246686Sbrian strnode_add(&skip_list, optarg, 0); 17336285Sbrian break; 17431514Sbrian default: 17536285Sbrian /* XXX should crunch it? */ 1766059Samurai break; 1776059Samurai } 1786059Samurai argc -= optind; 17928679Sbrian argv += optind; 1806059Samurai 1816059Samurai file_count = argc; 18254912Sbrian file_list = argv; 18354912Sbrian 1846059Samurai DPRINTF((stderr, "parse_args\n")); 1856059Samurai initialize(); 1866059Samurai DPRINTF((stderr, "initialize\n")); 1876059Samurai crunch_all_files(); 18846686Sbrian DPRINTF((stderr, "crunch_all_files\n")); 18946686Sbrian generate_ordering(); 19036285Sbrian DPRINTF((stderr, "generate_ordering\n")); 19146686Sbrian 1926059Samurai exit(exit_code); 1936059Samurai} 19436285Sbrian 19536285Sbrian/* 19636285Sbrian * initialise various variables. 1976059Samurai */ 1986059Samuraistatic void 1996059Samuraiinitialize(void) 20036285Sbrian{ 2016059Samurai 20230715Sbrian fn_head = &fn_head_s; 2036059Samurai 20436285Sbrian provide_hash = &provide_hash_s; 2056059Samurai Hash_InitTable(provide_hash, file_count); 2066059Samurai} 2076059Samurai 2086059Samurai/* generic function to insert a new strnodelist element */ 20954912Sbrianstatic void 21046686Sbrianstrnode_add(strnodelist **listp, char *s, filenode *fnode) 21146686Sbrian{ 2126059Samurai strnodelist *ent; 2136059Samurai 21431514Sbrian ent = emalloc(sizeof *ent + strlen(s)); 21536285Sbrian ent->node = fnode; 2166059Samurai strcpy(ent->s, s); 21736285Sbrian ent->next = *listp; 2186059Samurai *listp = ent; 2196059Samurai} 2206059Samurai 2216059Samurai/* 22231514Sbrian * below are the functions that deal with creating the lists 2236059Samurai * from the filename's given dependencies and provisions 22454912Sbrian * in each of these files. no ordering or checking is done here. 2256059Samurai */ 22654912Sbrian 2276059Samurai/* 2286059Samurai * we have a new filename, create a new filenode structure. 2296059Samurai * fill in the bits, and put it in the filenode linked list 2306059Samurai */ 2316059Samuraistatic filenode * 23236285Sbrianfilenode_new(char *filename) 2336059Samurai{ 23436285Sbrian filenode *temp; 23536285Sbrian 2366059Samurai temp = emalloc(sizeof(*temp)); 23728679Sbrian memset(temp, 0, sizeof(*temp)); 23844650Sbrian temp->filename = estrdup(filename); 23944650Sbrian temp->req_list = NULL; 24054912Sbrian temp->prov_list = NULL; 24154912Sbrian temp->keyword_list = NULL; 24231514Sbrian temp->in_progress = RESET; 2436059Samurai /* 2446059Samurai * link the filenode into the list of filenodes. 2456059Samurai * note that the double linking means we can delete a 24644792Sbrian * filenode without searching for where it belongs. 24744792Sbrian */ 24844792Sbrian temp->next = fn_head->next; 24954912Sbrian if (temp->next != NULL) 25054912Sbrian temp->next->last = temp; 25144792Sbrian temp->last = fn_head; 2526059Samurai fn_head->next = temp; 25336285Sbrian return (temp); 25436285Sbrian} 2556059Samurai 2566059Samurai/* 2576059Samurai * add a requirement to a filenode. 25828679Sbrian */ 2596059Samuraistatic void 26054912Sbrianadd_require(filenode *fnode, char *s) 2616059Samurai{ 26254912Sbrian Hash_Entry *entry; 26354912Sbrian f_reqnode *rnode; 2646059Samurai int new; 26531514Sbrian 26631514Sbrian entry = Hash_CreateEntry(provide_hash, s, &new); 26754912Sbrian if (new) 26854912Sbrian Hash_SetValue(entry, NULL); 2696059Samurai rnode = emalloc(sizeof(*rnode)); 27054912Sbrian rnode->entry = entry; 27154912Sbrian rnode->next = fnode->req_list; 27231514Sbrian fnode->req_list = rnode; 2736059Samurai} 27454912Sbrian 27531514Sbrian/* 27628679Sbrian * add a provision to a filenode. if this provision doesn't 27744792Sbrian * have a head node, create one here. 27844792Sbrian */ 27944792Sbrianstatic void 28044792Sbrianadd_provide(filenode *fnode, char *s) 28144792Sbrian{ 28244650Sbrian Hash_Entry *entry; 28354912Sbrian f_provnode *f_pnode; 2846059Samurai provnode *pnode, *head; 28554912Sbrian int new; 28631514Sbrian 2876059Samurai entry = Hash_CreateEntry(provide_hash, s, &new); 28831514Sbrian head = Hash_GetValue(entry); 28931514Sbrian 29046828Sbrian /* create a head node if necessary. */ 29131514Sbrian if (head == NULL) { 29231514Sbrian head = emalloc(sizeof(*head)); 29331514Sbrian head->head = SET; 29431514Sbrian head->in_progress = RESET; 29531514Sbrian head->fnode = NULL; 29631514Sbrian head->last = head->next = NULL; 29731514Sbrian Hash_SetValue(entry, head); 29831514Sbrian } 29931514Sbrian#if 0 30031514Sbrian /* 30136285Sbrian * Don't warn about this. We want to be able to support 30231514Sbrian * scripts that do two complex things: 30331514Sbrian * 30431514Sbrian * - Two independent scripts which both provide the 30531514Sbrian * same thing. Both scripts must be executed in 30631514Sbrian * any order to meet the barrier. An example: 30736285Sbrian * 30831514Sbrian * Script 1: 30936285Sbrian * 31036285Sbrian * PROVIDE: mail 31131514Sbrian * REQUIRE: LOGIN 31231514Sbrian * 31331514Sbrian * Script 2: 31431514Sbrian * 31531514Sbrian * PROVIDE: mail 31636285Sbrian * REQUIRE: LOGIN 31736285Sbrian * 31836285Sbrian * - Two interdependent scripts which both provide the 31936285Sbrian * same thing. Both scripts must be executed in 32036285Sbrian * graph order to meet the barrier. An example: 32136285Sbrian * 32231514Sbrian * Script 1: 32331514Sbrian * 32436285Sbrian * PROVIDE: nameservice dnscache 32531514Sbrian * REQUIRE: SERVERS 32631514Sbrian * 32736285Sbrian * Script 2: 32831514Sbrian * 32936285Sbrian * PROVIDE: nameservice nscd 33031514Sbrian * REQUIRE: dnscache 33131514Sbrian */ 33231514Sbrian else if (new == 0) { 33331514Sbrian warnx("file `%s' provides `%s'.", fnode->filename, s); 33431514Sbrian warnx("\tpreviously seen in `%s'.", 33536285Sbrian head->next->fnode->filename); 33636285Sbrian } 33731514Sbrian#endif 33836285Sbrian 33931514Sbrian pnode = emalloc(sizeof(*pnode)); 34031514Sbrian pnode->head = RESET; 34131514Sbrian pnode->in_progress = RESET; 34231514Sbrian pnode->fnode = fnode; 343 pnode->next = head->next; 344 pnode->last = head; 345 head->next = pnode; 346 if (pnode->next != NULL) 347 pnode->next->last = pnode; 348 349 f_pnode = emalloc(sizeof(*f_pnode)); 350 f_pnode->pnode = pnode; 351 f_pnode->next = fnode->prov_list; 352 fnode->prov_list = f_pnode; 353} 354 355/* 356 * put the BEFORE: lines to a list and handle them later. 357 */ 358static void 359add_before(filenode *fnode, char *s) 360{ 361 strnodelist *bf_ent; 362 363 bf_ent = emalloc(sizeof *bf_ent + strlen(s)); 364 bf_ent->node = fnode; 365 strcpy(bf_ent->s, s); 366 bf_ent->next = bl_list; 367 bl_list = bf_ent; 368} 369 370/* 371 * add a key to a filenode. 372 */ 373static void 374add_keyword(filenode *fnode, char *s) 375{ 376 377 strnode_add(&fnode->keyword_list, s, fnode); 378} 379 380/* 381 * loop over the rest of a REQUIRE line, giving each word to 382 * add_require() to do the real work. 383 */ 384static void 385parse_require(filenode *node, char *buffer) 386{ 387 char *s; 388 389 while ((s = strsep(&buffer, " \t\n")) != NULL) 390 if (*s != '\0') 391 add_require(node, s); 392} 393 394/* 395 * loop over the rest of a PROVIDE line, giving each word to 396 * add_provide() to do the real work. 397 */ 398static void 399parse_provide(filenode *node, char *buffer) 400{ 401 char *s; 402 403 while ((s = strsep(&buffer, " \t\n")) != NULL) 404 if (*s != '\0') 405 add_provide(node, s); 406} 407 408/* 409 * loop over the rest of a BEFORE line, giving each word to 410 * add_before() to do the real work. 411 */ 412static void 413parse_before(filenode *node, char *buffer) 414{ 415 char *s; 416 417 while ((s = strsep(&buffer, " \t\n")) != NULL) 418 if (*s != '\0') 419 add_before(node, s); 420} 421 422/* 423 * loop over the rest of a KEYWORD line, giving each word to 424 * add_keyword() to do the real work. 425 */ 426static void 427parse_keywords(filenode *node, char *buffer) 428{ 429 char *s; 430 431 while ((s = strsep(&buffer, " \t\n")) != NULL) 432 if (*s != '\0') 433 add_keyword(node, s); 434} 435 436/* 437 * given a file name, create a filenode for it, read in lines looking 438 * for provision and requirement lines, building the graphs as needed. 439 */ 440static void 441crunch_file(char *filename) 442{ 443 FILE *fp; 444 char *buf; 445 int require_flag, provide_flag, before_flag, keywords_flag; 446 enum { BEFORE_PARSING, PARSING, PARSING_DONE } state; 447 filenode *node; 448 char delims[3] = { '\\', '\\', '\0' }; 449 struct stat st; 450 451 if ((fp = fopen(filename, "r")) == NULL) { 452 warn("could not open %s", filename); 453 return; 454 } 455 456 if (fstat(fileno(fp), &st) == -1) { 457 warn("could not stat %s", filename); 458 fclose(fp); 459 return; 460 } 461 462 if (!S_ISREG(st.st_mode)) { 463#if 0 464 warnx("%s is not a file", filename); 465#endif 466 fclose(fp); 467 return; 468 } 469 470 node = filenode_new(filename); 471 472 /* 473 * we don't care about length, line number, don't want # for comments, 474 * and have no flags. 475 */ 476 for (state = BEFORE_PARSING; state != PARSING_DONE && 477 (buf = fparseln(fp, NULL, NULL, delims, 0)) != NULL; free(buf)) { 478 require_flag = provide_flag = before_flag = keywords_flag = 0; 479 if (strncmp(REQUIRE_STR, buf, REQUIRE_LEN) == 0) 480 require_flag = REQUIRE_LEN; 481 else if (strncmp(REQUIRES_STR, buf, REQUIRES_LEN) == 0) 482 require_flag = REQUIRES_LEN; 483 else if (strncmp(PROVIDE_STR, buf, PROVIDE_LEN) == 0) 484 provide_flag = PROVIDE_LEN; 485 else if (strncmp(PROVIDES_STR, buf, PROVIDES_LEN) == 0) 486 provide_flag = PROVIDES_LEN; 487 else if (strncmp(BEFORE_STR, buf, BEFORE_LEN) == 0) 488 before_flag = BEFORE_LEN; 489 else if (strncmp(KEYWORD_STR, buf, KEYWORD_LEN) == 0) 490 keywords_flag = KEYWORD_LEN; 491 else if (strncmp(KEYWORDS_STR, buf, KEYWORDS_LEN) == 0) 492 keywords_flag = KEYWORDS_LEN; 493 else { 494 if (state == PARSING) 495 state = PARSING_DONE; 496 continue; 497 } 498 499 state = PARSING; 500 if (require_flag) 501 parse_require(node, buf + require_flag); 502 else if (provide_flag) 503 parse_provide(node, buf + provide_flag); 504 else if (before_flag) 505 parse_before(node, buf + before_flag); 506 else if (keywords_flag) 507 parse_keywords(node, buf + keywords_flag); 508 } 509 fclose(fp); 510} 511 512static Hash_Entry * 513make_fake_provision(filenode *node) 514{ 515 Hash_Entry *entry; 516 f_provnode *f_pnode; 517 provnode *head, *pnode; 518 static int i = 0; 519 int new; 520 char buffer[30]; 521 522 do { 523 snprintf(buffer, sizeof buffer, "fake_prov_%08d", i++); 524 entry = Hash_CreateEntry(provide_hash, buffer, &new); 525 } while (new == 0); 526 head = emalloc(sizeof(*head)); 527 head->head = SET; 528 head->in_progress = RESET; 529 head->fnode = NULL; 530 head->last = head->next = NULL; 531 Hash_SetValue(entry, head); 532 533 pnode = emalloc(sizeof(*pnode)); 534 pnode->head = RESET; 535 pnode->in_progress = RESET; 536 pnode->fnode = node; 537 pnode->next = head->next; 538 pnode->last = head; 539 head->next = pnode; 540 if (pnode->next != NULL) 541 pnode->next->last = pnode; 542 543 f_pnode = emalloc(sizeof(*f_pnode)); 544 f_pnode->pnode = pnode; 545 f_pnode->next = node->prov_list; 546 node->prov_list = f_pnode; 547 548 return (entry); 549} 550 551/* 552 * go through the BEFORE list, inserting requirements into the graph(s) 553 * as required. in the before list, for each entry B, we have a file F 554 * and a string S. we create a "fake" provision (P) that F provides. 555 * for each entry in the provision list for S, add a requirement to 556 * that provisions filenode for P. 557 */ 558static void 559insert_before(void) 560{ 561 Hash_Entry *entry, *fake_prov_entry; 562 provnode *pnode; 563 f_reqnode *rnode; 564 strnodelist *bl; 565 int new; 566 567 while (bl_list != NULL) { 568 bl = bl_list->next; 569 570 fake_prov_entry = make_fake_provision(bl_list->node); 571 572 entry = Hash_CreateEntry(provide_hash, bl_list->s, &new); 573 if (new == 1) 574 warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s); 575 576 for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) { 577 if (pnode->head) 578 continue; 579 580 rnode = emalloc(sizeof(*rnode)); 581 rnode->entry = fake_prov_entry; 582 rnode->next = pnode->fnode->req_list; 583 pnode->fnode->req_list = rnode; 584 } 585 586 free(bl_list); 587 bl_list = bl; 588 } 589} 590 591/* 592 * loop over all the files calling crunch_file() on them to do the 593 * real work. after we have built all the nodes, insert the BEFORE: 594 * lines into graph(s). 595 */ 596static void 597crunch_all_files(void) 598{ 599 int i; 600 601 for (i = 0; i < file_count; i++) 602 crunch_file(file_list[i]); 603 insert_before(); 604} 605 606/* 607 * below are the functions that traverse the graphs we have built 608 * finding out the desired ordering, printing each file in turn. 609 * if missing requirements, or cyclic graphs are detected, a 610 * warning will be issued, and we will continue on.. 611 */ 612 613/* 614 * given a requirement node (in a filename) we attempt to satisfy it. 615 * we do some sanity checking first, to ensure that we have providers, 616 * aren't already satisfied and aren't already being satisfied (ie, 617 * cyclic). if we pass all this, we loop over the provision list 618 * calling do_file() (enter recursion) for each filenode in this 619 * provision. 620 */ 621static void 622satisfy_req(f_reqnode *rnode, char *filename) 623{ 624 Hash_Entry *entry; 625 provnode *head; 626 627 entry = rnode->entry; 628 head = Hash_GetValue(entry); 629 630 if (head == NULL) { 631 warnx("requirement `%s' in file `%s' has no providers.", 632 Hash_GetKey(entry), filename); 633 exit_code = 1; 634 return; 635 } 636 637 /* return if the requirement is already satisfied. */ 638 if (head->next == NULL) 639 return; 640 641 /* 642 * if list is marked as in progress, 643 * print that there is a circular dependency on it and abort 644 */ 645 if (head->in_progress == SET) { 646 warnx("Circular dependency on provision `%s' in file `%s'.", 647 Hash_GetKey(entry), filename); 648 exit_code = 1; 649 return; 650 } 651 652 head->in_progress = SET; 653 654 /* 655 * while provision_list is not empty 656 * do_file(first_member_of(provision_list)); 657 */ 658 while (head->next != NULL) 659 do_file(head->next->fnode); 660} 661 662static int 663skip_ok(filenode *fnode) 664{ 665 strnodelist *s; 666 strnodelist *k; 667 668 for (s = skip_list; s; s = s->next) 669 for (k = fnode->keyword_list; k; k = k->next) 670 if (strcmp(k->s, s->s) == 0) 671 return (0); 672 673 return (1); 674} 675 676static int 677keep_ok(filenode *fnode) 678{ 679 strnodelist *s; 680 strnodelist *k; 681 682 for (s = keep_list; s; s = s->next) 683 for (k = fnode->keyword_list; k; k = k->next) 684 if (strcmp(k->s, s->s) == 0) 685 return (1); 686 687 /* an empty keep_list means every one */ 688 return (!keep_list); 689} 690 691/* 692 * given a filenode, we ensure we are not a cyclic graph. if this 693 * is ok, we loop over the filenodes requirements, calling satisfy_req() 694 * for each of them.. once we have done this, remove this filenode 695 * from each provision table, as we are now done. 696 * 697 * NOTE: do_file() is called recursively from several places and cannot 698 * safely free() anything related to items that may be recursed on. 699 * Circular dependencies will cause problems if we do. 700 */ 701static void 702do_file(filenode *fnode) 703{ 704 f_reqnode *r; 705 f_provnode *p, *p_tmp; 706 provnode *pnode; 707 int was_set; 708 709 DPRINTF((stderr, "do_file on %s.\n", fnode->filename)); 710 711 /* 712 * if fnode is marked as in progress, 713 * print that fnode; is circularly depended upon and abort. 714 */ 715 if (fnode->in_progress == SET) { 716 warnx("Circular dependency on file `%s'.", 717 fnode->filename); 718 was_set = exit_code = 1; 719 } else 720 was_set = 0; 721 722 /* mark fnode */ 723 fnode->in_progress = SET; 724 725 /* 726 * for each requirement of fnode -> r 727 * satisfy_req(r, filename) 728 */ 729 r = fnode->req_list; 730 while (r != NULL) { 731 satisfy_req(r, fnode->filename); 732 r = r->next; 733 } 734 fnode->req_list = NULL; 735 736 /* 737 * for each provision of fnode -> p 738 * remove fnode from provision list for p in hash table 739 */ 740 p = fnode->prov_list; 741 while (p != NULL) { 742 p_tmp = p; 743 pnode = p->pnode; 744 if (pnode->next != NULL) { 745 pnode->next->last = pnode->last; 746 } 747 if (pnode->last != NULL) { 748 pnode->last->next = pnode->next; 749 } 750 free(pnode); 751 p = p->next; 752 free(p_tmp); 753 } 754 fnode->prov_list = NULL; 755 756 /* do_it(fnode) */ 757 DPRINTF((stderr, "next do: ")); 758 759 /* if we were already in progress, don't print again */ 760 if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode)) 761 printf("%s\n", fnode->filename); 762 763 if (fnode->next != NULL) { 764 fnode->next->last = fnode->last; 765 } 766 if (fnode->last != NULL) { 767 fnode->last->next = fnode->next; 768 } 769 770 DPRINTF((stderr, "nuking %s\n", fnode->filename)); 771#if 0 772 if (was_set == 0) { 773 free(fnode->filename); 774 free(fnode); 775 } 776#endif 777} 778 779static void 780generate_ordering(void) 781{ 782 783 /* 784 * while there remain undone files{f}, 785 * pick an arbitrary f, and do_file(f) 786 * Note that the first file in the file list is perfectly 787 * arbitrary, and easy to find, so we use that. 788 */ 789 790 /* 791 * N.B.: the file nodes "self delete" after they execute, so 792 * after each iteration of the loop, the head will be pointing 793 * to something totally different. The loop ends up being 794 * executed only once for every strongly connected set of 795 * nodes. 796 */ 797 while (fn_head->next != NULL) { 798 DPRINTF((stderr, "generate on %s\n", fn_head->next->filename)); 799 do_file(fn_head->next); 800 } 801} 802