summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDiego Nieto Cid <dnietoc@gmail.com>2015-06-04 22:58:10 -0300
committerJustus Winter <4winter@informatik.uni-hamburg.de>2015-06-05 18:34:02 +0200
commitdb48e1651302797806f5656c856cf22e73761ea5 (patch)
treee52eae39156d12d93f27932adde086d15f207a27
parentffea85471c65fd7758e159207ae7f7a089106644 (diff)
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.
-rw-r--r--console-client/xkb/kstoucs.c8
1 files changed, 4 insertions, 4 deletions
diff --git a/console-client/xkb/kstoucs.c b/console-client/xkb/kstoucs.c
index fb62445e..eb47bdeb 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;
}