Changeset View
Changeset View
Standalone View
Standalone View
sbin/rcorder/rcorder.c
Show First 20 Lines • Show All 71 Lines • ▼ Show 20 Lines | |||||
#define BEFORE_LEN (sizeof(BEFORE_STR) - 1) | #define BEFORE_LEN (sizeof(BEFORE_STR) - 1) | ||||
#define KEYWORD_STR "# KEYWORD:" | #define KEYWORD_STR "# KEYWORD:" | ||||
#define KEYWORD_LEN (sizeof(KEYWORD_STR) - 1) | #define KEYWORD_LEN (sizeof(KEYWORD_STR) - 1) | ||||
#define KEYWORDS_STR "# KEYWORDS:" | #define KEYWORDS_STR "# KEYWORDS:" | ||||
#define KEYWORDS_LEN (sizeof(KEYWORDS_STR) - 1) | #define KEYWORDS_LEN (sizeof(KEYWORDS_STR) - 1) | ||||
static int exit_code; | static int exit_code; | ||||
static int file_count; | static int file_count; | ||||
static int generation; | |||||
static char **file_list; | static char **file_list; | ||||
typedef int bool; | typedef int bool; | ||||
#define TRUE 1 | #define TRUE 1 | ||||
#define FALSE 0 | #define FALSE 0 | ||||
typedef bool flag; | typedef bool flag; | ||||
#define SET TRUE | #define SET TRUE | ||||
#define RESET FALSE | #define RESET FALSE | ||||
Show All 31 Lines | |||||
struct filenode { | struct filenode { | ||||
char *filename; | char *filename; | ||||
flag in_progress; | flag in_progress; | ||||
filenode *next, *last; | filenode *next, *last; | ||||
f_reqnode *req_list; | f_reqnode *req_list; | ||||
f_provnode *prov_list; | f_provnode *prov_list; | ||||
strnodelist *keyword_list; | strnodelist *keyword_list; | ||||
int generation; | |||||
}; | }; | ||||
static filenode fn_head_s, *fn_head; | static filenode fn_head_s, *fn_head; | ||||
static strnodelist *bl_list; | static strnodelist *bl_list; | ||||
static strnodelist *keep_list; | static strnodelist *keep_list; | ||||
static strnodelist *skip_list; | static strnodelist *skip_list; | ||||
Show All 12 Lines | |||||
static void add_provide(filenode *, char *); | static void add_provide(filenode *, char *); | ||||
static void add_before(filenode *, char *); | static void add_before(filenode *, char *); | ||||
static void add_keyword(filenode *, char *); | static void add_keyword(filenode *, char *); | ||||
static void insert_before(void); | static void insert_before(void); | ||||
static Hash_Entry *make_fake_provision(filenode *); | static Hash_Entry *make_fake_provision(filenode *); | ||||
static void crunch_all_files(void); | static void crunch_all_files(void); | ||||
static void initialize(void); | static void initialize(void); | ||||
static void generate_ordering(void); | static void generate_ordering(void); | ||||
static void generate_parallel(void); | |||||
static int parallel = 0; | |||||
int | int | ||||
main(int argc, char *argv[]) | main(int argc, char *argv[]) | ||||
{ | { | ||||
int ch; | int ch; | ||||
while ((ch = getopt(argc, argv, "dk:s:")) != -1) | while ((ch = getopt(argc, argv, "dk:ps:")) != -1) | ||||
switch (ch) { | switch (ch) { | ||||
case 'd': | case 'd': | ||||
#ifdef DEBUG | #ifdef DEBUG | ||||
debug = 1; | debug = 1; | ||||
#else | #else | ||||
warnx("debugging not compiled in, -d ignored"); | warnx("debugging not compiled in, -d ignored"); | ||||
#endif | #endif | ||||
break; | break; | ||||
case 'k': | case 'k': | ||||
strnode_add(&keep_list, optarg, 0); | strnode_add(&keep_list, optarg, 0); | ||||
break; | break; | ||||
case 'p': | |||||
parallel = 1; | |||||
break; | |||||
case 's': | case 's': | ||||
strnode_add(&skip_list, optarg, 0); | strnode_add(&skip_list, optarg, 0); | ||||
break; | break; | ||||
default: | default: | ||||
/* XXX should crunch it? */ | /* XXX should crunch it? */ | ||||
break; | break; | ||||
} | } | ||||
argc -= optind; | argc -= optind; | ||||
argv += optind; | argv += optind; | ||||
file_count = argc; | file_count = argc; | ||||
file_list = argv; | file_list = argv; | ||||
DPRINTF((stderr, "parse_args\n")); | DPRINTF((stderr, "parse_args\n")); | ||||
initialize(); | initialize(); | ||||
DPRINTF((stderr, "initialize\n")); | DPRINTF((stderr, "initialize\n")); | ||||
crunch_all_files(); | crunch_all_files(); | ||||
DPRINTF((stderr, "crunch_all_files\n")); | DPRINTF((stderr, "crunch_all_files\n")); | ||||
if (parallel) { | |||||
generate_parallel(); | |||||
} else { | |||||
generate_ordering(); | generate_ordering(); | ||||
} | |||||
DPRINTF((stderr, "generate_ordering\n")); | DPRINTF((stderr, "generate_ordering\n")); | ||||
exit(exit_code); | exit(exit_code); | ||||
} | } | ||||
/* | /* | ||||
* initialise various variables. | * initialise various variables. | ||||
*/ | */ | ||||
▲ Show 20 Lines • Show All 516 Lines • ▼ Show 20 Lines | do_file(filenode *fnode) | ||||
*/ | */ | ||||
if (fnode->in_progress == SET) { | if (fnode->in_progress == SET) { | ||||
warnx("Circular dependency on file `%s'.", | warnx("Circular dependency on file `%s'.", | ||||
fnode->filename); | fnode->filename); | ||||
was_set = exit_code = 1; | was_set = exit_code = 1; | ||||
} else | } else | ||||
was_set = 0; | was_set = 0; | ||||
if (parallel) { | |||||
/* | |||||
* Mark node as handled in the current iteration. | |||||
* When running in parallel mode, we use this mechanism | |||||
* instead of removing dependencies, because in case | |||||
* where we have "A" node and its dependency "B", we must | |||||
* make sure we don't emit "B A", but always "B\nA". | |||||
*/ | |||||
DPRINTF((stderr, "node %s done in generation %d\n", | |||||
fnode->filename, generation)); | |||||
fnode->generation = generation; | |||||
} else { | |||||
/* mark fnode */ | /* mark fnode */ | ||||
fnode->in_progress = SET; | fnode->in_progress = SET; | ||||
/* | /* | ||||
* for each requirement of fnode -> r | * for each requirement of fnode -> r | ||||
* satisfy_req(r, filename) | * satisfy_req(r, filename) | ||||
*/ | */ | ||||
r = fnode->req_list; | r = fnode->req_list; | ||||
while (r != NULL) { | while (r != NULL) { | ||||
#if 0 | |||||
imp: clean this up.
| |||||
r_tmp = r; | |||||
#endif | |||||
satisfy_req(r, fnode->filename); | satisfy_req(r, fnode->filename); | ||||
r = r->next; | r = r->next; | ||||
#if 0 | |||||
if (was_set == 0) | |||||
free(r_tmp); | |||||
#endif | |||||
} | } | ||||
fnode->req_list = NULL; | fnode->req_list = NULL; | ||||
/* | /* | ||||
* for each provision of fnode -> p | * for each provision of fnode -> p | ||||
* remove fnode from provision list for p in hash table | * remove fnode from provision list for p in hash table | ||||
*/ | */ | ||||
p = fnode->prov_list; | p = fnode->prov_list; | ||||
while (p != NULL) { | while (p != NULL) { | ||||
p_tmp = p; | p_tmp = p; | ||||
pnode = p->pnode; | pnode = p->pnode; | ||||
if (pnode->next != NULL) { | if (pnode->next != NULL) { | ||||
pnode->next->last = pnode->last; | pnode->next->last = pnode->last; | ||||
} | } | ||||
if (pnode->last != NULL) { | if (pnode->last != NULL) { | ||||
pnode->last->next = pnode->next; | pnode->last->next = pnode->next; | ||||
} | } | ||||
free(pnode); | free(pnode); | ||||
p = p->next; | p = p->next; | ||||
free(p_tmp); | free(p_tmp); | ||||
} | } | ||||
fnode->prov_list = NULL; | fnode->prov_list = NULL; | ||||
} | |||||
/* do_it(fnode) */ | /* do_it(fnode) */ | ||||
DPRINTF((stderr, "next do: ")); | DPRINTF((stderr, "next do: ")); | ||||
/* if we were already in progress, don't print again */ | /* if we were already in progress, don't print again */ | ||||
if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode)) | if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode)) | ||||
printf("%s\n", fnode->filename); | printf("%s%s", fnode->filename, parallel ? " " : "\n"); | ||||
if (fnode->next != NULL) { | if (fnode->next != NULL) { | ||||
fnode->next->last = fnode->last; | fnode->next->last = fnode->last; | ||||
} | } | ||||
if (fnode->last != NULL) { | if (fnode->last != NULL) { | ||||
fnode->last->next = fnode->next; | fnode->last->next = fnode->next; | ||||
} | } | ||||
DPRINTF((stderr, "nuking %s\n", fnode->filename)); | DPRINTF((stderr, "nuking %s\n", fnode->filename)); | ||||
#if 0 | #if 0 | ||||
if (was_set == 0) { | if (was_set == 0) { | ||||
free(fnode->filename); | free(fnode->filename); | ||||
free(fnode); | free(fnode); | ||||
} | } | ||||
impUnsubmitted Not Done Inline Actionsthis should be deleted. imp: this should be deleted.
| |||||
#endif | #endif | ||||
} | |||||
static bool | |||||
unsatisfied_req(const struct filenode *fnode) | |||||
{ | |||||
const Hash_Entry *entry; | |||||
const provnode *head; | |||||
const f_reqnode *r; | |||||
int ndeps = 0; | |||||
for (r = fnode->req_list; r != NULL; r = r->next) { | |||||
entry = r->entry; | |||||
head = Hash_GetValue(entry); | |||||
if (head == NULL) { | |||||
warnx("requirement `%s' in file `%s' has no providers.", | |||||
Hash_GetKey(entry), fnode->filename); | |||||
continue; | |||||
} | |||||
for (head = head->next; head != NULL; head = head->next) { | |||||
/* | |||||
* Ignore dependencies handled in previous runs, | |||||
* but not those handled in the current one. Increase | |||||
* current generation counter, emit newline, and go | |||||
* around. | |||||
*/ | |||||
if (head->fnode->generation != 0 && | |||||
head->fnode->generation < generation) { | |||||
DPRINTF((stderr, "%s had dependency %s handled " | |||||
"in generation %d\n", | |||||
fnode->filename, head->fnode->filename, | |||||
head->fnode->generation)); | |||||
} else { | |||||
DPRINTF((stderr, "%s has dependency %s\n", | |||||
fnode->filename, head->fnode->filename)); | |||||
//return (TRUE); | |||||
impUnsubmitted Not Done Inline Actionsummm, this comment makes no sense. imp: ummm, this comment makes no sense.
| |||||
ndeps++; | |||||
} | |||||
} | |||||
} | |||||
if (ndeps > 0) | |||||
return (TRUE); | |||||
return (FALSE); | |||||
} | |||||
static void | |||||
generate_parallel(void) | |||||
{ | |||||
static filenode *fnode, *fnode_next; | |||||
int nodes_done; | |||||
bool ignore_deps; | |||||
/* | |||||
* Iterate over nodes, printing out leaf ones. After each pass | |||||
* emit "\n" to mark dependency of the following nodes on the | |||||
* preceding ones. Continue until there are no nodes left. | |||||
*/ | |||||
ignore_deps = FALSE; | |||||
generation = 1; | |||||
do { | |||||
nodes_done = 0; | |||||
for (fnode = fn_head->next; fnode != NULL; fnode = fnode_next) { | |||||
fnode_next = fnode->next; | |||||
if (ignore_deps) { | |||||
warnx("cycle detected; ignoring dependencies " | |||||
"for %s", fnode->filename); | |||||
ignore_deps = FALSE; | |||||
} else if (unsatisfied_req(fnode)) { | |||||
DPRINTF((stderr, "%s has dependencies; " | |||||
"skipping\n", fnode->filename)); | |||||
continue; | |||||
} | |||||
nodes_done++; | |||||
do_file(fnode); | |||||
} | |||||
generation++; | |||||
if (nodes_done > 0) { | |||||
printf("\n"); | |||||
} else { | |||||
/* | |||||
* There were no leaf nodes, ie nodes with no | |||||
* dependencies. This means the graph is cyclic. | |||||
* It's hard to handle this in a sensible way; just | |||||
* ignore dependencies for the next node and try again. | |||||
*/ | |||||
ignore_deps = TRUE; | |||||
} | |||||
} while (fn_head->next != NULL); | |||||
} | } | ||||
static void | static void | ||||
generate_ordering(void) | generate_ordering(void) | ||||
{ | { | ||||
/* | /* | ||||
* while there remain undone files{f}, | * while there remain undone files{f}, | ||||
Show All 17 Lines |
clean this up.