diff options
author | wmeier <wmeier@f5534014-38df-0310-8fa8-9805f1628bb7> | 2012-08-24 20:44:33 +0000 |
---|---|---|
committer | wmeier <wmeier@f5534014-38df-0310-8fa8-9805f1628bb7> | 2012-08-24 20:44:33 +0000 |
commit | 08e40c8a9ca3344afe5f59f954811b141aee8770 (patch) | |
tree | 75587af9c72567e6d9e94fbdaec684d1b526490c | |
parent | 82e36e4376d5b63dbf7557c97ad0929d9a03fb0f (diff) |
Force extended value string linear search (not binary search) in one case:
Fixed: { -2, -1, 0, 1, 3} (note gap) used a binary search (which would fail);
Note: { -2, -1, 0, 1, 2 ,3 } (no gap) allowed; will still do a direct access;
Also: Add a comment to README.developer extended value string section.
git-svn-id: http://anonsvn.wireshark.org/wireshark/trunk@44659 f5534014-38df-0310-8fa8-9805f1628bb7
-rw-r--r-- | doc/README.developer | 12 | ||||
-rw-r--r-- | epan/value_string.c | 17 |
2 files changed, 26 insertions, 3 deletions
diff --git a/doc/README.developer b/doc/README.developer index 600cbce8fd..02bc3b73ef 100644 --- a/doc/README.developer +++ b/doc/README.developer @@ -1895,9 +1895,9 @@ field would be set to NULL. -- Extended value strings You can also use an extended version of the value_string for faster lookups. -It requires a value_string as input. +It requires a value_string array as input. If all of a contiguous range of values from min to max are present in the array -the value will be used as as a direct index into a value_string array. +in ascending order the value will be used as as a direct index into a value_string array. If the values in the array are not contiguous (ie: there are "gaps"), but are in ascending order a binary search will be used. @@ -1905,6 +1905,14 @@ in ascending order a binary search will be used. Note: "gaps" in a value_string array can be filled with "empty" entries eg: {value, "Unknown"} so that direct access to the array is is possible. +Note: the value_string array values are *unsigned*; IOW: -1 is greater than 0. + So: + { -2, -1, 1, 2 }; wrong: linear search will be used (note gap) + { 1, 2, -2, -1 }; correct: binary search will be used + + As a special case: + { -2, -1, 0, 1, 2 }; OK: direct(indexed) access will be used (note no gap) + The init macro (see below) will perform a check on the value string the first time it is used to determine which search algorithm fits and fall back to a linear search if the value_string does not meet the criteria above. diff --git a/epan/value_string.c b/epan/value_string.c index 43453f1f14..f48b3155ff 100644 --- a/epan/value_string.c +++ b/epan/value_string.c @@ -285,6 +285,20 @@ _match_strval_ext_init(const guint32 val, const value_string_ext *a_vse) * 1 Binary search, the values MUST be in numerical order. * 2 The value used as an index(the value string MUST have all values between first and last defined in numerical order) */ + +/* Note: The value_string 'value' is *unsigned*. + * + * Special case: + * { -3, -2, -1, 0, 1, 2 } will be treated as "ascending ordered" (altho not really such) + * thus allowing as a 'direct' search. + * + * Note: + * { -3, -2, 0, 1, 2 } and { -3, -2, -1, 0, 2 } will both be considered as "out-of-order with gaps" + * thus requiring a 'linear' search. + * { 0, 1, 2, -3, -2 } and { 0, 2, -3, -2, -1 } will be considered "ascending ordered with gaps" + * thus allowing a 'binary' search. + */ + enum { VS_SEARCH = 0, VS_BIN_TREE, VS_INDEX } type = VS_INDEX; guint32 prev_value; @@ -303,7 +317,8 @@ _match_strval_ext_init(const guint32 val, const value_string_ext *a_vse) type = VS_BIN_TREE; } /* XXX: Should check for dups ?? */ - if ((type == VS_BIN_TREE) && (prev_value > vs_p[i].value)) { + if ((type == VS_BIN_TREE) && + ((prev_value > vs_p[i].value) || (first_value > vs_p[i].value))) { type = VS_SEARCH; break; } |