aboutsummaryrefslogtreecommitdiffstats
path: root/src/vppinfra/test_ptclosure.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/vppinfra/test_ptclosure.c')
-rw-r--r--src/vppinfra/test_ptclosure.c212
1 files changed, 212 insertions, 0 deletions
diff --git a/src/vppinfra/test_ptclosure.c b/src/vppinfra/test_ptclosure.c
new file mode 100644
index 00000000000..be7d51dfa7d
--- /dev/null
+++ b/src/vppinfra/test_ptclosure.c
@@ -0,0 +1,212 @@
+/*
+ * Copyright (c) 2015 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <vppinfra/ptclosure.h>
+#include <vppinfra/hash.h>
+
+typedef struct
+{
+ uword *index_by_name;
+ u8 *items;
+} test_main_t;
+
+test_main_t test_main;
+
+static char *items[] = {
+ "d",
+ "a",
+ "b",
+ "c",
+};
+
+char *constraints[] = {
+ "a,b",
+ "b,c",
+ "d,b",
+ // "c,a", /* no partial order possible */
+};
+
+u32
+vl (void *p)
+{
+ return vec_len (p);
+}
+
+static void
+dump_closure (test_main_t * tm, char *s, u8 ** orig)
+{
+ int i, j;
+
+ fformat (stdout, "--------- %s --------------\n", s);
+ for (i = 0; i < vec_len (orig); i++)
+ {
+ for (j = 0; j < vec_len (orig); j++)
+ if (orig[i][j])
+ {
+ fformat (stdout, "%s <before> %s\n", items[i], items[j]);
+ }
+ }
+}
+
+int
+comma_split (u8 * s, u8 ** a, u8 ** b)
+{
+ *a = s;
+
+ while (*s && *s != ',')
+ s++;
+
+ if (*s == ',')
+ *s = 0;
+ else
+ return 1;
+
+ *b = (u8 *) (s + 1);
+ return 0;
+}
+
+int
+test_ptclosure_main (unformat_input_t * input)
+{
+ test_main_t *tm = &test_main;
+ u8 *item_name;
+ int i, j;
+ u8 **orig;
+ u8 **closure;
+ u8 *a_name, *b_name;
+ int a_index, b_index;
+ uword *p;
+ u8 *this_constraint;
+ int n;
+ u32 *result = 0;
+
+ tm->index_by_name = hash_create_string (0, sizeof (uword));
+
+ n = ARRAY_LEN (items);
+
+ for (i = 0; i < n; i++)
+ {
+ item_name = (u8 *) items[i];
+ hash_set_mem (tm->index_by_name, item_name, i);
+ }
+
+ orig = clib_ptclosure_alloc (n);
+
+ for (i = 0; i < ARRAY_LEN (constraints); i++)
+ {
+ this_constraint = format (0, "%s%c", constraints[i], 0);
+
+ if (comma_split (this_constraint, &a_name, &b_name))
+ {
+ clib_warning ("couldn't split '%s'", constraints[i]);
+ return 1;
+ }
+
+ p = hash_get_mem (tm->index_by_name, a_name);
+ if (p == 0)
+ {
+ clib_warning ("couldn't find '%s'", a_name);
+ return 1;
+ }
+ a_index = p[0];
+
+ p = hash_get_mem (tm->index_by_name, b_name);
+ if (p == 0)
+ {
+ clib_warning ("couldn't find '%s'", b_name);
+ return 1;
+ }
+ b_index = p[0];
+
+ orig[a_index][b_index] = 1;
+ vec_free (this_constraint);
+ }
+
+ dump_closure (tm, "original relation", orig);
+
+ closure = clib_ptclosure (orig);
+
+ dump_closure (tm, "closure", closure);
+
+ /*
+ * Output partial order
+ */
+
+again:
+ for (i = 0; i < n; i++)
+ {
+ for (j = 0; j < n; j++)
+ {
+ if (closure[i][j])
+ goto item_constrained;
+ }
+ /* Item i can be output */
+ vec_add1 (result, i);
+ {
+ int k;
+ for (k = 0; k < n; k++)
+ closure[k][i] = 0;
+ /* "Magic" a before a, to keep from ever outputting it again */
+ closure[i][i] = 1;
+ goto again;
+ }
+ item_constrained:
+ ;
+ }
+
+ if (vec_len (result) != n)
+ {
+ clib_warning ("no partial order exists");
+ exit (1);
+ }
+
+ fformat (stdout, "Partial order:\n");
+
+ for (i = vec_len (result) - 1; i >= 0; i--)
+ {
+ fformat (stdout, "%s\n", items[result[i]]);
+ }
+
+ vec_free (result);
+ clib_ptclosure_free (orig);
+ clib_ptclosure_free (closure);
+
+ return 0;
+}
+
+#ifdef CLIB_UNIX
+int
+main (int argc, char *argv[])
+{
+ unformat_input_t i;
+ int ret;
+
+ clib_mem_init (0, 3ULL << 30);
+
+ unformat_init_command_line (&i, argv);
+ ret = test_ptclosure_main (&i);
+ unformat_free (&i);
+
+ return ret;
+}
+#endif /* CLIB_UNIX */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */