/*
- * $XFree86: xc/lib/fontconfig/src/fcpat.c,v 1.3 2002/02/19 07:50:44 keithp Exp $
+ * $XFree86: xc/lib/fontconfig/src/fcpat.c,v 1.18 2002/09/18 17:11:46 tsi Exp $
*
* Copyright © 2000 Keith Packard, member of The XFree86 Project, Inc.
*
#include <stdlib.h>
#include <string.h>
+#include <assert.h>
#include "fcint.h"
FcPattern *
p->num = 0;
p->size = 0;
p->elts = 0;
+ p->ref = 1;
return p;
}
case FcTypeCharSet:
FcCharSetDestroy ((FcCharSet *) v.u.c);
break;
+ case FcTypeLangSet:
+ FcLangSetDestroy ((FcLangSet *) v.u.l);
+ break;
default:
break;
}
if (!v.u.c)
v.type = FcTypeVoid;
break;
+ case FcTypeLangSet:
+ v.u.l = FcLangSetCopy (v.u.l);
+ if (!v.u.l)
+ v.type = FcTypeVoid;
+ break;
default:
break;
}
case FcTypeCharSet:
FcCharSetDestroy ((FcCharSet *) l->value.u.c);
break;
+ case FcTypeLangSet:
+ FcLangSetDestroy ((FcLangSet *) l->value.u.l);
+ break;
default:
break;
}
return FcMatrixEqual (va.u.m, vb.u.m);
case FcTypeCharSet:
return FcCharSetEqual (va.u.c, vb.u.c);
+ case FcTypeFTFace:
+ return va.u.f == vb.u.f;
+ case FcTypeLangSet:
+ return FcLangSetEqual (va.u.l, vb.u.l);
+ }
+ return FcFalse;
+}
+
+static FcChar32
+FcDoubleHash (double d)
+{
+ if (d < 0)
+ d = -d;
+ if (d > 0xffffffff)
+ d = 0xffffffff;
+ return (FcChar32) d;
+}
+
+static FcChar32
+FcStringHash (const FcChar8 *s)
+{
+ FcChar8 c;
+ FcChar32 h = 0;
+
+ if (s)
+ while ((c = *s++))
+ h = ((h << 1) | (h >> 31)) ^ c;
+ return h;
+}
+
+static FcChar32
+FcValueHash (FcValue v)
+{
+ switch (v.type) {
+ case FcTypeVoid:
+ return 0;
+ case FcTypeInteger:
+ return (FcChar32) v.u.i;
+ case FcTypeDouble:
+ return FcDoubleHash (v.u.d);
+ case FcTypeString:
+ return FcStringHash (v.u.s);
+ case FcTypeBool:
+ return (FcChar32) v.u.b;
+ case FcTypeMatrix:
+ return (FcDoubleHash (v.u.m->xx) ^
+ FcDoubleHash (v.u.m->xy) ^
+ FcDoubleHash (v.u.m->yx) ^
+ FcDoubleHash (v.u.m->yy));
+ case FcTypeCharSet:
+ return (FcChar32) v.u.c->num;
+ case FcTypeFTFace:
+ return FcStringHash ((const FcChar8 *) ((FT_Face) v.u.f)->family_name) ^
+ FcStringHash ((const FcChar8 *) ((FT_Face) v.u.f)->style_name);
+ case FcTypeLangSet:
+ return FcLangSetHash (v.u.l);
}
return FcFalse;
}
static FcBool
FcValueListEqual (FcValueList *la, FcValueList *lb)
{
+ if (la == lb)
+ return FcTrue;
+
while (la && lb)
{
if (!FcValueEqual (la->value, lb->value))
return FcTrue;
}
+static FcChar32
+FcValueListHash (FcValueList *l)
+{
+ FcChar32 hash = 0;
+
+ while (l)
+ {
+ hash = ((hash << 1) | (hash >> 31)) ^ FcValueHash (l->value);
+ l = l->next;
+ }
+ return hash;
+}
+
void
FcPatternDestroy (FcPattern *p)
{
int i;
+ if (p->ref == FC_REF_CONSTANT || --p->ref > 0)
+ return;
+
for (i = 0; i < p->num; i++)
FcValueListDestroy (p->elts[i].values);
free (p);
}
-FcPatternElt *
-FcPatternFind (FcPattern *p, const char *object, FcBool insert)
-{
- int i;
- int s;
- FcPatternElt *e;
+#define FC_VALUE_LIST_HASH_SIZE 257
+#define FC_PATTERN_HASH_SIZE 67
+
+typedef struct _FcValueListEnt FcValueListEnt;
+
+struct _FcValueListEnt {
+ FcValueListEnt *next;
+ FcValueList *list;
+ FcChar32 hash, pad;
+};
+
+typedef union _FcValueListAlign {
+ FcValueListEnt ent;
+ FcValueList list;
+} FcValueListAlign;
+
+static int FcValueListFrozenCount[FcTypeLangSet + 1];
+static int FcValueListFrozenBytes[FcTypeLangSet + 1];
+static char *FcValueListFrozenName[] = {
+ "Void",
+ "Integer",
+ "Double",
+ "String",
+ "Bool",
+ "Matrix",
+ "CharSet",
+ "FTFace",
+ "LangSet"
+};
+
+void
+FcValueListReport (void);
- int low, high;
+void
+FcValueListReport (void)
+{
+ FcType t;
- /* match existing */
- low = 0;
- high = p->num;
+ printf ("Fc Frozen Values:\n");
+ printf ("\t%8s %9s %9s\n", "Type", "Count", "Bytes");
+ for (t = FcTypeVoid; t <= FcTypeLangSet; t++)
+ printf ("\t%8s %9d %9d\n", FcValueListFrozenName[t],
+ FcValueListFrozenCount[t], FcValueListFrozenBytes[t]);
+}
+
+static FcValueListEnt *
+FcValueListEntCreate (FcValueList *h)
+{
+ FcValueListAlign *ea;
+ FcValueListEnt *e;
+ FcValueList *l, *new;
+ int n;
+ int string_size = 0;
+ FcChar8 *strs;
+ int size;
- while (low + 1 < high)
+ n = 0;
+ for (l = h; l; l = l->next)
{
- i = (low + high) >> 1;
- s = FcStrCmpIgnoreCase ((FcChar8 *) object, (FcChar8 *) p->elts[i].object);
- if (s == 0)
- return &p->elts[i];
- if (s < 0)
- low = i;
+ if (l->value.type == FcTypeString)
+ string_size += strlen ((char *) l->value.u.s) + 1;
+ n++;
+ }
+ size = sizeof (FcValueListAlign) + n * sizeof (FcValueList) + string_size;
+ FcValueListFrozenCount[h->value.type]++;
+ FcValueListFrozenBytes[h->value.type] += size;
+ ea = malloc (size);
+ if (!ea)
+ return 0;
+ FcMemAlloc (FC_MEM_VALLIST, size);
+ e = &ea->ent;
+ e->list = (FcValueList *) (ea + 1);
+ strs = (FcChar8 *) (e->list + n);
+ new = e->list;
+ for (l = h; l; l = l->next, new++)
+ {
+ if (l->value.type == FcTypeString)
+ {
+ new->value.type = FcTypeString;
+ new->value.u.s = strs;
+ strcpy ((char *) strs, (char *) l->value.u.s);
+ strs += strlen ((char *) strs) + 1;
+ }
else
- high = i;
+ {
+ new->value = l->value;
+ new->value = FcValueSave (new->value);
+ }
+ new->binding = l->binding;
+ if (l->next)
+ new->next = new + 1;
+ else
+ new->next = 0;
}
+ return e;
+}
+
+static int FcValueListTotal;
+static int FcValueListUsed;
- i = low;
- while (i < high)
+static FcValueList *
+FcValueListFreeze (FcValueList *l)
+{
+ static FcValueListEnt *hashTable[FC_VALUE_LIST_HASH_SIZE];
+ FcChar32 hash = FcValueListHash (l);
+ FcValueListEnt **bucket = &hashTable[hash % FC_VALUE_LIST_HASH_SIZE];
+ FcValueListEnt *ent;
+
+ FcValueListTotal++;
+ for (ent = *bucket; ent; ent = ent->next)
{
- s = FcStrCmpIgnoreCase ((FcChar8 *) object, (FcChar8 *) p->elts[i].object);
- if (s == 0)
- return &p->elts[i];
- if (s > 0)
- break;
- i++;
+ if (ent->hash == hash && FcValueListEqual (ent->list, l))
+ return ent->list;
}
- if (!insert)
+ ent = FcValueListEntCreate (l);
+ if (!ent)
return 0;
- /* grow array */
- if (p->num + 1 >= p->size)
+ FcValueListUsed++;
+ ent->hash = hash;
+ ent->next = *bucket;
+ *bucket = ent;
+ return ent->list;
+}
+
+static FcChar32
+FcPatternBaseHash (FcPattern *b)
+{
+ FcChar32 hash = b->num;
+ int i;
+
+ for (i = 0; i < b->num; i++)
+ hash = ((hash << 1) | (hash >> 31)) ^ ((long) b->elts[i].values);
+ return hash;
+}
+
+typedef struct _FcPatternEnt FcPatternEnt;
+
+struct _FcPatternEnt {
+ FcPatternEnt *next;
+ FcChar32 hash;
+ FcPattern pattern;
+};
+
+static int FcPatternTotal;
+static int FcPatternUsed;
+
+static FcPattern *
+FcPatternBaseFreeze (FcPattern *b)
+{
+ static FcPatternEnt *hashTable[FC_VALUE_LIST_HASH_SIZE];
+ FcChar32 hash = FcPatternBaseHash (b);
+ FcPatternEnt **bucket = &hashTable[hash % FC_VALUE_LIST_HASH_SIZE];
+ FcPatternEnt *ent;
+ int i;
+ char *objects;
+ int size_objects;
+ int size;
+
+ FcPatternTotal++;
+ for (ent = *bucket; ent; ent = ent->next)
{
- s = p->size + 16;
- if (p->elts)
- e = (FcPatternElt *) realloc (p->elts, s * sizeof (FcPatternElt));
- else
- e = (FcPatternElt *) malloc (s * sizeof (FcPatternElt));
- if (!e)
- return FcFalse;
- p->elts = e;
- if (p->size)
- FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
- FcMemAlloc (FC_MEM_PATELT, s * sizeof (FcPatternElt));
- while (p->size < s)
+ if (ent->hash == hash && b->num == ent->pattern.num)
{
- p->elts[p->size].object = 0;
- p->elts[p->size].values = 0;
- p->size++;
+ for (i = 0; i < b->num; i++)
+ {
+ if (strcmp (b->elts[i].object, ent->pattern.elts[i].object))
+ break;
+ if (b->elts[i].values != ent->pattern.elts[i].values)
+ break;
+ }
+ if (i == b->num)
+ return &ent->pattern;
}
}
+
+ /*
+ * Compute size of pattern + elts + object names
+ */
+ size_objects = 0;
+ for (i = 0; i < b->num; i++)
+ size_objects += strlen (b->elts[i].object) + 1;
+
+ size = sizeof (FcPatternEnt) + b->num*sizeof (FcPatternElt) + size_objects;
+ ent = malloc (size);
+ if (!ent)
+ return 0;
+
+ FcMemAlloc (FC_MEM_PATTERN, size);
+ FcPatternUsed++;
+
+ ent->pattern.elts = (FcPatternElt *) (ent + 1);
+ ent->pattern.num = b->num;
+ ent->pattern.size = b->num;
+ ent->pattern.ref = FC_REF_CONSTANT;
+
+ objects = (char *) (ent->pattern.elts + b->num);
+ for (i = 0; i < b->num; i++)
+ {
+ ent->pattern.elts[i].values = b->elts[i].values;
+ strcpy (objects, b->elts[i].object);
+ ent->pattern.elts[i].object = objects;
+ objects += strlen (objects) + 1;
+ }
+
+ ent->hash = hash;
+ ent->next = *bucket;
+ *bucket = ent;
+ return &ent->pattern;
+}
+
+FcPattern *
+FcPatternFreeze (FcPattern *p)
+{
+ FcPattern *b, *n = 0;
+ int size;
+ int i;
- /* move elts up */
- memmove (p->elts + i + 1,
- p->elts + i,
- sizeof (FcPatternElt) *
- (p->num - i));
-
- /* bump count */
- p->num++;
+ size = sizeof (FcPattern) + p->num * sizeof (FcPatternElt);
+ b = (FcPattern *) malloc (size);
+ if (!b)
+ return 0;
+ FcMemAlloc (FC_MEM_PATTERN, size);
+ b->num = p->num;
+ b->size = b->num;
+ b->ref = 1;
+ b->elts = (FcPatternElt *) (b + 1);
+ /*
+ * Freeze object lists
+ */
+ for (i = 0; i < p->num; i++)
+ {
+ b->elts[i].object = p->elts[i].object;
+ b->elts[i].values = FcValueListFreeze (p->elts[i].values);
+ if (!b->elts[i].values)
+ goto bail;
+ }
+ /*
+ * Freeze base
+ */
+ n = FcPatternBaseFreeze (b);
+#ifdef CHATTY
+ if (FcDebug() & FC_DBG_MEMORY)
+ {
+ printf ("ValueLists: total %9d used %9d\n", FcValueListTotal, FcValueListUsed);
+ printf ("Patterns: total %9d used %9d\n", FcPatternTotal, FcPatternUsed);
+ }
+#endif
+bail:
+ free (b);
+#ifdef DEBUG
+ assert (FcPatternEqual (n, p));
+#endif
+ return n;
+}
+
+static int
+FcPatternPosition (const FcPattern *p, const char *object)
+{
+ int low, high, mid, c;
+
+ low = 0;
+ high = p->num - 1;
+ c = 1;
+ mid = 0;
+ while (low <= high)
+ {
+ mid = (low + high) >> 1;
+ c = strcmp (p->elts[mid].object, object);
+ if (c == 0)
+ return mid;
+ if (c < 0)
+ low = mid + 1;
+ else
+ high = mid - 1;
+ }
+ if (c < 0)
+ mid++;
+ return -(mid + 1);
+}
+
+FcPatternElt *
+FcPatternFindElt (const FcPattern *p, const char *object)
+{
+ int i = FcPatternPosition (p, object);
+ if (i < 0)
+ return 0;
+ return &p->elts[i];
+}
+
+FcPatternElt *
+FcPatternInsertElt (FcPattern *p, const char *object)
+{
+ int i;
+ FcPatternElt *e;
- p->elts[i].object = object;
- p->elts[i].values = 0;
+ i = FcPatternPosition (p, object);
+ if (i < 0)
+ {
+ i = -i - 1;
+
+ /* grow array */
+ if (p->num + 1 >= p->size)
+ {
+ int s = p->size + 16;
+ if (p->elts)
+ e = (FcPatternElt *) realloc (p->elts, s * sizeof (FcPatternElt));
+ else
+ e = (FcPatternElt *) malloc (s * sizeof (FcPatternElt));
+ if (!e)
+ return FcFalse;
+ p->elts = e;
+ if (p->size)
+ FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
+ FcMemAlloc (FC_MEM_PATELT, s * sizeof (FcPatternElt));
+ while (p->size < s)
+ {
+ p->elts[p->size].object = 0;
+ p->elts[p->size].values = 0;
+ p->size++;
+ }
+ }
+
+ /* move elts up */
+ memmove (p->elts + i + 1,
+ p->elts + i,
+ sizeof (FcPatternElt) *
+ (p->num - i));
+
+ /* bump count */
+ p->num++;
+
+ p->elts[i].object = object;
+ p->elts[i].values = 0;
+ }
return &p->elts[i];
}
FcBool
-FcPatternEqual (FcPattern *pa, FcPattern *pb)
+FcPatternEqual (const FcPattern *pa, const FcPattern *pb)
{
int i;
+ if (pa == pb)
+ return FcTrue;
+
if (pa->num != pb->num)
return FcFalse;
for (i = 0; i < pa->num; i++)
{
- if (FcStrCmpIgnoreCase ((FcChar8 *) pa->elts[i].object,
- (FcChar8 *) pb->elts[i].object) != 0)
+ if (strcmp (pa->elts[i].object, pb->elts[i].object) != 0)
return FcFalse;
if (!FcValueListEqual (pa->elts[i].values, pb->elts[i].values))
return FcFalse;
return FcTrue;
}
+FcChar32
+FcPatternHash (const FcPattern *p)
+{
+ int i;
+ FcChar32 h = 0;
+
+ for (i = 0; i < p->num; i++)
+ {
+ h = (((h << 1) | (h >> 31)) ^
+ FcStringHash ((const FcChar8 *) p->elts[i].object) ^
+ FcValueListHash (p->elts[i].values));
+ }
+ return h;
+}
+
FcBool
-FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
+FcPatternEqualSubset (const FcPattern *pa, const FcPattern *pb, const FcObjectSet *os)
+{
+ FcPatternElt *ea, *eb;
+ int i;
+
+ for (i = 0; i < os->nobject; i++)
+ {
+ ea = FcPatternFindElt (pa, os->objects[i]);
+ eb = FcPatternFindElt (pb, os->objects[i]);
+ if (ea)
+ {
+ if (!eb)
+ return FcFalse;
+ if (!FcValueListEqual (ea->values, eb->values))
+ return FcFalse;
+ }
+ else
+ {
+ if (eb)
+ return FcFalse;
+ }
+ }
+ return FcTrue;
+}
+
+FcBool
+FcPatternAddWithBinding (FcPattern *p,
+ const char *object,
+ FcValue value,
+ FcValueBinding binding,
+ FcBool append)
{
FcPatternElt *e;
FcValueList *new, **prev;
+ if (p->ref == FC_REF_CONSTANT)
+ goto bail0;
+
new = (FcValueList *) malloc (sizeof (FcValueList));
if (!new)
goto bail0;
goto bail1;
new->value = value;
+ new->binding = binding;
new->next = 0;
- e = FcPatternFind (p, object, FcTrue);
+ e = FcPatternInsertElt (p, object);
if (!e)
goto bail2;
case FcTypeCharSet:
FcCharSetDestroy ((FcCharSet *) value.u.c);
break;
+ case FcTypeLangSet:
+ FcLangSetDestroy ((FcLangSet *) value.u.l);
+ break;
default:
break;
}
return FcFalse;
}
+FcBool
+FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
+{
+ return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
+}
+
+FcBool
+FcPatternAddWeak (FcPattern *p, const char *object, FcValue value, FcBool append)
+{
+ return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
+}
+
FcBool
FcPatternDel (FcPattern *p, const char *object)
{
FcPatternElt *e;
int i;
- e = FcPatternFind (p, object, FcFalse);
+ e = FcPatternFindElt (p, object);
if (!e)
return FcFalse;
return FcPatternAdd (p, object, v, FcTrue);
}
+FcBool
+FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
+{
+ FcValue v;
+
+ v.type = FcTypeFTFace;
+ v.u.f = (void *) f;
+ return FcPatternAdd (p, object, v, FcTrue);
+}
+
+FcBool
+FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
+{
+ FcValue v;
+
+ v.type = FcTypeLangSet;
+ v.u.l = (FcLangSet *) ls;
+ return FcPatternAdd (p, object, v, FcTrue);
+}
+
FcResult
-FcPatternGet (FcPattern *p, const char *object, int id, FcValue *v)
+FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
{
FcPatternElt *e;
FcValueList *l;
- e = FcPatternFind (p, object, FcFalse);
+ e = FcPatternFindElt (p, object);
if (!e)
return FcResultNoMatch;
for (l = e->values; l; l = l->next)
}
FcResult
-FcPatternGetInteger (FcPattern *p, const char *object, int id, int *i)
+FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
{
FcValue v;
FcResult r;
}
FcResult
-FcPatternGetDouble (FcPattern *p, const char *object, int id, double *d)
+FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
{
FcValue v;
FcResult r;
}
FcResult
-FcPatternGetString (FcPattern *p, const char *object, int id, FcChar8 ** s)
+FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
{
FcValue v;
FcResult r;
}
FcResult
-FcPatternGetMatrix (FcPattern *p, const char *object, int id, FcMatrix **m)
+FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
{
FcValue v;
FcResult r;
FcResult
-FcPatternGetBool (FcPattern *p, const char *object, int id, FcBool *b)
+FcPatternGetBool(const FcPattern *p, const char *object, int id, FcBool *b)
{
FcValue v;
FcResult r;
}
FcResult
-FcPatternGetCharSet (FcPattern *p, const char *object, int id, FcCharSet **c)
+FcPatternGetCharSet(const FcPattern *p, const char *object, int id, FcCharSet **c)
{
FcValue v;
FcResult r;
return FcResultMatch;
}
+FcResult
+FcPatternGetFTFace(const FcPattern *p, const char *object, int id, FT_Face *f)
+{
+ FcValue v;
+ FcResult r;
+
+ r = FcPatternGet (p, object, id, &v);
+ if (r != FcResultMatch)
+ return r;
+ if (v.type != FcTypeFTFace)
+ return FcResultTypeMismatch;
+ *f = (FT_Face) v.u.f;
+ return FcResultMatch;
+}
+
+FcResult
+FcPatternGetLangSet(const FcPattern *p, const char *object, int id, FcLangSet **ls)
+{
+ FcValue v;
+ FcResult r;
+
+ r = FcPatternGet (p, object, id, &v);
+ if (r != FcResultMatch)
+ return r;
+ if (v.type != FcTypeLangSet)
+ return FcResultTypeMismatch;
+ *ls = (FcLangSet *) v.u.l;
+ return FcResultMatch;
+}
+
FcPattern *
-FcPatternDuplicate (FcPattern *orig)
+FcPatternDuplicate (const FcPattern *orig)
{
FcPattern *new;
int i;
return 0;
}
+void
+FcPatternReference (FcPattern *p)
+{
+ if (p->ref != FC_REF_CONSTANT)
+ p->ref++;
+}
+
FcPattern *
FcPatternVaBuild (FcPattern *orig, va_list va)
{