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