1#include "ninqu.h"
 2
 3#include <stdio.h>
 4#include <stdlib.h>
 5
 6/* kahn topo sort, one ready level at a time so each level
 7 * runs in parallel. failures are reported but do not stop the
 8 * batch, so one broken file does not block the rest */
 9void
10schedule_and_run(void)
11{
12  int  *indeg      = ecalloc((size_t)ninsts, sizeof *indeg);
13  int **dependents = emalloc((size_t)ninsts * sizeof *dependents);
14  int  *ndep       = ecalloc((size_t)ninsts, sizeof *ndep);
15  int  *capdep     = ecalloc((size_t)ninsts, sizeof *capdep);
16  int  *level      = emalloc((size_t)ninsts * sizeof *level);
17  int   levn = 0, done_count = 0;
18  int   i, j;
19
20  for (i = 0; i < ninsts; i++) {
21    indeg[i]      = insts[i].n_dep;
22    dependents[i] = NULL;
23  }
24  for (i = 0; i < ninsts; i++) {
25    for (j = 0; j < insts[i].n_dep; j++) {
26      int d = insts[i].dep_inst[j];
27      if (ndep[d] >= capdep[d]) {
28        capdep[d]     = capdep[d] ? capdep[d] * 2 : 4;
29        dependents[d] = erealloc(dependents[d], (size_t)capdep[d] * sizeof *dependents[d]);
30      }
31      dependents[d][ndep[d]++] = i;
32    }
33  }
34  for (i = 0; i < ninsts; i++)
35    if (indeg[i] == 0)
36      level[levn++] = i;
37
38  while (levn > 0) {
39    int *next_level = emalloc((size_t)ninsts * sizeof *next_level);
40    int  nextn      = 0;
41
42    if (summary_mode) {
43      for (i = 0; i < levn; i++) {
44        struct Inst *inst = &insts[level[i]];
45        int          will = inst_stale(inst);
46        int          d;
47        for (d = 0; d < inst->n_dep && !will; d++)
48          if (insts[inst->dep_inst[d]].will_build)
49            will = 1;
50        inst->will_build = will;
51        printf(
52            "%-4s %-12s %s\n",
53            will ? "BUILD" : "OK",
54            rules[inst->rule_idx].name,
55            inst->out[0] ? inst->out : "(phony)"
56        );
57        if (rules[inst->rule_idx].description[0])
58          printf("       # %s\n", rules[inst->rule_idx].description);
59        if (will) {
60          char *cmd = sl_join(&inst->cmd.argv);
61          printf("       cmd: %s\n", cmd);
62          free(cmd);
63        }
64      }
65    } else {
66      run_batch(level, levn);
67    }
68
69    done_count += levn;
70    for (i = 0; i < levn; i++) {
71      int u = level[i];
72      for (j = 0; j < ndep[u]; j++) {
73        int v = dependents[u][j];
74        if (--indeg[v] == 0)
75          next_level[nextn++] = v;
76      }
77    }
78    free(level);
79    level = next_level;
80    levn  = nextn;
81  }
82
83  if (done_count < ninsts)
84    eprintf("manifest: dependency cycle among %d instances\n", ninsts - done_count);
85
86  free(level);
87  free(indeg);
88  for (i = 0; i < ninsts; i++)
89    free(dependents[i]);
90  free(dependents);
91  free(ndep);
92  free(capdep);
93}