Quoting Diego Nieto Cid (2015-06-05 03:58:10) > 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.
Merged. This is indeed much nicer, thanks for following up on this :) > > * 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; > } > > -- > 2.1.4 > >