This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Add inline bsearch expansion


Hello, 
I looked into qsort/bsearch functions. Here I
added inline version of bsearch.

It saves multiplications instructions as size is 
most of time known in advance.
When compiled with gcc-4.7.1 and icc 12.1.4 with -O2
it can inline ccmp functions from example below.
gcc-4.5.3 does not inline ccmp.

int ccmp(char *a,char *b){
  return *a-*b;
}
int main(int argc,char **argv){
  char x=42;
  return *((char*)bsearch(&x,argv[0],100,1,ccmp));
}

Same can be done with lsearch when I find application that
calls it.

tested on x86-64

OK for 2.18

  * stdlib/stdlib.h (bsearch): Add inline variant.

---
 stdlib/stdlib.h |   29 +++++++++++++++++++++++++++++
 1 files changed, 29 insertions(+), 0 deletions(-)

diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h
index fc83f4e..c14f0b3 100644
--- a/stdlib/stdlib.h
+++ b/stdlib/stdlib.h
@@ -755,6 +755,35 @@ extern void *bsearch (const void *__key, const void *__base,
 		      size_t __nmemb, size_t __size, __compar_fn_t __compar)
      __nonnull ((1, 2, 5)) __wur;
 
+
+extern inline
+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;
+}
+
+
 /* 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,
-- 
1.7.4.4


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]