epan/dissectors/packet-epl-profile-parser.c

   1 /* packet-epl-profile-parser.c
   2  * Routines for reading in Ethernet POWERLINK XDD and CANopen EDS profiles
   3  * (Ethernet POWERLINK XML Device Description (DS301) Draft Standard v1.2.0)
   4  *
   5  * Copyright (c) 2017: Karlsruhe Institute of Technology (KIT)
   6  *                     Institute for Anthropomatics and Robotics (IAR)
   7  *                     Intelligent Process Control and Robotics (IPR)
   8  *                     http://rob.ipr.kit.edu/
   9  *
  10  *                     - Ahmad Fatoum <ahmad[AT]a3f.at>
  11  *
  12  * Wireshark - Network traffic analyzer
  13  * By Gerald Combs <gerald@wireshark.org>
  14  * Copyright 1998 Gerald Combs
  15  *
  16  * SPDX-License-Identifier: GPL-2.0-or-later
  17  */
  18
  19 #include "config.h"
  20
  21 #include "packet-epl.h"
  22 #include "ws_attributes.h"
  23
  24 #include <epan/ws_printf.h>
  25 #include <epan/range.h>
  26
  27 #include <string.h>
  28 #include <stdlib.h>
  29
  30 #include <wsutil/strtoi.h>
  31 #include <wsutil/str_util.h>
  32 #include <wsutil/wslog.h>
  33 #include <epan/wmem_scopes.h>
  34
  35 #if defined HAVE_LIBXML2
  36 #include <libxml/xmlversion.h>
  37
  38 #if defined LIBXML_XPATH_ENABLED \
  39 &&  defined LIBXML_SAX1_ENABLED  \
  40 &&  defined LIBXML_TREE_ENABLED
  41 #include <libxml/tree.h>
  42 #include <libxml/parser.h>
  43 #include <libxml/xpath.h>
  44 #include <libxml/xpathInternals.h>
  45
  46 #define PARSE_XDD 1
  47
  48 typedef int xpath_handler(xmlNodeSetPtr, void*);
  49 static xpath_handler populate_object_list, populate_datatype_list, populate_profile_name;
  50
  51 static struct xpath_namespace {
  52         const xmlChar *prefix, *href;
  53 } namespaces[] = {
  54         { BAD_CAST "x",   BAD_CAST "http://www.ethernet-powerlink.org" },
  55         { BAD_CAST "xsi", BAD_CAST "http://www.w3.org/2001/XMLSchema-instance" },
  56         { NULL, NULL }
  57 };
  58
  59 static struct xpath {
  60         const xmlChar *expr;
  61         xpath_handler *handler;
  62 } xpaths[] = {
  63         {
  64                 BAD_CAST "//x:ISO15745Profile[x:ProfileHeader/x:ProfileIdentification='Powerlink_Communication_Profile']/x:ProfileHeader/x:ProfileName",
  65                 populate_profile_name
  66         },
  67         {
  68                 BAD_CAST "//x:ProfileBody[@xsi:type='ProfileBody_CommunicationNetwork_Powerlink']/x:ApplicationLayers/x:DataTypeList/x:defType",
  69                 populate_datatype_list
  70         },
  71         {
  72                 BAD_CAST "//x:ProfileBody[@xsi:type='ProfileBody_CommunicationNetwork_Powerlink']/x:ApplicationLayers/x:ObjectList/x:Object",
  73                 populate_object_list
  74         },
  75         { NULL, NULL }
  76 };
  77
  78
  79 #endif /* LIBXML_XPATH_ENABLED && LIBXML_SAX1_ENABLED && LIBXML_TREE_ENABLED */
  80
  81 #endif /* HAVE_LIBXML2 */
  82
  83 struct datatype {
  84         uint16_t id;
  85         const struct epl_datatype *ptr;
  86 };
  87
  88 static struct typemap_entry {
  89         uint16_t id;
  90         const char *name;
  91         struct epl_datatype *type;
  92 } epl_datatypes[] = {
  93         {0x0001, "Boolean",        NULL},
  94         {0x0002, "Integer8",       NULL},
  95         {0x0003, "Integer16",      NULL},
  96         {0x0004, "Integer32",      NULL},
  97         {0x0005, "Unsigned8",      NULL},
  98         {0x0006, "Unsigned16",     NULL},
  99         {0x0007, "Unsigned32",     NULL},
 100         {0x0008, "Real32",         NULL},
 101         {0x0009, "Visible_String", NULL},
 102         {0x0010, "Integer24",      NULL},
 103         {0x0011, "Real64",         NULL},
 104         {0x0012, "Integer40",      NULL},
 105         {0x0013, "Integer48",      NULL},
 106         {0x0014, "Integer56",      NULL},
 107         {0x0015, "Integer64",      NULL},
 108         {0x000A, "Octet_String",   NULL},
 109         {0x000B, "Unicode_String", NULL},
 110         {0x000C, "Time_of_Day",    NULL},
 111         {0x000D, "Time_Diff",      NULL},
 112         {0x000F, "Domain",         NULL},
 113         {0x0016, "Unsigned24",     NULL},
 114         {0x0018, "Unsigned40",     NULL},
 115         {0x0019, "Unsigned48",     NULL},
 116         {0x001A, "Unsigned56",     NULL},
 117         {0x001B, "Unsigned64",     NULL},
 118         {0x0401, "MAC_ADDRESS",    NULL},
 119         {0x0402, "IP_ADDRESS",     NULL},
 120         {0x0403, "NETTIME",        NULL},
 121         {0x0000, NULL,             NULL}
 122 };
 123
 124 static wmem_map_t *eds_typemap;
 125
 126 struct epl_wmem_iarray {
 127         GEqualFunc equal;
 128         wmem_allocator_t *scope;
 129         GArray *arr;
 130         unsigned cb_id;
 131         uint8_t is_sorted :1;
 132 };
 133
 134 static epl_wmem_iarray_t *epl_wmem_iarray_new(wmem_allocator_t *allocator, const unsigned elem_size, GEqualFunc cmp) G_GNUC_MALLOC;
 135 static void epl_wmem_iarray_insert(epl_wmem_iarray_t *iarr, uint32_t where, range_admin_t *data);
 136 static void epl_wmem_iarray_sort_and_compact(epl_wmem_iarray_t *iarr);
 137
 138 static bool
 139 epl_ishex(const char *num)
 140 {
 141         if (g_str_has_prefix(num, "0x"))
 142                 return true;
 143
 144         for (; g_ascii_isxdigit(*num); num++)
 145                 ;
 146
 147         if (g_ascii_tolower(*num) == 'h')
 148                 return true;
 149
 150         return false;
 151 }
 152
 153 static uint16_t
 154 epl_g_key_file_get_uint16(GKeyFile *gkf, const char *group_name, const char *key, GError **error)
 155 {
 156         uint16_t ret = 0;
 157         const char *endptr;
 158         char *val = g_key_file_get_string(gkf, group_name, key, error);
 159
 160         if (!val)
 161                 return 0;
 162
 163         if (epl_ishex(val)) /* We need to support XXh, but no octals (is that right?) */
 164                 ws_hexstrtou16(val, &endptr, &ret);
 165         else
 166                 ws_strtou16(val, &endptr, &ret);
 167
 168         g_free(val);
 169         return ret;
 170 }
 171
 172 static void
 173 sort_subindices(void *key _U_, void *value, void *user_data _U_)
 174 {
 175         epl_wmem_iarray_t *subindices = ((struct object*)value)->subindices;
 176         if (subindices)
 177                 epl_wmem_iarray_sort_and_compact(subindices);
 178 }
 179
 180 void
 181 epl_eds_init(void)
 182 {
 183         struct typemap_entry *entry;
 184         eds_typemap = wmem_map_new(wmem_epan_scope(), g_direct_hash, g_direct_equal);
 185         for (entry = epl_datatypes; entry->name; entry++)
 186         {
 187                 const struct epl_datatype *type = epl_type_to_hf(entry->name);
 188                 wmem_map_insert(eds_typemap, GUINT_TO_POINTER(entry->id), (void*)type);
 189         }
 190 }
 191
 192 struct profile *
 193 epl_eds_load(struct profile *profile, const char *eds_file)
 194 {
 195         GKeyFile* gkf;
 196         GError *err;
 197         char **group, **groups;
 198         char *val;
 199         size_t groups_count;
 200
 201         gkf = g_key_file_new();
 202
 203         /* Load EDS document */
 204         if (!g_key_file_load_from_file(gkf, eds_file, G_KEY_FILE_NONE, &err)){
 205                 ws_log(NULL, LOG_LEVEL_WARNING, "Error: unable to parse file \"%s\"\n", eds_file);
 206                 profile = NULL;
 207                 goto cleanup;
 208         }
 209
 210         profile->path = wmem_strdup(profile->scope, eds_file);
 211
 212         val = g_key_file_get_string(gkf, "FileInfo", "Description", NULL);
 213         /* This leaves a trailing space, but that's ok */
 214         profile->name = wmem_strndup(profile->scope, val, strcspn(val, "#"));
 215         g_free(val);
 216
 217         groups = g_key_file_get_groups(gkf, &groups_count);
 218         for (group = groups; *group; group++)
 219         {
 220                 char *name;
 221                 const char *endptr;
 222                 uint16_t idx = 0, datatype;
 223                 struct object *obj = NULL;
 224                 struct od_entry tmpobj = OD_ENTRY_INITIALIZER;
 225                 bool is_object = true;
 226
 227                 if (!g_ascii_isxdigit(**group))
 228                         continue;
 229
 230                 ws_hexstrtou16(*group, &endptr, &idx);
 231                 if (*endptr == '\0')
 232                 { /* index */
 233                         tmpobj.idx = idx;
 234                 }
 235                 else if (g_str_has_prefix(endptr, "sub"))
 236                 { /* subindex */
 237                         if (!ws_hexstrtou16(endptr + 3, &endptr, &tmpobj.idx)
 238                         || tmpobj.idx > 0xFF)
 239                                 continue;
 240
 241                         is_object = false;
 242                 }
 243                 else continue;
 244
 245                 tmpobj.type_class = epl_g_key_file_get_uint16(gkf, *group, "ObjectType", NULL);
 246                 if (!tmpobj.type_class)
 247                         continue;
 248
 249                 datatype = epl_g_key_file_get_uint16(gkf, *group, "DataType", NULL);
 250                 if (datatype)
 251                         tmpobj.type = (const struct epl_datatype*)wmem_map_lookup(eds_typemap, GUINT_TO_POINTER(datatype));
 252
 253                 if ((name = g_key_file_get_string(gkf, *group, "ParameterName", NULL)))
 254                 {
 255                         size_t count = strcspn(name, "#") + 1;
 256                         (void) g_strlcpy(
 257                                 tmpobj.name,
 258                                 name,
 259                                 count > sizeof tmpobj.name ? sizeof tmpobj.name : count
 260                         );
 261                         g_free(name);
 262                 }
 263
 264                 obj = epl_profile_object_lookup_or_add(profile, idx);
 265
 266                 if (is_object)
 267                 { /* Let's add a new object! Exciting! */
 268                         obj->info = tmpobj;
 269                 }
 270                 else
 271                 { /* Object already there, let's add subindices */
 272                         struct subobject subobj = SUBOBJECT_INITIALIZER;
 273
 274                         if (!obj->subindices)
 275                         {
 276                                 obj->subindices = epl_wmem_iarray_new(
 277                                                         profile->scope,
 278                                                         sizeof (struct subobject),
 279                                                         subobject_equal
 280                                 );
 281                         }
 282
 283                         subobj.info = tmpobj;
 284                         epl_wmem_iarray_insert(obj->subindices, subobj.info.idx, &subobj.range);
 285                 }
 286         }
 287         g_strfreev(groups);
 288
 289         /* Unlike with XDDs, subindices might interleave with others, so let's sort them now */
 290         wmem_map_foreach(profile->objects, sort_subindices, NULL);
 291
 292         /* We don't read object mappings from EDS files */
 293         /* epl_profile_object_mappings_update(profile); */
 294
 295 cleanup:
 296         g_key_file_free(gkf);
 297         return profile;
 298 }
 299
 300 #ifdef PARSE_XDD
 301
 302 struct profile *
 303 epl_xdd_load(struct profile *profile, const char *xml_file)
 304 {
 305         xmlXPathContextPtr xpathCtx = NULL;
 306         xmlDoc *doc = NULL;
 307         struct xpath_namespace *ns = NULL;
 308         struct xpath *xpath = NULL;
 309         GHashTable *typemap = NULL;
 310
 311         /* Load XML document */
 312         doc = xmlParseFile(xml_file);
 313         if (!doc)
 314         {
 315                 ws_log(NULL, LOG_LEVEL_WARNING, "Error: unable to parse file \"%s\"\n", xml_file);
 316                 profile = NULL;
 317                 goto cleanup;
 318         }
 319
 320
 321         /* Create xpath evaluation context */
 322         xpathCtx = xmlXPathNewContext(doc);
 323         if(!xpathCtx)
 324         {
 325                 ws_log(NULL, LOG_LEVEL_WARNING, "Error: unable to create new XPath context\n");
 326                 profile = NULL;
 327                 goto cleanup;
 328         }
 329
 330         /* Register namespaces from list */
 331         for (ns = namespaces; ns->href; ns++)
 332         {
 333                 if(xmlXPathRegisterNs(xpathCtx, ns->prefix, ns->href) != 0)
 334                 {
 335                         ws_log(NULL, LOG_LEVEL_WARNING, "Error: unable to register NS with prefix=\"%s\" and href=\"%s\"\n", ns->prefix, ns->href);
 336                         profile = NULL;
 337                         goto cleanup;
 338                 }
 339         }
 340
 341         profile->path = wmem_strdup(profile->scope, xml_file);
 342
 343         /* mapping type ids to &hf_s */
 344         profile->data = typemap = (GHashTable*)g_hash_table_new_full(g_direct_hash, g_direct_equal, NULL, g_free);
 345
 346         /* Evaluate xpath expressions */
 347         for (xpath = xpaths; xpath->expr; xpath++)
 348         {
 349                 xmlXPathObjectPtr xpathObj = xmlXPathEvalExpression(xpath->expr, xpathCtx);
 350                 if (!xpathObj || !xpathObj->nodesetval)
 351                 {
 352                         ws_log(NULL, LOG_LEVEL_WARNING, "Error: unable to evaluate xpath expression \"%s\"\n", xpath->expr);
 353                         xmlXPathFreeObject(xpathObj);
 354                         profile = NULL;
 355                         goto cleanup;
 356                 }
 357
 358                 /* run handler */
 359                 if (xpath->handler && xpathObj->nodesetval->nodeNr)
 360                         xpath->handler(xpathObj->nodesetval, profile);
 361                 xmlXPathFreeObject(xpathObj);
 362         }
 363
 364         /* We create ObjectMappings while reading the XML, this is makes it likely,
 365          * that we won't be able to reference a mapped object in the ObjectMapping
 366          * as we didn't reach its XML tag yet. Therefore, after reading the XDD
 367          * completely, we update mappings in the profile
 368          */
 369         epl_profile_object_mappings_update(profile);
 370
 371 cleanup:
 372         if (typemap)
 373                 g_hash_table_destroy(typemap);
 374
 375         if (xpathCtx)
 376                 xmlXPathFreeContext(xpathCtx);
 377         if (doc)
 378                 xmlFreeDoc(doc);
 379
 380         return profile;
 381 }
 382
 383 static int
 384 populate_profile_name(xmlNodeSetPtr nodes, void *_profile)
 385 {
 386         struct profile *profile = (struct profile*)_profile;
 387         if (nodes->nodeNr == 1
 388         &&  nodes->nodeTab[0]->type == XML_ELEMENT_NODE
 389         &&  nodes->nodeTab[0]->children)
 390         {
 391                 profile->name = wmem_strdup(profile->scope, (char*)nodes->nodeTab[0]->children->content);
 392                 return 0;
 393         }
 394
 395         return -1;
 396 }
 397
 398 static int
 399 populate_datatype_list(xmlNodeSetPtr nodes, void *_profile)
 400 {
 401         xmlNodePtr cur;
 402         int i;
 403         struct profile *profile = (struct profile*)_profile;
 404
 405         for(i = 0; i < nodes->nodeNr; ++i)
 406         {
 407                 xmlAttrPtr attr;
 408
 409                 if(!nodes->nodeTab[i] || nodes->nodeTab[i]->type != XML_ELEMENT_NODE)
 410                         return -1;
 411
 412                 cur = nodes->nodeTab[i];
 413
 414
 415                 for(attr = cur->properties; attr; attr = attr->next)
 416                 {
 417                         const char *endptr;
 418                         const char *key = (const char*)attr->name;
 419                         const char *val = (const char*)attr->children->content;
 420
 421                         if (g_str_equal("dataType", key))
 422                         {
 423                                 xmlNode *subnode;
 424                                 uint16_t idx = 0;
 425
 426                                 if (!ws_hexstrtou16(val, &endptr, &idx))
 427                                         continue;
 428
 429                                 for (subnode = cur->children; subnode; subnode = subnode->next)
 430                                 {
 431                                         if (subnode->type == XML_ELEMENT_NODE)
 432                                         {
 433                                                 struct datatype *type;
 434                                                 const struct epl_datatype *ptr = epl_type_to_hf((const char*)subnode->name);
 435                                                 if (!ptr)
 436                                                 {
 437                                                         ws_log(NULL, LOG_LEVEL_INFO, "Skipping unknown type '%s'\n", subnode->name);
 438                                                         continue;
 439                                                 }
 440                                                 type = g_new(struct datatype, 1);
 441                                                 type->id = idx;
 442                                                 type->ptr = ptr;
 443                                                 g_hash_table_insert((GHashTable*)profile->data, GUINT_TO_POINTER(type->id), type);
 444                                                 continue;
 445                                         }
 446                                 }
 447
 448                         }
 449                 }
 450         }
 451
 452         return 0;
 453 }
 454
 455 static bool
 456 parse_obj_tag(xmlNode *cur, struct od_entry *out, struct profile *profile) {
 457                 xmlAttrPtr attr;
 458                 const char *defaultValue = NULL, *actualValue = NULL;
 459                 const char *endptr;
 460
 461                 for(attr = cur->properties; attr; attr = attr->next)
 462                 {
 463                         const char *key = (const char*)attr->name,
 464                                    *val = (const char*)attr->children->content;
 465
 466                         if (g_str_equal("index", key))
 467                         {
 468                                 if (!ws_hexstrtou16(val, &endptr, &out->idx))
 469                                         return false;
 470
 471                         } else if (g_str_equal("subIndex", key)) {
 472                                 if (!ws_hexstrtou16(val, &endptr, &out->idx))
 473                                         return false;
 474
 475                         } else if (g_str_equal("name", key)) {
 476                                 (void) g_strlcpy(out->name, val, sizeof out->name);
 477
 478                         } else if (g_str_equal("objectType", key)) {
 479                                 out->type_class = 0;
 480                                 ws_hexstrtou16(val, &endptr, &out->type_class);
 481
 482                         } else if (g_str_equal("dataType", key)) {
 483                                 uint16_t id;
 484                                 if (ws_hexstrtou16(val, &endptr, &id))
 485                                 {
 486                                         struct datatype *type = (struct datatype*)g_hash_table_lookup((GHashTable*)profile->data, GUINT_TO_POINTER(id));
 487                                         if (type) out->type = type->ptr;
 488                                 }
 489
 490                         } else if (g_str_equal("defaultValue", key)) {
 491                                 defaultValue = val;
 492
 493                         } else if (g_str_equal("actualValue", key)) {
 494                                 actualValue = val;
 495                         }
 496 #if 0
 497                         else if (g_str_equal("PDOmapping", key)) {
 498                           obj.PDOmapping = get_index(ObjectPDOmapping_tostr, val);
 499                           assert(obj.PDOmapping >= 0);
 500                         }
 501 #endif
 502                 }
 503
 504                 if (actualValue)
 505                         out->value =  g_ascii_strtoull(actualValue, NULL, 0);
 506                 else if (defaultValue)
 507                         out->value =  g_ascii_strtoull(defaultValue, NULL, 0);
 508                 else
 509                         out->value = 0;
 510
 511
 512                 return true;
 513 }
 514
 515 static int
 516 populate_object_list(xmlNodeSetPtr nodes, void *_profile)
 517 {
 518         int i;
 519         struct profile *profile = (struct profile*)_profile;
 520
 521         for(i = 0; i < nodes->nodeNr; ++i)
 522         {
 523                 xmlNodePtr cur = nodes->nodeTab[i];
 524                 struct od_entry tmpobj = OD_ENTRY_INITIALIZER;
 525
 526                 if (!nodes->nodeTab[i] || nodes->nodeTab[i]->type != XML_ELEMENT_NODE)
 527                         continue;
 528
 529                 parse_obj_tag(cur, &tmpobj, profile);
 530
 531                 if (tmpobj.idx)
 532                 {
 533                         struct object *obj = epl_profile_object_add(profile, tmpobj.idx);
 534                         obj->info = tmpobj;
 535
 536                         if (tmpobj.type_class == OD_ENTRY_ARRAY || tmpobj.type_class == OD_ENTRY_RECORD)
 537                         {
 538                                 xmlNode *subcur;
 539                                 struct subobject subobj = SUBOBJECT_INITIALIZER;
 540
 541                                 obj->subindices = epl_wmem_iarray_new(profile->scope, sizeof (struct subobject), subobject_equal);
 542
 543                                 for (subcur = cur->children; subcur; subcur = subcur->next)
 544                                 {
 545                                         if (subcur->type != XML_ELEMENT_NODE)
 546                                                 continue;
 547
 548                                         if (parse_obj_tag(subcur, &subobj.info, profile))
 549                                         {
 550                                                 epl_wmem_iarray_insert(obj->subindices,
 551                                                                         subobj.info.idx, &subobj.range);
 552                                         }
 553                                         if (subobj.info.value && epl_profile_object_mapping_add(
 554                                             profile, obj->info.idx, (uint8_t)subobj.info.idx, subobj.info.value))
 555                                         {
 556                                                 ws_log(NULL, LOG_LEVEL_INFO,
 557                                                 "Loaded mapping from XDC %s:%s", obj->info.name, subobj.info.name);
 558                                         }
 559                                 }
 560                                 epl_wmem_iarray_sort_and_compact(obj->subindices);
 561                         }
 562                 }
 563         }
 564
 565         return 0;
 566 }
 567
 568
 569 #else  /* ! PARSE_XDD */
 570
 571 #ifdef HAVE_LIBXML2
 572 struct profile *
 573 epl_xdd_load(struct profile *profile _U_, const char *xml_file _U_)
 574 {
 575         return NULL;
 576 }
 577 #endif  /* HAVE_LIBXML2 */
 578
 579 #endif  /* ! PARSE_XDD */
 580
 581 /**
 582  * A sorted array keyed by intervals
 583  * You keep inserting items, then sort the array.
 584  * sorting also combines items that compare equal into one and adjusts
 585  * the interval accordingly. find uses binary search to find the item
 586  *
 587  * This is particularly useful, if many similar items exist adjacent to each other
 588  * e.g. ObjectMapping subindices in EPL XDD (packet-epl-profile-parser.c)
 589  *
 590  * Interval Trees wouldn't work for this scenario, because they don't allow
 591  * expansion of existing intervals. Using an array instead of a tree,
 592  * may additionally offer a possible performance advantage
 593
 594  * Much room for optimization in the creation process of the array,
 595  * but we assume this to be an infrequent operation, with space utilization and
 596  * finding speed being more important.
 597  */
 598
 599
 600 static bool
 601 free_garray(wmem_allocator_t *scope _U_, wmem_cb_event_t event _U_, void *data)
 602 {
 603         GArray *arr = (GArray*)data;
 604         g_array_free(arr, true);
 605         return false;
 606 }
 607
 608 /**
 609  * \param scope wmem pool to use
 610  * \param elem_size size of elements to add into the iarray
 611  * \param equal establishes whether two adjacent elements are equal and thus
 612  *            shall be combined at sort-time
 613  *
 614  * \returns a new interval array or NULL on failure
 615  *
 616  * Creates a new interval array.
 617  * Elements must have a range_admin_t as their first element,
 618  * which will be managed by the implementation.
 619  * \NOTE The cmp parameter can be used to free resources. When combining,
 620  * it's always the second argument that's getting removed.
 621  */
 622
 623 static epl_wmem_iarray_t *
 624 epl_wmem_iarray_new(wmem_allocator_t *scope, const unsigned elem_size, GEqualFunc equal)
 625 {
 626         epl_wmem_iarray_t *iarr;
 627
 628         if (elem_size < sizeof(range_t)) return NULL;
 629
 630         iarr = wmem_new(scope, epl_wmem_iarray_t);
 631         if (!iarr) return NULL;
 632
 633         iarr->equal = equal;
 634         iarr->scope = scope;
 635         iarr->arr = g_array_new(false, false, elem_size);
 636         iarr->is_sorted = true;
 637
 638         wmem_register_callback(scope, free_garray, iarr->arr);
 639
 640         return iarr;
 641 }
 642
 643
 644 /** Returns true if the iarr is empty. */
 645 bool
 646 epl_wmem_iarray_is_empty(epl_wmem_iarray_t *iarr)
 647 {
 648         return iarr->arr->len == 0;
 649 }
 650
 651 /** Returns true if the iarr is sorted. */
 652 bool
 653 epl_wmem_iarray_is_sorted(epl_wmem_iarray_t *iarr)
 654 {
 655         return iarr->is_sorted;
 656 }
 657
 658 /** Inserts an element */
 659 static void
 660 epl_wmem_iarray_insert(epl_wmem_iarray_t *iarr, uint32_t where, range_admin_t *data)
 661 {
 662         if (iarr->arr->len)
 663                 iarr->is_sorted = false;
 664
 665         data->high = data->low = where;
 666         g_array_append_vals(iarr->arr, data, 1);
 667 }
 668
 669 static int u32cmp(uint32_t a, uint32_t b)
 670 {
 671         if (a < b) return -1;
 672         if (a > b) return +1;
 673
 674         return 0;
 675 }
 676
 677 static int
 678 epl_wmem_iarray_cmp(const void *a, const void *b)
 679 {
 680         return u32cmp(*(const uint32_t*)a, *(const uint32_t*)b);
 681 }
 682
 683 /** Makes array suitable for searching */
 684 static void
 685 epl_wmem_iarray_sort_and_compact(epl_wmem_iarray_t *iarr)
 686 {
 687         range_admin_t *elem, *prev = NULL;
 688         unsigned i, len;
 689         len = iarr->arr->len;
 690         if (iarr->is_sorted)
 691                 return;
 692
 693         g_array_sort(iarr->arr, epl_wmem_iarray_cmp);
 694         prev = elem = (range_admin_t*)iarr->arr->data;
 695
 696         for (i = 1; i < len; i++) {
 697                 elem = (range_admin_t*)((char*)elem + g_array_get_element_size(iarr->arr));
 698
 699                 /* neighbours' range must be within one of each other and their content equal */
 700                 while (i < len && elem->low - prev->high <= 1 && iarr->equal(elem, prev)) {
 701                         prev->high = elem->high;
 702
 703                         g_array_remove_index(iarr->arr, i);
 704                         len--;
 705                 }
 706                 prev = elem;
 707         }
 708
 709         iarr->is_sorted = 1;
 710 }
 711
 712 static int
 713 find_in_range(const void *_a, const void *_b)
 714 {
 715         const range_admin_t *a = (const range_admin_t*)_a,
 716                             *b = (const range_admin_t*)_b;
 717
 718         if (a->low <= b->high && b->low <= a->high) /* overlap */
 719                 return 0;
 720
 721         return u32cmp(a->low, b->low);
 722 }
 723
 724 static void*
 725 bsearch_garray(const void *key, GArray *arr, int (*cmp)(const void*, const void*))
 726 {
 727         return bsearch(key, arr->data, arr->len, g_array_get_element_size(arr), cmp);
 728 }
 729
 730 /*
 731  * Finds an element in the interval array. Returns NULL if it doesn't exist
 732  * Calling this is unspecified if the array wasn't sorted before
 733  */
 734 range_admin_t *
 735 epl_wmem_iarray_find(epl_wmem_iarray_t *iarr, uint32_t value) {
 736         epl_wmem_iarray_sort_and_compact(iarr);
 737
 738         range_admin_t needle;
 739         needle.low  = value;
 740         needle.high = value;
 741         return (range_admin_t*)bsearch_garray(&needle, iarr->arr, find_in_range);
 742 }
 743
 744 #if 0
 745 void
 746 epl_wmem_print_iarr(epl_wmem_iarray_t *iarr)
 747 {
 748         range_admin_t *elem;
 749         unsigned i, len;
 750         elem = (range_admin_t*)iarr->arr->data;
 751         len = iarr->arr->len;
 752         for (i = 0; i < len; i++)
 753         {
 754
 755                 ws_debug_printf("Range: low=%" PRIu32 " high=%" PRIu32 "\n", elem->low, elem->high);
 756
 757                 elem = (range_admin_t*)((char*)elem + g_array_get_element_size(iarr->arr));
 758         }
 759 }
 760 #endif
 761
 762 /*
 763  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 764  *
 765  * Local variables:
 766  * c-basic-offset: 8
 767  * tab-width: 8
 768  * indent-tabs-mode: t
 769  * End:
 770  *
 771  * vi: set shiftwidth=8 tabstop=8 noexpandtab:
 772  * :indentSize=8:tabSize=8:noTabs=false:
 773  */