--- /dev/null
+/*
+ * $XFree86: $
+ *
+ * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission. Keith Packard makes no
+ * representations about the suitability of this software for any purpose. It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+/*
+ * Semi-Balanced trees (avl). This only contains two
+ * routines - insert and delete. Searching is
+ * reserved for the client to write.
+ */
+
+#include "fcint.h"
+#include "fcavl.h"
+
+static FcBool
+FcAvlRebalanceRight (FcAvlNode **);
+
+static FcBool
+FcAvlRebalanceLeft (FcAvlNode **);
+
+/*
+ * insert a new node
+ *
+ * this routine returns FcTrue if the tree has grown
+ * taller
+ */
+
+FcBool
+FcAvlInsert (FcAvlMore more, FcAvlNode **treep, FcAvlNode *new)
+{
+ if (!(*treep))
+ {
+ new->left = 0;
+ new->right = 0;
+ new->balance = 0;
+ *treep = new;
+ return FcTrue;
+ }
+ else
+ {
+ if ((*more) (new, *treep))
+ {
+ if (FcAvlInsert (more, &(*treep)->right, new))
+ switch (++(*treep)->balance) {
+ case 0:
+ return FcFalse;
+ case 1:
+ return FcTrue;
+ case 2:
+ (void) FcAvlRebalanceRight (treep);
+ }
+ }
+ else
+ {
+ if (FcAvlInsert (more, &(*treep)->left, new))
+ switch (--(*treep)->balance) {
+ case 0:
+ return FcFalse;
+ case -1:
+ return FcTrue;
+ case -2:
+ (void) FcAvlRebalanceLeft (treep);
+ }
+ }
+ }
+ return 0;
+}
+
+/*
+ * delete a node from a tree
+ *
+ * this routine return FcTrue if the tree has been shortened
+ */
+
+FcBool
+FcAvlDelete (FcAvlMore more, FcAvlNode **treep, FcAvlNode *old)
+{
+ if (!*treep)
+ return FcFalse; /* node not found */
+ if (old == *treep)
+ {
+ FcAvlNode *replacement;
+ FcAvlNode *replacement_parent;
+ int replacement_direction;
+ int delete_direction;
+ FcAvlNode *swap_temp;
+ int balance_temp;
+
+ /*
+ * find an empty down pointer (if any)
+ * and rehook the tree
+ */
+ if (!old->right) {
+ (*treep) = old->left;
+ return FcTrue;
+ } else if (!old->left) {
+ (*treep) = old->right;
+ return FcTrue;
+ } else {
+ /*
+ * if both down pointers are full, then
+ * move a node from the bottom of the tree up here.
+ *
+ * This builds an incorrect tree -- the replacement
+ * node and the old node will not
+ * be in correct order. This doesn't matter as
+ * the old node will obviously not leave
+ * this routine alive.
+ */
+ /*
+ * if the tree is left heavy, then go left
+ * else go right
+ */
+ replacement_parent = old;
+ if (old->balance == -1) {
+ delete_direction = -1;
+ replacement_direction = -1;
+ replacement = old->left;
+ while (replacement->right) {
+ replacement_parent = replacement;
+ replacement_direction = 1;
+ replacement = replacement->right;
+ }
+ } else {
+ delete_direction = 1;
+ replacement_direction = 1;
+ replacement = old->right;
+ while (replacement->left) {
+ replacement_parent = replacement;
+ replacement_direction = -1;
+ replacement = replacement->left;
+ }
+ }
+ /*
+ * swap the replacement node into
+ * the tree where the node is to be removed
+ *
+ * this would be faster if only the data
+ * element was swapped -- but that
+ * won't work for kalypso. The alternate
+ * code would be:
+ data_temp = old->data;
+ to _be_deleted->data = replacement->data;
+ replacement->data = data_temp;
+ */
+ swap_temp = old->left;
+ old->left = replacement->left;
+ replacement->left = swap_temp;
+
+ swap_temp = old->right;
+ old->right = replacement->right;
+ replacement->right = swap_temp;
+
+ balance_temp = old->balance;
+ old->balance = replacement->balance;
+ replacement->balance = balance_temp;
+ /*
+ * if the replacement node is directly below
+ * the to-be-removed node, hook the old
+ * node below it (instead of below itself!)
+ */
+ if (replacement_parent == old)
+ replacement_parent = replacement;
+ if (replacement_direction == -1)
+ replacement_parent->left = old;
+ else
+ replacement_parent->right = old;
+ (*treep) = replacement;
+ /*
+ * delete the node from the sub-tree
+ */
+ if (delete_direction == -1)
+ {
+ if (FcAvlDelete (more, &(*treep)->left, old))
+ {
+ switch (++(*treep)->balance) {
+ case 2:
+ abort ();
+ case 1:
+ return FcFalse;
+ case 0:
+ return FcTrue;
+ }
+ }
+ return 0;
+ }
+ else
+ {
+ if (FcAvlDelete (more, &(*treep)->right, old))
+ {
+ switch (--(*treep)->balance) {
+ case -2:
+ abort ();
+ case -1:
+ return FcFalse;
+ case 0:
+ return FcTrue;
+ }
+ }
+ return 0;
+ }
+ }
+ }
+ else if ((*more) (old, *treep))
+ {
+ if (FcAvlDelete (more, &(*treep)->right, old))
+ {
+ /*
+ * check the balance factors
+ * Note that the conditions are
+ * inverted from the insertion case
+ */
+ switch (--(*treep)->balance) {
+ case 0:
+ return FcFalse;
+ case -1:
+ return FcTrue;
+ case -2:
+ return FcAvlRebalanceLeft (treep);
+ }
+ }
+ return 0;
+ }
+ else
+ {
+ if (FcAvlDelete (more, &(*treep)->left, old))
+ {
+ switch (++(*treep)->balance) {
+ case 0:
+ return FcTrue;
+ case 1:
+ return FcFalse;
+ case 2:
+ return FcAvlRebalanceRight (treep);
+ }
+ }
+ return 0;
+ }
+ /*NOTREACHED*/
+}
+
+/*
+ * two routines to rebalance the tree.
+ *
+ * rebalance_right -- the right sub-tree is too long
+ * rebalance_left -- the left sub-tree is too long
+ *
+ * These routines are the heart of avl trees, I've tried
+ * to make their operation reasonably clear with comments,
+ * but some study will be necessary to understand the
+ * algorithm.
+ *
+ * these routines return FcTrue if the resultant
+ * tree is shorter than the un-balanced version. This
+ * is only of interest to the delete routine as the
+ * balance after insertion can never actually shorten
+ * the tree.
+ */
+
+static FcBool
+FcAvlRebalanceRight (FcAvlNode **treep)
+{
+ FcAvlNode *temp;
+ /*
+ * rebalance the tree
+ */
+ if ((*treep)->right->balance == -1) {
+ /*
+ * double whammy -- the inner sub-sub tree
+ * is longer than the outer sub-sub tree
+ *
+ * this is the "double rotation" from
+ * knuth. Scheme: replace the tree top node
+ * with the inner sub-tree top node and
+ * adjust the maze of pointers and balance
+ * factors accordingly.
+ */
+ temp = (*treep)->right->left;
+ (*treep)->right->left = temp->right;
+ temp->right = (*treep)->right;
+ switch (temp->balance) {
+ case -1:
+ temp->right->balance = 1;
+ (*treep)->balance = 0;
+ break;
+ case 0:
+ temp->right->balance = 0;
+ (*treep)->balance = 0;
+ break;
+ case 1:
+ temp->right->balance = 0;
+ (*treep)->balance = -1;
+ break;
+ }
+ temp->balance = 0;
+ (*treep)->right = temp->left;
+ temp->left = (*treep);
+ (*treep) = temp;
+ return FcTrue;
+ } else {
+ /*
+ * a simple single rotation
+ *
+ * Scheme: replace the tree top node
+ * with the sub-tree top node
+ */
+ temp = (*treep)->right->left;
+ (*treep)->right->left = (*treep);
+ (*treep) = (*treep)->right;
+ (*treep)->left->right = temp;
+ /*
+ * only two possible configurations --
+ * if the right sub-tree was balanced, then
+ * *both* sides of it were longer than the
+ * left side, so the resultant tree will
+ * have a long leg (the left inner leg being
+ * the same length as the right leg)
+ */
+ if ((*treep)->balance == 0) {
+ (*treep)->balance = -1;
+ (*treep)->left->balance = 1;
+ return FcFalse;
+ } else {
+ (*treep)->balance = 0;
+ (*treep)->left->balance = 0;
+ return FcTrue;
+ }
+ }
+}
+
+static FcBool
+FcAvlRebalanceLeft (FcAvlNode **treep)
+{
+ FcAvlNode *temp;
+ /*
+ * rebalance the tree
+ */
+ if ((*treep)->left->balance == 1) {
+ /*
+ * double whammy -- the inner sub-sub tree
+ * is longer than the outer sub-sub tree
+ *
+ * this is the "double rotation" from
+ * knuth. Scheme: replace the tree top node
+ * with the inner sub-tree top node and
+ * adjust the maze of pointers and balance
+ * factors accordingly.
+ */
+ temp = (*treep)->left->right;
+ (*treep)->left->right = temp->left;
+ temp->left = (*treep)->left;
+ switch (temp->balance) {
+ case 1:
+ temp->left->balance = -1;
+ (*treep)->balance = 0;
+ break;
+ case 0:
+ temp->left->balance = 0;
+ (*treep)->balance = 0;
+ break;
+ case -1:
+ temp->left->balance = 0;
+ (*treep)->balance = 1;
+ break;
+ }
+ temp->balance = 0;
+ (*treep)->left = temp->right;
+ temp->right = (*treep);
+ (*treep) = temp;
+ return FcTrue;
+ } else {
+ /*
+ * a simple single rotation
+ *
+ * Scheme: replace the tree top node
+ * with the sub-tree top node
+ */
+ temp = (*treep)->left->right;
+ (*treep)->left->right = (*treep);
+ (*treep) = (*treep)->left;
+ (*treep)->right->left = temp;
+ /*
+ * only two possible configurations --
+ * if the left sub-tree was balanced, then
+ * *both* sides of it were longer than the
+ * right side, so the resultant tree will
+ * have a long leg (the right inner leg being
+ * the same length as the left leg)
+ */
+ if ((*treep)->balance == 0) {
+ (*treep)->balance = 1;
+ (*treep)->right->balance = -1;
+ return FcTrue;
+ } else {
+ (*treep)->balance = 0;
+ (*treep)->right->balance = 0;
+ return FcFalse;
+ }
+ }
+}
return FcTrue;
}
+FcPattern *
+FcFontRenderPrepare (FcConfig *config,
+ FcPattern *pat,
+ FcPattern *font)
+{
+ FcPattern *new;
+ int i;
+ FcPatternElt *fe, *pe;
+ FcValue v;
+ double score[NUM_MATCHER];
+ FcResult result;
+
+ new = FcPatternCreate ();
+ if (!new)
+ return 0;
+ for (i = 0; i < font->num; i++)
+ {
+ fe = &font->elts[i];
+ pe = FcPatternFind (pat, fe->object, FcFalse);
+ if (pe)
+ {
+ if (!FcCompareValueList (pe->object, pe->values,
+ fe->values, &v, score, &result))
+ {
+ FcPatternDestroy (new);
+ return 0;
+ }
+ }
+ else
+ v = fe->values->value;
+ FcPatternAdd (new, fe->object, v, FcTrue);
+ }
+ for (i = 0; i < pat->num; i++)
+ {
+ pe = &pat->elts[i];
+ fe = FcPatternFind (font, pe->object, FcFalse);
+ if (!fe)
+ FcPatternAdd (new, pe->object, pe->values->value, FcTrue);
+ }
+ FcConfigSubstitute (config, new, FcMatchFont);
+ return new;
+}
+
FcPattern *
FcFontSetMatch (FcConfig *config,
FcFontSet **sets,
int f;
FcFontSet *s;
FcPattern *best;
- FcPattern *new;
- FcPatternElt *fe, *pe;
- FcValue v;
int i;
- FcSetName set;
+ int set;
for (i = 0; i < NUM_MATCHER; i++)
bestscore[i] = 0;
*result = FcResultNoMatch;
return 0;
}
- new = FcPatternCreate ();
- if (!new)
- return 0;
- for (i = 0; i < best->num; i++)
- {
- fe = &best->elts[i];
- pe = FcPatternFind (p, fe->object, FcFalse);
- if (pe)
- {
- if (!FcCompareValueList (pe->object, pe->values,
- fe->values, &v, score, result))
- {
- FcPatternDestroy (new);
- return 0;
- }
- }
- else
- v = fe->values->value;
- FcPatternAdd (new, fe->object, v, FcTrue);
- }
- for (i = 0; i < p->num; i++)
- {
- pe = &p->elts[i];
- fe = FcPatternFind (best, pe->object, FcFalse);
- if (!fe)
- FcPatternAdd (new, pe->object, pe->values->value, FcTrue);
- }
- FcConfigSubstitute (config, new, FcMatchFont);
- return new;
+ return FcFontRenderPrepare (config, p, best);
}
FcPattern *
sets[nsets++] = config->fonts[FcSetApplication];
return FcFontSetMatch (config, sets, nsets, p, result);
}
+
+#include "fcavl.h"
+
+typedef struct _FcSortNode {
+ FcAvlNode avl;
+ FcPattern *pattern;
+ double score[NUM_MATCHER];
+} FcSortNode;
+
+static FcBool
+FcSortMore (FcAvlNode *aa, FcAvlNode *ab)
+{
+ FcSortNode *a = (FcSortNode *) aa;
+ FcSortNode *b = (FcSortNode *) ab;
+ int i;
+
+ for (i = 0; i < NUM_MATCHER; i++)
+ {
+ if (a->score[i] > b->score[i])
+ return FcTrue;
+ if (a->score[i] < b->score[i])
+ return FcFalse;
+ }
+ if (aa > ab)
+ return FcTrue;
+ return FcFalse;
+}
+
+static FcBool
+FcSortWalk (FcSortNode *n, FcFontSet *fs, FcCharSet **cs, FcBool trim)
+{
+ FcCharSet *ncs;
+
+ if (!n)
+ return FcTrue;
+ if (!FcSortWalk ((FcSortNode *) n->avl.left, fs, cs, trim))
+ return FcFalse;
+ if (FcPatternGetCharSet (n->pattern, FC_CHARSET, 0, &ncs) == FcResultMatch)
+ {
+ if (!trim || !*cs || FcCharSetSubtractCount (ncs, *cs) != 0)
+ {
+ if (*cs)
+ {
+ ncs = FcCharSetUnion (ncs, *cs);
+ if (!ncs)
+ return FcFalse;
+ FcCharSetDestroy (*cs);
+ }
+ else
+ ncs = FcCharSetCopy (ncs);
+ *cs = ncs;
+ if (!FcFontSetAdd (fs, n->pattern))
+ return FcFalse;
+ }
+ }
+ if (!FcSortWalk ((FcSortNode *) n->avl.right, fs, cs, trim))
+ return FcFalse;
+ return FcTrue;
+}
+
+FcFontSet *
+FcFontSetSort (FcConfig *config,
+ FcFontSet **sets,
+ int nsets,
+ FcPattern *p,
+ FcBool trim,
+ FcCharSet **csp,
+ FcResult *result)
+{
+ FcFontSet *ret;
+ FcFontSet *s;
+ FcSortNode *nodes;
+ int nnodes;
+ FcSortNode *root;
+ FcSortNode *new;
+ FcCharSet *cs;
+ int set;
+ int f;
+ int i;
+
+ nnodes = 0;
+ for (set = 0; set < nsets; set++)
+ {
+ s = sets[set];
+ if (!s)
+ continue;
+ nnodes += s->nfont;
+ }
+ if (!nnodes)
+ goto bail0;
+ nodes = malloc (nnodes * sizeof (FcSortNode));
+ if (!nodes)
+ goto bail0;
+
+ root = 0;
+ new = nodes;
+ for (set = 0; set < nsets; set++)
+ {
+ s = sets[set];
+ if (!s)
+ continue;
+ for (f = 0; f < s->nfont; f++)
+ {
+ if (FcDebug () & FC_DBG_MATCHV)
+ {
+ printf ("Font %d ", f);
+ FcPatternPrint (s->fonts[f]);
+ }
+ new->pattern = s->fonts[f];
+ if (!FcCompare (p, new->pattern, new->score, result))
+ goto bail1;
+ if (FcDebug () & FC_DBG_MATCHV)
+ {
+ printf ("Score");
+ for (i = 0; i < NUM_MATCHER; i++)
+ {
+ printf (" %g", new->score[i]);
+ }
+ printf ("\n");
+ }
+ FcAvlInsert (FcSortMore, (FcAvlNode **) &root, &new->avl);
+ new++;
+ }
+ }
+
+ ret = FcFontSetCreate ();
+ if (!ret)
+ goto bail1;
+
+ cs = 0;
+
+ if (!FcSortWalk (root, ret, &cs, trim))
+ goto bail2;
+
+ *csp = cs;
+
+ return ret;
+
+bail2:
+ if (cs)
+ FcCharSetDestroy (cs);
+ FcFontSetDestroy (ret);
+bail1:
+ free (nodes);
+bail0:
+ return 0;
+}
git.wh0rd.org / fontconfig.git / commitdiff
