diff options
Diffstat (limited to 'vppinfra')
| -rw-r--r-- | vppinfra/Makefile.am | 9 | ||||
| -rw-r--r-- | vppinfra/vppinfra/ptclosure.c | 113 | ||||
| -rw-r--r-- | vppinfra/vppinfra/ptclosure.h | 32 | ||||
| -rw-r--r-- | vppinfra/vppinfra/test_ptclosure.c | 198 |
4 files changed, 351 insertions, 1 deletions
diff --git a/vppinfra/Makefile.am b/vppinfra/Makefile.am index 1b4d627dfb6..b99f3d53716 100644 --- a/vppinfra/Makefile.am +++ b/vppinfra/Makefile.am @@ -20,7 +20,7 @@ endif lib_LIBRARIES = -TESTS = +TESTS = if ENABLE_TESTS TESTS += test_bihash_template \ @@ -37,6 +37,7 @@ TESTS += test_bihash_template \ test_pfhash \ test_phash \ test_pool_iterate \ + test_ptclosure \ test_qhash \ test_random \ test_random_isaac \ @@ -66,6 +67,7 @@ test_mheap_SOURCES = vppinfra/test_mheap.c test_pfhash_SOURCES = vppinfra/test_pfhash.c test_phash_SOURCES = vppinfra/test_phash.c test_pool_iterate_SOURCES = vppinfra/test_pool_iterate.c +test_ptclosure_SOURCES = vppinfra/test_ptclosure.c test_qhash_SOURCES = vppinfra/test_qhash.c test_random_SOURCES = vppinfra/test_random.c test_random_isaac_SOURCES = vppinfra/test_random_isaac.c @@ -93,6 +95,7 @@ test_mheap_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_pfhash_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_phash_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_pool_iterate_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG +test_ptclosure_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_qhash_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_random_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_random_isaac_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG @@ -118,6 +121,7 @@ test_mheap_LDADD = libvppinfra.la test_pfhash_LDADD = libvppinfra.la test_phash_LDADD = libvppinfra.la test_pool_iterate_LDADD = libvppinfra.la +test_ptclosure_LDADD = libvppinfra.la test_qhash_LDADD = libvppinfra.la test_random_LDADD = libvppinfra.la test_random_isaac_LDADD = libvppinfra.la @@ -143,6 +147,7 @@ test_mheap_LDFLAGS = -static test_pfhash_LDFLAGS = -static test_phash_LDFLAGS = -static test_pool_iterate_LDFLAGS = -static +test_ptclosure_LDFLAGS = -static test_qhash_LDFLAGS = -static test_random_LDFLAGS = -static test_random_isaac_LDFLAGS = -static @@ -199,6 +204,7 @@ nobase_include_HEADERS = \ vppinfra/phash.h \ vppinfra/pipeline.h \ vppinfra/pool.h \ + vppinfra/ptclosure.h \ vppinfra/qhash.h \ vppinfra/random.h \ vppinfra/random_buffer.h \ @@ -249,6 +255,7 @@ CLIB_CORE = \ vppinfra/mem_mheap.c \ vppinfra/pfhash.c \ vppinfra/phash.c \ + vppinfra/ptclosure.c \ vppinfra/qhash.c \ vppinfra/random.c \ vppinfra/random_buffer.c \ diff --git a/vppinfra/vppinfra/ptclosure.c b/vppinfra/vppinfra/ptclosure.c new file mode 100644 index 00000000000..705af62c18a --- /dev/null +++ b/vppinfra/vppinfra/ptclosure.c @@ -0,0 +1,113 @@ +/* + * Copyright (c) 2016 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> + +u8 ** clib_ptclosure_alloc (int n) +{ + u8 ** rv = 0; + u8 * row; + int i; + + ASSERT (n > 0); + + vec_validate (rv, n-1); + for (i = 0; i < n; i++) + { + row = 0; + vec_validate (row, n-1); + + rv[i] = row; + } + return rv; +} + +void clib_ptclosure_free (u8 ** ptc) +{ + u8 * row; + int n = vec_len (ptc); + int i; + + ASSERT (n > 0); + + for (i = 0; i < n; i++) + { + row = ptc[i]; + vec_free (row); + } + vec_free (ptc); +} + +void clib_ptclosure_copy (u8 ** dst, u8 **src) +{ + int i, n; + u8 * src_row, * dst_row; + + n = vec_len (dst); + + for (i = 0; i < vec_len(dst); i++) + { + src_row = src[i]; + dst_row = dst[i]; + clib_memcpy (dst_row, src_row, n); + } +} + +/* + * compute the positive transitive closure + * of a relation via Warshall's algorithm. + * + * Ref: + * Warshall, Stephen (January 1962). "A theorem on Boolean matrices". + * Journal of the ACM 9 (1): 11–12. + * + * foo[i][j] = 1 means that item i + * "bears the relation" to item j. + * + * For example: "item i must be before item j" + * + * You could use a bitmap, but since the algorithm is + * O(n**3) in the first place, large N is inadvisable... + * + */ + +u8 ** clib_ptclosure (u8 ** orig) +{ + int i, j, k; + int n; + u8 ** prev, ** cur; + + n = vec_len (orig); + prev = clib_ptclosure_alloc (n); + cur = clib_ptclosure_alloc (n); + + clib_ptclosure_copy (prev, orig); + + for (k = 0; k < n; k++) + { + for (i = 0; i < n; i++) + { + for (j = 0; j < n; j++) + { + cur[i][j] = prev[i][j] || (prev[i][k] && prev[k][j]); + } + } + clib_ptclosure_copy (prev, cur); + } + clib_ptclosure_free (prev); + return cur; +} + + diff --git a/vppinfra/vppinfra/ptclosure.h b/vppinfra/vppinfra/ptclosure.h new file mode 100644 index 00000000000..c3b71743703 --- /dev/null +++ b/vppinfra/vppinfra/ptclosure.h @@ -0,0 +1,32 @@ +/* + * Copyright (c) 2016 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. + */ +#ifndef included_clib_ptclosure_h +#define included_clib_ptclosure_h + +#include <vppinfra/vec.h> +#include <vppinfra/format.h> +#include <vppinfra/error.h> + +/* + * set r[i][j] if item i "bears the relation to" item j + * + */ + +u8 ** clib_ptclosure_alloc (int n); +void clib_ptclosure_free (u8 ** ptc); +void clib_ptclosure_copy (u8 ** dst, u8 **src); +u8 ** clib_ptclosure (u8 ** orig); + +#endif /* included_clib_ptclosure_h */ diff --git a/vppinfra/vppinfra/test_ptclosure.c b/vppinfra/vppinfra/test_ptclosure.c new file mode 100644 index 00000000000..b5ac13f7de5 --- /dev/null +++ b/vppinfra/vppinfra/test_ptclosure.c @@ -0,0 +1,198 @@ +/* + * 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 */ |