Line data    Source code

       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             : __clib_export u8 **
      19       51987 : clib_ptclosure_alloc (int n)
      20             : {
      21       51987 :   u8 **rv = 0;
      22             :   u8 *row;
      23             :   int i;
      24             : 
      25       51987 :   ASSERT (n > 0);
      26             : 
      27       51987 :   vec_validate (rv, n - 1);
      28     1147240 :   for (i = 0; i < n; i++)
      29             :     {
      30     1095260 :       row = 0;
      31     1095260 :       vec_validate (row, n - 1);
      32             : 
      33     1095260 :       rv[i] = row;
      34             :     }
      35       51987 :   return rv;
      36             : }
      37             : 
      38             : __clib_export void
      39       51987 : clib_ptclosure_free (u8 ** ptc)
      40             : {
      41             :   u8 *row;
      42       51987 :   int n = vec_len (ptc);
      43             :   int i;
      44             : 
      45       51987 :   ASSERT (n > 0);
      46             : 
      47     1147240 :   for (i = 0; i < n; i++)
      48             :     {
      49     1095260 :       row = ptc[i];
      50     1095260 :       vec_free (row);
      51             :     }
      52       51987 :   vec_free (ptc);
      53       51987 : }
      54             : 
      55             : void
      56      382415 : clib_ptclosure_copy (u8 ** dst, u8 ** src)
      57             : {
      58             :   int i, n;
      59             :   u8 *src_row, *dst_row;
      60             : 
      61      382415 :   n = vec_len (dst);
      62             : 
      63    70726200 :   for (i = 0; i < vec_len (dst); i++)
      64             :     {
      65    70343700 :       src_row = src[i];
      66    70343700 :       dst_row = dst[i];
      67    70343700 :       clib_memcpy (dst_row, src_row, n);
      68             :     }
      69      382415 : }
      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             : __clib_export u8 **
      90       17329 : clib_ptclosure (u8 ** orig)
      91             : {
      92             :   int i, j, k;
      93             :   int n;
      94             :   u8 **prev, **cur;
      95             : 
      96       17329 :   n = vec_len (orig);
      97       17329 :   prev = clib_ptclosure_alloc (n);
      98       17329 :   cur = clib_ptclosure_alloc (n);
      99             : 
     100       17329 :   clib_ptclosure_copy (prev, orig);
     101             : 
     102      382415 :   for (k = 0; k < n; k++)
     103             :     {
     104    70343700 :       for (i = 0; i < n; i++)
     105             :         {
     106 21972500000 :           for (j = 0; j < n; j++)
     107             :             {
     108 21902500000 :               cur[i][j] = prev[i][j] || (prev[i][k] && prev[k][j]);
     109             :             }
     110             :         }
     111      365086 :       clib_ptclosure_copy (prev, cur);
     112             :     }
     113       17329 :   clib_ptclosure_free (prev);
     114       17329 :   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             :  */