From 74ab227b58ee3eae152c1142eb9144ee5332a7d9 Mon Sep 17 00:00:00 2001 From: Thomas Martitz Date: Mon, 18 Jul 2011 18:55:20 +0000 Subject: 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 --- firmware/include/bsearch.h | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100644 firmware/include/bsearch.h (limited to 'firmware/include') diff --git a/firmware/include/bsearch.h b/firmware/include/bsearch.h new file mode 100644 index 0000000..e113676 --- /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 -- cgit v1.1