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
  68   if (nmemb > 0)
  69     memmove (s->comparators + c_num, s->comparators + (c_num + 1),
  70         nmemb * sizeof (sn_comparator_t));
  71   s->comparators_num--;
  72
  73   /* Free the unused memory */
  74   temp = (sn_comparator_t *) realloc (s->comparators,
  75       s->comparators_num * sizeof (sn_comparator_t));
  76   if (temp == NULL)
  77     return (-1);
  78   s->comparators = temp;
  79
  80   return (0);
  81 } /* int sn_stage_comparator_remove */
  82
  83 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c0)
  84 {
  85   int i;
  86
  87   for (i = 0; i < s->comparators_num; i++)
  88   {
  89     sn_comparator_t *c1 = s->comparators + i;
  90     if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
  91         || (SN_COMP_MIN(c0) == SN_COMP_MAX(c1))
  92         || (SN_COMP_MAX(c0) == SN_COMP_MIN(c1))
  93         || (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
  94     {
  95       if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
  96           && (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
  97         return (2);
  98       else
  99         return (1);
 100     }
 101   }
 102
 103   return (0);
 104 } /* int sn_stage_comparator_check_conflict */
 105
 106 int sn_stage_show (sn_stage_t *s)
 107 {
 108   int lines[s->comparators_num];
 109   int right[s->comparators_num];
 110   int lines_used = 0;
 111   int i;
 112   int j;
 113   int k;
 114
 115
 116   for (i = 0; i < s->comparators_num; i++)
 117   {
 118     lines[i] = -1;
 119     right[i] = -1;
 120   }
 121
 122   for (i = 0; i < s->comparators_num; i++)
 123   {
 124     int j;
 125     sn_comparator_t *c = s->comparators + i;
 126
 127     for (j = 0; j < lines_used; j++)
 128       if (SN_COMP_LEFT (c) > right[j])
 129         break;
 130
 131     lines[i] = j;
 132     right[j] = SN_COMP_RIGHT (c);
 133     if (j >= lines_used)
 134       lines_used = j + 1;
 135   }
 136
 137   for (i = 0; i < lines_used; i++)
 138   {
 139     printf ("%3i: ", s->depth);
 140
 141     for (j = 0; j <= right[i]; j++)
 142     {
 143       int on_elem = 0;
 144       int line_after = 0;
 145
 146       for (k = 0; k < s->comparators_num; k++)
 147       {
 148         sn_comparator_t *c = s->comparators + k;
 149
 150         /* Check if this comparator is displayed on another line */
 151         if (lines[k] != i)
 152           continue;
 153
 154         if (j == SN_COMP_MIN (c))
 155           on_elem = -1;
 156         else if (j == SN_COMP_MAX (c))
 157           on_elem = 1;
 158
 159         if ((j >= SN_COMP_LEFT (c)) && (j < SN_COMP_RIGHT (c)))
 160           line_after = 1;
 161
 162         if ((on_elem != 0) || (line_after != 0))
 163           break;
 164       }
 165
 166       if (on_elem == 0)
 167       {
 168         if (line_after == 0)
 169           printf ("     ");
 170         else
 171           printf ("-----");
 172       }
 173       else if (on_elem == -1)
 174       {
 175         if (line_after == 0)
 176           printf ("-!   ");
 177         else
 178           printf (" !---");
 179       }
 180       else
 181       {
 182         if (line_after == 0)
 183           printf ("->   ");
 184         else
 185           printf (" <---");
 186       }
 187     } /* for (columns) */
 188
 189     printf ("\n");
 190   } /* for (lines) */
 191
 192   return (0);
 193 } /* int sn_stage_show */
 194
 195 int sn_stage_invert (sn_stage_t *s)
 196 {
 197   int i;
 198
 199   for (i = 0; i < s->comparators_num; i++)
 200     sn_comparator_invert (s->comparators + i);
 201
 202   return (0);
 203 } /* int sn_stage_invert */
 204
 205 int sn_stage_swap (sn_stage_t *s, int con0, int con1)
 206 {
 207   int i;
 208
 209   for (i = 0; i < s->comparators_num; i++)
 210     sn_comparator_swap (s->comparators + i, con0, con1);
 211
 212   return (0);
 213 } /* int sn_stage_swap */
 214
 215 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir)
 216 {
 217   int new_position = input;
 218   int i;
 219
 220   for (i = 0; i < s->comparators_num; i++)
 221   {
 222     sn_comparator_t *c = s->comparators + i;
 223
 224     if ((SN_COMP_MIN (c) != input) && (SN_COMP_MAX (c) != input))
 225       continue;
 226
 227     if ((dir == DIR_MIN) && (SN_COMP_MAX (c) == input))
 228     {
 229       new_position = SN_COMP_MIN (c);
 230     }
 231     else if ((dir == DIR_MAX) && (SN_COMP_MIN (c) == input))
 232     {
 233       new_position = SN_COMP_MAX (c);
 234     }
 235     break;
 236   }
 237
 238   /*
 239   if (i < s->comparators_num)
 240     sn_stage_comparator_remove (s, i);
 241     */
 242
 243   return (new_position);
 244 } /* int sn_stage_cut_at */
 245
 246 int sn_stage_remove_input (sn_stage_t *s, int input)
 247 {
 248   int i;
 249
 250   for (i = 0; i < s->comparators_num; i++)
 251   {
 252     sn_comparator_t *c = s->comparators + i;
 253
 254     if ((SN_COMP_MIN (c) == input) || (SN_COMP_MAX (c) == input))
 255     {
 256       sn_stage_comparator_remove (s, i);
 257       i--;
 258       continue;
 259     }
 260
 261     if (SN_COMP_MIN (c) > input)
 262       SN_COMP_MIN (c) = SN_COMP_MIN (c) - 1;
 263     if (SN_COMP_MAX (c) > input)
 264       SN_COMP_MAX (c) = SN_COMP_MAX (c) - 1;
 265   }
 266
 267   return (0);
 268 }
 269
 270 sn_stage_t *sn_stage_read (FILE *fh)
 271 {
 272   sn_stage_t *s;
 273   char buffer[64];
 274   char *buffer_ptr;
 275
 276   s = sn_stage_create (0);
 277   if (s == NULL)
 278     return (NULL);
 279
 280   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 281   {
 282     char *endptr;
 283     sn_comparator_t c;
 284
 285     if ((buffer[0] == '\0') || (buffer[0] == '\n') || (buffer[0] == '\r'))
 286       break;
 287
 288     buffer_ptr = buffer;
 289     endptr = NULL;
 290     c.min = (int) strtol (buffer_ptr, &endptr, 0);
 291     if (buffer_ptr == endptr)
 292       continue;
 293
 294     buffer_ptr = endptr;
 295     endptr = NULL;
 296     c.max = (int) strtol (buffer_ptr, &endptr, 0);
 297     if (buffer_ptr == endptr)
 298       continue;
 299
 300     sn_stage_comparator_add (s, &c);
 301   }
 302
 303   if (s->comparators_num == 0)
 304   {
 305     sn_stage_destroy (s);
 306     return (NULL);
 307   }
 308
 309   return (s);
 310 } /* sn_stage_t *sn_stage_read */
 311
 312 int sn_stage_write (sn_stage_t *s, FILE *fh)
 313 {
 314   int i;
 315
 316   if (s->comparators_num <= 0)
 317     return (0);
 318
 319   for (i = 0; i < s->comparators_num; i++)
 320     fprintf (fh, "%i %i\n",
 321         SN_COMP_MIN (s->comparators + i),
 322         SN_COMP_MAX (s->comparators + i));
 323   fprintf (fh, "\n");
 324
 325   return (0);
 326 } /* int sn_stage_write */
 327
 328 /* vim: set shiftwidth=2 softtabstop=2 : */