sfeed.c: optimize tag lookup by reverting the binary search to a linear lookup - sfeed - RSS and Atom parser
(HTM) git clone git://git.codemadness.org/sfeed
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
(DIR) commit 4d445d3e47de2d3e5b101c1a6520690d306a5d6c
(DIR) parent c2231c4b4f91a86df6192c9830235f3ca499810e
(HTM) Author: Hiltjo Posthuma <hiltjo@codemadness.org>
Date: Tue, 7 Jan 2025 19:51:15 +0100
sfeed.c: optimize tag lookup by reverting the binary search to a linear lookup
This removes an intended optimization.
It was changed to bsearch() in commit 3031d855807de20fc86cd3dd2375ce9473e86947
After some more testing: because the tags table is so small doing a linear scan
over the table by first checking the length, and then (if needed) the tag name
comparison is bit faster (6-11%), but of course depends on the input) in common
cases than a binary search.
In practise there is no noticable difference though.
This simplifies the code a bit.
Diffstat:
M sfeed.c | 33 +++++++++++++++----------------
1 file changed, 16 insertions(+), 17 deletions(-)
---
(DIR) diff --git a/sfeed.c b/sfeed.c
@@ -125,7 +125,7 @@ static void xmltagstart(XMLParser *, const char *, size_t);
static void xmltagstartparsed(XMLParser *, const char *, size_t, int);
/* map tag name to TagId type */
-/* RSS, must be alphabetical order */
+/* RSS, keep this in alphabetical order */
static const FeedTag rsstags[] = {
{ STRP("author"), RSSTagAuthor },
{ STRP("category"), RSSTagCategory },
@@ -142,7 +142,7 @@ static const FeedTag rsstags[] = {
{ STRP("title"), RSSTagTitle }
};
-/* Atom, must be alphabetical order */
+/* Atom, keep this in alphabetical order */
static const FeedTag atomtags[] = {
{ STRP("author"), AtomTagAuthor },
{ STRP("category"), AtomTagCategory },
@@ -212,34 +212,33 @@ static FeedContext ctx;
static XMLParser parser; /* XML parser state */
static String attrispermalink, attrrel, attrtype, tmpstr;
-static int
-tagcmp(const void *v1, const void *v2)
-{
- return strcasecmp(((FeedTag *)v1)->name, ((FeedTag *)v2)->name);
-}
-
-/* Unique tagid for parsed tag name. */
+/* Unique tag(id) for parsed tag name. */
static FeedTag *
gettag(enum FeedType feedtype, const char *name, size_t namelen)
{
- FeedTag f, *r = NULL;
-
- f.name = (char *)name;
+ FeedTag *r;
+ size_t i;
switch (feedtype) {
case FeedTypeRSS:
- r = bsearch(&f, rsstags, sizeof(rsstags) / sizeof(rsstags[0]),
- sizeof(rsstags[0]), tagcmp);
+ for (i = 0; i < sizeof(rsstags) / sizeof(rsstags[0]); i++) {
+ r = (FeedTag *)&rsstags[i];
+ if (r->len == namelen && !strcasecmp(r->name, name))
+ return r;
+ }
break;
case FeedTypeAtom:
- r = bsearch(&f, atomtags, sizeof(atomtags) / sizeof(atomtags[0]),
- sizeof(atomtags[0]), tagcmp);
+ for (i = 0; i < sizeof(atomtags) / sizeof(atomtags[0]); i++) {
+ r = (FeedTag *)&atomtags[i];
+ if (r->len == namelen && !strcasecmp(r->name, name))
+ return r;
+ }
break;
default:
break;
}
- return r;
+ return NULL;
}
static char *