summaryrefslogtreecommitdiffstats
path: root/firmware
diff options
context:
space:
mode:
authorThomas Martitz <kugel@rockbox.org>2011-07-18 18:55:20 +0000
committerThomas Martitz <kugel@rockbox.org>2011-07-18 18:55:20 +0000
commit74ab227b58ee3eae152c1142eb9144ee5332a7d9 (patch)
tree0a3b90bc96169a3ed00fc51120d5009d443bd8c0 /firmware
parente0970817b0d8b426f4b26090017868067d0f516e (diff)
downloadrockbox-74ab227b58ee3eae152c1142eb9144ee5332a7d9.tar.gz
rockbox-74ab227b58ee3eae152c1142eb9144ee5332a7d9.zip
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
Diffstat (limited to 'firmware')
-rw-r--r--firmware/SOURCES1
-rw-r--r--firmware/common/bsearch.c49
-rw-r--r--firmware/include/bsearch.h28
3 files changed, 78 insertions, 0 deletions
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