FD.io VPP  v17.04-9-g99c0734
Vector Packet Processing
ptclosure.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #include <vppinfra/ptclosure.h>
17 
18 u8 **
20 {
21  u8 **rv = 0;
22  u8 *row;
23  int i;
24 
25  ASSERT (n > 0);
26 
27  vec_validate (rv, n - 1);
28  for (i = 0; i < n; i++)
29  {
30  row = 0;
31  vec_validate (row, n - 1);
32 
33  rv[i] = row;
34  }
35  return rv;
36 }
37 
38 void
40 {
41  u8 *row;
42  int n = vec_len (ptc);
43  int i;
44 
45  ASSERT (n > 0);
46 
47  for (i = 0; i < n; i++)
48  {
49  row = ptc[i];
50  vec_free (row);
51  }
52  vec_free (ptc);
53 }
54 
55 void
56 clib_ptclosure_copy (u8 ** dst, u8 ** src)
57 {
58  int i, n;
59  u8 *src_row, *dst_row;
60 
61  n = vec_len (dst);
62 
63  for (i = 0; i < vec_len (dst); i++)
64  {
65  src_row = src[i];
66  dst_row = dst[i];
67  clib_memcpy (dst_row, src_row, n);
68  }
69 }
70 
71 /*
72  * compute the positive transitive closure
73  * of a relation via Warshall's algorithm.
74  *
75  * Ref:
76  * Warshall, Stephen (January 1962). "A theorem on Boolean matrices".
77  * Journal of the ACM 9 (1): 11–12.
78  *
79  * foo[i][j] = 1 means that item i
80  * "bears the relation" to item j.
81  *
82  * For example: "item i must be before item j"
83  *
84  * You could use a bitmap, but since the algorithm is
85  * O(n**3) in the first place, large N is inadvisable...
86  *
87  */
88 
89 u8 **
90 clib_ptclosure (u8 ** orig)
91 {
92  int i, j, k;
93  int n;
94  u8 **prev, **cur;
95 
96  n = vec_len (orig);
97  prev = clib_ptclosure_alloc (n);
98  cur = clib_ptclosure_alloc (n);
99 
100  clib_ptclosure_copy (prev, orig);
101 
102  for (k = 0; k < n; k++)
103  {
104  for (i = 0; i < n; i++)
105  {
106  for (j = 0; j < n; j++)
107  {
108  cur[i][j] = prev[i][j] || (prev[i][k] && prev[k][j]);
109  }
110  }
111  clib_ptclosure_copy (prev, cur);
112  }
113  clib_ptclosure_free (prev);
114  return cur;
115 }
116 
117 
118 
119 /*
120  * fd.io coding-style-patch-verification: ON
121  *
122  * Local Variables:
123  * eval: (c-set-style "gnu")
124  * End:
125  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:436
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
u8 ** clib_ptclosure_alloc(int n)
Definition: ptclosure.c:19
void clib_ptclosure_free(u8 **ptc)
Definition: ptclosure.c:39
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:340
#define clib_memcpy(a, b, c)
Definition: string.h:69
#define ASSERT(truth)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
u8 ** clib_ptclosure(u8 **orig)
Definition: ptclosure.c:90
void clib_ptclosure_copy(u8 **dst, u8 **src)
Definition: ptclosure.c:56