[tyndur-devel] [PATCH 1/2] libc: Binäresuche für bsearch

[Andreas Freimuth <m.nemo@xxxxxxx>]

* libc/bsearch: sucht jetzt binär

Signed-off-by: Andreas Freimuth <m.nemo@xxxxxxx>
---
 src/lib/stdlibc/bsearch.c |   22 ++++++++++++++--------
 1 files changed, 14 insertions(+), 8 deletions(-)

diff --git a/src/lib/stdlibc/bsearch.c b/src/lib/stdlibc/bsearch.c
index ef64eda..39f0a9c 100644
--- a/src/lib/stdlibc/bsearch.c
+++ b/src/lib/stdlibc/bsearch.c
@@ -50,18 +50,24 @@
 void *bsearch(const void *key, const void *base, size_t nel,
     size_t width, int (*compar)(const void *, const void *))
 {
-    size_t i;
     const void* obj;
 
-    // FIXME Binaer suchen ginge schneller...
+    if (nel == 0) {
+        return NULL;
+    }
+
+    obj = base + (width * (nel >> 1));
+    int cmp = compar(key, obj);
 
-    for (i = 0; i < nel; i++) {
-        obj = base + (width * i);
-        if (compar(key, obj) == 0) {
-            return (void*) obj;
+    if (cmp == 0) {
+        return (void*)obj;
+    } else if (cmp < 0) {
+        if (nel >> 1 == 0) {
+            return NULL;
         }
+        return bsearch(key, base, nel - (nel >> 1), width, compar);
+    } else {
+        return bsearch(key, obj + width, nel - (nel >> 1) - 1, width, compar);
     }
-
-    return NULL;
 }
 
-- 
1.7.6.4