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