From 1412a69926307b2736745737c7c66172ebc56724 Mon Sep 17 00:00:00 2001 From: Keith Packard Date: Wed, 29 May 2002 08:21:33 +0000 Subject: [PATCH] Apply some obvious fixes to FcFontSetSort from Owen. Speed up FcCharSet primitives and FcFontSetSort --- fontconfig/fontconfig.h | 8 +- src/fccfg.c | 10 +- src/fccharset.c | 197 ++++++++++++++++++++++++++++++++++++++-- src/fcint.h | 3 +- src/fcmatch.c | 23 ++++- 5 files changed, 219 insertions(+), 22 deletions(-) diff --git a/fontconfig/fontconfig.h b/fontconfig/fontconfig.h index db4ff3b..eef136d 100644 --- 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 a35215a..edb6df3 100644 --- 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 b0251d7..f154346 100644 --- 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 713d09c..334883a 100644 --- 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 7ce4f06..62fb403 100644 --- 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: -- 2.39.5