diff options
Diffstat (limited to 'vppinfra/vppinfra/ptclosure.c')
-rw-r--r-- | vppinfra/vppinfra/ptclosure.c | 64 |
1 files changed, 38 insertions, 26 deletions
diff --git a/vppinfra/vppinfra/ptclosure.c b/vppinfra/vppinfra/ptclosure.c index 705af62c18a..cda873ef442 100644 --- a/vppinfra/vppinfra/ptclosure.c +++ b/vppinfra/vppinfra/ptclosure.c @@ -15,33 +15,35 @@ #include <vppinfra/ptclosure.h> -u8 ** clib_ptclosure_alloc (int n) +u8 ** +clib_ptclosure_alloc (int n) { - u8 ** rv = 0; - u8 * row; + u8 **rv = 0; + u8 *row; int i; ASSERT (n > 0); - vec_validate (rv, n-1); + vec_validate (rv, n - 1); for (i = 0; i < n; i++) { row = 0; - vec_validate (row, n-1); - + vec_validate (row, n - 1); + rv[i] = row; } return rv; } -void clib_ptclosure_free (u8 ** ptc) +void +clib_ptclosure_free (u8 ** ptc) { - u8 * row; + u8 *row; int n = vec_len (ptc); int i; ASSERT (n > 0); - + for (i = 0; i < n; i++) { row = ptc[i]; @@ -50,14 +52,15 @@ void clib_ptclosure_free (u8 ** ptc) vec_free (ptc); } -void clib_ptclosure_copy (u8 ** dst, u8 **src) +void +clib_ptclosure_copy (u8 ** dst, u8 ** src) { int i, n; - u8 * src_row, * dst_row; + u8 *src_row, *dst_row; n = vec_len (dst); - for (i = 0; i < vec_len(dst); i++) + for (i = 0; i < vec_len (dst); i++) { src_row = src[i]; dst_row = dst[i]; @@ -67,13 +70,13 @@ void clib_ptclosure_copy (u8 ** dst, u8 **src) /* * compute the positive transitive closure - * of a relation via Warshall's algorithm. - * + * 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. + * 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 + * foo[i][j] = 1 means that item i * "bears the relation" to item j. * * For example: "item i must be before item j" @@ -83,11 +86,12 @@ void clib_ptclosure_copy (u8 ** dst, u8 **src) * */ -u8 ** clib_ptclosure (u8 ** orig) +u8 ** +clib_ptclosure (u8 ** orig) { int i, j, k; int n; - u8 ** prev, ** cur; + u8 **prev, **cur; n = vec_len (orig); prev = clib_ptclosure_alloc (n); @@ -98,16 +102,24 @@ u8 ** clib_ptclosure (u8 ** 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]); - } - } + { + 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; } - + + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |