lib/numberset.c

   1 /* numberset.c */
   2
   3 /*
   4  * Copyright (C) 2012-2013 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     /* deallocate data */
 196     while (cur)
 197     {
 198       tmp = cur;
 199       cur = cur->next;
 200       free(tmp);
 201     }
 202
 203     s = last_pos;
 204     if (number_set)
 205       *number_set = error_code;
 206   }
 207   else
 208   {
 209     /* success; now reverse list to have elements in ascending order */
 210     number_range* list = NULL;
 211
 212
 213     while (cur)
 214     {
 215       tmp = cur;
 216       cur = cur->next;
 217       tmp->next = list;
 218       list = tmp;
 219     }
 220
 221     if (number_set)
 222       *number_set = list;
 223   }
 224
 225   return s;
 226 }
 227
 228
 229 void
 230 number_set_free(number_range* number_set)
 231 {
 232   number_range* nr = number_set;
 233
 234
 235   while (nr)
 236   {
 237     number_range* tmp;
 238
 239
 240     tmp = nr;
 241     nr = nr->next;
 242     free(tmp);
 243   }
 244 }
 245
 246
 247 char*
 248 number_set_show(number_range* number_set,
 249                 int min,
 250                 int max)
 251 {
 252   char* s;
 253   char* s_new;
 254   size_t s_len;
 255   size_t s_len_new;
 256
 257   number_range* nr = number_set;
 258
 259   char tmp[256];
 260   int tmp_len;
 261   int t;
 262   const char *comma;
 263
 264
 265   if (min < 0)
 266     min = 0;
 267   if (max < 0)
 268     max = INT_MAX;
 269   if (min > max)
 270   {
 271     t = min;
 272     min = max;
 273     max = t;
 274   }
 275
 276   /* we return an empty string for an empty number set */
 277   /* (this is, number_set == NULL or unsuitable `min' and `max' values) */
 278   s = (char*)malloc(1);
 279   if (!s)
 280     return NULL;
 281   *s = '\0';
 282
 283   s_len = 1;
 284
 285   while (nr)
 286   {
 287     if (nr->start > max)
 288       return s;
 289     if (nr->end < min)
 290       goto Again;
 291
 292     comma = (s_len == 1) ? "" : ", ";
 293
 294     if (nr->start <= min
 295         && nr->end >= max)
 296       tmp_len = sprintf(tmp, "-");
 297     else if (nr->start <= min)
 298       tmp_len = sprintf(tmp, "-%i",
 299                              nr->end);
 300     else if (nr->end >= max)
 301       tmp_len = sprintf(tmp, "%s%i-",
 302                              comma, nr->start);
 303     else
 304     {
 305       if (nr->start == nr->end)
 306         tmp_len = sprintf(tmp, "%s%i",
 307                                comma, nr->start);
 308       else
 309         tmp_len = sprintf(tmp, "%s%i-%i",
 310                                comma, nr->start, nr->end);
 311     }
 312
 313     s_len_new = s_len + tmp_len;
 314     s_new = (char*)realloc(s, s_len_new);
 315     if (!s_new)
 316     {
 317       free(s);
 318       return NULL;
 319     }
 320     strcpy(s_new + s_len - 1, tmp);
 321     s_len = s_len_new;
 322     s = s_new;
 323
 324   Again:
 325     nr = nr->next;
 326   }
 327
 328   return s;
 329 }
 330
 331
 332 int
 333 number_set_is_element(number_range* number_set,
 334                       int number)
 335 {
 336   number_range* nr = number_set;
 337
 338
 339   while (nr)
 340   {
 341     if (number < nr->start)
 342       return 0;
 343     if (nr->start <= number
 344         && number <= nr->end)
 345       return 1;
 346     nr = nr->next;
 347   }
 348
 349   return 0;
 350 }
 351
 352 /* end of numberset.c */