lib/numberset.c

   1 /* numberset.c */
   2
   3 /*
   4  * Copyright (C) 2012-2014 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_start = -1;
  37   int last_end = -1;
  38   int t;
  39   number_range* error_code = NULL;
  40
  41
  42   if (!s)
  43     return NULL;
  44
  45   if (min < 0)
  46     min = 0;
  47   if (max < 0)
  48     max = INT_MAX;
  49   if (min > max)
  50   {
  51     t = min;
  52     min = max;
  53     max = t;
  54   }
  55
  56   for (;;)
  57   {
  58     int digit;
  59     int n = -1;
  60     int m = -1;
  61
  62
  63     while (isspace(*s))
  64       s++;
  65
  66     if (*s == ',')
  67     {
  68       s++;
  69       continue;
  70     }
  71     else if (*s == '-')
  72     {
  73       last_pos = s;
  74       n = min;
  75     }
  76     else if (isdigit(*s))
  77     {
  78       last_pos = s;
  79       n = 0;
  80       do
  81       {
  82         digit = *s - '0';
  83         if (n > INT_MAX / 10
  84             || (n == INT_MAX / 10 && digit > 5))
  85         {
  86           error_code = NUMBERSET_OVERFLOW;
  87           break;
  88         }
  89
  90         n = n * 10 + digit;
  91         s++;
  92       } while (isdigit(*s));
  93
  94       if (error_code)
  95         break;
  96
  97       while (isspace(*s))
  98         s++;
  99     }
 100     else if (*s == '\0')
 101       break; /* end of data */
 102     else
 103     {
 104       error_code = NUMBERSET_INVALID_CHARACTER;
 105       break;
 106     }
 107
 108     if (*s == '-')
 109     {
 110       s++;
 111
 112       while (isspace(*s))
 113         s++;
 114
 115       if (isdigit(*s))
 116       {
 117         m = 0;
 118         do
 119         {
 120           digit = *s - '0';
 121           if (m > INT_MAX / 10
 122               || (m == INT_MAX / 10 && digit > 5))
 123           {
 124             error_code = NUMBERSET_OVERFLOW;
 125             break;
 126           }
 127
 128           m = m * 10 + digit;
 129           s++;
 130         } while (isdigit(*s));
 131
 132         if (error_code)
 133           break;
 134       }
 135     }
 136     else
 137       m = n;
 138
 139     if (m == -1)
 140       m = max;
 141
 142     if (m < n)
 143     {
 144       t = n;
 145       n = m;
 146       m = t;
 147     }
 148
 149     if (n < min || m > max)
 150     {
 151       error_code = NUMBERSET_INVALID_RANGE;
 152       break;
 153     }
 154
 155     if (last_end >= n)
 156     {
 157       if (last_start >= m)
 158         error_code = NUMBERSET_NOT_ASCENDING;
 159       else
 160         error_code = NUMBERSET_OVERLAPPING_RANGES;
 161       break;
 162     }
 163
 164     if (cur
 165         && last_end + 1 == n)
 166     {
 167       /* merge adjacent ranges */
 168       cur->end = m;
 169     }
 170     else
 171     {
 172       if (number_set)
 173       {
 174         new_range = (number_range*)malloc(sizeof (number_range));
 175         if (!new_range)
 176         {
 177           error_code = NUMBERSET_ALLOCATION_ERROR;
 178           break;
 179         }
 180
 181         /* prepend new range to list */
 182         new_range->start = n;
 183         new_range->end = m;
 184         new_range->next = cur;
 185         cur = new_range;
 186       }
 187     }
 188
 189     last_start = n;
 190     last_end = m;
 191   } /* end of loop */
 192
 193   if (error_code)
 194   {
 195     number_set_free(cur);
 196
 197     s = last_pos;
 198     if (number_set)
 199       *number_set = error_code;
 200   }
 201   else
 202   {
 203     /* success; now reverse list to have elements in ascending order */
 204     number_range* list = NULL;
 205
 206
 207     while (cur)
 208     {
 209       tmp = cur;
 210       cur = cur->next;
 211       tmp->next = list;
 212       list = tmp;
 213     }
 214
 215     if (number_set)
 216       *number_set = list;
 217   }
 218
 219   return s;
 220 }
 221
 222
 223 void
 224 number_set_free(number_range* number_set)
 225 {
 226   number_range* nr = number_set;
 227
 228
 229   while (nr)
 230   {
 231     number_range* tmp;
 232
 233
 234     tmp = nr;
 235     nr = nr->next;
 236     free(tmp);
 237   }
 238 }
 239
 240
 241 char*
 242 number_set_show(number_range* number_set,
 243                 int min,
 244                 int max)
 245 {
 246   char* s;
 247   char* s_new;
 248   size_t s_len;
 249   size_t s_len_new;
 250
 251   number_range* nr = number_set;
 252
 253   char tmp[256];
 254   int tmp_len;
 255   int t;
 256   const char *comma;
 257
 258
 259   if (min < 0)
 260     min = 0;
 261   if (max < 0)
 262     max = INT_MAX;
 263   if (min > max)
 264   {
 265     t = min;
 266     min = max;
 267     max = t;
 268   }
 269
 270   /* we return an empty string for an empty number set */
 271   /* (this is, number_set == NULL or unsuitable `min' and `max' values) */
 272   s = (char*)malloc(1);
 273   if (!s)
 274     return NULL;
 275   *s = '\0';
 276
 277   s_len = 1;
 278
 279   while (nr)
 280   {
 281     if (nr->start > max)
 282       return s;
 283     if (nr->end < min)
 284       goto Again;
 285
 286     comma = (s_len == 1) ? "" : ", ";
 287
 288     if (nr->start <= min
 289         && nr->end >= max)
 290       tmp_len = sprintf(tmp, "-");
 291     else if (nr->start <= min)
 292       tmp_len = sprintf(tmp, "-%i",
 293                              nr->end);
 294     else if (nr->end >= max)
 295       tmp_len = sprintf(tmp, "%s%i-",
 296                              comma, nr->start);
 297     else
 298     {
 299       if (nr->start == nr->end)
 300         tmp_len = sprintf(tmp, "%s%i",
 301                                comma, nr->start);
 302       else
 303         tmp_len = sprintf(tmp, "%s%i-%i",
 304                                comma, nr->start, nr->end);
 305     }
 306
 307     s_len_new = s_len + tmp_len;
 308     s_new = (char*)realloc(s, s_len_new);
 309     if (!s_new)
 310     {
 311       free(s);
 312       return NULL;
 313     }
 314     strcpy(s_new + s_len - 1, tmp);
 315     s_len = s_len_new;
 316     s = s_new;
 317
 318   Again:
 319     nr = nr->next;
 320   }
 321
 322   return s;
 323 }
 324
 325
 326 int
 327 number_set_is_element(number_range* number_set,
 328                       int number)
 329 {
 330   number_range* nr = number_set;
 331
 332
 333   while (nr)
 334   {
 335     if (number < nr->start)
 336       return 0;
 337     if (nr->start <= number
 338         && number <= nr->end)
 339       return 1;
 340     nr = nr->next;
 341   }
 342
 343   return 0;
 344 }
 345
 346
 347 int
 348 number_set_get_first(number_set_iter* iter_p)
 349 {
 350   if (!iter_p || !iter_p->range)
 351     return 0;
 352
 353   iter_p->val = iter_p->range->start;
 354
 355   return iter_p->val;
 356 }
 357
 358
 359 int
 360 number_set_get_next(number_set_iter* iter_p)
 361 {
 362   if (!iter_p || !iter_p->range)
 363     return 0;
 364
 365   iter_p->val++;
 366
 367   if (iter_p->val > iter_p->range->end)
 368   {
 369     iter_p->range = iter_p->range->next;
 370
 371     if (iter_p->range)
 372       iter_p->val = iter_p->range->start;
 373   }
 374
 375   return iter_p->val;
 376 }
 377
 378 /* end of numberset.c */