[PATCH] Reduce number of allocations during FcSortWalk().

[Chris Wilson]

The current behaviour of FcSortWalk() is to create a new FcCharSet on
each iteration that is the union of the previous iteration with the next
FcCharSet in the font set. This causes the existing FcCharSet to be
reproduced in its entirety and then allocates fresh leaves for the new
FcCharSet. In essence the number of allocations is quadratic wrt the
number of fonts required.

By introducing a new method for merging a new FcCharSet with an existing
one we can change the behaviour to be effectively linear with the number
of fonts - allocating no more leaves than necessary to cover all the
fonts in the set.

For example, profiling 'gedit UTF-8-demo.txt'
    Allocator		    nAllocs	    nBytes
Before:
    FcCharSetFindLeafCreate 62886	    2012352
    FcCharSetPutLeaf        9361	    11441108
After:
    FcCharSetFindLeafCreate 1940	    62080
    FcCharSetPutLeaf        281		    190336
---
 fontconfig/fontconfig.h |    3 ++
 src/fccharset.c         |   71 +++++++++++++++++++++++++++++++++++++----------
 src/fcmatch.c           |   13 ++------
 3 files changed, 62 insertions(+), 25 deletions(-)

diff --git a/fontconfig/fontconfig.h b/fontconfig/fontconfig.h
index 36e4ccc..445657d 100644
--- a/fontconfig/fontconfig.h
+++ b/fontconfig/fontconfig.h
@@ -427,6 +427,9 @@ FcPublic FcCharSet*
 FcCharSetUnion (const FcCharSet *a, const FcCharSet *b);
 
 FcPublic FcCharSet*
+FcCharSetMerge (FcCharSet *a, const FcCharSet *b);
+
+FcPublic FcCharSet*
 FcCharSetSubtract (const FcCharSet *a, const FcCharSet *b);
 
 FcPublic FcBool
diff --git a/src/fccharset.c b/src/fccharset.c
index 5da1312..3a6c003 100644
--- a/src/fccharset.c
+++ b/src/fccharset.c
@@ -348,7 +348,8 @@ FcCharSetAddLeaf (FcCharSet	*fcs,
 }
 
 static FcCharSet *
-FcCharSetOperate (const FcCharSet   *a,
+FcCharSetOperate (FcCharSet *fcs,
+	          const FcCharSet   *a,
 		  const FcCharSet   *b,
 		  FcBool	    (*overlap) (FcCharLeaf	    *result,
 						const FcCharLeaf    *al,
@@ -356,12 +357,8 @@ FcCharSetOperate (const FcCharSet   *a,
 		  FcBool	aonly,
 		  FcBool	bonly)
 {
-    FcCharSet	    *fcs;
     FcCharSetIter   ai, bi;
 
-    fcs = FcCharSetCreate ();
-    if (!fcs)
-	goto bail0;
     FcCharSetIterStart (a, &ai);
     FcCharSetIterStart (b, &bi);
     while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
@@ -371,7 +368,7 @@ FcCharSetOperate (const FcCharSet   *a,
 	    if (aonly)
 	    {
 		if (!FcCharSetAddLeaf (fcs, ai.ucs4, ai.leaf))
-		    goto bail1;
+		    return NULL;
 		FcCharSetIterNext (a, &ai);
 	    }
 	    else
@@ -385,7 +382,7 @@ FcCharSetOperate (const FcCharSet   *a,
 	    if (bonly)
 	    {
 		if (!FcCharSetAddLeaf (fcs, bi.ucs4, bi.leaf))
-		    goto bail1;
+		    return NULL;
 		FcCharSetIterNext (b, &bi);
 	    }
 	    else
@@ -401,17 +398,36 @@ FcCharSetOperate (const FcCharSet   *a,
 	    if ((*overlap) (&leaf, ai.leaf, bi.leaf))
 	    {
 		if (!FcCharSetAddLeaf (fcs, ai.ucs4, &leaf))
-		    goto bail1;
+		    return NULL;
 	    }
 	    FcCharSetIterNext (a, &ai);
 	    FcCharSetIterNext (b, &bi);
 	}
     }
     return fcs;
-bail1:
-    FcCharSetDestroy (fcs);
-bail0:
-    return 0;
+}
+
+static FcCharSet *
+FcCharSetOperateCreate (const FcCharSet   *a,
+			const FcCharSet   *b,
+			FcBool	    (*overlap) (FcCharLeaf	    *result,
+						const FcCharLeaf    *al,
+						const FcCharLeaf    *bl),
+			FcBool	aonly,
+			FcBool	bonly)
+{
+    FcCharSet *fcs, *ret;
+
+    fcs = FcCharSetCreate ();
+    if (fcs == NULL)
+	return NULL;
+
+    ret = FcCharSetOperate (fcs, a, b, overlap, aonly, bonly);
+
+    if (ret == NULL)
+	FcCharSetDestroy (fcs);
+
+    return ret;
 }
 
 static FcBool
@@ -431,7 +447,7 @@ FcCharSetIntersectLeaf (FcCharLeaf *result,
 FcCharSet *
 FcCharSetIntersect (const FcCharSet *a, const FcCharSet *b)
 {
-    return FcCharSetOperate (a, b, FcCharSetIntersectLeaf, FcFalse, FcFalse);
+    return FcCharSetOperateCreate (a, b, FcCharSetIntersectLeaf, FcFalse, FcFalse);
 }
 
 static FcBool
@@ -449,7 +465,32 @@ FcCharSetUnionLeaf (FcCharLeaf *result,
 FcCharSet *
 FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
 {
-    return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
+    return FcCharSetOperateCreate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
+}
+
+FcCharSet *
+FcCharSetMerge (FcCharSet *a, const FcCharSet *b)
+{
+    FcCharSet *ret, *fcs;
+
+    if (a == NULL) {
+	return FcCharSetCopy ((FcCharSet *) b);
+    } else if (a->ref == FC_REF_CONSTANT) {
+	fcs = FcCharSetCreate ();
+	if (fcs == NULL)
+	    return NULL;
+    } else
+	fcs = a;
+
+    ret = FcCharSetOperate (fcs, a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
+
+    if (ret == NULL)
+	FcCharSetDestroy (fcs);
+
+    if (fcs != a)
+	FcCharSetDestroy (a);
+
+    return ret;
 }
 
 static FcBool
@@ -469,7 +510,7 @@ FcCharSetSubtractLeaf (FcCharLeaf *result,
 FcCharSet *
 FcCharSetSubtract (const FcCharSet *a, const FcCharSet *b)
 {
-    return FcCharSetOperate (a, b, FcCharSetSubtractLeaf, FcTrue, FcFalse);
+    return FcCharSetOperateCreate (a, b, FcCharSetSubtractLeaf, FcTrue, FcFalse);
 }
 
 FcBool
diff --git a/src/fcmatch.c b/src/fcmatch.c
index f041052..dc08655 100644
--- a/src/fcmatch.c
+++ b/src/fcmatch.c
@@ -602,16 +602,9 @@ FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool tri
 	    {
                 if (trim || build_cs)
                 {
-                    if (*cs)
-                    {
-                        ncs = FcCharSetUnion (ncs, *cs);
-                        if (!ncs)
-                            return FcFalse;
-                        FcCharSetDestroy (*cs);
-                    }
-                    else
-                        ncs = FcCharSetCopy (ncs);
-                    *cs = ncs;
+		    *cs = FcCharSetMerge (*cs, ncs);
+		    if (*cs == NULL)
+			return FcFalse;
                 }
 
 		FcPatternReference (node->pattern);
-- 
1.5.5.1


--=-gl8JK4SFssHjIDLW5O3E--