[Mesa-dev] [PATCH 2/3] glx/glvnd: Use strcmp() based binary search in FindGLXFunction()

[Kyle Brenneman]

That binary search needs to set middle inside the while loop, not just 
once at the top.

Also, I think that should be "last = middle - 1", not "last = middle".

-Kyle

On 05/11/2016 12:01 PM, Adam Jackson wrote:
> From: Emil Velikov <emil.velikov at collabora.com>
>
> It will allows us to find the function within 6 attempts, out of the ~80
> entry long table.
>
> Reviewed-by: Adam Jackson <ajax at redhat.com>
> Signed-off-by: Emil Velikov <emil.velikov at collabora.com>
> ---
>   src/glx/glxglvnd.c | 17 +++++++++++++----
>   1 file changed, 13 insertions(+), 4 deletions(-)
>
> diff --git a/src/glx/glxglvnd.c b/src/glx/glxglvnd.c
> index c7c35ca..9475023 100644
> --- a/src/glx/glxglvnd.c
> +++ b/src/glx/glxglvnd.c
> @@ -19,11 +19,20 @@ static void *__glXGLVNDGetProcAddress(const GLubyte *procName)
>   
>   static int FindGLXFunction(const GLubyte *name)
>   {
> -    int i;
> +    unsigned first = 0;
> +    unsigned last = DI_FUNCTION_COUNT - 1;
> +    unsigned middle = (first + last) / 2;
>   
> -    for (i = 0; i < DI_FUNCTION_COUNT; i++) {
> -        if (strcmp((const char *) name, __glXDispatchTableStrings[i]) == 0)
> -            return i;
> +    while (first <= last) {
> +        int comp = strcmp((const char *) name,
> +                          __glXDispatchTableStrings[middle]);
> +
> +        if (comp < 0)
> +            first = middle + 1;
> +        else if (comp > 0)
> +            last = middle;
> +        else
> +            return middle;
>       }
>       return -1;
>   }