From a9c3c58c9fb22e71e0878d4da1d3de0cd9e36445 Mon Sep 17 00:00:00 2001 From: hniksic Date: Wed, 8 Oct 2003 09:00:10 -0700 Subject: [PATCH] [svn] Switch to binary search for find_tag. --- src/ChangeLog | 4 ++++ src/html-url.c | 28 +++++++++++++++++----------- 2 files changed, 21 insertions(+), 11 deletions(-) diff --git a/src/ChangeLog b/src/ChangeLog index 85b0f3da..baa4c581 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,7 @@ +2003-10-08 Hrvoje Niksic + + * html-url.c (find_tag): Switch to binary search. + 2003-10-08 Hrvoje Niksic * main.c (print_help): Fix typo; stured -> stored. diff --git a/src/html-url.c b/src/html-url.c index 756bf2ab..abaa2f8e 100644 --- a/src/html-url.c +++ b/src/html-url.c @@ -270,30 +270,36 @@ init_interesting (void) } } +/* Find tag with name TAG_NAME in KNOWN_TAGS and return its index. */ + static int find_tag (const char *tag_name) { - int i; + /* Originally implemented as linear search. In Wget 1.9 known_tags + contains 21 elements, for which binary search requires max. 5 + comparisons, whereas linear search performs 10 on average. */ - /* This is linear search; if the number of tags grow, we can switch - to binary search. */ + int lo = 0, hi = countof (known_tags) - 1; - for (i = 0; i < countof (known_tags); i++) + while (lo <= hi) { - int cmp = strcasecmp (known_tags[i].name, tag_name); - /* known_tags are sorted alphabetically, so we can - micro-optimize. */ - if (cmp > 0) - break; - else if (cmp == 0) - return i; + int mid = (lo + hi) >> 1; + int cmp = strcasecmp (tag_name, known_tags[mid].name); + if (cmp < 0) + hi = mid - 1; + else if (cmp > 0) + lo = mid + 1; + else + return mid; } + return -1; } /* Find the value of attribute named NAME in the taginfo TAG. If the attribute is not present, return NULL. If ATTRIND is non-NULL, the index of the attribute in TAG will be stored there. */ + static char * find_attr (struct taginfo *tag, const char *name, int *attrind) { -- 2.39.2