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   number_range* tmp;
 234
 235
 236   while (nr)
 237   {
 238     tmp = nr;
 239     nr = nr->next;
 240     free(tmp);
 241   }
 242 }
 243
 244
 245 char*
 246 number_set_show(number_range* number_set,
 247                 int min,
 248                 int max)
 249 {
 250   char* s;
 251   char* s_new;
 252   size_t s_len;
 253   size_t s_len_new;
 254
 255   number_range* nr = number_set;
 256
 257   char tmp[256];
 258   int tmp_len;
 259   int t;
 260   const char *comma;
 261
 262
 263   if (min < 0)
 264     min = 0;
 265   if (max < 0)
 266     max = INT_MAX;
 267   if (min > max)
 268   {
 269     t = min;
 270     min = max;
 271     max = t;
 272   }
 273
 274   /* we return an empty string for an empty number set */
 275   /* (this is, number_set == NULL or unsuitable `min' and `max' values) */
 276   s = (char*)malloc(1);
 277   if (!s)
 278     return NULL;
 279   *s = '\0';
 280
 281   s_len = 1;
 282
 283   while (nr)
 284   {
 285     if (nr->start > max)
 286       return s;
 287     if (nr->end < min)
 288       goto Again;
 289
 290     comma = (s_len == 1) ? "" : ", ";
 291
 292     if (nr->start <= min
 293         && nr->end >= max)
 294       tmp_len = sprintf(tmp, "-");
 295     else if (nr->start <= min)
 296       tmp_len = sprintf(tmp, "-%i",
 297                              nr->end);
 298     else if (nr->end >= max)
 299       tmp_len = sprintf(tmp, "%s%i-",
 300                              comma, nr->start);
 301     else
 302     {
 303       if (nr->start == nr->end)
 304         tmp_len = sprintf(tmp, "%s%i",
 305                                comma, nr->start);
 306       else
 307         tmp_len = sprintf(tmp, "%s%i-%i",
 308                                comma, nr->start, nr->end);
 309     }
 310
 311     s_len_new = s_len + tmp_len;
 312     s_new = (char*)realloc(s, s_len_new);
 313     if (!s_new)
 314     {
 315       free(s);
 316       return NULL;
 317     }
 318     strcpy(s_new + s_len - 1, tmp);
 319     s_len = s_len_new;
 320     s = s_new;
 321
 322   Again:
 323     nr = nr->next;
 324   }
 325
 326   return s;
 327 }
 328
 329
 330 int
 331 number_set_is_element(number_range* number_set,
 332                       int number)
 333 {
 334   number_range* nr = number_set;
 335
 336
 337   while (nr)
 338   {
 339     if (number < nr->start)
 340       return 0;
 341     if (nr->start <= number
 342         && number <= nr->end)
 343       return 1;
 344     nr = nr->next;
 345   }
 346
 347   return 0;
 348 }
 349
 350 /* end of numberset.c */