Apply some obvious fixes to FcFontSetSort from Owen. Speed up FcCharSet

    primitives and FcFontSetSort

diff --git a/fontconfig/fontconfig.h b/fontconfig/fontconfig.h
index db4ff3b910c723bdf00a073696c061cbb788648b..eef136d2cef43ec74e04842376af13d16b7a5bfc 100644 (file)
--- a/fontconfig/fontconfig.h
+++ b/fontconfig/fontconfig.h
@@ -1,5 +1,5 @@
 /*
- * $XFree86: xc/lib/fontconfig/fontconfig/fontconfig.h,v 1.9 2002/05/22 04:37:07 keithp Exp $
+ * $XFree86: xc/lib/fontconfig/fontconfig/fontconfig.h,v 1.11 2002/05/24 05:20:02 keithp Exp $
  *
  * Copyright © 2001 Keith Packard, member of The XFree86 Project, Inc.
  *
@@ -347,6 +347,9 @@ FcCharSetIntersectCount (const FcCharSet *a, const FcCharSet *b);
 FcChar32
 FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b);
 
+FcBool
+FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b);
+
 #define FC_CHARSET_MAP_SIZE (256/32)
 #define FC_CHARSET_DONE        ((FcChar32) -1)
 
@@ -513,6 +516,9 @@ FcFontSetSort (FcConfig         *config,
               FcCharSet    **csp,
               FcResult     *result);
 
+void
+FcFontSetSortDestroy (FcFontSet *fs);
+
 /* fcmatrix.c */
 FcMatrix *
 FcMatrixCopy (const FcMatrix *mat);

diff --git a/src/fccfg.c b/src/fccfg.c
index a35215ae8c042fa2e4fe85fd7cdb30dccc768489..edb6df30e42bf39fe98027059b1dc28ca3906c59 100644 (file)
--- a/src/fccfg.c
+++ b/src/fccfg.c
@@ -1,5 +1,5 @@
 /*
- * $XFree86: xc/lib/fontconfig/src/fccfg.c,v 1.5 2002/03/01 01:00:54 keithp Exp $
+ * $XFree86: xc/lib/fontconfig/src/fccfg.c,v 1.6 2002/05/21 17:06:22 keithp Exp $
  *
  * Copyright © 2000 Keith Packard, member of The XFree86 Project, Inc.
  *
@@ -559,8 +559,8 @@ FcConfigCompareValue (FcValue       m,
        case FcTypeCharSet:
            switch (op) {
            case FcOpContains:
-               /* m contains v if v - m is empty */
-               ret = FcCharSetSubtractCount (v.u.c, m.u.c) == 0;
+               /* m contains v if v is a subset of m */
+               ret = FcCharSetIsSubset (v.u.c, m.u.c);
                break;
            case FcOpEqual:
                ret = FcCharSetEqual (m.u.c, v.u.c);
@@ -804,9 +804,9 @@ FcConfigEvaluate (FcPattern *p, FcExpr *e)
            case FcTypeCharSet:
                switch (e->op) {
                case FcOpContains:
-                   /* vl contains vr if vr - vl is empty */
+                   /* vl contains vr if vr is a subset of vl */
                    v.type = FcTypeBool;
-                   v.u.b = FcCharSetSubtractCount (vr.u.c, vl.u.c) == 0;
+                   v.u.b = FcCharSetIsSubset (vr.u.c, vl.u.c);
                    break;
                case FcOpEqual:
                    v.type = FcTypeBool;

diff --git a/src/fccharset.c b/src/fccharset.c
index b0251d7567bbb46b5fb117904c48accaab8d37b6..f15434685ce15e920291a95edd930c98170b9702 100644 (file)
--- a/src/fccharset.c
+++ b/src/fccharset.c
@@ -1,5 +1,5 @@
 /*
- * $XFree86: xc/lib/fontconfig/src/fccharset.c,v 1.6 2002/03/27 04:33:55 keithp Exp $
+ * $XFree86: xc/lib/fontconfig/src/fccharset.c,v 1.7 2002/05/24 05:20:02 keithp Exp $
  *
  * Copyright © 2001 Keith Packard, member of The XFree86 Project, Inc.
  *
@@ -67,6 +67,7 @@ FcCharSetCheckLevel (FcCharSet *fcs, FcChar32 ucs4)
                return FcFalse;
            FcMemAlloc (FC_MEM_CHARNODE, sizeof (FcCharBranch));
            branch->nodes[0] = fcs->node;
+           /* next pointers are all zero */
            fcs->node.branch = branch;
        }
        ++fcs->levels;
@@ -169,7 +170,9 @@ FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
 {
     int                    l;
     FcCharNode     *prev, node;
-    FcChar32       i;
+    FcChar32       i = 0;
+    int                    j;
+    FcChar8        *next = 0, old;
 
     if (!FcCharSetCheckLevel (fcs, ucs4))
        return FcFalse;
@@ -185,9 +188,16 @@ FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
                return 0;
            FcMemAlloc (FC_MEM_CHARNODE, sizeof (FcCharBranch));
            *prev = node;
+           if (next)
+           {
+               old = next[i];
+               for (j = (int) i - 1; j >= 0 && next[j] == old; j--)
+                   next[j] = i;
+           }
        }
        i = (ucs4 >> (l << 3)) & 0xff;
        prev = &node.branch->nodes[i];
+       next = &node.branch->next[0];
     }
     node = *prev;
     if (!node.leaf)
@@ -197,6 +207,13 @@ FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
            return 0;
        FcMemAlloc (FC_MEM_CHARNODE, sizeof (FcCharLeaf));
        *prev = node;
+       ucs4 = ucs4 & ~0xff;
+       if (next)
+       {
+           old = next[i];
+           for (j = i - 1; j >= 0 && next[j] == old; j--)
+               next[j] = i;
+       }
     }
     return node.leaf;
 }
@@ -224,6 +241,8 @@ FcCharSetAddChar (FcCharSet *fcs, FcChar32 ucs4)
 typedef struct _fcCharSetIter {
     FcCharLeaf     *leaf;
     FcChar32       ucs4;
+    FcCharBranch    *branch_stack[5];
+    int                    branch_stackp;
 } FcCharSetIter;
 
 /*
@@ -265,25 +284,146 @@ FcCharSetIterLeaf (FcCharNode node, int level, FcChar32 *ucs4)
 static void
 FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
 {
-    if (FcCharSetLevels (iter->ucs4) > fcs->levels)
+    int                    level = fcs->levels;
+    FcChar32       ucs4 = iter->ucs4;
+    FcCharNode     node = fcs->node;
+
+    iter->branch_stackp = 0;
+    if (ucs4 >= 1 << (level << 3))
+    {
        iter->leaf = 0;
-    else
-       iter->leaf = FcCharSetIterLeaf (fcs->node, fcs->levels,
-                                       &iter->ucs4);
-    if (!iter->leaf)
        iter->ucs4 = ~0;
+       return;
+    }
+    if (level > 1)
+    {
+       level--;
+       for (;;)
+       {
+           FcCharBranch        *branch = node.branch;
+           FcChar32            byte;
+    
+           byte = (ucs4 >> (level << 3)) & 0xff;
+           
+           node = branch->nodes[byte];
+           if (!node.leaf)
+           {
+               while (!(byte = branch->next[byte]))
+               {
+                   if (iter->branch_stackp == 0)
+                   {
+                       iter->leaf = 0;
+                       iter->ucs4 = ~0;
+                       return;
+                   }
+                   branch = node.branch = iter->branch_stack[--iter->branch_stackp];
+                   level++;
+                   ucs4 += 1 << (level << 3);
+                   byte = (ucs4 >> (level << 3)) & 0xff;
+               }
+               ucs4 = (ucs4 & ~ ((1 << ((level + 1) << 3)) - 1)) |
+                           (byte << (level << 3));
+               node = branch->nodes[byte];
+           }
+           iter->branch_stack[iter->branch_stackp++] = branch;
+           if (--level == 0)
+               break;
+       }
+    }
+    if (!(iter->leaf = node.leaf))
+       ucs4 = ~0;
+    iter->ucs4 = ucs4;
+#if 0
+    printf ("set %08x: %08x\n", ucs4, node.leaf);
+#endif
 }
 
 static void
 FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
 {
-    iter->ucs4 += 0x100;
-    FcCharSetIterSet (fcs, iter);
+    FcCharNode     node;
+    FcCharBranch    *branch;
+    FcChar32       ucs4;
+    int                    level;
+
+    if (!iter->branch_stackp)
+    {
+       iter->ucs4 = ~0;
+       iter->leaf = 0;
+       return;
+    }
+
+    level = 1;
+    node.branch = iter->branch_stack[--iter->branch_stackp];
+    ucs4 = iter->ucs4;
+    for (;;)
+    {
+       FcChar32    byte;
+
+       branch = node.branch;
+       while (!(byte = branch->next[(ucs4 >> (level << 3)) & 0xff]))
+       {
+           if (iter->branch_stackp == 0)
+           {
+               iter->leaf = 0;
+               iter->ucs4 = ~0;
+               return;
+           }
+           branch = node.branch = iter->branch_stack[--iter->branch_stackp];
+           level++;
+           ucs4 += 1 << (level << 3);
+       }
+        ucs4 = (ucs4 & ~ ((1 << ((level + 1) << 3)) - 1)) |
+               (byte << (level << 3));
+        node = branch->nodes[byte];
+        iter->branch_stack[iter->branch_stackp++] = branch;
+       if (--level == 0)
+           break;
+    }
+    iter->ucs4 = ucs4;
+    iter->leaf = node.leaf;
 }
 
+#if 0
+static void
+FcCharSetDump (FcCharNode node, int level, FcChar32 ucs4, int indent)
+{
+    if (level)
+    {
+       if (node.branch)
+       {
+           FcChar32    inc = (1 << (level << 3));
+           int         i;
+           FcCharBranch    *branch = node.branch;
+    
+           for (i = 0; i < indent; i++)
+               printf ("    ");
+           printf ("%08x: %08x\n", ucs4, branch);
+           for (i = 0; i < 256; i++)
+           {
+               FcCharSetDump (branch->nodes[i], level - 1, ucs4, indent+1);
+               ucs4 += inc;
+           }
+       }
+    }
+    else
+    {
+       if (node.leaf)
+       {
+           while (indent--)
+               printf ("    ");
+           printf ("%08x: %08x\n", ucs4, node.leaf);
+       }
+    }
+}
+#endif
+
 static void
 FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
 {
+#if 0
+    FcCharSetDump (fcs->node, fcs->levels - 1, 0, 0);
+#endif
     iter->ucs4 = 0;
     FcCharSetIterSet (fcs, iter);
 }
@@ -345,7 +485,7 @@ FcCharSetOperate (const FcCharSet   *a,
        goto bail0;
     FcCharSetIterStart (a, &ai);
     FcCharSetIterStart (b, &bi);
-    while ((ai.leaf || bonly) && (bi.leaf || aonly))
+    while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
     {
        if (ai.ucs4 < bi.ucs4)
        {
@@ -557,6 +697,43 @@ FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b)
     return count;
 }
 
+/*
+ * return FcTrue iff a is a subset of b
+ */
+FcBool
+FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
+{
+    FcCharSetIter   ai, bi;
+    
+    FcCharSetIterStart (a, &ai);
+    while (ai.leaf)
+    {
+       bi.ucs4 = ai.ucs4;
+       FcCharSetIterSet (b, &bi);
+       /*
+        * Check if a has a page that b does not
+        */
+       if (ai.ucs4 < bi.ucs4)
+           return FcFalse;
+       /*
+        * Check if they have a page in common, if so,
+        * look to see if there any bits in a not in b
+        */
+       if (ai.ucs4 == bi.ucs4)
+       {
+           FcChar32    *am = ai.leaf->map;
+           FcChar32    *bm = bi.leaf->map;
+           int         i = 256/32;
+           
+           while (i--)
+               if (*am++ & ~*bm++)
+                   return FcFalse;
+       }
+       FcCharSetIterNext (a, &ai);
+    }
+    return FcTrue;
+}
+
 /*
  * These two functions efficiently walk the entire charmap for
  * other software (like pango) that want their own copy

diff --git a/src/fcint.h b/src/fcint.h
index 713d09c9864866a9057d29d392533b28fc38287c..334883a4c344644e46de3c63af2ee15b1cfff2af 100644 (file)
--- a/src/fcint.h
+++ b/src/fcint.h
@@ -1,5 +1,5 @@
 /*
- * $XFree86: xc/lib/fontconfig/src/fcint.h,v 1.4 2002/02/19 08:33:23 keithp Exp $
+ * $XFree86: xc/lib/fontconfig/src/fcint.h,v 1.8 2002/05/21 17:06:22 keithp Exp $
  *
  * Copyright © 2000 Keith Packard, member of The XFree86 Project, Inc.
  *
@@ -171,6 +171,7 @@ union _FcCharNode {
 
 struct _FcCharBranch {
     FcCharNode     nodes[256];
+    FcChar8        next[256];
 };
 
 struct _FcCharSet {

diff --git a/src/fcmatch.c b/src/fcmatch.c
index 7ce4f060fb16ea8110e6a7c96b41be4db2cf1f8a..62fb403d3fb5c091a93f9986c69ac8de26795546 100644 (file)
--- a/src/fcmatch.c
+++ b/src/fcmatch.c
@@ -398,9 +398,9 @@ FcSortCompare (const void *aa, const void *ab)
     for (i = 0; i < NUM_MATCHER; i++)
     {
        if (a->score[i] > b->score[i])
-           return -1;
-       if (a->score[i] < b->score[i])
            return 1;
+       if (a->score[i] < b->score[i])
+           return -1;
     }
     return 0;
 }
@@ -417,7 +417,11 @@ FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool tri
        if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) == 
            FcResultMatch)
        {
-           if (!trim || !*cs || FcCharSetSubtractCount (ncs, *cs) != 0)
+           /*
+            * If this font isn't a subset of the previous fonts,
+            * add it to the list
+            */
+           if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
            {
                if (*cs)
                {
@@ -437,6 +441,13 @@ FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool tri
     return FcTrue;
 }
 
+void
+FcFontSetSortDestroy (FcFontSet *fs)
+{
+    fs->nfont = 0;
+    FcFontSetDestroy (fs);
+}
+
 FcFontSet *
 FcFontSetSort (FcConfig            *config,
               FcFontSet    **sets,
@@ -470,7 +481,7 @@ FcFontSetSort (FcConfig         *config,
     nodes = malloc (nnodes * sizeof (FcSortNode) + nnodes * sizeof (FcSortNode *));
     if (!nodes)
        goto bail0;
-    nodeps = (FcSortNode **) nodes + nnodes;
+    nodeps = (FcSortNode **) (nodes + nnodes);
     
     new = nodes;
     nodep = nodeps;
@@ -506,7 +517,7 @@ FcFontSetSort (FcConfig         *config,
 
     nnodes = new - nodes;
     
-    qsort (nodeps, sizeof (FcSortNode *), nnodes,
+    qsort (nodeps, nnodes, sizeof (FcSortNode *),
           FcSortCompare);
 
     ret = FcFontSetCreate ();
@@ -520,6 +531,8 @@ FcFontSetSort (FcConfig         *config,
 
     *csp = cs;
 
+    free (nodes);
+
     return ret;
 
 bail2: