2 /* $NetBSD: rcorder.c,v 1.7 2000/08/04 07:33:55 enami Exp $ */
6 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
8 * Copyright (c) 1998, 1999 Matthew R. Green
11 * Perry E. Metzger. All rights reserved.
13 * Boris N. Lytochkin. All rights reserved.
15 * Redistribution and use in source and binary forms, with or without
16 * modification, are permitted provided that the following conditions
18 * 1. Redistributions of source code must retain the above copyright
19 * notice, this list of conditions and the following disclaimer.
20 * 2. Redistributions in binary form must reproduce the above copyright
21 * notice, this list of conditions and the following disclaimer in the
22 * documentation and/or other materials provided with the distribution.
23 * 3. All advertising materials mentioning features or use of this software
24 * must display the following acknowledgement:
25 * This product includes software developed for the NetBSD Project
26 * by Perry E. Metzger.
27 * 4. The name of the author may not be used to endorse or promote products
28 * derived from this software without specific prior written permission.
30 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
31 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
33 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
34 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
35 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
39 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42 #include <sys/types.h>
43 __FBSDID("$FreeBSD$");
62 # define DPRINTF(args) if (debug) { fflush(stdout); fprintf args; }
64 # define DPRINTF(args)
67 #define REQUIRE_STR "# REQUIRE:"
68 #define REQUIRE_LEN (sizeof(REQUIRE_STR) - 1)
69 #define REQUIRES_STR "# REQUIRES:"
70 #define REQUIRES_LEN (sizeof(REQUIRES_STR) - 1)
71 #define PROVIDE_STR "# PROVIDE:"
72 #define PROVIDE_LEN (sizeof(PROVIDE_STR) - 1)
73 #define PROVIDES_STR "# PROVIDES:"
74 #define PROVIDES_LEN (sizeof(PROVIDES_STR) - 1)
75 #define BEFORE_STR "# BEFORE:"
76 #define BEFORE_LEN (sizeof(BEFORE_STR) - 1)
77 #define KEYWORD_STR "# KEYWORD:"
78 #define KEYWORD_LEN (sizeof(KEYWORD_STR) - 1)
79 #define KEYWORDS_STR "# KEYWORDS:"
80 #define KEYWORDS_LEN (sizeof(KEYWORDS_STR) - 1)
82 #define FAKE_PROV_NAME "fake_prov_"
85 static int file_count;
86 static char **file_list;
94 static flag do_graphviz = false;
95 static flag do_parallel = false;
97 static Hash_Table provide_hash_s, *provide_hash;
99 typedef struct provnode provnode;
100 typedef struct filenode filenode;
101 typedef struct f_provnode f_provnode;
102 typedef struct f_reqnode f_reqnode;
103 typedef struct strnodelist strnodelist;
110 provnode *next, *last;
133 filenode *next, *last;
135 f_provnode *prov_list;
136 strnodelist *keyword_list;
141 static filenode fn_head_s, *fn_head, **fn_seqlist;
142 static int max_sequence = 0;
144 static strnodelist *bl_list;
145 static strnodelist *keep_list;
146 static strnodelist *skip_list;
148 static void do_file(filenode *fnode, strnodelist *);
149 static void strnode_add(strnodelist **, char *, filenode *);
150 static int skip_ok(filenode *fnode);
151 static int keep_ok(filenode *fnode);
152 static char *generate_loop_for_req(strnodelist *, provnode *, filenode *);
153 static void satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *);
154 static void crunch_file(char *);
155 static void parse_require(filenode *, char *);
156 static void parse_provide(filenode *, char *);
157 static void parse_before(filenode *, char *);
158 static void parse_keywords(filenode *, char *);
159 static filenode *filenode_new(char *);
160 static void add_require(filenode *, char *);
161 static void add_provide(filenode *, char *);
162 static void add_before(filenode *, char *);
163 static void add_keyword(filenode *, char *);
164 static void insert_before(void);
165 static Hash_Entry *make_fake_provision(filenode *);
166 static void crunch_all_files(void);
167 static void initialize(void);
168 static void generate_graphviz_header(void);
169 static void generate_graphviz_footer(void);
170 static void generate_graphviz_file_links(Hash_Entry *, filenode *);
171 static void generate_graphviz_providers(void);
172 static inline int is_fake_prov(const char *);
173 static int sequence_cmp(const void *, const void *);
174 static void generate_ordering(void);
177 main(int argc, char *argv[])
181 while ((ch = getopt(argc, argv, "dgk:ps:")) != -1)
187 warnx("debugging not compiled in, -d ignored");
194 strnode_add(&keep_list, optarg, 0);
200 strnode_add(&skip_list, optarg, 0);
203 /* XXX should crunch it? */
212 DPRINTF((stderr, "parse_args\n"));
214 DPRINTF((stderr, "initialize\n"));
215 generate_graphviz_header();
217 DPRINTF((stderr, "crunch_all_files\n"));
218 generate_graphviz_providers();
220 DPRINTF((stderr, "generate_ordering\n"));
221 generate_graphviz_footer();
227 * initialise various variables.
233 fn_head = &fn_head_s;
235 provide_hash = &provide_hash_s;
236 Hash_InitTable(provide_hash, file_count);
239 /* generic function to insert a new strnodelist element */
241 strnode_add(strnodelist **listp, char *s, filenode *fnode)
245 ent = emalloc(sizeof *ent + strlen(s));
253 * below are the functions that deal with creating the lists
254 * from the filename's given dependencies and provisions
255 * in each of these files. no ordering or checking is done here.
259 * we have a new filename, create a new filenode structure.
260 * fill in the bits, and put it in the filenode linked list
263 filenode_new(char *filename)
267 temp = emalloc(sizeof(*temp));
268 memset(temp, 0, sizeof(*temp));
269 temp->filename = estrdup(filename);
270 temp->req_list = NULL;
271 temp->prov_list = NULL;
272 temp->keyword_list = NULL;
273 temp->in_progress = RESET;
275 * link the filenode into the list of filenodes.
276 * note that the double linking means we can delete a
277 * filenode without searching for where it belongs.
279 temp->next = fn_head->next;
280 if (temp->next != NULL)
281 temp->next->last = temp;
282 temp->last = fn_head;
283 fn_head->next = temp;
288 * add a requirement to a filenode.
291 add_require(filenode *fnode, char *s)
297 entry = Hash_CreateEntry(provide_hash, s, &new);
299 Hash_SetValue(entry, NULL);
300 rnode = emalloc(sizeof(*rnode));
301 rnode->entry = entry;
302 rnode->next = fnode->req_list;
303 fnode->req_list = rnode;
307 * add a provision to a filenode. if this provision doesn't
308 * have a head node, create one here.
311 add_provide(filenode *fnode, char *s)
315 provnode *pnode, *head;
318 entry = Hash_CreateEntry(provide_hash, s, &new);
319 head = Hash_GetValue(entry);
321 /* create a head node if necessary. */
323 head = emalloc(sizeof(*head));
325 head->in_progress = RESET;
328 head->last = head->next = NULL;
329 Hash_SetValue(entry, head);
333 * Don't warn about this. We want to be able to support
334 * scripts that do two complex things:
336 * - Two independent scripts which both provide the
337 * same thing. Both scripts must be executed in
338 * any order to meet the barrier. An example:
350 * - Two interdependent scripts which both provide the
351 * same thing. Both scripts must be executed in
352 * graph order to meet the barrier. An example:
356 * PROVIDE: nameservice dnscache
361 * PROVIDE: nameservice nscd
365 warnx("file `%s' provides `%s'.", fnode->filename, s);
366 warnx("\tpreviously seen in `%s'.",
367 head->next->fnode->filename);
371 pnode = emalloc(sizeof(*pnode));
373 pnode->in_progress = RESET;
374 pnode->fnode = fnode;
375 pnode->next = head->next;
378 if (pnode->next != NULL)
379 pnode->next->last = pnode;
381 f_pnode = emalloc(sizeof(*f_pnode));
382 f_pnode->pnode = pnode;
383 f_pnode->entry = entry;
384 f_pnode->next = fnode->prov_list;
385 fnode->prov_list = f_pnode;
389 * put the BEFORE: lines to a list and handle them later.
392 add_before(filenode *fnode, char *s)
396 bf_ent = emalloc(sizeof *bf_ent + strlen(s));
397 bf_ent->node = fnode;
398 strcpy(bf_ent->s, s);
399 bf_ent->next = bl_list;
404 * add a key to a filenode.
407 add_keyword(filenode *fnode, char *s)
410 strnode_add(&fnode->keyword_list, s, fnode);
414 * loop over the rest of a REQUIRE line, giving each word to
415 * add_require() to do the real work.
418 parse_require(filenode *node, char *buffer)
422 while ((s = strsep(&buffer, " \t\n")) != NULL)
424 add_require(node, s);
428 * loop over the rest of a PROVIDE line, giving each word to
429 * add_provide() to do the real work.
432 parse_provide(filenode *node, char *buffer)
436 while ((s = strsep(&buffer, " \t\n")) != NULL)
438 add_provide(node, s);
442 * loop over the rest of a BEFORE line, giving each word to
443 * add_before() to do the real work.
446 parse_before(filenode *node, char *buffer)
450 while ((s = strsep(&buffer, " \t\n")) != NULL)
456 * loop over the rest of a KEYWORD line, giving each word to
457 * add_keyword() to do the real work.
460 parse_keywords(filenode *node, char *buffer)
464 while ((s = strsep(&buffer, " \t\n")) != NULL)
466 add_keyword(node, s);
470 * given a file name, create a filenode for it, read in lines looking
471 * for provision and requirement lines, building the graphs as needed.
474 crunch_file(char *filename)
478 int require_flag, provide_flag, before_flag, keywords_flag;
479 enum { BEFORE_PARSING, PARSING, PARSING_DONE } state;
481 char delims[3] = { '\\', '\\', '\0' };
484 if ((fp = fopen(filename, "r")) == NULL) {
485 warn("could not open %s", filename);
489 if (fstat(fileno(fp), &st) == -1) {
490 warn("could not stat %s", filename);
495 if (!S_ISREG(st.st_mode)) {
497 warnx("%s is not a file", filename);
503 node = filenode_new(filename);
506 * we don't care about length, line number, don't want # for comments,
509 for (state = BEFORE_PARSING; state != PARSING_DONE &&
510 (buf = fparseln(fp, NULL, NULL, delims, 0)) != NULL; free(buf)) {
511 require_flag = provide_flag = before_flag = keywords_flag = 0;
512 if (strncmp(REQUIRE_STR, buf, REQUIRE_LEN) == 0)
513 require_flag = REQUIRE_LEN;
514 else if (strncmp(REQUIRES_STR, buf, REQUIRES_LEN) == 0)
515 require_flag = REQUIRES_LEN;
516 else if (strncmp(PROVIDE_STR, buf, PROVIDE_LEN) == 0)
517 provide_flag = PROVIDE_LEN;
518 else if (strncmp(PROVIDES_STR, buf, PROVIDES_LEN) == 0)
519 provide_flag = PROVIDES_LEN;
520 else if (strncmp(BEFORE_STR, buf, BEFORE_LEN) == 0)
521 before_flag = BEFORE_LEN;
522 else if (strncmp(KEYWORD_STR, buf, KEYWORD_LEN) == 0)
523 keywords_flag = KEYWORD_LEN;
524 else if (strncmp(KEYWORDS_STR, buf, KEYWORDS_LEN) == 0)
525 keywords_flag = KEYWORDS_LEN;
527 if (state == PARSING)
528 state = PARSING_DONE;
534 parse_require(node, buf + require_flag);
535 else if (provide_flag)
536 parse_provide(node, buf + provide_flag);
537 else if (before_flag)
538 parse_before(node, buf + before_flag);
539 else if (keywords_flag)
540 parse_keywords(node, buf + keywords_flag);
546 make_fake_provision(filenode *node)
550 provnode *head, *pnode;
556 snprintf(buffer, sizeof buffer, FAKE_PROV_NAME "%08d", i++);
557 entry = Hash_CreateEntry(provide_hash, buffer, &new);
559 head = emalloc(sizeof(*head));
561 head->in_progress = RESET;
563 head->last = head->next = NULL;
564 Hash_SetValue(entry, head);
566 pnode = emalloc(sizeof(*pnode));
568 pnode->in_progress = RESET;
570 pnode->next = head->next;
573 if (pnode->next != NULL)
574 pnode->next->last = pnode;
576 f_pnode = emalloc(sizeof(*f_pnode));
577 f_pnode->entry = entry;
578 f_pnode->pnode = pnode;
579 f_pnode->next = node->prov_list;
580 node->prov_list = f_pnode;
586 * go through the BEFORE list, inserting requirements into the graph(s)
587 * as required. in the before list, for each entry B, we have a file F
588 * and a string S. we create a "fake" provision (P) that F provides.
589 * for each entry in the provision list for S, add a requirement to
590 * that provisions filenode for P.
595 Hash_Entry *entry, *fake_prov_entry;
601 while (bl_list != NULL) {
604 fake_prov_entry = make_fake_provision(bl_list->node);
606 entry = Hash_CreateEntry(provide_hash, bl_list->s, &new);
608 warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s);
610 if (new == 1 && do_graphviz == true)
611 generate_graphviz_file_links(
612 Hash_FindEntry(provide_hash, bl_list->s),
615 for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) {
619 rnode = emalloc(sizeof(*rnode));
620 rnode->entry = fake_prov_entry;
621 rnode->next = pnode->fnode->req_list;
622 pnode->fnode->req_list = rnode;
631 * loop over all the files calling crunch_file() on them to do the
632 * real work. after we have built all the nodes, insert the BEFORE:
633 * lines into graph(s).
636 crunch_all_files(void)
640 for (i = 0; i < file_count; i++)
641 crunch_file(file_list[i]);
646 is_fake_prov(const char *name)
649 return (name == strstr(name, FAKE_PROV_NAME));
652 /* loop though provide list of vnode drawing all non-fake dependencies */
654 generate_graphviz_file_links(Hash_Entry *entry, filenode *fnode)
656 char *dep_name, *fname;
658 f_provnode *fpnode, *rfpnode;
661 dep_name = Hash_GetKey(entry);
662 if (is_fake_prov(dep_name))
664 head = Hash_GetValue(entry);
666 for (fpnode = fnode->prov_list; fpnode && fpnode->entry;
667 fpnode = fpnode->next) {
668 fname = Hash_GetKey(fpnode->entry);
669 if (is_fake_prov(fname))
674 dep_name = Hash_GetKey(rfpnode->entry);
676 dep_name = Hash_GetKey(entry);
678 if (!is_fake_prov(dep_name)) {
679 printf("\"%s\" -> \"%s\" [%s%s];\n",
682 (is_before ? "style=dashed" : "style=solid"),
685 (head->next && head->in_progress == SET)) ?
686 ", color=red, penwidth=4" : ""));
690 /* dependency is solved already */
691 if (head == NULL || head->next == NULL)
695 rfpnode = head->next->fnode->prov_list;
697 rfpnode = rfpnode->next;
703 * Walk the stack, find the looping point and generate traceback.
704 * NULL is returned on failure, otherwize pointer to a buffer holding
705 * text representation is returned, caller must run free(3) for the
709 generate_loop_for_req(strnodelist *stack_tail, provnode *head,
713 strnodelist *stack_ptr, *loop_entry;
714 char *buf, **revstack;
719 /* fast forward stack to the component that is required now */
720 for (pnode = head->next; pnode; pnode = pnode->next) {
724 for (stack_ptr = stack_tail; stack_ptr;
725 stack_ptr = stack_ptr->next) {
727 if (stack_ptr->node == pnode->fnode) {
728 loop_entry = stack_ptr;
734 if (loop_entry == NULL)
737 stack_depth += 2; /* fnode + loop_entry */
738 revstack = emalloc(sizeof(char *) * stack_depth);
739 bzero(revstack, (sizeof(char *) * stack_depth));
741 /* reverse stack and estimate buffer size to allocate */
742 bufsize = 1; /* tralining \0 */
744 revstack[stack_depth - 1] = loop_entry->node->filename;
745 bufsize += strlen(revstack[stack_depth - 1]);
747 revstack[stack_depth - 2] = fnode->filename;
748 bufsize += strlen(revstack[stack_depth - 2]);
749 fnode->issues_count++;
751 stack_ptr = stack_tail;
752 for (i = stack_depth - 3; i >= 0; i--) {
753 revstack[i] = stack_ptr->node->filename;
754 stack_ptr->node->issues_count++;
755 stack_ptr = stack_ptr->next;
756 bufsize += strlen(revstack[i]);
758 bufsize += strlen(" -> ") * (stack_depth - 1);
760 buf = emalloc(bufsize);
763 for (i = 0; i < stack_depth; i++) {
764 strlcat(buf, revstack[i], bufsize);
765 if (i < stack_depth - 1)
766 strlcat(buf, " -> ", bufsize);
773 * below are the functions that traverse the graphs we have built
774 * finding out the desired ordering, printing each file in turn.
775 * if missing requirements, or cyclic graphs are detected, a
776 * warning will be issued, and we will continue on..
780 * given a requirement node (in a filename) we attempt to satisfy it.
781 * we do some sanity checking first, to ensure that we have providers,
782 * aren't already satisfied and aren't already being satisfied (ie,
783 * cyclic). if we pass all this, we loop over the provision list
784 * calling do_file() (enter recursion) for each filenode in this
788 satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *stack_ptr)
792 strnodelist stack_item;
795 entry = rnode->entry;
796 head = Hash_GetValue(entry);
798 if (do_graphviz == true)
799 generate_graphviz_file_links(entry, fnode);
802 warnx("requirement `%s' in file `%s' has no providers.",
803 Hash_GetKey(entry), fnode->filename);
808 /* return if the requirement is already satisfied. */
809 if (head->next == NULL)
813 * if list is marked as in progress,
814 * print that there is a circular dependency on it and abort
816 if (head->in_progress == SET) {
818 buf = generate_loop_for_req(stack_ptr, head,
822 warnx("Circular dependency on provision `%s' in "
823 "file `%s' (tracing has failed).",
824 Hash_GetKey(entry), fnode->filename);
828 warnx("Circular dependency on provision `%s': %s.",
829 Hash_GetKey(entry), buf);
834 head->in_progress = SET;
836 stack_item.next = stack_ptr;
837 stack_item.node = fnode;
840 * while provision_list is not empty
841 * do_file(first_member_of(provision_list));
843 while (head->next != NULL)
844 do_file(head->next->fnode, &stack_item);
848 skip_ok(filenode *fnode)
853 for (s = skip_list; s; s = s->next)
854 for (k = fnode->keyword_list; k; k = k->next)
855 if (strcmp(k->s, s->s) == 0)
862 keep_ok(filenode *fnode)
867 for (s = keep_list; s; s = s->next)
868 for (k = fnode->keyword_list; k; k = k->next)
869 if (strcmp(k->s, s->s) == 0)
872 /* an empty keep_list means every one */
877 * given a filenode, we ensure we are not a cyclic graph. if this
878 * is ok, we loop over the filenodes requirements, calling satisfy_req()
879 * for each of them.. once we have done this, remove this filenode
880 * from each provision table, as we are now done.
882 * NOTE: do_file() is called recursively from several places and cannot
883 * safely free() anything related to items that may be recursed on.
884 * Circular dependencies will cause problems if we do.
887 do_file(filenode *fnode, strnodelist *stack_ptr)
890 f_provnode *p, *p_tmp;
891 provnode *pnode, *head;
895 DPRINTF((stderr, "do_file on %s.\n", fnode->filename));
898 * if fnode is marked as in progress,
899 * print that fnode; is circularly depended upon and abort.
901 if (fnode->in_progress == SET) {
902 warnx("Circular dependency on file `%s'.",
904 was_set = exit_code = 1;
909 fnode->in_progress = SET;
912 * for each requirement of fnode -> r
913 * satisfy_req(r, filename)
918 satisfy_req(r, fnode, stack_ptr);
919 /* find sequence number where all requirements are satisfied */
920 head = Hash_GetValue(r->entry);
921 if (head && head->sequence > fnode->sequence)
922 fnode->sequence = head->sequence;
925 fnode->req_list = NULL;
928 /* if we've seen issues with this file - put it to the tail */
929 if (fnode->issues_count)
930 fnode->sequence = max_sequence + 1;
932 if (max_sequence < fnode->sequence)
933 max_sequence = fnode->sequence;
936 * for each provision of fnode -> p
937 * remove fnode from provision list for p in hash table
939 p = fnode->prov_list;
941 /* mark all troublemakers on graphviz */
942 if (do_graphviz == true && fnode->issues_count) {
943 dep_name = Hash_GetKey(p->entry);
944 if (!is_fake_prov(dep_name))
945 printf("\"%s\" [ color=red, penwidth=4 ];\n",
949 /* update sequence when provided requirements are satisfied */
950 head = Hash_GetValue(p->entry);
951 if (head->sequence < fnode->sequence)
952 head->sequence = fnode->sequence;
956 if (pnode->next != NULL) {
957 pnode->next->last = pnode->last;
959 if (pnode->last != NULL) {
960 pnode->last->next = pnode->next;
966 fnode->prov_list = NULL;
969 DPRINTF((stderr, "next do: "));
971 /* if we were already in progress, don't print again */
972 if (do_graphviz != true && was_set == 0 && skip_ok(fnode) &&
978 if (fnode->next != NULL) {
979 fnode->next->last = fnode->last;
981 if (fnode->last != NULL) {
982 fnode->last->next = fnode->next;
985 if (fnode->issues_count)
986 warnx("`%s' was seen in circular dependencies for %d times.",
987 fnode->filename, fnode->issues_count);
989 DPRINTF((stderr, "nuking %s\n", fnode->filename));
993 generate_graphviz_header(void)
996 if (do_graphviz != true)
999 printf("digraph rcorder {\n"
1001 "node [style=rounded, shape=record];\n"
1002 "graph [overlap = false];\n");
1006 generate_graphviz_footer(void)
1009 if (do_graphviz == true)
1014 generate_graphviz_providers(void)
1017 Hash_Search psearch;
1018 provnode *head, *pnode;
1021 if (do_graphviz != true)
1024 entry = Hash_EnumFirst(provide_hash, &psearch);
1029 dep_name = Hash_GetKey(entry);
1030 if (is_fake_prov(dep_name))
1032 head = Hash_GetValue(entry);
1033 /* no providers for this requirement */
1034 if (head == NULL || head->next == NULL) {
1035 printf("\"%s\" [label=\"{ %s | ENOENT }\", "
1036 "style=\"rounded,filled\", color=red];\n",
1037 dep_name, dep_name);
1040 /* one PROVIDE word for one file that matches */
1041 if (head->next->next == NULL &&
1043 basename(head->next->fnode->filename)) == 0) {
1046 printf("\"%s\" [label=\"{ %s | ", dep_name, dep_name);
1047 for (pnode = head->next; pnode; pnode = pnode->next)
1048 printf("%s\\n", basename(pnode->fnode->filename));
1051 } while (NULL != (entry = Hash_EnumNext(&psearch)));
1055 sequence_cmp(const void *a, const void *b)
1057 const filenode *fna = *((const filenode * const *)a);
1058 const filenode *fnb = *((const filenode * const *)b);
1061 /* push phantom files to the end */
1062 if (fna == NULL || fnb == NULL)
1063 return ((fna < fnb) - (fna > fnb));
1065 left = fna->sequence;
1066 right = fnb->sequence;
1068 return ((left > right) - (left < right));
1072 generate_ordering(void)
1074 filenode **seqlist, **psl;
1077 /* Prepare order buffer, use an additional one as a list terminator */
1078 seqlist = emalloc(sizeof(filenode *) * (file_count + 1));
1079 bzero(seqlist, sizeof(filenode *) * (file_count + 1));
1080 fn_seqlist = seqlist;
1083 * while there remain undone files{f},
1084 * pick an arbitrary f, and do_file(f)
1085 * Note that the first file in the file list is perfectly
1086 * arbitrary, and easy to find, so we use that.
1090 * N.B.: the file nodes "self delete" after they execute, so
1091 * after each iteration of the loop, the head will be pointing
1092 * to something totally different. The loop ends up being
1093 * executed only once for every strongly connected set of
1096 while (fn_head->next != NULL) {
1097 DPRINTF((stderr, "generate on %s\n", fn_head->next->filename));
1098 do_file(fn_head->next, NULL);
1101 /* Sort filenode list based on sequence */
1102 qsort(seqlist, file_count, sizeof(filenode *), sequence_cmp);
1104 for (psl = seqlist; *psl; psl++) {
1106 (last_seq == 0 ? "" :
1107 (do_parallel != true || last_seq != (*psl)->sequence) ?
1110 last_seq = (*psl)->sequence;
1111 free((*psl)->filename);