src/sn_stage.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include <assert.h>
   4
   5 #include "sn_comparator.h"
   6 #include "sn_stage.h"
   7
   8 sn_stage_t *sn_stage_create (int depth)
   9 {
  10   sn_stage_t *s;
  11
  12   s = (sn_stage_t *) malloc (sizeof (sn_stage_t));
  13   if (s == NULL)
  14     return (NULL);
  15   memset (s, '\0', sizeof (sn_stage_t));
  16
  17   s->depth = depth;
  18
  19   return (s);
  20 } /* sn_stage_t *sn_stage_create */
  21
  22 void sn_stage_destroy (sn_stage_t *s)
  23 {
  24   if (s == NULL)
  25     return;
  26   if (s->comparators != NULL)
  27     free (s->comparators);
  28   free (s);
  29 } /* void sn_stage_destroy */
  30
  31 int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c)
  32 {
  33   sn_comparator_t *temp;
  34   int i;
  35
  36   temp = (sn_comparator_t *) realloc (s->comparators,
  37       (s->comparators_num + 1) * sizeof (sn_comparator_t));
  38   if (temp == NULL)
  39     return (-1);
  40   s->comparators = temp;
  41   temp = NULL;
  42
  43   for (i = 0; i < s->comparators_num; i++)
  44     if (sn_comparator_compare (c, s->comparators + i) <= 0)
  45       break;
  46
  47   /* Insert the elements in ascending order */
  48   assert (i <= s->comparators_num);
  49   if (i < s->comparators_num)
  50   {
  51     int nmemb = s->comparators_num - i;
  52     memmove (s->comparators + (i + 1), s->comparators + i,
  53         nmemb * sizeof (sn_comparator_t));
  54   }
  55   memcpy (s->comparators + i, c, sizeof (sn_comparator_t));
  56   s->comparators_num++;
  57
  58   return (0);
  59 } /* int sn_stage_comparator_add */
  60
  61 int sn_stage_comparator_remove (sn_stage_t *s, int c_num)
  62 {
  63   int nmemb = s->comparators_num - (c_num + 1);
  64   sn_comparator_t *temp;
  65
  66   assert (c_num < s->comparators_num);
  67   assert (c_num >= 0);
  68
  69   if (nmemb > 0)
  70     memmove (s->comparators + c_num, s->comparators + (c_num + 1),
  71         nmemb * sizeof (sn_comparator_t));
  72   s->comparators_num--;
  73
  74   /* Free the unused memory */
  75   if (s->comparators_num == 0)
  76   {
  77     free (s->comparators);
  78     s->comparators = NULL;
  79   }
  80   else
  81   {
  82     temp = (sn_comparator_t *) realloc (s->comparators,
  83         s->comparators_num * sizeof (sn_comparator_t));
  84     if (temp == NULL)
  85       return (-1);
  86     s->comparators = temp;
  87   }
  88
  89   return (0);
  90 } /* int sn_stage_comparator_remove */
  91
  92 sn_stage_t *sn_stage_clone (const sn_stage_t *s)
  93 {
  94   sn_stage_t *s_copy;
  95
  96   s_copy = sn_stage_create (s->depth);
  97   if (s_copy == NULL)
  98     return (NULL);
  99
 100   s_copy->comparators = (sn_comparator_t *) malloc (s->comparators_num
 101       * sizeof (sn_comparator_t));
 102   if (s_copy->comparators == NULL)
 103   {
 104     free (s_copy);
 105     return (NULL);
 106   }
 107
 108   memcpy (s_copy->comparators, s->comparators,
 109       s->comparators_num * sizeof (sn_comparator_t));
 110   s_copy->comparators_num = s->comparators_num;
 111
 112   return (s_copy);
 113 } /* sn_stage_t *sn_stage_clone */
 114
 115 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c0)
 116 {
 117   int i;
 118
 119   for (i = 0; i < s->comparators_num; i++)
 120   {
 121     sn_comparator_t *c1 = s->comparators + i;
 122     if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
 123         || (SN_COMP_MIN(c0) == SN_COMP_MAX(c1))
 124         || (SN_COMP_MAX(c0) == SN_COMP_MIN(c1))
 125         || (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
 126     {
 127       if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
 128           && (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
 129         return (2);
 130       else
 131         return (1);
 132     }
 133   }
 134
 135   return (0);
 136 } /* int sn_stage_comparator_check_conflict */
 137
 138 int sn_stage_show (sn_stage_t *s)
 139 {
 140   int lines[s->comparators_num];
 141   int right[s->comparators_num];
 142   int lines_used = 0;
 143   int i;
 144   int j;
 145   int k;
 146
 147
 148   for (i = 0; i < s->comparators_num; i++)
 149   {
 150     lines[i] = -1;
 151     right[i] = -1;
 152   }
 153
 154   for (i = 0; i < s->comparators_num; i++)
 155   {
 156     int j;
 157     sn_comparator_t *c = s->comparators + i;
 158
 159     for (j = 0; j < lines_used; j++)
 160       if (SN_COMP_LEFT (c) > right[j])
 161         break;
 162
 163     lines[i] = j;
 164     right[j] = SN_COMP_RIGHT (c);
 165     if (j >= lines_used)
 166       lines_used = j + 1;
 167   }
 168
 169   for (i = 0; i < lines_used; i++)
 170   {
 171     printf ("%3i: ", s->depth);
 172
 173     for (j = 0; j <= right[i]; j++)
 174     {
 175       int on_elem = 0;
 176       int line_after = 0;
 177
 178       for (k = 0; k < s->comparators_num; k++)
 179       {
 180         sn_comparator_t *c = s->comparators + k;
 181
 182         /* Check if this comparator is displayed on another line */
 183         if (lines[k] != i)
 184           continue;
 185
 186         if (j == SN_COMP_MIN (c))
 187           on_elem = -1;
 188         else if (j == SN_COMP_MAX (c))
 189           on_elem = 1;
 190
 191         if ((j >= SN_COMP_LEFT (c)) && (j < SN_COMP_RIGHT (c)))
 192           line_after = 1;
 193
 194         if ((on_elem != 0) || (line_after != 0))
 195           break;
 196       }
 197
 198       if (on_elem == 0)
 199       {
 200         if (line_after == 0)
 201           printf ("     ");
 202         else
 203           printf ("-----");
 204       }
 205       else if (on_elem == -1)
 206       {
 207         if (line_after == 0)
 208           printf ("-!   ");
 209         else
 210           printf (" !---");
 211       }
 212       else
 213       {
 214         if (line_after == 0)
 215           printf ("->   ");
 216         else
 217           printf (" <---");
 218       }
 219     } /* for (columns) */
 220
 221     printf ("\n");
 222   } /* for (lines) */
 223
 224   return (0);
 225 } /* int sn_stage_show */
 226
 227 int sn_stage_invert (sn_stage_t *s)
 228 {
 229   int i;
 230
 231   for (i = 0; i < s->comparators_num; i++)
 232     sn_comparator_invert (s->comparators + i);
 233
 234   return (0);
 235 } /* int sn_stage_invert */
 236
 237 int sn_stage_swap (sn_stage_t *s, int con0, int con1)
 238 {
 239   int i;
 240
 241   for (i = 0; i < s->comparators_num; i++)
 242     sn_comparator_swap (s->comparators + i, con0, con1);
 243
 244   return (0);
 245 } /* int sn_stage_swap */
 246
 247 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir)
 248 {
 249   int new_position = input;
 250   int i;
 251
 252   for (i = 0; i < s->comparators_num; i++)
 253   {
 254     sn_comparator_t *c = s->comparators + i;
 255
 256     if ((SN_COMP_MIN (c) != input) && (SN_COMP_MAX (c) != input))
 257       continue;
 258
 259     if ((dir == DIR_MIN) && (SN_COMP_MAX (c) == input))
 260     {
 261       new_position = SN_COMP_MIN (c);
 262     }
 263     else if ((dir == DIR_MAX) && (SN_COMP_MIN (c) == input))
 264     {
 265       new_position = SN_COMP_MAX (c);
 266     }
 267     break;
 268   }
 269
 270   /*
 271   if (i < s->comparators_num)
 272     sn_stage_comparator_remove (s, i);
 273     */
 274
 275   return (new_position);
 276 } /* int sn_stage_cut_at */
 277
 278 int sn_stage_remove_input (sn_stage_t *s, int input)
 279 {
 280   int i;
 281
 282   for (i = 0; i < s->comparators_num; i++)
 283   {
 284     sn_comparator_t *c = s->comparators + i;
 285
 286     if ((SN_COMP_MIN (c) == input) || (SN_COMP_MAX (c) == input))
 287     {
 288       sn_stage_comparator_remove (s, i);
 289       i--;
 290       continue;
 291     }
 292
 293     if (SN_COMP_MIN (c) > input)
 294       SN_COMP_MIN (c) = SN_COMP_MIN (c) - 1;
 295     if (SN_COMP_MAX (c) > input)
 296       SN_COMP_MAX (c) = SN_COMP_MAX (c) - 1;
 297   }
 298
 299   return (0);
 300 }
 301
 302 sn_stage_t *sn_stage_read (FILE *fh)
 303 {
 304   sn_stage_t *s;
 305   char buffer[64];
 306   char *buffer_ptr;
 307
 308   s = sn_stage_create (0);
 309   if (s == NULL)
 310     return (NULL);
 311
 312   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 313   {
 314     char *endptr;
 315     sn_comparator_t c;
 316
 317     if ((buffer[0] == '\0') || (buffer[0] == '\n') || (buffer[0] == '\r'))
 318       break;
 319
 320     buffer_ptr = buffer;
 321     endptr = NULL;
 322     c.min = (int) strtol (buffer_ptr, &endptr, 0);
 323     if (buffer_ptr == endptr)
 324       continue;
 325
 326     buffer_ptr = endptr;
 327     endptr = NULL;
 328     c.max = (int) strtol (buffer_ptr, &endptr, 0);
 329     if (buffer_ptr == endptr)
 330       continue;
 331
 332     sn_stage_comparator_add (s, &c);
 333   }
 334
 335   if (s->comparators_num == 0)
 336   {
 337     sn_stage_destroy (s);
 338     return (NULL);
 339   }
 340
 341   return (s);
 342 } /* sn_stage_t *sn_stage_read */
 343
 344 int sn_stage_write (sn_stage_t *s, FILE *fh)
 345 {
 346   int i;
 347
 348   if (s->comparators_num <= 0)
 349     return (0);
 350
 351   for (i = 0; i < s->comparators_num; i++)
 352     fprintf (fh, "%i %i\n",
 353         SN_COMP_MIN (s->comparators + i),
 354         SN_COMP_MAX (s->comparators + i));
 355   fprintf (fh, "\n");
 356
 357   return (0);
 358 } /* int sn_stage_write */
 359
 360 /* vim: set shiftwidth=2 softtabstop=2 : */