Wireshark · Wireshark-dev: [Wireshark-dev] RFC: sorted value_string + bsearch

[Jakub Zawadzki <darkjames@xxxxxxxxxxxxxxxx>]

Hi,

In wireshark there are some large value_string arrays.
Some developers keep them sorted, some don't :)

Dissectors in which value_string are sorted could be a little faster
thanks to binary search.

In attachment patch to introduce new 'fast' functions for value_string.

Can this patch be commited? I don't know if I will have time to rewrite dissectors.
Some time later it should be also possible to get rid of (hated) value_string NULL terminator. 


I'm also attaching sample dns_types rewrite.

Cheers.

diff --git epan/value_string.c epan/value_string.c
index 0e43750..8edd94a 100644
--- epan/value_string.c
+++ epan/value_string.c
@@ -49,6 +49,19 @@ val_to_str(const guint32 val, const value_string *vs, const char *fmt) {
   return ep_strdup_printf(fmt, val);
 }
 
+const gchar*
+val_to_str_fast(const guint32 val, const value_string_fast *vs, const char *fmt) {
+  const gchar *ret;
+
+  g_assert(fmt != NULL);
+
+  ret = match_strval_fast(val, vs);
+  if (ret != NULL)
+    return ret;
+
+  return ep_strdup_printf(fmt, val);
+}
+
 /* Tries to match val against each element in the value_string array vs.
    Returns the associated string ptr on a match.
    Returns 'unknown_str', on failure. */
@@ -65,6 +78,19 @@ val_to_str_const(const guint32 val, const value_string *vs, const char *unknown_
   return unknown_str;
 }
 
+const gchar*
+val_to_str_fast_const(const guint32 val, const value_string_fast *vs, const char *unknown_str) {
+  const gchar *ret;
+
+  g_assert(unknown_str != NULL);
+
+  ret = match_strval_fast(val, vs);
+  if (ret != NULL)
+    return ret;
+
+  return unknown_str;
+}
+
 /* Tries to match val against each element in the value_string array vs.
    Returns the associated string ptr, and sets "*idx" to the index in
    that table, on a match, and returns NULL, and sets "*idx" to -1,
@@ -94,6 +120,27 @@ match_strval(const guint32 val, const value_string *vs) {
     return match_strval_idx(val, vs, &ignore_me);
 }
 
+const gchar*
+match_strval_fast(const guint32 val, const value_string_fast *vs) {
+  guint low, idx, max;
+  guint32 item;
+  if(vs) {
+    /* XXX, bsearch() */
+    for (low = 0, max = vs->length; low < max; ) {
+      idx = (low + max) / 2;
+      item = vs->vals[idx].value;
+
+      if (val < item)
+        max = idx;
+      else if (val > item)
+        low = idx + 1;
+      else
+        return vs->vals[idx].strptr;
+    }
+  }
+  return NULL;
+}
+
 /* Tries to match val against each element in the value_string array vs.
    Returns the associated string ptr on a match.
    Formats val with fmt, and returns the resulting string, on failure. */
diff --git epan/value_string.h epan/value_string.h
index 7fcbb30..cd3c031 100644
--- epan/value_string.h
+++ epan/value_string.h
@@ -34,6 +34,14 @@ typedef struct _value_string {
   const gchar   *strptr;
 } value_string;
 
+typedef struct {
+  guint length;
+  const value_string *vals;
+} value_string_fast;
+
+#define VALUE_STRING_FAST(x) \
+	value_string_fast x##_fast = { array_length(x)-1, x }
+
 /* Struct for the str_to_str, match_strstr_idx, and match_strstr functions */
 
 typedef struct _string_string {
@@ -59,16 +67,19 @@ extern const gchar* match_strval_idx(const guint32 val, const value_string *vs,
 
 /* Like match_strval_idx(), but doesn't return the index. */
 extern const gchar* match_strval(const guint32 val, const value_string *vs);
+extern const gchar* match_strval_fast(const guint32 val, const value_string_fast *vs);
 
 /* Tries to match val against each element in the value_string array vs.
    Returns the associated string ptr on a match.
    Formats val with fmt, and returns the resulting string, on failure. */
 extern const gchar* val_to_str(const guint32 val, const value_string *vs, const char *fmt);
+extern const gchar* val_to_str_fast(const guint32 val, const value_string_fast *vs, const char *fmt);
 
 /* Tries to match val against each element in the value_string array vs.
    Returns the associated string ptr on a match.
    Returns 'unknown_str', on failure. */
 extern const gchar* val_to_str_const(const guint32 val, const value_string *vs, const char *unknown_str);
+extern const gchar* val_to_str_fast_const(const guint32 val, const value_string_fast *vs, const char *unknown_str);
 
 /* Tries to match val against each element in the value_string array vs.
    Returns the associated string ptr, and sets "*idx" to the index in

diff --git epan/dissectors/packet-dns.c epan/dissectors/packet-dns.c
index 3a702f5..57e58fc 100644
--- epan/dissectors/packet-dns.c
+++ epan/dissectors/packet-dns.c
@@ -499,9 +503,6 @@ static const value_string dns_types[] = {
 	{ T_TKEY,	"TKEY"},
 	{ T_TSIG,	"TSIG"},
 
-	{ T_WINS,	"WINS"},
-	{ T_WINS_R,	"WINS-R"},
-
 	{ 251,		"IXFR"},
 	{ 252,		"AXFR"},
 	{ 253,		"MAILB"},
@@ -510,13 +511,18 @@ static const value_string dns_types[] = {
 
 
 	{ T_DLV,        "DLV" }, /* Domain Lookaside Validation DNS Resource Record (RFC 4431) */
+
+	{ T_WINS,	"WINS"},
+	{ T_WINS_R,	"WINS-R"},
 	{0,		NULL}
 };
 
+static const VALUE_STRING_FAST(dns_types); /* dns_types_fast */
+
 static const char *
 dns_type_name (guint type)
 {
-  return val_to_str(type, dns_types, "Unknown (%u)");
+  return val_to_str_fast(type, &dns_types_fast, "Unknown (%u)");
 }
 
 static char *