diff options
| author | Justus Winter <4winter@informatik.uni-hamburg.de> | 2015-05-23 10:51:05 +0200 |
|---|---|---|
| committer | Justus Winter <4winter@informatik.uni-hamburg.de> | 2015-05-23 10:51:05 +0200 |
| commit | 7410d78ed496c66a6c1d806360d1f83aa3321c01 (patch) | |
| tree | 3b460f1713376e5df59a3e14e447ddd51c1c39d9 /console-client/xkb | |
| parent | 0df1499b87688d3e9ff6132617dac1631b7733f4 (diff) | |
console-client: fix binary search
Previously, the binary search through the keysym map was incorrectly
implemented. This resulted in infinite loops (thanks to the compilers
tail call optimization) or crashes (if the stack space was exhausted).
* console-client/xkb/kstoucs.c (find_ucs): Fix binary search.
Diffstat (limited to 'console-client/xkb')
| -rw-r--r-- | console-client/xkb/kstoucs.c | 6 |
1 files changed, 4 insertions, 2 deletions
diff --git a/console-client/xkb/kstoucs.c b/console-client/xkb/kstoucs.c index 81e71b9b..8471e942 100644 --- a/console-client/xkb/kstoucs.c +++ b/console-client/xkb/kstoucs.c @@ -13,8 +13,10 @@ find_ucs (int keysym, struct ksmap *first, struct ksmap *last) if (middle->keysym == keysym) return middle->ucs; /* base case: needle found. */ - else if (middle == first && middle == last) - return 0; /* base case: empty search space. */ + else if (first == last /* empty search space */ + || keysym < first->keysym /* lookup failure */ + || keysym > last->keysym) /* lookup failure */ + return 0; /* recursive cases: halve search space. */ else if (middle->keysym < keysym) return find_ucs (keysym, middle+1, last); |