diff options
| -rw-r--r-- | ChangeLog | 6 | ||||
| -rw-r--r-- | bits/stdlib-bsearch.h | 43 | ||||
| -rw-r--r-- | stdlib/bsearch.c | 31 | ||||
| -rw-r--r-- | stdlib/stdlib.h | 4 |
4 files changed, 56 insertions, 28 deletions
diff --git a/ChangeLog b/ChangeLog index e6a7fdf491..99ec09702e 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +2013-02-09 Ondřej Bílka <neleai@seznam.cz> + + * bits/stdlib-bsearch.h: New file. + * stdlib/bsearch.c: Include bits/stdlib-bsearch.h. + * stdlib/stdlib.h (bsearch): Add inline bsearch. + 2013-02-11 Roland McGrath <roland@hack.frob.com> * manual/conf.texi (General Limits): Fix SSIZE_MAX type to ssize_t. diff --git a/bits/stdlib-bsearch.h b/bits/stdlib-bsearch.h new file mode 100644 index 0000000000..4cb58abe6c --- /dev/null +++ b/bits/stdlib-bsearch.h @@ -0,0 +1,43 @@ +/* Perform binary search - inline version. + Copyright (C) 1991-2013 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, see + <http://www.gnu.org/licenses/>. */ + +__extern_inline void * +bsearch (const void *__key, const void *__base, size_t __nmemb, size_t __size, + __compar_fn_t __compar) +{ + 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; +} diff --git a/stdlib/bsearch.c b/stdlib/bsearch.c index 55b4f37527..4a357efeef 100644 --- a/stdlib/bsearch.c +++ b/stdlib/bsearch.c @@ -17,32 +17,7 @@ #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; -} +#undef __extern_inline +#define __extern_inline /* Empty, so we get a normal definition. */ +#include <bits/stdlib-bsearch.h> libc_hidden_def (bsearch) diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h index b49a41cc5d..fa1175c028 100644 --- a/stdlib/stdlib.h +++ b/stdlib/stdlib.h @@ -756,6 +756,10 @@ extern void *bsearch (const void *__key, const void *__base, size_t __nmemb, size_t __size, __compar_fn_t __compar) __nonnull ((1, 2, 5)) __wur; +#ifdef __USE_EXTERN_INLINES +# include <bits/stdlib-bsearch.h> +#endif + /* Sort NMEMB elements of BASE, of SIZE bytes each, using COMPAR to perform the comparisons. */ extern void qsort (void *__base, size_t __nmemb, size_t __size, |