diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/comp.c | 113 | ||||
-rw-r--r-- | src/depmap.c | 40 | ||||
-rw-r--r-- | src/pies.h | 6 |
3 files changed, 100 insertions, 59 deletions
@@ -126,5 +126,5 @@ component_lookup_index (const char *tag) for (i = 0; i < comp_count; i++) - if (comp_array[i] && strcmp (comp_array[i]->tag, tag) == 0) + if (strcmp (comp_array[i]->tag, tag) == 0) return i; return -1; @@ -389,22 +389,52 @@ list_str_cmp (const void *a, const void *b) } +/* Report cyclic dependency starting at IDX. Mark each element with + CF_REMOVE for subsequent removal. + DP is a transitive closure of depmap. +*/ static void -component_log_dep (size_t idx) +report_cyclic_dependency (pies_depmap_t dp, size_t idx) { - pies_depmap_pos_t pos; - size_t n; + size_t i; - logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[idx]->tag); - for (n = depmap_first (depmap, depmap_col, idx, &pos); - n != (size_t)-1; - n = depmap_next (depmap, pos)) + i = idx; + do { - logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[n]->tag); + size_t n; + pies_depmap_pos_t pos; + + logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[i]->tag); + comp_array[i]->flags |= CF_REMOVE; + for (n = depmap_first (depmap, depmap_col, i, &pos); + n != (size_t)-1; + n = depmap_next (depmap, pos)) + { + if (n == i) + continue; + if (depmap_isset (dp, n, i) && depmap_isset (dp, n, n)) + break; + } + depmap_end (pos); + + if (n == (size_t)-1) + break; + i = n; } - depmap_end (pos); + while (i != idx); logmsg_printf (LOG_NOTICE, "%s\n", comp_array[idx]->tag); } void +comp_array_remove (size_t i) +{ + struct component *comp = comp_array[i]; + if (i < comp_count - 1) + memmove (&comp_array[i], &comp_array[i+1], + (comp_count - i - 1) * sizeof comp_array[0]); + component_free (comp); + comp_count--; +} + +void component_build_depmap (void) { @@ -414,5 +444,5 @@ component_build_depmap (void) free (depmap); depmap = depmap_alloc (comp_count); - for (i = 0; i < comp_count; i++) + for (i = 0; i < comp_count; ) { struct component *comp = comp_array[i]; @@ -430,8 +460,6 @@ component_build_depmap (void) "which is not declared"), comp->tag, tag); - component_free (comp); - comp_array[i] = NULL; - depmap_clear_all (depmap, depmap_row, i); - depmap_clear_all (depmap, depmap_col, i); + comp_array_remove (i); + depmap_remove (depmap, i); continue; } @@ -453,4 +481,6 @@ component_build_depmap (void) depmap_set (depmap, tgt, i); } + + i++; } @@ -458,15 +488,21 @@ component_build_depmap (void) depmap_tc (dp); for (i = 0; i < comp_count; i++) - if (depmap_isset (dp, i, i)) + if (!(comp_array[i]->flags & CF_REMOVE) && depmap_isset (dp, i, i)) { logmsg (LOG_ERR, _("component %s depends on itself"), comp_array[i]->tag); - component_log_dep (i); - component_free (comp_array[i]); - comp_array[i] = NULL; - depmap_clear_all (depmap, depmap_row, i); - depmap_clear_all (depmap, depmap_col, i); - continue; + report_cyclic_dependency (dp, i); + } + + + for (i = 0; i < comp_count;) + if (comp_array[i]->flags & CF_REMOVE) + { + comp_array_remove (i); + depmap_remove (depmap, i); } + else + i++; + free (dp); } @@ -749,28 +785,19 @@ component_get (size_t n) void -components_dump_depmap (void) +depmap_dump (pies_depmap_t dpm) { - size_t i, j, k; + size_t i, j; printf ("%s:\n", _("Dependency map")); printf (" "); - for (i = k = 0; i < comp_count; i++) - if (comp_array[i]) - { - printf (" %2lu", (unsigned long)k); - k++; - } + for (i = 0; i < comp_count; i++) + printf (" %2lu", (unsigned long)i); printf ("\n"); - for (i = k = 0; i < comp_count; i++) + for (i = 0; i < comp_count; i++) { - if (comp_array[i]) - { - printf ("%2lu ", (unsigned long)k); - for (j = 0; j < comp_count; j++) - if (comp_array[j]) - printf (" %c ", depmap_isset (depmap, i, j) ? 'X' : ' '); - printf ("\n"); - k++; - } + printf ("%2lu", (unsigned long)i); + for (j = 0; j < comp_count; j++) + printf (" %c", depmap_isset (dpm, i, j) ? 'X' : ' '); + printf ("\n"); } printf ("\n%s:\n", _("Legend")); @@ -780,4 +807,10 @@ components_dump_depmap (void) void +components_dump_depmap (void) +{ + depmap_dump (depmap); +} + +void component_trace (size_t idx, enum pies_depmap_direction dir) { diff --git a/src/depmap.c b/src/depmap.c index 3ea5722..cb50548 100644 --- a/src/depmap.c +++ b/src/depmap.c @@ -82,7 +82,7 @@ TC (unsigned *R, int n) struct pies_depmap { - size_t nrows; - size_t rowlen; - unsigned r[1]; + size_t nrows; /* Number of rows (== number of mapped elements) */ + size_t rowlen; /* Length of a row in words */ + unsigned r[1]; /* Data rows */ }; @@ -98,9 +98,16 @@ depmap_alloc (size_t count) } +/* Return size of a depmap row in bytes */ +static inline size_t +depmap_row_size (pies_depmap_t dpm) +{ + return dpm->rowlen * sizeof (unsigned); +} + pies_depmap_t depmap_copy (pies_depmap_t dpm) { pies_depmap_t copy = depmap_alloc (dpm->nrows); - memcpy (copy->r, dpm->r, dpm->nrows * dpm->rowlen * sizeof (unsigned)); + memcpy (copy->r, dpm->r, dpm->nrows * depmap_row_size (dpm)); return copy; } @@ -175,20 +182,21 @@ depmap_end (pies_depmap_pos_t pos) } +/* Remove nth row and column from the map */ void -depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir, - size_t coord) +depmap_remove (pies_depmap_t dmap, size_t n) { - size_t i; - - switch (dir) + if (n < dmap->nrows - 1) { - case depmap_row: - for (i = 0; i < dmap->nrows; i++) - depmap_clear (dmap, coord, i); - break; - - case depmap_col: + size_t i, j; + + /* Remove nth row */ + memmove (depmap_rowptr (dmap, n), depmap_rowptr (dmap, n + 1), + (dmap->nrows - n - 1) * depmap_row_size (dmap)); + /* Renumber all columns j >= n: j = j - 1 */ for (i = 0; i < dmap->nrows; i++) - depmap_clear (dmap, i, coord); + for (j = n; j < dmap->nrows - 1; j++) + (depmap_isset (dmap, i, j + 1) ? depmap_set : depmap_clear) + (dmap, i, j); } + dmap->nrows--; } @@ -200,4 +200,6 @@ enum pies_comp_mode #define CF_NULLINPUT 0x200 /* Provide null input stream */ +#define CF_REMOVE 0x400 /* Marked for removal */ + #define ISCF_TCPMUX(f) ((f) & (CF_TCPMUX | CF_TCPMUXPLUS)) @@ -375,7 +377,5 @@ void depmap_set (pies_depmap_t dmap, size_t row, size_t col); int depmap_isset (pies_depmap_t dmap, size_t row, size_t col); void depmap_clear (pies_depmap_t dmap, size_t row, size_t col); - -void depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir, - size_t coord); +void depmap_remove (pies_depmap_t dmap, size_t n); void depmap_tc (pies_depmap_t dmap); |