lib/numberset.c

   1 /* numberset.c */
   2
   3 /*
   4  * Copyright (C) 2012 by Werner Lemberg.
   5  *
   6  * This file is part of the ttfautohint library, and may only be used,
   7  * modified, and distributed under the terms given in `COPYING'.  By
   8  * continuing to use, modify, or distribute this file you indicate that you
   9  * have read `COPYING' and understand and accept it fully.
  10  *
  11  * The file `COPYING' mentioned in the previous paragraph is distributed
  12  * with the ttfautohint library.
  13  */
  14
  15
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include <string.h>
  19 #include <ctype.h>
  20 #include <limits.h>
  21
  22 #include "numberset.h"
  23
  24
  25 const char*
  26 number_set_parse(const char* s,
  27                  number_range** number_set,
  28                  int min,
  29                  int max)
  30 {
  31   number_range* cur = NULL;
  32   number_range* new_range;
  33   number_range* tmp;
  34
  35   const char* last_pos = s;
  36   int last_end = -1;
  37   int t;
  38   number_range* error_code = NULL;
  39
  40
  41   if (min < 0)
  42     min = 0;
  43   if (max < 0)
  44     max = INT_MAX;
  45   if (min > max)
  46   {
  47     t = min;
  48     min = max;
  49     max = t;
  50   }
  51
  52   for (;;)
  53   {
  54     int digit;
  55     int n = -1;
  56     int m = -1;
  57
  58
  59     while (isspace(*s))
  60       s++;
  61
  62     if (*s == ',')
  63     {
  64       s++;
  65       continue;
  66     }
  67     else if (*s == '-')
  68     {
  69       last_pos = s;
  70       n = min;
  71     }
  72     else if (isdigit(*s))
  73     {
  74       last_pos = s;
  75       n = 0;
  76       do
  77       {
  78         digit = *s - '0';
  79         if (n > INT_MAX / 10
  80             || (n == INT_MAX / 10 && digit > 5))
  81         {
  82           error_code = NUMBERSET_OVERFLOW;
  83           break;
  84         }
  85
  86         n = n * 10 + digit;
  87         s++;
  88       } while (isdigit(*s));
  89
  90       while (isspace(*s))
  91         s++;
  92     }
  93     else if (*s == '\0')
  94       break; /* end of data */
  95     else
  96     {
  97       error_code = NUMBERSET_INVALID_CHARACTER;
  98       break;
  99     }
 100
 101     if (*s == '-')
 102     {
 103       s++;
 104
 105       while (isspace(*s))
 106         s++;
 107
 108       if (isdigit(*s))
 109       {
 110         m = 0;
 111         do
 112         {
 113           digit = *s - '0';
 114           if (m > INT_MAX / 10
 115               || (m == INT_MAX / 10 && digit > 5))
 116           {
 117             error_code = NUMBERSET_OVERFLOW;
 118             break;
 119           }
 120
 121           m = m * 10 + digit;
 122           s++;
 123         } while (isdigit(*s));
 124       }
 125     }
 126     else
 127       m = n;
 128
 129     if (m == -1)
 130       m = max;
 131
 132     if (m < n)
 133     {
 134       t = n;
 135       n = m;
 136       m = t;
 137     }
 138
 139     if (n < min || m > max)
 140     {
 141       error_code = NUMBERSET_INVALID_RANGE;
 142       break;
 143     }
 144
 145     if (last_end >= n)
 146     {
 147       error_code = NUMBERSET_OVERLAPPING_RANGES;
 148       break;
 149     }
 150
 151     if (cur
 152         && last_end + 1 == n)
 153     {
 154       /* merge adjacent ranges */
 155       cur->end = m;
 156     }
 157     else
 158     {
 159       if (number_set)
 160       {
 161         new_range = (number_range*)malloc(sizeof (number_range));
 162         if (!new_range)
 163         {
 164           error_code = NUMBERSET_ALLOCATION_ERROR;
 165           break;
 166         }
 167
 168         /* prepend new range to list */
 169         new_range->start = n;
 170         new_range->end = m;
 171         new_range->next = cur;
 172         cur = new_range;
 173       }
 174
 175       last_end = m;
 176     }
 177   } /* end of loop */
 178
 179   if (error_code)
 180   {
 181     /* deallocate data */
 182     while (cur)
 183     {
 184       tmp = cur;
 185       cur = cur->next;
 186       free(tmp);
 187     }
 188
 189     s = last_pos;
 190     if (number_set)
 191       *number_set = error_code;
 192   }
 193   else
 194   {
 195     /* success; now reverse list to have elements in ascending order */
 196     number_range* list = NULL;
 197
 198
 199     while (cur)
 200     {
 201       tmp = cur;
 202       cur = cur->next;
 203       tmp->next = list;
 204       list = tmp;
 205     }
 206
 207     if (number_set)
 208       *number_set = list;
 209   }
 210
 211   return s;
 212 }
 213
 214
 215 void
 216 number_set_free(number_range* number_set)
 217 {
 218   number_range* nr = number_set;
 219   number_range* tmp;
 220
 221
 222   while (nr)
 223   {
 224     tmp = nr;
 225     nr = nr->next;
 226     free(tmp);
 227   }
 228 }
 229
 230
 231 char*
 232 number_set_show(number_range* number_set,
 233                 int min,
 234                 int max)
 235 {
 236   char* s;
 237   char* s_new;
 238   size_t s_len;
 239   size_t s_len_new;
 240
 241   number_range* nr = number_set;
 242
 243   char tmp[256];
 244   int tmp_len;
 245   int t;
 246   const char *comma;
 247
 248
 249   if (min < 0)
 250     min = 0;
 251   if (max < 0)
 252     max = INT_MAX;
 253   if (min > max)
 254   {
 255     t = min;
 256     min = max;
 257     max = t;
 258   }
 259
 260   /* we return an empty string for an empty number set */
 261   /* (this is, number_set == NULL or unsuitable `min' and `max' values) */
 262   s = (char*)malloc(1);
 263   if (!s)
 264     return NULL;
 265   *s = '\0';
 266
 267   s_len = 1;
 268
 269   while (nr)
 270   {
 271     if (nr->start > max)
 272       return s;
 273     if (nr->end < min)
 274       goto Again;
 275
 276     comma = (s_len == 1) ? "" : ", ";
 277
 278     if (nr->start <= min
 279         && nr->end >= max)
 280       tmp_len = sprintf(tmp, "-");
 281     else if (nr->start <= min)
 282       tmp_len = sprintf(tmp, "-%i",
 283                              nr->end);
 284     else if (nr->end >= max)
 285       tmp_len = sprintf(tmp, "%s%i-",
 286                              comma, nr->start);
 287     else
 288     {
 289       if (nr->start == nr->end)
 290         tmp_len = sprintf(tmp, "%s%i",
 291                                comma, nr->start);
 292       else
 293         tmp_len = sprintf(tmp, "%s%i-%i",
 294                                comma, nr->start, nr->end);
 295     }
 296
 297     s_len_new = s_len + tmp_len;
 298     s_new = (char*)realloc(s, s_len_new);
 299     if (!s_new)
 300     {
 301       free(s);
 302       return NULL;
 303     }
 304     strcpy(s_new + s_len - 1, tmp);
 305     s_len = s_len_new;
 306     s = s_new;
 307
 308   Again:
 309     nr = nr->next;
 310   }
 311
 312   return s;
 313 }
 314
 315
 316 int
 317 number_set_is_element(number_range* number_set,
 318                       int number)
 319 {
 320   number_range* nr = number_set;
 321
 322
 323   while (nr)
 324   {
 325     if (number < nr->start)
 326       return 0;
 327     if (nr->start <= number
 328         && number <= nr->end)
 329       return 1;
 330     nr = nr->next;
 331   }
 332
 333   return 0;
 334 }
 335
 336 /* end of numberset.c */