[Fontconfig] fontconfig: Branch 'master'

[Akira TAGOH]

 src/fcblanks.c |   21 ++++++++++++++++++---
 1 file changed, 18 insertions(+), 3 deletions(-)

New commits:
commit 96a3f6879c13577cc9edd867b3f89b0cba469073
Author: Akira TAGOH <akira at tagoh.org>
Date:   Thu Mar 5 17:52:04 2015 +0900

    Improve the performance on searching blanks
    
    After the change of d6a5cc665a1d7e91332944353e92c83ad114368c
    we have a lot of code points in FcBlanks. doing the linear search
    on the array isn't comfortable anymore.
    So re-implementing FcBlanksIsMember() to use the binary search.
    
    Figuring out how much improved after this change depends on
    how many fonts proceed with fc-cache say though, it's about 20 times
    faster here on testing. which sounds good enough for
    improvement.

diff --git a/src/fcblanks.c b/src/fcblanks.c
index 49f520b..f163a8f 100644
--- a/src/fcblanks.c
+++ b/src/fcblanks.c
@@ -82,11 +82,26 @@ FcBlanksAdd (FcBlanks *b, FcChar32 ucs4)
 FcBool
 FcBlanksIsMember (FcBlanks *b, FcChar32 ucs4)
 {
-    int	i;
+    int lower = 0, higher = b->nblank, middle;
 
-    for (i = 0; i < b->nblank; i++)
-	if (b->blanks[i] == ucs4)
+    if (b->nblank == 0 ||
+	b->blanks[0] > ucs4 ||
+	b->blanks[b->nblank - 1] < ucs4)
+	return FcFalse;
+    while (1)
+    {
+	middle = (lower + higher) / 2;
+	if (b->blanks[middle] == ucs4)
 	    return FcTrue;
+	if (middle == lower ||
+	    middle == higher)
+	    break;
+	if (b->blanks[middle] < ucs4)
+	    lower = middle + 1;
+	else
+	    higher = middle - 1;
+    }
+
     return FcFalse;
 }
 #define __fcblanks__