diff options
-rw-r--r-- | src/comp.c | 113 | ||||
-rw-r--r-- | src/depmap.c | 40 | ||||
-rw-r--r-- | src/pies.h | 6 | ||||
-rw-r--r-- | tests/Makefile.am | 1 | ||||
-rw-r--r-- | tests/atlocal.in | 6 | ||||
-rw-r--r-- | tests/cyclic.at | 114 | ||||
-rw-r--r-- | tests/testsuite.at | 2 |
7 files changed, 222 insertions, 60 deletions
@@ -127,3 +127,3 @@ component_lookup_index (const char *tag) | |||
127 | for (i = 0; i < comp_count; i++) | 127 | for (i = 0; i < comp_count; i++) |
128 | if (comp_array[i] && strcmp (comp_array[i]->tag, tag) == 0) | 128 | if (strcmp (comp_array[i]->tag, tag) == 0) |
129 | return i; | 129 | return i; |
@@ -390,16 +390,35 @@ list_str_cmp (const void *a, const void *b) | |||
390 | 390 | ||
391 | /* Report cyclic dependency starting at IDX. Mark each element with | ||
392 | CF_REMOVE for subsequent removal. | ||
393 | DP is a transitive closure of depmap. | ||
394 | */ | ||
391 | static void | 395 | static void |
392 | component_log_dep (size_t idx) | 396 | report_cyclic_dependency (pies_depmap_t dp, size_t idx) |
393 | { | 397 | { |
394 | pies_depmap_pos_t pos; | 398 | size_t i; |
395 | size_t n; | ||
396 | 399 | ||
397 | logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[idx]->tag); | 400 | i = idx; |
398 | for (n = depmap_first (depmap, depmap_col, idx, &pos); | 401 | do |
399 | n != (size_t)-1; | ||
400 | n = depmap_next (depmap, pos)) | ||
401 | { | 402 | { |
402 | logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[n]->tag); | 403 | size_t n; |
404 | pies_depmap_pos_t pos; | ||
405 | |||
406 | logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[i]->tag); | ||
407 | comp_array[i]->flags |= CF_REMOVE; | ||
408 | for (n = depmap_first (depmap, depmap_col, i, &pos); | ||
409 | n != (size_t)-1; | ||
410 | n = depmap_next (depmap, pos)) | ||
411 | { | ||
412 | if (n == i) | ||
413 | continue; | ||
414 | if (depmap_isset (dp, n, i) && depmap_isset (dp, n, n)) | ||
415 | break; | ||
416 | } | ||
417 | depmap_end (pos); | ||
418 | |||
419 | if (n == (size_t)-1) | ||
420 | break; | ||
421 | i = n; | ||
403 | } | 422 | } |
404 | depmap_end (pos); | 423 | while (i != idx); |
405 | logmsg_printf (LOG_NOTICE, "%s\n", comp_array[idx]->tag); | 424 | logmsg_printf (LOG_NOTICE, "%s\n", comp_array[idx]->tag); |
@@ -408,2 +427,13 @@ component_log_dep (size_t idx) | |||
408 | void | 427 | void |
428 | comp_array_remove (size_t i) | ||
429 | { | ||
430 | struct component *comp = comp_array[i]; | ||
431 | if (i < comp_count - 1) | ||
432 | memmove (&comp_array[i], &comp_array[i+1], | ||
433 | (comp_count - i - 1) * sizeof comp_array[0]); | ||
434 | component_free (comp); | ||
435 | comp_count--; | ||
436 | } | ||
437 | |||
438 | void | ||
409 | component_build_depmap (void) | 439 | component_build_depmap (void) |
@@ -415,3 +445,3 @@ component_build_depmap (void) | |||
415 | depmap = depmap_alloc (comp_count); | 445 | depmap = depmap_alloc (comp_count); |
416 | for (i = 0; i < comp_count; i++) | 446 | for (i = 0; i < comp_count; ) |
417 | { | 447 | { |
@@ -431,6 +461,4 @@ component_build_depmap (void) | |||
431 | comp->tag, tag); | 461 | comp->tag, tag); |
432 | component_free (comp); | 462 | comp_array_remove (i); |
433 | comp_array[i] = NULL; | 463 | depmap_remove (depmap, i); |
434 | depmap_clear_all (depmap, depmap_row, i); | ||
435 | depmap_clear_all (depmap, depmap_col, i); | ||
436 | continue; | 464 | continue; |
@@ -454,2 +482,4 @@ component_build_depmap (void) | |||
454 | } | 482 | } |
483 | |||
484 | i++; | ||
455 | } | 485 | } |
@@ -459,3 +489,3 @@ component_build_depmap (void) | |||
459 | for (i = 0; i < comp_count; i++) | 489 | for (i = 0; i < comp_count; i++) |
460 | if (depmap_isset (dp, i, i)) | 490 | if (!(comp_array[i]->flags & CF_REMOVE) && depmap_isset (dp, i, i)) |
461 | { | 491 | { |
@@ -463,9 +493,15 @@ component_build_depmap (void) | |||
463 | comp_array[i]->tag); | 493 | comp_array[i]->tag); |
464 | component_log_dep (i); | 494 | report_cyclic_dependency (dp, i); |
465 | component_free (comp_array[i]); | 495 | } |
466 | comp_array[i] = NULL; | 496 | |
467 | depmap_clear_all (depmap, depmap_row, i); | 497 | |
468 | depmap_clear_all (depmap, depmap_col, i); | 498 | for (i = 0; i < comp_count;) |
469 | continue; | 499 | if (comp_array[i]->flags & CF_REMOVE) |
500 | { | ||
501 | comp_array_remove (i); | ||
502 | depmap_remove (depmap, i); | ||
470 | } | 503 | } |
504 | else | ||
505 | i++; | ||
506 | |||
471 | free (dp); | 507 | free (dp); |
@@ -750,5 +786,5 @@ component_get (size_t n) | |||
750 | void | 786 | void |
751 | components_dump_depmap (void) | 787 | depmap_dump (pies_depmap_t dpm) |
752 | { | 788 | { |
753 | size_t i, j, k; | 789 | size_t i, j; |
754 | 790 | ||
@@ -756,20 +792,11 @@ components_dump_depmap (void) | |||
756 | printf (" "); | 792 | printf (" "); |
757 | for (i = k = 0; i < comp_count; i++) | 793 | for (i = 0; i < comp_count; i++) |
758 | if (comp_array[i]) | 794 | printf (" %2lu", (unsigned long)i); |
759 | { | ||
760 | printf (" %2lu", (unsigned long)k); | ||
761 | k++; | ||
762 | } | ||
763 | printf ("\n"); | 795 | printf ("\n"); |
764 | for (i = k = 0; i < comp_count; i++) | 796 | for (i = 0; i < comp_count; i++) |
765 | { | 797 | { |
766 | if (comp_array[i]) | 798 | printf ("%2lu", (unsigned long)i); |
767 | { | 799 | for (j = 0; j < comp_count; j++) |
768 | printf ("%2lu ", (unsigned long)k); | 800 | printf (" %c", depmap_isset (dpm, i, j) ? 'X' : ' '); |
769 | for (j = 0; j < comp_count; j++) | 801 | printf ("\n"); |
770 | if (comp_array[j]) | ||
771 | printf (" %c ", depmap_isset (depmap, i, j) ? 'X' : ' '); | ||
772 | printf ("\n"); | ||
773 | k++; | ||
774 | } | ||
775 | } | 802 | } |
@@ -781,2 +808,8 @@ components_dump_depmap (void) | |||
781 | void | 808 | void |
809 | components_dump_depmap (void) | ||
810 | { | ||
811 | depmap_dump (depmap); | ||
812 | } | ||
813 | |||
814 | void | ||
782 | component_trace (size_t idx, enum pies_depmap_direction dir) | 815 | 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 | |||
@@ -83,5 +83,5 @@ struct pies_depmap | |||
83 | { | 83 | { |
84 | size_t nrows; | 84 | size_t nrows; /* Number of rows (== number of mapped elements) */ |
85 | size_t rowlen; | 85 | size_t rowlen; /* Length of a row in words */ |
86 | unsigned r[1]; | 86 | unsigned r[1]; /* Data rows */ |
87 | }; | 87 | }; |
@@ -99,2 +99,9 @@ depmap_alloc (size_t count) | |||
99 | 99 | ||
100 | /* Return size of a depmap row in bytes */ | ||
101 | static inline size_t | ||
102 | depmap_row_size (pies_depmap_t dpm) | ||
103 | { | ||
104 | return dpm->rowlen * sizeof (unsigned); | ||
105 | } | ||
106 | |||
100 | pies_depmap_t | 107 | pies_depmap_t |
@@ -103,3 +110,3 @@ depmap_copy (pies_depmap_t dpm) | |||
103 | pies_depmap_t copy = depmap_alloc (dpm->nrows); | 110 | pies_depmap_t copy = depmap_alloc (dpm->nrows); |
104 | memcpy (copy->r, dpm->r, dpm->nrows * dpm->rowlen * sizeof (unsigned)); | 111 | memcpy (copy->r, dpm->r, dpm->nrows * depmap_row_size (dpm)); |
105 | return copy; | 112 | return copy; |
@@ -176,19 +183,20 @@ depmap_end (pies_depmap_pos_t pos) | |||
176 | 183 | ||
184 | /* Remove nth row and column from the map */ | ||
177 | void | 185 | void |
178 | depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir, | 186 | depmap_remove (pies_depmap_t dmap, size_t n) |
179 | size_t coord) | ||
180 | { | 187 | { |
181 | size_t i; | 188 | if (n < dmap->nrows - 1) |
182 | |||
183 | switch (dir) | ||
184 | { | 189 | { |
185 | case depmap_row: | 190 | size_t i, j; |
186 | for (i = 0; i < dmap->nrows; i++) | 191 | |
187 | depmap_clear (dmap, coord, i); | 192 | /* Remove nth row */ |
188 | break; | 193 | memmove (depmap_rowptr (dmap, n), depmap_rowptr (dmap, n + 1), |
189 | 194 | (dmap->nrows - n - 1) * depmap_row_size (dmap)); | |
190 | case depmap_col: | 195 | /* Renumber all columns j >= n: j = j - 1 */ |
191 | for (i = 0; i < dmap->nrows; i++) | 196 | for (i = 0; i < dmap->nrows; i++) |
192 | depmap_clear (dmap, i, coord); | 197 | for (j = n; j < dmap->nrows - 1; j++) |
198 | (depmap_isset (dmap, i, j + 1) ? depmap_set : depmap_clear) | ||
199 | (dmap, i, j); | ||
193 | } | 200 | } |
201 | dmap->nrows--; | ||
194 | } | 202 | } |
@@ -201,2 +201,4 @@ enum pies_comp_mode | |||
201 | 201 | ||
202 | #define CF_REMOVE 0x400 /* Marked for removal */ | ||
203 | |||
202 | #define ISCF_TCPMUX(f) ((f) & (CF_TCPMUX | CF_TCPMUXPLUS)) | 204 | #define ISCF_TCPMUX(f) ((f) & (CF_TCPMUX | CF_TCPMUXPLUS)) |
@@ -376,5 +378,3 @@ int depmap_isset (pies_depmap_t dmap, size_t row, size_t col); | |||
376 | void depmap_clear (pies_depmap_t dmap, size_t row, size_t col); | 378 | void depmap_clear (pies_depmap_t dmap, size_t row, size_t col); |
377 | 379 | void depmap_remove (pies_depmap_t dmap, size_t n); | |
378 | void depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir, | ||
379 | size_t coord); | ||
380 | 380 | ||
diff --git a/tests/Makefile.am b/tests/Makefile.am index 5ef3796..6c387cb 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am | |||
@@ -43,2 +43,3 @@ TESTSUITE_AT = \ | |||
43 | control.at\ | 43 | control.at\ |
44 | cyclic.at\ | ||
44 | respawn.at\ | 45 | respawn.at\ |
diff --git a/tests/atlocal.in b/tests/atlocal.in index 2ba1462..9069bbd 100644 --- a/tests/atlocal.in +++ b/tests/atlocal.in | |||
@@ -2,3 +2,3 @@ | |||
2 | # Configurable variable values for GNU Pies test suite. | 2 | # Configurable variable values for GNU Pies test suite. |
3 | # Copyright (C) 2016-2017 Sergey Poznyakoff | 3 | # Copyright (C) 2016-2019 Sergey Poznyakoff |
4 | 4 | ||
@@ -6 +6,5 @@ PATH=@abs_builddir@:@abs_top_builddir@/src:$srcdir:$PATH | |||