vppinfra/vppinfra/ptclosure.c

   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 ** clib_ptclosure_alloc (int n)
  19 {
  20   u8 ** rv = 0;
  21   u8 * row;
  22   int i;
  23
  24   ASSERT (n > 0);
  25
  26   vec_validate (rv, n-1);
  27   for (i = 0; i < n; i++)
  28     {
  29       row = 0;
  30       vec_validate (row, n-1);
  31
  32       rv[i] = row;
  33     }
  34   return rv;
  35 }
  36
  37 void clib_ptclosure_free (u8 ** ptc)
  38 {
  39   u8 * row;
  40   int n = vec_len (ptc);
  41   int i;
  42
  43   ASSERT (n > 0);
  44
  45   for (i = 0; i < n; i++)
  46     {
  47       row = ptc[i];
  48       vec_free (row);
  49     }
  50   vec_free (ptc);
  51 }
  52
  53 void clib_ptclosure_copy (u8 ** dst, u8 **src)
  54 {
  55   int i, n;
  56   u8 * src_row, * dst_row;
  57
  58   n = vec_len (dst);
  59
  60   for (i = 0; i < vec_len(dst); i++)
  61     {
  62       src_row = src[i];
  63       dst_row = dst[i];
  64       clib_memcpy (dst_row, src_row, n);
  65     }
  66 }
  67
  68 /*
  69  * compute the positive transitive closure
  70  * of a relation via Warshall's algorithm.
  71  *
  72  * Ref:
  73  * Warshall, Stephen (January 1962). "A theorem on Boolean matrices".
  74  * Journal of the ACM 9 (1): 11–12.
  75  *
  76  * foo[i][j] = 1 means that item i
  77  * "bears the relation" to item j.
  78  *
  79  * For example: "item i must be before item j"
  80  *
  81  * You could use a bitmap, but since the algorithm is
  82  * O(n**3) in the first place, large N is inadvisable...
  83  *
  84  */
  85
  86 u8 ** clib_ptclosure (u8 ** orig)
  87 {
  88   int i, j, k;
  89   int n;
  90   u8 ** prev, ** cur;
  91
  92   n = vec_len (orig);
  93   prev = clib_ptclosure_alloc (n);
  94   cur = clib_ptclosure_alloc (n);
  95
  96   clib_ptclosure_copy (prev, orig);
  97
  98   for (k = 0; k < n; k++)
  99     {
 100       for (i = 0; i < n; i++)
 101         {
 102           for (j = 0; j < n; j++)
 103             {
 104               cur[i][j] = prev[i][j] || (prev[i][k] && prev[k][j]);
 105             }
 106         }
 107       clib_ptclosure_copy (prev, cur);
 108     }
 109   clib_ptclosure_free (prev);
 110   return cur;
 111 }
 112
 113