src/fcblanks.c | 21 ++++++++++++++++++---
1 file changed, 18 insertions(+), 3 deletions(-)
New commits:
commit 96a3f6879c13577cc9edd867b3f89b0cba469073
Author: Akira TAGOH <akira@xxxxxxxxx>
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__
_______________________________________________
Fontconfig mailing list
Fontconfig@xxxxxxxxxxxxxxxxxxxxx
http://lists.freedesktop.org/mailman/listinfo/fontconfig
