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