epan/range.c

   1 /* range.c
   2  * Range routines
   3  *
   4  * Dick Gooris <gooris@lucent.com>
   5  * Ulf Lamping <ulf.lamping@web.de>
   6  *
   7  * Wireshark - Network traffic analyzer
   8  * By Gerald Combs <gerald@wireshark.org>
   9  * Copyright 1998 Gerald Combs
  10  *
  11  * This program is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU General Public License
  13  * as published by the Free Software Foundation; either version 2
  14  * of the License, or (at your option) any later version.
  15  *
  16  * This program is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public License
  22  * along with this program; if not, write to the Free Software
  23  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  24  */
  25
  26 #include "config.h"
  27
  28 #include <string.h>
  29 #include <stdlib.h>
  30 #include <errno.h>
  31
  32 #include <glib.h>
  33
  34 #include <epan/frame_data.h>
  35
  36 #include <epan/range.h>
  37 #include <stdio.h>
  38
  39 /*
  40  * Size of the header of a range_t.
  41  */
  42 #define RANGE_HDR_SIZE (sizeof (range_t) - sizeof (range_admin_t))
  43
  44 /* Allocate an empty range. */
  45 range_t *range_empty(wmem_allocator_t *scope)
  46 {
  47    range_t *range;
  48
  49    range = (range_t *)wmem_alloc(scope, RANGE_HDR_SIZE);
  50    range->nranges = 0;
  51    return range;
  52 }
  53
  54 /******************** Range Entry Parser *********************************/
  55
  56 /* Converts a range string to a fast comparable array of ranges.
  57  * The parameter 'es' points to the string to be converted.
  58  * The parameter 'max_value' specifies the maximum value in a
  59  * range.
  60  *
  61  * This function allocates a range_t large enough to hold the number
  62  * of ranges specified, and fills the array range->ranges containing
  63  * low and high values with the number of ranges being range->nranges.
  64  * After having called this function, the function value_is_in_range()
  65  * determines whether a given number is within the range or not.
  66  *
  67  * In case of a single number, we make a range where low is equal to high.
  68  * We take care on wrongly entered ranges; opposite order will be taken
  69  * care of.
  70  *
  71  * The following syntax is accepted :
  72  *
  73  *   1-20,30-40     Range from 1 to 20, and packets 30 to 40
  74  *   -20,30         Range from 1 to 20, and packet 30
  75  *   20,30,40-      20, 30, and the range from 40 to the end
  76  *   20-10,30-25    Range from 10 to 20, and from 25 to 30
  77  *   -              All values
  78  */
  79
  80 convert_ret_t
  81 range_convert_str(wmem_allocator_t *scope, range_t **rangep, const gchar *es, guint32 max_value)
  82 {
  83    return range_convert_str_work(scope, rangep, es, max_value, TRUE);
  84 }
  85
  86 /*  This version of range_convert_str() allows the caller to specify whether
  87  *  values in excess of the range's specified maximum should cause an error or
  88  *  be silently lowered.
  89  *  XXX - both the function and the variable could probably use better names.
  90  */
  91 convert_ret_t
  92 range_convert_str_work(wmem_allocator_t *scope, range_t **rangep, const gchar *es, guint32 max_value,
  93                        gboolean err_on_max)
  94 {
  95
  96    range_t       *range;
  97    guint         nranges;
  98    const gchar   *p;
  99    char          *endp;
 100    gchar         c;
 101    guint         i;
 102    guint32       tmp;
 103    unsigned long val;
 104
 105    if ( (rangep == NULL) || (es == NULL) )
 106       return CVT_SYNTAX_ERROR;
 107
 108    /* Allocate a range; this has room for one subrange. */
 109    range = (range_t *)wmem_alloc(scope, RANGE_HDR_SIZE + sizeof (range_admin_t));
 110    range->nranges = 0;
 111    nranges = 1;
 112
 113    /* Process the ranges separately until we get a comma or end of string.
 114     *
 115     * We build a structure array called ranges of high and low values. After the
 116     * following loop, we have the nranges variable which tells how many ranges
 117     * were found. The number of individual ranges is limited to 'MaxRanges'
 118     */
 119
 120    p = es;
 121    for (;;) {
 122       /* Skip white space. */
 123       while ((c = *p) == ' ' || c == '\t')
 124          p++;
 125       if (c == '\0')
 126          break;
 127
 128       /* This must be a subrange.  Make sure we have room for it. */
 129       if (range->nranges >= nranges) {
 130          /* Grow the structure.
 131           * 4 is an arbitrarily chosen number.
 132           * We start with 1, under the assumption that people
 133           * will often give a single number or range, and then
 134           * proceed to keep it a multiple of 4.
 135           */
 136          if (nranges == 1)
 137             nranges = 4;
 138          else
 139             nranges += 4;
 140          range = (range_t *)wmem_realloc(scope, range, RANGE_HDR_SIZE +
 141                                       nranges*sizeof (range_admin_t));
 142       }
 143
 144       if (c == '-') {
 145          /* Subrange starts with 1. */
 146          range->ranges[range->nranges].low = 1;
 147       } else if (g_ascii_isdigit(c)) {
 148          /* Subrange starts with the specified number */
 149          errno = 0;
 150          val = strtoul(p, &endp, 0);
 151          if (p == endp) {
 152             /* That wasn't a valid number. */
 153             wmem_free(scope, range);
 154             return CVT_SYNTAX_ERROR;
 155          }
 156          if (errno == ERANGE || val > max_value) {
 157             /* That was valid, but it's too big.  Return an error if requested
 158              * (e.g., except when reading from the preferences file).
 159              */
 160             if (err_on_max) {
 161                wmem_free(scope, range);
 162                return CVT_NUMBER_TOO_BIG;
 163             } else {
 164                /* Silently use the range's maximum value */
 165                val = max_value;
 166             }
 167          }
 168          p = endp;
 169          range->ranges[range->nranges].low = (guint32)val;
 170
 171          /* Skip white space. */
 172          while ((c = *p) == ' ' || c == '\t')
 173             p++;
 174       } else {
 175          /* Neither empty nor a number. */
 176          wmem_free(scope, range);
 177          return CVT_SYNTAX_ERROR;
 178       }
 179
 180       if (c == '-') {
 181          /* There's a hyphen in the range.  Skip past it. */
 182          p++;
 183
 184          /* Skip white space. */
 185          while ((c = *p) == ' ' || c == '\t')
 186             p++;
 187
 188          if (c == ',' || c == '\0') {
 189             /* End of subrange string; that means the subrange ends
 190              * with max_value.
 191              */
 192             range->ranges[range->nranges].high = max_value;
 193          } else if (g_ascii_isdigit(c)) {
 194             /* Subrange ends with the specified number. */
 195             errno = 0;
 196             val = strtoul(p, &endp, 0);
 197             if (p == endp) {
 198                /* That wasn't a valid number. */
 199                wmem_free(scope, range);
 200                return CVT_SYNTAX_ERROR;
 201             }
 202             if (errno == ERANGE || val > max_value) {
 203                /* That was valid, but it's too big.  Return an error if requested
 204                 * (e.g., except when reading from the preferences file).
 205                 */
 206                if (err_on_max) {
 207                   wmem_free(scope, range);
 208                   return CVT_NUMBER_TOO_BIG;
 209                } else {
 210                   /* Silently use the range's maximum value */
 211                   val = max_value;
 212                }
 213             }
 214             p = endp;
 215             range->ranges[range->nranges].high = (guint32)val;
 216
 217             /* Skip white space. */
 218             while ((c = *p) == ' ' || c == '\t')
 219                p++;
 220          } else {
 221             /* Neither empty nor a number. */
 222             wmem_free(scope, range);
 223             return CVT_SYNTAX_ERROR;
 224          }
 225       } else if (c == ',' || c == '\0') {
 226          /* End of subrange string; that means there's no hyphen
 227           * in the subrange, so the start and the end are the same.
 228           */
 229          range->ranges[range->nranges].high = range->ranges[range->nranges].low;
 230       } else {
 231          /* Invalid character. */
 232          wmem_free(scope, range);
 233          return CVT_SYNTAX_ERROR;
 234       }
 235       range->nranges++;
 236
 237       if (c == ',') {
 238          /* Subrange is followed by a comma; skip it. */
 239          p++;
 240       }
 241    }
 242
 243    /* Now we are going through the low and high values, and check
 244     * whether they are in a proper order. Low should be equal or lower
 245     * than high. So, go through the loop and swap if needed.
 246     */
 247    for (i=0; i < range->nranges; i++) {
 248       if (range->ranges[i].low > range->ranges[i].high) {
 249          tmp = range->ranges[i].low;
 250          range->ranges[i].low  = range->ranges[i].high;
 251          range->ranges[i].high = tmp;
 252       }
 253    }
 254
 255    /* In case we want to know what the result ranges are :
 256     *
 257     * for (i=0; i < range->nranges; i++) {
 258     *  printf("Function : range_convert_str L=%u \t H=%u\n",range->ranges[i].low,range->ranges[i].high);
 259     * }
 260     *
 261     */
 262    *rangep = range;
 263    return CVT_NO_ERROR;
 264 } /* range_convert_str */
 265
 266 /* This function returns TRUE if a given value is within one of the ranges
 267  * stored in the ranges array.
 268  */
 269 gboolean
 270 value_is_in_range(range_t *range, guint32 val)
 271 {
 272    guint i;
 273
 274    if (range) {
 275       for (i=0; i < range->nranges; i++) {
 276          if (val >= range->ranges[i].low && val <= range->ranges[i].high)
 277             return TRUE;
 278       }
 279    }
 280    return(FALSE);
 281 }
 282
 283 /* This function returns TRUE if val has successfully been added to
 284  * a range.  This may extend an existing range or create a new one
 285  */
 286 gboolean
 287 range_add_value(wmem_allocator_t *scope, range_t **range, guint32 val)
 288 {
 289    guint i;
 290
 291    if ((range) && (*range)) {
 292       for (i=0; i < (*range)->nranges; i++) {
 293          if (val >= (*range)->ranges[i].low && val <= (*range)->ranges[i].high)
 294             return TRUE;
 295
 296          if (val == (*range)->ranges[i].low-1)
 297          {
 298              /* Sink to a new low */
 299              (*range)->ranges[i].low = val;
 300              return TRUE;
 301          }
 302
 303          if (val == (*range)->ranges[i].high+1)
 304          {
 305              /* Reach a new high */
 306              (*range)->ranges[i].high = val;
 307              return TRUE;
 308          }
 309       }
 310
 311       (*range) = (range_t *)wmem_realloc(scope, (*range), RANGE_HDR_SIZE +
 312                                 ((*range)->nranges+1)*sizeof (range_admin_t));
 313       (*range)->nranges++;
 314       (*range)->ranges[i].low = (*range)->ranges[i].high = val;
 315       return TRUE;
 316    }
 317    return(FALSE);
 318 }
 319
 320 /* This function returns TRUE if val has successfully been removed from
 321  * a range.  This may delete an existing range
 322  */
 323 gboolean
 324 range_remove_value(wmem_allocator_t *scope, range_t **range, guint32 val)
 325 {
 326    guint i, j, new_j;
 327    range_t *new_range;
 328
 329    if ((range) && (*range)) {
 330       for (i=0; i < (*range)->nranges; i++) {
 331
 332           /* value is in the middle of the range, so it can't really be removed */
 333          if (val > (*range)->ranges[i].low && val < (*range)->ranges[i].high)
 334             return TRUE;
 335
 336          if ((val ==  (*range)->ranges[i].low) && (val == (*range)->ranges[i].high))
 337          {
 338              /* Remove the range item entirely */
 339              new_range = (range_t*)wmem_alloc(scope, RANGE_HDR_SIZE + ((*range)->nranges-1)*sizeof (range_admin_t));
 340              new_range->nranges = (*range)->nranges-1;
 341              for (j=0, new_j = 0; j < (*range)->nranges; j++) {
 342
 343                  /* Skip the current range */
 344                  if (j == i)
 345                      continue;
 346
 347                  new_range->ranges[new_j].low = (*range)->ranges[j].low;
 348                  new_range->ranges[new_j].high = (*range)->ranges[j].high;
 349                  new_j++;
 350              }
 351
 352              wmem_free(scope, *range);
 353              *range = new_range;
 354              return TRUE;
 355          }
 356
 357          if (val == (*range)->ranges[i].low)
 358          {
 359              /* Raise low */
 360              (*range)->ranges[i].low++;
 361              return TRUE;
 362          }
 363
 364          if (val == (*range)->ranges[i].high)
 365          {
 366              /* Reach a new high */
 367              (*range)->ranges[i].high--;
 368              return TRUE;
 369          }
 370       }
 371       return TRUE;
 372    }
 373    return(FALSE);
 374 }
 375
 376 /* This function returns TRUE if the two given range_t's are equal.
 377  */
 378 gboolean
 379 ranges_are_equal(range_t *a, range_t *b)
 380 {
 381    guint i;
 382
 383    if ( (a == NULL) || (b == NULL) )
 384        return FALSE;
 385
 386    if (a->nranges != b->nranges)
 387       return FALSE;
 388
 389    for (i=0; i < a->nranges; i++) {
 390       if (a->ranges[i].low != b->ranges[i].low)
 391          return FALSE;
 392
 393       if (a->ranges[i].high != b->ranges[i].high)
 394          return FALSE;
 395    }
 396
 397    return TRUE;
 398
 399 }
 400
 401 /* This function calls the provided callback function for each value in
 402  * in the range.
 403  */
 404 void
 405 range_foreach(range_t *range, void (*callback)(guint32 val, gpointer ptr), gpointer ptr)
 406 {
 407    guint32 i, j;
 408
 409    if (range && callback) {
 410       for (i=0; i < range->nranges; i++) {
 411          for (j = range->ranges[i].low; j <= range->ranges[i].high; j++)
 412             callback(j, ptr);
 413       }
 414    }
 415 }
 416
 417 /* This function converts a range_t to a (wmem-allocated) string.  */
 418 char *
 419 range_convert_range(wmem_allocator_t *scope, const range_t *range)
 420 {
 421    guint32 i;
 422    gboolean prepend_comma = FALSE;
 423    wmem_strbuf_t *strbuf;
 424
 425    strbuf=wmem_strbuf_new(scope, "");
 426
 427    if (range) {
 428       for (i=0; i < range->nranges; i++) {
 429          if (range->ranges[i].low == range->ranges[i].high) {
 430             wmem_strbuf_append_printf(strbuf, "%s%u", prepend_comma?",":"", range->ranges[i].low);
 431          } else {
 432             wmem_strbuf_append_printf(strbuf, "%s%u-%u", prepend_comma?",":"", range->ranges[i].low, range->ranges[i].high);
 433          }
 434          prepend_comma = TRUE;
 435       }
 436    }
 437    return wmem_strbuf_finalize(strbuf);
 438 }
 439
 440 /* Create a copy of a range. */
 441 range_t *
 442 range_copy(wmem_allocator_t *scope, range_t *src)
 443 {
 444    range_t *dst;
 445    size_t range_size;
 446
 447    if (src == NULL)
 448        return NULL;
 449
 450    range_size = RANGE_HDR_SIZE + src->nranges*sizeof (range_admin_t);
 451    dst = (range_t *)wmem_memdup(scope, src, range_size);
 452    return dst;
 453 }
 454
 455 #if 0
 456 /* This is a debug function to check the range functionality */
 457 static void
 458 value_is_in_range_check(range_t *range, guint32 val)
 459 {
 460    /* Print the result for a given value */
 461    printf("Function : value_is_in_range_check Number %u\t",val);
 462
 463    if (value_is_in_range(range, val)) {
 464       printf("is in range\n");
 465    } else {
 466       printf("is not in range\n");
 467    }
 468 }
 469 #endif
 470
 471 /*
 472  * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
 473  *
 474  * Local Variables:
 475  * c-basic-offset: 3
 476  * tab-width: 8
 477  * indent-tabs-mode: nil
 478  * End:
 479  *
 480  * ex: set shiftwidth=3 tabstop=8 expandtab:
 481  * :indentSize=3:tabSize=8:noTabs=true:
 482  */