[hurd] 07/15: console-client: Fix lower range of binary search

[Samuel Thibault]

This is an automated email from the git hooks/post-receive script.

sthibault pushed a commit to branch upstream
in repository hurd.

commit db48e1651302797806f5656c856cf22e73761ea5
Author: Diego Nieto Cid <address@hidden>
Date:   Thu Jun 4 22:58:10 2015 -0300

    console-client: Fix lower range of binary search
    
    To prevent infinite recursion range checking was introduced
    as an exit condition adding two extra comparisons on each
    recursive call.
    
    By fixing the range used by the recursive call over the lower
    half of the array one can avoid penalizing successful lookups
    while still preventing infinite recursion due to `first`
    parameter being greater than `last` parameter.
    
    * console-client/xkb/kstoucs.c (find_ucs): don't remove middle from the
    lower range. Remove extra comparisons.
---
 console-client/xkb/kstoucs.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/console-client/xkb/kstoucs.c b/console-client/xkb/kstoucs.c
index fb62445..eb47bde 100644
--- a/console-client/xkb/kstoucs.c
+++ b/console-client/xkb/kstoucs.c
@@ -17,15 +17,15 @@ find_ucs (int keysym, struct ksmap *first, struct ksmap 
*last)
 
   if (middle->keysym == keysym)
     return middle->ucs; /* base case: needle found. */
-  else if (first == last               /* empty search space */
-           || keysym < first->keysym   /* lookup failure */
-           || keysym > last->keysym)   /* lookup failure */
+  else if (first == last) /* empty search space */
     return 0;
   /* recursive cases: halve search space. */
   else if (middle->keysym < keysym)
     return find_ucs (keysym, middle+1, last);
   else if (middle->keysym > keysym)
-    return find_ucs (keysym, first, middle-1);
+    /* don't remove middle from the range to compensate
+       for rounding down in it's calculation */
+    return find_ucs (keysym, first, middle);
   return 0;
 }
 

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-hurd/hurd.git