vppinfra/vppinfra/test_ptclosure.c

   1 /*
   2  * Copyright (c) 2015 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 #include <vppinfra/hash.h>
  18
  19 typedef struct {
  20   uword * index_by_name;
  21   u8 * items;
  22 } test_main_t;
  23
  24 test_main_t test_main;
  25
  26 static char * items [] = {
  27     "d",
  28     "a",
  29     "b",
  30     "c",
  31 };
  32
  33 char * constraints [] = {
  34     "a,b",
  35     "b,c",
  36     "d,b",
  37     //    "c,a", /* no partial order possible */
  38 };
  39
  40 u32 vl(void *p)
  41 {
  42   return vec_len (p);
  43 }
  44
  45 static void dump_closure (test_main_t * tm, char * s, u8 ** orig)
  46 {
  47   int i, j;
  48
  49   fformat (stdout, "--------- %s --------------\n", s);
  50   for (i = 0; i < vec_len (orig); i++)
  51     {
  52       for (j = 0; j < vec_len (orig); j++)
  53         if (orig[i][j])
  54           {
  55             fformat (stdout, "%s <before> %s\n", items[i], items[j]);
  56           }
  57     }
  58 }
  59
  60 int comma_split (u8 *s, u8 **a, u8 **b)
  61 {
  62   *a = s;
  63
  64   while (*s && *s != ',')
  65     s++;
  66
  67   if (*s == ',')
  68     *s = 0;
  69   else
  70     return 1;
  71
  72   *b = (u8 *) (s+1);
  73   return 0;
  74 }
  75
  76 int test_ptclosure_main (unformat_input_t * input)
  77 {
  78   test_main_t * tm = &test_main;
  79   u8 * item_name;
  80   int i, j;
  81   u8 ** orig;
  82   u8 ** closure;
  83   u8 * a_name, * b_name;
  84   int a_index, b_index;
  85   uword * p;
  86   u8 * this_constraint;
  87   int n;
  88   u32 * result = 0;
  89
  90   tm->index_by_name = hash_create_string (0, sizeof (uword));
  91
  92   n = ARRAY_LEN(items);
  93
  94   for (i = 0; i < n; i++)
  95     {
  96       item_name = (u8 *) items[i];
  97       hash_set_mem (tm->index_by_name, item_name, i);
  98     }
  99
 100   orig = clib_ptclosure_alloc (n);
 101
 102   for (i = 0; i < ARRAY_LEN(constraints); i++)
 103     {
 104       this_constraint = format (0, "%s%c", constraints[i], 0);
 105
 106       if (comma_split (this_constraint, &a_name, &b_name))
 107         {
 108           clib_warning ("couldn't split '%s'", constraints[i]);
 109           return 1;
 110         }
 111
 112       p = hash_get_mem (tm->index_by_name, a_name);
 113       if (p == 0)
 114         {
 115           clib_warning ("couldn't find '%s'", a_name);
 116           return 1;
 117         }
 118       a_index = p[0];
 119
 120       p = hash_get_mem (tm->index_by_name, b_name);
 121       if (p == 0)
 122         {
 123           clib_warning ("couldn't find '%s'", b_name);
 124           return 1;
 125         }
 126       b_index = p[0];
 127
 128       orig[a_index][b_index] = 1;
 129       vec_free (this_constraint);
 130     }
 131
 132   dump_closure (tm, "original relation", orig);
 133
 134   closure = clib_ptclosure (orig);
 135
 136   dump_closure (tm, "closure", closure);
 137
 138   /*
 139    * Output partial order
 140    */
 141
 142  again:
 143   for (i = 0; i < n; i++)
 144     {
 145       for (j = 0; j < n; j++)
 146         {
 147           if (closure[i][j])
 148             goto item_constrained;
 149         }
 150       /* Item i can be output */
 151       vec_add1 (result, i);
 152       {
 153         int k;
 154         for (k = 0; k < n; k++)
 155           closure [k][i] = 0;
 156         /* "Magic" a before a, to keep from ever outputting it again */
 157         closure [i][i] = 1;
 158         goto again;
 159       }
 160     item_constrained:
 161       ;
 162     }
 163
 164   if (vec_len (result) != n)
 165     {
 166       clib_warning ("no partial order exists");
 167       exit (1);
 168     }
 169
 170   fformat (stdout, "Partial order:\n");
 171
 172   for (i = vec_len(result)-1; i >= 0; i--)
 173     {
 174       fformat (stdout, "%s\n", items[result[i]]);
 175     }
 176
 177   vec_free (result);
 178   clib_ptclosure_free (orig);
 179   clib_ptclosure_free (closure);
 180
 181   return 0;
 182 }
 183
 184 #ifdef CLIB_UNIX
 185 int main (int argc, char * argv[])
 186 {
 187   unformat_input_t i;
 188   int ret;
 189
 190   clib_mem_init (0, 3ULL<<30);
 191
 192   unformat_init_command_line (&i, argv);
 193   ret = test_ptclosure_main (&i);
 194   unformat_free (&i);
 195
 196   return ret;
 197 }
 198 #endif /* CLIB_UNIX */