Re: [PATCH 2/2] console-client: Fix lower range of binary search

[Justus Winter]

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
> 
>