Add interval array data structure, with growable intervals

A sorted array keyed by intervals
You keep inserting items, then sort the array.
sorting also compacts items that compare equal into one and adjusts
the interval accordingly. find uses binary search to find the item

This is particularly useful, if you got many similar items,
e.g. ObjectMapping subindices in the XDD. XDDs can be upward of
25k lines long with much duplication (253 subindices having the same
content).

Interval Trees wouldn't work, because they didn't allow expanding
existing intervals. Using an array instead of a tree, additionally offers
a possible performance advantage, but it's not that critical here,
as finding should only happen in the async frames

There's room for optimization in the creation process of the array,
but it doesn't matter much, as they aren't created frequently.
Finding speed is what matters for the use case of parsing EDS
and XDD files

Change-Id: Iaaddc90059f0e49b456774a111d8d42452b90cf9
Reviewed-on: https://code.wireshark.org/review/21111
Petri-Dish: Peter Wu <peter@lekensteyn.nl>
Tested-by: Petri Dish Buildbot <buildbot-no-reply@wireshark.org>
Reviewed-by: Peter Wu <peter@lekensteyn.nl>

1 files changed, 35 insertions, 0 deletions

diff --git a/epan/dissectors/packet-epl.h b/epan/dissectors/packet-epl.h
new file mode 100644
index 0000000000..c94e6ddd98
--- /dev/null
+++ b/epan/dissectors/packet-epl.h
@@ -0,0 +1,35 @@
+/* packet-epl.h
+ * Routines for "Ethernet POWERLINK 2.0" dissection
+ * (Ethernet POWERLINK V2.0 Communication Profile Specification Draft Standard Version 1.2.0)
+ *
+ * A dissector for:
+ * Wireshark - Network traffic analyzer
+ * By Gerald Combs <gerald@wireshark.org>
+ * Copyright 1999 Gerald Combs
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#ifndef __EPL_H_
+#define __EPL_H_
+
+#include <glib.h>
+#include <epan/address.h>
+#include <epan/wmem/wmem.h>
+#include <epan/range.h>
+
+typedef struct epl_wmem_iarray epl_wmem_iarray_t;
+
+#endif