Alexandre Julliard : ntdll: Reimplement bsearch to avoid redundant and possibly out of bounds comparisons .

Alexandre Julliard julliard at winehq.org
Mon May 24 11:30:47 CDT 2010


Module: wine
Branch: master
Commit: 4dae774893615c1d78f7ddc46a2b20ab548b302a
URL:    http://source.winehq.org/git/wine.git/?a=commit;h=4dae774893615c1d78f7ddc46a2b20ab548b302a

Author: Alexandre Julliard <julliard at winehq.org>
Date:   Sun May 23 22:25:06 2010 +0200

ntdll: Reimplement bsearch to avoid redundant and possibly out of bounds comparisons.

---

 dlls/ntdll/misc.c |   25 +++++++++----------------
 1 files changed, 9 insertions(+), 16 deletions(-)

diff --git a/dlls/ntdll/misc.c b/dlls/ntdll/misc.c
index eedef65..621848e 100644
--- a/dlls/ntdll/misc.c
+++ b/dlls/ntdll/misc.c
@@ -302,27 +302,20 @@ void * __cdecl
 NTDLL_bsearch( const void *key, const void *base, size_t nmemb,
                size_t size, int (__cdecl *compar)(const void *, const void *) )
 {
-    int begin, end, cursor;
-
-    begin = 0;
-    end = nmemb-1;
-    while (1) {
-	int ret;
-        cursor = (end-begin)/2+begin;
-        ret = compar(key,(char*)base+(cursor*size));
+    ssize_t min = 0;
+    ssize_t max = nmemb - 1;
+
+    while (min <= max)
+    {
+        ssize_t cursor = (min + max) / 2;
+        int ret = compar(key,(const char *)base+(cursor*size));
         if (!ret)
             return (char*)base+(cursor*size);
         if (ret < 0)
-            end = cursor;
+            max = cursor - 1;
         else
-            begin = cursor;
-        if ((end-begin)<=1)
-            break;
+            min = cursor + 1;
     }
-    if (!compar(key,(char*)base+(begin*size)))
-        return (char*)base+(begin*size);
-    if (!compar(key,(char*)base+(end*size)))
-        return (char*)base+(end*size);
     return NULL;
 }
 




More information about the wine-cvs mailing list