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

1 files changed, 49 insertions, 0 deletions

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) */