aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/comp.c113
-rw-r--r--src/depmap.c40
-rw-r--r--src/pies.h6
3 files changed, 100 insertions, 59 deletions
diff --git a/src/comp.c b/src/comp.c
index 17832ad..fcd0a14 100644
--- a/src/comp.c
+++ b/src/comp.c
@@ -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--;
}
diff --git a/src/pies.h b/src/pies.h
index 70d972a..e7e5d71 100644
--- a/src/pies.h
+++ b/src/pies.h
@@ -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);

Return to:

Send suggestions and report system problems to the System administrator.