From eab7e54981017d7b87242505a215a370dfcd5024 Mon Sep 17 00:00:00 2001 From: Emil Velikov Date: Wed, 11 May 2016 14:01:54 -0400 Subject: [PATCH] glx/glvnd: Use strcmp() based binary search in FindGLXFunction() It will allows us to find the function within 6 attempts, out of the ~80 entry long table. v2: calculate middle on each iteration, correctly set the lower limit. Reviewed-by: Adam Jackson (v1) Signed-off-by: Emil Velikov --- src/glx/glxglvnd.c | 19 ++++++++++++++----- 1 file changed, 14 insertions(+), 5 deletions(-) diff --git a/src/glx/glxglvnd.c b/src/glx/glxglvnd.c index c7c35ca3a14..96cd1fd7e95 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; - - for (i = 0; i < DI_FUNCTION_COUNT; i++) { - if (strcmp((const char *) name, __glXDispatchTableStrings[i]) == 0) - return i; + unsigned first = 0; + unsigned last = DI_FUNCTION_COUNT - 1; + + while (first <= last) { + unsigned middle = (first + last) / 2; + int comp = strcmp((const char *) name, + __glXDispatchTableStrings[middle]); + + if (comp < 0) + first = middle + 1; + else if (comp > 0) + last = middle - 1; + else + return middle; } return -1; } -- 2.30.2