Introduce bsearch() and use it in tagtree.c.

bsearch() is a general purpose binary search function for arrays.
It's supposedly faster than looping over arrays.
The array needs to be sorted in ascending order under the provided
comparison function. If the key and array element are of the same kind,
then the same compare function can be used for qsort() and bsearch().

Code taken from glibc.

git-svn-id: svn://svn.rockbox.org/rockbox/trunk@30155 a1c6a512-1295-4272-9138-f99709370657

4 files changed, 147 insertions, 65 deletions

diff --git a/apps/tagtree.c b/apps/tagtree.c
index 3df8d9db2b..1bdc0550a6 100644
--- a/apps/tagtree.c
+++ b/apps/tagtree.c
@@ -29,6 +29,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include "string-extra.h"
+#include "bsearch.h"
 #include "config.h"
 #include "system.h"
 #include "kernel.h"
@@ -160,6 +161,13 @@ struct match
     int symbol;
 };
 
+static int compare_match(const void* _key, const void* _elem)
+{
+    const char* key = _key;
+    const struct match *elem = _elem;
+    return strcasecmp(key, elem->str);
+}
+
 /* Statusbar text of the current view. */
 static char current_title[MAX_TAGS][128];
 
@@ -221,42 +229,42 @@ static int get_token_str(char *buf, int size)
 static int get_tag(int *tag)
 {
     static const struct match get_tag_match[] =
-    {
-        {"album", tag_album},
-        {"artist", tag_artist},
-        {"bitrate", tag_bitrate},
-        {"composer", tag_composer},
-        {"comment", tag_comment},
-        {"albumartist", tag_albumartist},
-        {"ensemble", tag_albumartist},
-        {"grouping", tag_grouping},
-        {"genre", tag_genre},
-        {"length", tag_length},
-        {"Lm", tag_virt_length_min},
-        {"Ls", tag_virt_length_sec},
-        {"Pm", tag_virt_playtime_min},
-        {"Ps", tag_virt_playtime_sec},
-        {"title", tag_title},
-        {"filename", tag_filename},
-        {"tracknum", tag_tracknumber},
-        {"discnum", tag_discnumber},
-        {"year", tag_year},
-        {"playcount", tag_playcount},
-        {"rating", tag_rating},
-        {"lastplayed", tag_lastplayed},
-        {"lastoffset", tag_lastoffset},
-        {"commitid", tag_commitid},
-        {"entryage", tag_virt_entryage},
-        {"autoscore", tag_virt_autoscore},
-        {"%sort", var_sorttype},
-        {"%limit", var_limit},
-        {"%strip", var_strip},
-        {"%menu_start", var_menu_start},
-        {"%include", var_include},
-        {"%root_menu", var_rootmenu},
-        {"%format", var_format},
-        {"->", menu_next},
-        {"==>", menu_load}
+    {   /* sorted by ascii (case insensitive) for bsearch */
+        { "%format", var_format },
+        { "%include", var_include },
+        { "%limit", var_limit },
+        {"%menu_start",var_menu_start},
+        {"%root_menu",var_rootmenu},
+        { "%sort", var_sorttype },
+        { "%strip", var_strip },
+        {"->",menu_next},
+        { "==>", menu_load },
+        { "album", tag_album },
+        { "albumartist", tag_albumartist },
+        { "artist", tag_artist },
+        { "autoscore", tag_virt_autoscore },
+        { "bitrate", tag_bitrate },
+        { "comment", tag_comment },
+        { "commitid", tag_commitid },
+        { "composer", tag_composer },
+        { "discnum", tag_discnumber },
+        { "ensemble", tag_albumartist },
+        { "entryage", tag_virt_entryage },
+        { "filename", tag_filename },
+        { "genre", tag_genre },
+        { "grouping", tag_grouping },
+        { "lastoffset", tag_lastoffset },
+        { "lastplayed", tag_lastplayed },
+        { "length", tag_length },
+        { "Lm", tag_virt_length_min },
+        { "Ls", tag_virt_length_sec },
+        { "playcount", tag_playcount },
+        { "Pm", tag_virt_playtime_min },
+        { "Ps", tag_virt_playtime_sec },
+        { "rating", tag_rating },
+        { "title", tag_title },
+        { "tracknum", tag_tracknumber },
+        { "year", tag_year },
     };
     char buf[128];
     unsigned int i;
@@ -277,15 +285,13 @@ static int get_tag(int *tag)
     }
     buf[i] = '\0';
 
-    for (i = 0; i < ARRAYLEN(get_tag_match); i++)
+    struct match *elem = bsearch(buf, get_tag_match, ARRAYLEN(get_tag_match),
+                                        sizeof(struct match), compare_match);
+    if (elem)
     {
-        if (!strcasecmp(buf, get_tag_match[i].str))
-        {
-            *tag = get_tag_match[i].symbol;
-            return 1;
-        }
+        *tag = elem->symbol;
+        return 1;
     }
-
     logf("NO MATCH: %s\n", buf);
     if (buf[0] == '?')
         return 0;
@@ -296,21 +302,21 @@ static int get_tag(int *tag)
 static int get_clause(int *condition)
 {
     static const struct match get_clause_match[] =
-    {
-        {"=", clause_is},
-        {"==", clause_is},
-        {"!=", clause_is_not},
-        {">", clause_gt},
-        {">=", clause_gteq},
-        {"<", clause_lt},
-        {"<=", clause_lteq},
-        {"~", clause_contains},
-        {"!~", clause_not_contains},
-        {"^", clause_begins_with},
-        {"!^", clause_not_begins_with},
-        {"$", clause_ends_with},
-        {"!$", clause_not_ends_with},
-        {"@", clause_oneof}
+    {   /* sorted by ascii (case insensitive) for bsearch */
+        { "!$", clause_not_ends_with },
+        { "!=", clause_is_not },
+        { "!^", clause_not_begins_with },
+        { "!~", clause_not_contains },
+        { "$", clause_ends_with },
+        { "<", clause_lt },
+        { "<=", clause_lteq },
+        { "=", clause_is },
+        { "==", clause_is },
+        { ">", clause_gt },
+        { ">=", clause_gteq },
+        { "@", clause_oneof },
+        { "^", clause_begins_with },
+        { "~", clause_contains },
     };
 
     char buf[4];
@@ -332,15 +338,13 @@ static int get_clause(int *condition)
     }
     buf[i] = '\0';
 
-    for (i = 0; i < ARRAYLEN(get_clause_match); i++)
+    struct match *elem = bsearch(buf, get_clause_match, ARRAYLEN(get_clause_match),
+                                        sizeof(struct match), compare_match);
+    if (elem)
     {
-        if (!strcasecmp(buf, get_clause_match[i].str))
-        {
-            *condition = get_clause_match[i].symbol;
-            return 1;
-        }
+        *condition = elem->symbol;
+        return 1;
     }
-
     return 0;
 }
 
diff --git a/firmware/SOURCES b/firmware/SOURCES
index 4aef86f002..dd3e028e30 100644
--- a/firmware/SOURCES
+++ b/firmware/SOURCES
@@ -105,6 +105,7 @@ libc/mktime.c
 
 /* Common */
 common/version.c
+common/bsearch.c
 common/config.c
 common/crc32.c
 #ifdef MI4_FORMAT
diff --git a/firmware/common/bsearch.c b/firmware/common/bsearch.c
new file mode 100644
index 0000000000..cbfec3578a
--- /dev/null
+++ b/firmware/common/bsearch.c
@@ -0,0 +1,49 @@
+/* Copyright (C) 1991,92,97,2000,02 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+#include <stdlib.h>
+
+
+/* Perform a binary search for KEY in BASE which has NMEMB elements
+   of SIZE bytes each.  The comparisons are done by (*COMPAR)().  */
+void *
+bsearch (const void *key, const void *base, size_t nmemb, size_t size,
+         int (*compar) (const void *, const void *))
+{
+  size_t l, u, idx;
+  const void *p;
+  int comparison;
+
+  l = 0;
+  u = nmemb;
+  while (l < u)
+    {
+      idx = (l + u) / 2;
+      p = (void *) (((const char *) base) + (idx * size));
+      comparison = (*compar) (key, p);
+      if (comparison < 0)
+        u = idx;
+      else if (comparison > 0)
+        l = idx + 1;
+      else
+        return (void *) p;
+    }
+
+  return NULL;
+}
+/* libc_hidden_def (bsearch) */
diff --git a/firmware/include/bsearch.h b/firmware/include/bsearch.h
new file mode 100644
index 0000000000..e113676a06
--- /dev/null
+++ b/firmware/include/bsearch.h
@@ -0,0 +1,28 @@
+/* Copyright (C) 1991,92,97,2000,02 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+#ifndef __BSEARCH_H__
+#define __BSEARCH_H__
+
+/* Perform a binary search for KEY in BASE which has NMEMB elements
+   of SIZE bytes each.  The comparisons are done by (*COMPAR)().  */
+void *
+bsearch (const void *key, const void *base, size_t nmemb, size_t size,
+         int (*compar) (const void *, const void *));
+
+#endif