[fontconfig.git] / src / fclist.c

/*
 * fontconfig/src/fclist.c
 *
 * Copyright © 2000 Keith Packard
 *
 * 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 the author(s) not be used in
 * advertising or publicity pertaining to distribution of the software without
 * specific, written prior permission.  The authors make no
 * representations about the suitability of this software for any purpose.  It
 * is provided "as is" without express or implied warranty.
 *
 * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
 * EVENT SHALL THE AUTHOR(S) 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.
 */

#include "fcint.h"
#include <stdlib.h>

FcObjectSet *
FcObjectSetCreate (void)
{
    FcObjectSet    *os;

    os = (FcObjectSet *) malloc (sizeof (FcObjectSet));
    if (!os)
	return 0;
    FcMemAlloc (FC_MEM_OBJECTSET, sizeof (FcObjectSet));
    os->nobject = 0;
    os->sobject = 0;
    os->objects = 0;
    return os;
}

FcBool
FcObjectSetAdd (FcObjectSet *os, const char *object)
{
    int		s;
    const char	**objects;
    int		high, low, mid, c;

    if (os->nobject == os->sobject)
    {
	s = os->sobject + 4;
	if (os->objects)
	    objects = (const char **) realloc ((void *) os->objects,
					       s * sizeof (const char *));
	else
	    objects = (const char **) malloc (s * sizeof (const char *));
	if (!objects)
	    return FcFalse;
	if (os->sobject)
	    FcMemFree (FC_MEM_OBJECTPTR, os->sobject * sizeof (const char *));
	FcMemAlloc (FC_MEM_OBJECTPTR, s * sizeof (const char *));
	os->objects = objects;
	os->sobject = s;
    }
    high = os->nobject - 1;
    low = 0;
    mid = 0;
    c = 1;
    object = (char *)FcStrStaticName ((FcChar8 *)object);
    while (low <= high)
    {
	mid = (low + high) >> 1;
	c = os->objects[mid] - object;
	if (c == 0)
	    return FcTrue;
	if (c < 0)
	    low = mid + 1;
	else
	    high = mid - 1;
    }
    if (c < 0)
	mid++;
    memmove (os->objects + mid + 1, os->objects + mid,
	     (os->nobject - mid) * sizeof (const char *));
    os->objects[mid] = object;
    os->nobject++;
    return FcTrue;
}

void
FcObjectSetDestroy (FcObjectSet *os)
{
    if (os->objects)
    {
	FcMemFree (FC_MEM_OBJECTPTR, os->sobject * sizeof (const char *));
	free ((void *) os->objects);
    }
    FcMemFree (FC_MEM_OBJECTSET, sizeof (FcObjectSet));
    free (os);
}

FcObjectSet *
FcObjectSetVaBuild (const char *first, va_list va)
{
    FcObjectSet    *ret;

    FcObjectSetVapBuild (ret, first, va);
    return ret;
}

FcObjectSet *
FcObjectSetBuild (const char *first, ...)
{
    va_list	    va;
    FcObjectSet    *os;

    va_start (va, first);
    FcObjectSetVapBuild (os, first, va);
    va_end (va);
    return os;
}

/*
 * Font must have a containing value for every value in the pattern
 */
static FcBool
FcListValueListMatchAny (FcValueListPtr patOrig,	    /* pattern */
			 FcValueListPtr fntOrig)	    /* font */
{
    FcValueListPtr	 pat, fnt;

    for (pat = patOrig; pat != NULL; pat = FcValueListNext(pat))
    {
	for (fnt = fntOrig; fnt != NULL; fnt = FcValueListNext(fnt))
	{
	    /*
	     * make sure the font 'contains' the pattern.
	     * (OpListing is OpContains except for strings
	     *  where it requires an exact match)
	     */
	    if (FcConfigCompareValue (&fnt->value,
				      FcOpListing,
				      &pat->value))
		break;
	}
	if (fnt == NULL)
	    return FcFalse;
    }
    return FcTrue;
}

static FcBool
FcListValueListEqual (FcValueListPtr v1orig,
		      FcValueListPtr v2orig)
{
    FcValueListPtr	    v1, v2;

    for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext(v1))
    {
	for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext(v2))
	    if (FcValueEqual (FcValueCanonicalize(&(v1)->value),
			      FcValueCanonicalize(&(v2)->value)))
		break;
	if (v2 == NULL)
	    return FcFalse;
    }
    for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext(v2))
    {
	for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext(v1))
	    if (FcValueEqual (FcValueCanonicalize(&v1->value),
			      FcValueCanonicalize(&v2->value)))
		break;
	if (v1 == NULL)
	    return FcFalse;
    }
    return FcTrue;
}

static FcBool
FcListPatternEqual (FcPattern	*p1,
		    FcPattern	*p2,
		    FcObjectSet	*os)
{
    int		    i;
    FcPatternElt    *e1, *e2;

    for (i = 0; i < os->nobject; i++)
    {
	e1 = FcPatternObjectFindElt (p1, FcObjectFromName (os->objects[i]));
	e2 = FcPatternObjectFindElt (p2, FcObjectFromName (os->objects[i]));
	if (!e1 && !e2)
	    continue;
	if (!e1 || !e2)
	    return FcFalse;
	if (!FcListValueListEqual (FcPatternEltValues(e1),
				   FcPatternEltValues(e2)))
	    return FcFalse;
    }
    return FcTrue;
}

/*
 * FcTrue iff all objects in "p" match "font"
 */

FcBool
FcListPatternMatchAny (const FcPattern *p,
		       const FcPattern *font)
{
    int		    i;

    for (i = 0; i < p->num; i++)
    {
	FcPatternElt	*pe = &FcPatternElts(p)[i];
	FcPatternElt	*fe = FcPatternObjectFindElt (font, pe->object);
	if (!fe)
	    return FcFalse;
	if (!FcListValueListMatchAny (FcPatternEltValues(pe),    /* pat elts */
				      FcPatternEltValues(fe)))   /* font elts */
	    return FcFalse;
    }
    return FcTrue;
}

static FcChar32
FcListMatrixHash (const FcMatrix *m)
{
    int	    xx = (int) (m->xx * 100),
	    xy = (int) (m->xy * 100),
	    yx = (int) (m->yx * 100),
	    yy = (int) (m->yy * 100);

    return ((FcChar32) xx) ^ ((FcChar32) xy) ^ ((FcChar32) yx) ^ ((FcChar32) yy);
}

static FcChar32
FcListValueHash (FcValue    *value)
{
    FcValue v = FcValueCanonicalize(value);
    switch (v.type) {
    case FcTypeVoid:
	return 0;
    case FcTypeInteger:
	return (FcChar32) v.u.i;
    case FcTypeDouble:
	return (FcChar32) (int) v.u.d;
    case FcTypeString:
	return FcStrHashIgnoreCase (v.u.s);
    case FcTypeBool:
	return (FcChar32) v.u.b;
    case FcTypeMatrix:
	return FcListMatrixHash (v.u.m);
    case FcTypeCharSet:
	return FcCharSetCount (v.u.c);
    case FcTypeFTFace:
	return (long) v.u.f;
    case FcTypeLangSet:
	return FcLangSetHash (v.u.l);
    }
    return 0;
}

static FcChar32
FcListValueListHash (FcValueListPtr list)
{
    FcChar32	h = 0;

    while (list != NULL)
    {
	h = h ^ FcListValueHash (&list->value);
	list = FcValueListNext(list);
    }
    return h;
}

static FcChar32
FcListPatternHash (FcPattern	*font,
		   FcObjectSet	*os)
{
    int		    n;
    FcPatternElt    *e;
    FcChar32	    h = 0;

    for (n = 0; n < os->nobject; n++)
    {
	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[n]));
	if (e)
	    h = h ^ FcListValueListHash (FcPatternEltValues(e));
    }
    return h;
}

typedef struct _FcListBucket {
    struct _FcListBucket    *next;
    FcChar32		    hash;
    FcPattern		    *pattern;
} FcListBucket;

#define FC_LIST_HASH_SIZE   4099

typedef struct _FcListHashTable {
    int		    entries;
    FcListBucket    *buckets[FC_LIST_HASH_SIZE];
} FcListHashTable;

static void
FcListHashTableInit (FcListHashTable *table)
{
    table->entries = 0;
    memset (table->buckets, '\0', sizeof (table->buckets));
}

static void
FcListHashTableCleanup (FcListHashTable *table)
{
    int	i;
    FcListBucket    *bucket, *next;

    for (i = 0; i < FC_LIST_HASH_SIZE; i++)
    {
	for (bucket = table->buckets[i]; bucket; bucket = next)
	{
	    next = bucket->next;
	    FcPatternDestroy (bucket->pattern);
	    FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
	    free (bucket);
	}
	table->buckets[i] = 0;
    }
    table->entries = 0;
}

static int
FcGetDefaultObjectLangIndex (FcPattern *font, FcObject object)
{
    FcChar8	   *lang = FcGetDefaultLang ();
    FcPatternElt   *e = FcPatternObjectFindElt (font, object);
    FcValueListPtr  v;
    FcValue         value;
    int             idx = -1;
    int             i;

    if (e)
    {
	for (v = FcPatternEltValues(e), i = 0; v; v = FcValueListNext(v), ++i)
	{
	    value = FcValueCanonicalize (&v->value);

	    if (value.type == FcTypeString)
	    {
		FcLangResult res = FcLangCompare (value.u.s, lang);
		if (res == FcLangEqual)
		    return i;

		if (res == FcLangDifferentCountry && idx < 0)
		    idx = i;
	    }
	}
    }

    return (idx > 0) ? idx : 0;
}

static FcBool
FcListAppend (FcListHashTable	*table,
	      FcPattern		*font,
	      FcObjectSet	*os)
{
    int		    o;
    FcPatternElt    *e;
    FcValueListPtr  v;
    FcChar32	    hash;
    FcListBucket    **prev, *bucket;
    int             familyidx = -1;
    int             fullnameidx = -1;
    int             styleidx = -1;
    int             defidx = 0;
    int             idx;

    hash = FcListPatternHash (font, os);
    for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
	 (bucket = *prev); prev = &(bucket->next))
    {
	if (bucket->hash == hash &&
	    FcListPatternEqual (bucket->pattern, font, os))
	    return FcTrue;
    }
    bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
    if (!bucket)
	goto bail0;
    FcMemAlloc (FC_MEM_LISTBUCK, sizeof (FcListBucket));
    bucket->next = 0;
    bucket->hash = hash;
    bucket->pattern = FcPatternCreate ();
    if (!bucket->pattern)
	goto bail1;

    for (o = 0; o < os->nobject; o++)
    {
	if (!strcmp (os->objects[o], FC_FAMILY) || !strcmp (os->objects[o], FC_FAMILYLANG))
	{
	    if (familyidx < 0)
		familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG_OBJECT);
	    defidx = familyidx;
	}
	else if (!strcmp (os->objects[o], FC_FULLNAME) || !strcmp (os->objects[o], FC_FULLNAMELANG))
	{
	    if (fullnameidx < 0)
		fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG_OBJECT);
	    defidx = fullnameidx;
	}
	else if (!strcmp (os->objects[o], FC_STYLE) || !strcmp (os->objects[o], FC_STYLELANG))
	{
	    if (styleidx < 0)
		styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG_OBJECT);
	    defidx = styleidx;
	}
	else
	    defidx = 0;

	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[o]));
	if (e)
	{
	    for (v = FcPatternEltValues(e), idx = 0; v;
		 v = FcValueListNext(v), ++idx)
	    {
		if (!FcPatternAdd (bucket->pattern,
				   os->objects[o],
				   FcValueCanonicalize(&v->value), defidx != idx))
		    goto bail2;
	    }
	}
    }
    *prev = bucket;
    ++table->entries;

    return FcTrue;

bail2:
    FcPatternDestroy (bucket->pattern);
bail1:
    FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
    free (bucket);
bail0:
    return FcFalse;
}

FcFontSet *
FcFontSetList (FcConfig	    *config,
	       FcFontSet    **sets,
	       int	    nsets,
	       FcPattern    *p,
	       FcObjectSet  *os)
{
    FcFontSet	    *ret;
    FcFontSet	    *s;
    int		    f;
    int		    set;
    FcListHashTable table;
    int		    i;
    FcListBucket    *bucket;
    int             destroy_os = 0;

    if (!config)
    {
	if (!FcInitBringUptoDate ())
	    goto bail0;

	config = FcConfigGetCurrent ();
	if (!config)
	    goto bail0;
    }
    FcListHashTableInit (&table);

    if (!os)
    {
	os = FcObjectGetSet ();
	destroy_os = 1;
    }

    /*
     * Walk all available fonts adding those that
     * match to the hash table
     */
    for (set = 0; set < nsets; set++)
    {
	s = sets[set];
	if (!s)
	    continue;
	for (f = 0; f < s->nfont; f++)
	    if (FcListPatternMatchAny (p,		/* pattern */
				       s->fonts[f]))	/* font */
		if (!FcListAppend (&table, s->fonts[f], os))
		    goto bail1;
    }
#if 0
    {
	int	max = 0;
	int	full = 0;
	int	ents = 0;
	int	len;
	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
	{
	    if ((bucket = table.buckets[i]))
	    {
		len = 0;
		for (; bucket; bucket = bucket->next)
		{
		    ents++;
		    len++;
		}
		if (len > max)
		    max = len;
		full++;
	    }
	}
	printf ("used: %d max: %d avg: %g\n", full, max,
		(double) ents / FC_LIST_HASH_SIZE);
    }
#endif
    /*
     * Walk the hash table and build
     * a font set
     */
    ret = FcFontSetCreate ();
    if (!ret)
	goto bail0;
    for (i = 0; i < FC_LIST_HASH_SIZE; i++)
	while ((bucket = table.buckets[i]))
	{
	    if (!FcFontSetAdd (ret, bucket->pattern))
		goto bail2;
	    table.buckets[i] = bucket->next;
	    FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
	    free (bucket);
	}

    return ret;

bail2:
    FcFontSetDestroy (ret);
bail1:
    FcListHashTableCleanup (&table);
bail0:
    if (destroy_os)
	FcObjectSetDestroy (os);
    return 0;
}

FcFontSet *
FcFontList (FcConfig	*config,
	    FcPattern	*p,
	    FcObjectSet *os)
{
    FcFontSet	*sets[2];
    int		nsets;

    if (!config)
    {
	if (!FcInitBringUptoDate ())
	    return 0;

	config = FcConfigGetCurrent ();
	if (!config)
	    return 0;
    }
    nsets = 0;
    if (config->fonts[FcSetSystem])
	sets[nsets++] = config->fonts[FcSetSystem];
    if (config->fonts[FcSetApplication])
	sets[nsets++] = config->fonts[FcSetApplication];
    return FcFontSetList (config, sets, nsets, p, os);
}
#define __fclist__
#include "fcaliastail.h"
#undef __fclist__
Commit	Line	Data
24330d27	1	/*
317b8492	2	* fontconfig/src/fclist.c
24330d27	3	*
46b51147	4	* Copyright © 2000 Keith Packard
24330d27 KP	5	*
	6	* Permission to use, copy, modify, distribute, and sell this software and its
	7	* documentation for any purpose is hereby granted without fee, provided that
	8	* the above copyright notice appear in all copies and that both that
	9	* copyright notice and this permission notice appear in supporting
5aaf466d	10	* documentation, and that the name of the author(s) not be used in
24330d27	11	* advertising or publicity pertaining to distribution of the software without
5aaf466d	12	* specific, written prior permission. The authors make no
24330d27 KP	13	* representations about the suitability of this software for any purpose. It
	14	* is provided "as is" without express or implied warranty.
	15	*
3074a73b	16	* THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
24330d27	17	* INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
3074a73b	18	* EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY SPECIAL, INDIRECT OR
24330d27 KP	19	* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
	20	* DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
	21	* TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
	22	* PERFORMANCE OF THIS SOFTWARE.
	23	*/
	24
24330d27	25	#include "fcint.h"
f045376c	26	#include <stdlib.h>
24330d27 KP	27
	28	FcObjectSet *
	29	FcObjectSetCreate (void)
	30	{
	31	FcObjectSet *os;
	32
	33	os = (FcObjectSet *) malloc (sizeof (FcObjectSet));
	34	if (!os)
	35	return 0;
	36	FcMemAlloc (FC_MEM_OBJECTSET, sizeof (FcObjectSet));
	37	os->nobject = 0;
	38	os->sobject = 0;
	39	os->objects = 0;
	40	return os;
	41	}
	42
	43	FcBool
	44	FcObjectSetAdd (FcObjectSet os, const char object)
	45	{
	46	int s;
4262e0b3	47	const char **objects;
e9be9cd1	48	int high, low, mid, c;
594dcef0	49
24330d27 KP	50	if (os->nobject == os->sobject)
	51	{
	52	s = os->sobject + 4;
	53	if (os->objects)
4262e0b3 PL	54	objects = (const char *) realloc ((void ) os->objects,
4262e0b3 PL	55	s * sizeof (const char *));
24330d27	56	else
4262e0b3	57	objects = (const char *) malloc (s sizeof (const char *));
24330d27 KP	58	if (!objects)
	59	return FcFalse;
	60	if (os->sobject)
	61	FcMemFree (FC_MEM_OBJECTPTR, os->sobject * sizeof (const char *));
	62	FcMemAlloc (FC_MEM_OBJECTPTR, s * sizeof (const char *));
	63	os->objects = objects;
	64	os->sobject = s;
	65	}
e9be9cd1 KP	66	high = os->nobject - 1;
	67	low = 0;
	68	mid = 0;
	69	c = 1;
8245771d	70	object = (char )FcStrStaticName ((FcChar8 )object);
e9be9cd1 KP	71	while (low <= high)
	72	{
	73	mid = (low + high) >> 1;
4262e0b3	74	c = os->objects[mid] - object;
e9be9cd1 KP	75	if (c == 0)
	76	return FcTrue;
	77	if (c < 0)
	78	low = mid + 1;
	79	else
	80	high = mid - 1;
	81	}
	82	if (c < 0)
	83	mid++;
594dcef0	84	memmove (os->objects + mid + 1, os->objects + mid,
4262e0b3 PL	85	(os->nobject - mid) * sizeof (const char *));
4262e0b3 PL	86	os->objects[mid] = object;
e9be9cd1	87	os->nobject++;
24330d27 KP	88	return FcTrue;
	89	}
	90
	91	void
	92	FcObjectSetDestroy (FcObjectSet *os)
	93	{
	94	if (os->objects)
	95	{
	96	FcMemFree (FC_MEM_OBJECTPTR, os->sobject * sizeof (const char *));
	97	free ((void *) os->objects);
	98	}
	99	FcMemFree (FC_MEM_OBJECTSET, sizeof (FcObjectSet));
	100	free (os);
	101	}
	102
	103	FcObjectSet *
	104	FcObjectSetVaBuild (const char *first, va_list va)
	105	{
	106	FcObjectSet *ret;
	107
	108	FcObjectSetVapBuild (ret, first, va);
	109	return ret;
	110	}
	111
	112	FcObjectSet *
	113	FcObjectSetBuild (const char *first, ...)
	114	{
	115	va_list va;
	116	FcObjectSet *os;
	117
	118	va_start (va, first);
	119	FcObjectSetVapBuild (os, first, va);
	120	va_end (va);
	121	return os;
	122	}
	123
74a623e0 KP	124	/*
	125	* Font must have a containing value for every value in the pattern
	126	*/
24330d27	127	static FcBool
cd2ec1a9 PL	128	FcListValueListMatchAny (FcValueListPtr patOrig, /* pattern */
cd2ec1a9 PL	129	FcValueListPtr fntOrig) /* font */
24330d27	130	{
cd2ec1a9	131	FcValueListPtr pat, fnt;
24330d27	132
7ce19673	133	for (pat = patOrig; pat != NULL; pat = FcValueListNext(pat))
74a623e0	134	{
7ce19673	135	for (fnt = fntOrig; fnt != NULL; fnt = FcValueListNext(fnt))
74a623e0 KP	136	{
	137	/*
	138	* make sure the font 'contains' the pattern.
	139	* (OpListing is OpContains except for strings
	140	* where it requires an exact match)
	141	*/
7ce19673	142	if (FcConfigCompareValue (&fnt->value,
594dcef0 BE	143	FcOpListing,
594dcef0 BE	144	&pat->value))
74a623e0 KP	145	break;
74a623e0 KP	146	}
7ce19673	147	if (fnt == NULL)
74a623e0 KP	148	return FcFalse;
	149	}
	150	return FcTrue;
24330d27 KP	151	}
	152
	153	static FcBool
cd2ec1a9 PL	154	FcListValueListEqual (FcValueListPtr v1orig,
cd2ec1a9 PL	155	FcValueListPtr v2orig)
24330d27	156	{
cd2ec1a9	157	FcValueListPtr v1, v2;
24330d27	158
7ce19673	159	for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext(v1))
24330d27	160	{
7ce19673 KP	161	for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext(v2))
	162	if (FcValueEqual (FcValueCanonicalize(&(v1)->value),
	163	FcValueCanonicalize(&(v2)->value)))
24330d27	164	break;
7ce19673	165	if (v2 == NULL)
24330d27 KP	166	return FcFalse;
24330d27 KP	167	}
7ce19673	168	for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext(v2))
24330d27	169	{
7ce19673 KP	170	for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext(v1))
	171	if (FcValueEqual (FcValueCanonicalize(&v1->value),
	172	FcValueCanonicalize(&v2->value)))
24330d27	173	break;
7ce19673	174	if (v1 == NULL)
24330d27 KP	175	return FcFalse;
	176	}
	177	return FcTrue;
	178	}
	179
24330d27	180	static FcBool
e9be9cd1 KP	181	FcListPatternEqual (FcPattern *p1,
	182	FcPattern *p2,
	183	FcObjectSet *os)
24330d27 KP	184	{
24330d27 KP	185	int i;
e9be9cd1	186	FcPatternElt e1, e2;
24330d27	187
e9be9cd1	188	for (i = 0; i < os->nobject; i++)
24330d27	189	{
7ce19673 KP	190	e1 = FcPatternObjectFindElt (p1, FcObjectFromName (os->objects[i]));
7ce19673 KP	191	e2 = FcPatternObjectFindElt (p2, FcObjectFromName (os->objects[i]));
e9be9cd1	192	if (!e1 && !e2)
47d4f950	193	continue;
e9be9cd1	194	if (!e1 \|\| !e2)
24330d27	195	return FcFalse;
7ce19673 KP	196	if (!FcListValueListEqual (FcPatternEltValues(e1),
7ce19673 KP	197	FcPatternEltValues(e2)))
24330d27 KP	198	return FcFalse;
	199	}
	200	return FcTrue;
	201	}
	202
e9be9cd1 KP	203	/*
	204	* FcTrue iff all objects in "p" match "font"
	205	*/
	206
4f27c1c0 KP	207	FcBool
	208	FcListPatternMatchAny (const FcPattern *p,
	209	const FcPattern *font)
24330d27 KP	210	{
24330d27 KP	211	int i;
24330d27	212
e9be9cd1	213	for (i = 0; i < p->num; i++)
24330d27	214	{
7ce19673 KP	215	FcPatternElt *pe = &FcPatternElts(p)[i];
	216	FcPatternElt *fe = FcPatternObjectFindElt (font, pe->object);
	217	if (!fe)
24330d27	218	return FcFalse;
7ce19673 KP	219	if (!FcListValueListMatchAny (FcPatternEltValues(pe), /* pat elts */
7ce19673 KP	220	FcPatternEltValues(fe))) /* font elts */
24330d27 KP	221	return FcFalse;
	222	}
	223	return FcTrue;
	224	}
	225
24330d27 KP	226	static FcChar32
	227	FcListMatrixHash (const FcMatrix *m)
	228	{
594dcef0 BE	229	int xx = (int) (m->xx * 100),
594dcef0 BE	230	xy = (int) (m->xy * 100),
24330d27 KP	231	yx = (int) (m->yx * 100),
	232	yy = (int) (m->yy * 100);
	233
	234	return ((FcChar32) xx) ^ ((FcChar32) xy) ^ ((FcChar32) yx) ^ ((FcChar32) yy);
	235	}
	236
	237	static FcChar32
4262e0b3	238	FcListValueHash (FcValue *value)
24330d27	239	{
4262e0b3	240	FcValue v = FcValueCanonicalize(value);
24330d27 KP	241	switch (v.type) {
	242	case FcTypeVoid:
	243	return 0;
	244	case FcTypeInteger:
	245	return (FcChar32) v.u.i;
	246	case FcTypeDouble:
	247	return (FcChar32) (int) v.u.d;
	248	case FcTypeString:
4262e0b3	249	return FcStrHashIgnoreCase (v.u.s);
24330d27 KP	250	case FcTypeBool:
	251	return (FcChar32) v.u.b;
	252	case FcTypeMatrix:
4262e0b3	253	return FcListMatrixHash (v.u.m);
24330d27	254	case FcTypeCharSet:
4262e0b3	255	return FcCharSetCount (v.u.c);
88c747e2	256	case FcTypeFTFace:
d1bec8c6	257	return (long) v.u.f;
d8d73958	258	case FcTypeLangSet:
4262e0b3	259	return FcLangSetHash (v.u.l);
24330d27 KP	260	}
	261	return 0;
	262	}
	263
	264	static FcChar32
cd2ec1a9	265	FcListValueListHash (FcValueListPtr list)
24330d27 KP	266	{
24330d27 KP	267	FcChar32 h = 0;
594dcef0	268
7ce19673	269	while (list != NULL)
24330d27	270	{
7ce19673 KP	271	h = h ^ FcListValueHash (&list->value);
7ce19673 KP	272	list = FcValueListNext(list);
24330d27 KP	273	}
	274	return h;
	275	}
	276
	277	static FcChar32
	278	FcListPatternHash (FcPattern *font,
	279	FcObjectSet *os)
	280	{
	281	int n;
	282	FcPatternElt *e;
	283	FcChar32 h = 0;
	284
	285	for (n = 0; n < os->nobject; n++)
	286	{
7ce19673	287	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[n]));
24330d27	288	if (e)
7ce19673	289	h = h ^ FcListValueListHash (FcPatternEltValues(e));
24330d27 KP	290	}
	291	return h;
	292	}
	293
	294	typedef struct _FcListBucket {
	295	struct _FcListBucket *next;
	296	FcChar32 hash;
	297	FcPattern *pattern;
	298	} FcListBucket;
	299
	300	#define FC_LIST_HASH_SIZE 4099
	301
	302	typedef struct _FcListHashTable {
	303	int entries;
	304	FcListBucket *buckets[FC_LIST_HASH_SIZE];
	305	} FcListHashTable;
594dcef0	306
24330d27 KP	307	static void
	308	FcListHashTableInit (FcListHashTable *table)
	309	{
	310	table->entries = 0;
	311	memset (table->buckets, '\0', sizeof (table->buckets));
	312	}
	313
	314	static void
	315	FcListHashTableCleanup (FcListHashTable *table)
	316	{
	317	int i;
	318	FcListBucket bucket, next;
	319
	320	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
	321	{
	322	for (bucket = table->buckets[i]; bucket; bucket = next)
	323	{
	324	next = bucket->next;
	325	FcPatternDestroy (bucket->pattern);
	326	FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
	327	free (bucket);
	328	}
	329	table->buckets[i] = 0;
	330	}
	331	table->entries = 0;
	332	}
	333
90442681	334	static int
7ce19673	335	FcGetDefaultObjectLangIndex (FcPattern *font, FcObject object)
90442681 PL	336	{
90442681 PL	337	FcChar8 *lang = FcGetDefaultLang ();
7ce19673	338	FcPatternElt *e = FcPatternObjectFindElt (font, object);
90442681 PL	339	FcValueListPtr v;
	340	FcValue value;
	341	int idx = -1;
	342	int i;
	343
	344	if (e)
	345	{
7ce19673	346	for (v = FcPatternEltValues(e), i = 0; v; v = FcValueListNext(v), ++i)
90442681	347	{
7ce19673	348	value = FcValueCanonicalize (&v->value);
90442681 PL	349
	350	if (value.type == FcTypeString)
	351	{
	352	FcLangResult res = FcLangCompare (value.u.s, lang);
792ce655 KT	353	if (res == FcLangEqual)
	354	return i;
	355
	356	if (res == FcLangDifferentCountry && idx < 0)
90442681 PL	357	idx = i;
	358	}
	359	}
	360	}
	361
	362	return (idx > 0) ? idx : 0;
	363	}
	364
24330d27 KP	365	static FcBool
	366	FcListAppend (FcListHashTable *table,
	367	FcPattern *font,
	368	FcObjectSet *os)
	369	{
	370	int o;
	371	FcPatternElt *e;
cd2ec1a9	372	FcValueListPtr v;
24330d27 KP	373	FcChar32 hash;
24330d27 KP	374	FcListBucket *prev, bucket;
90442681 PL	375	int familyidx = -1;
	376	int fullnameidx = -1;
	377	int styleidx = -1;
	378	int defidx = 0;
	379	int idx;
24330d27 KP	380
	381	hash = FcListPatternHash (font, os);
	382	for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
	383	(bucket = *prev); prev = &(bucket->next))
	384	{
594dcef0	385	if (bucket->hash == hash &&
24330d27 KP	386	FcListPatternEqual (bucket->pattern, font, os))
	387	return FcTrue;
	388	}
	389	bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
	390	if (!bucket)
	391	goto bail0;
	392	FcMemAlloc (FC_MEM_LISTBUCK, sizeof (FcListBucket));
	393	bucket->next = 0;
	394	bucket->hash = hash;
	395	bucket->pattern = FcPatternCreate ();
	396	if (!bucket->pattern)
	397	goto bail1;
594dcef0	398
24330d27 KP	399	for (o = 0; o < os->nobject; o++)
24330d27 KP	400	{
90442681 PL	401	if (!strcmp (os->objects[o], FC_FAMILY) \|\| !strcmp (os->objects[o], FC_FAMILYLANG))
	402	{
	403	if (familyidx < 0)
7ce19673	404	familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG_OBJECT);
90442681 PL	405	defidx = familyidx;
	406	}
	407	else if (!strcmp (os->objects[o], FC_FULLNAME) \|\| !strcmp (os->objects[o], FC_FULLNAMELANG))
	408	{
	409	if (fullnameidx < 0)
7ce19673	410	fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG_OBJECT);
90442681 PL	411	defidx = fullnameidx;
	412	}
	413	else if (!strcmp (os->objects[o], FC_STYLE) \|\| !strcmp (os->objects[o], FC_STYLELANG))
	414	{
	415	if (styleidx < 0)
7ce19673	416	styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG_OBJECT);
90442681 PL	417	defidx = styleidx;
	418	}
	419	else
	420	defidx = 0;
	421
7ce19673	422	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[o]));
24330d27 KP	423	if (e)
24330d27 KP	424	{
7ce19673 KP	425	for (v = FcPatternEltValues(e), idx = 0; v;
7ce19673 KP	426	v = FcValueListNext(v), ++idx)
24330d27	427	{
594dcef0 BE	428	if (!FcPatternAdd (bucket->pattern,
594dcef0 BE	429	os->objects[o],
7ce19673	430	FcValueCanonicalize(&v->value), defidx != idx))
24330d27 KP	431	goto bail2;
	432	}
	433	}
	434	}
	435	*prev = bucket;
	436	++table->entries;
	437
	438	return FcTrue;
594dcef0	439
24330d27 KP	440	bail2:
	441	FcPatternDestroy (bucket->pattern);
	442	bail1:
	443	FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
	444	free (bucket);
	445	bail0:
	446	return FcFalse;
	447	}
	448
	449	FcFontSet *
80c053b7 KP	450	FcFontSetList (FcConfig *config,
	451	FcFontSet **sets,
	452	int nsets,
	453	FcPattern *p,
	454	FcObjectSet *os)
24330d27 KP	455	{
	456	FcFontSet *ret;
	457	FcFontSet *s;
	458	int f;
80c053b7	459	int set;
24330d27 KP	460	FcListHashTable table;
	461	int i;
	462	FcListBucket *bucket;
29874098	463	int destroy_os = 0;
24330d27 KP	464
	465	if (!config)
	466	{
179c3995 KP	467	if (!FcInitBringUptoDate ())
	468	goto bail0;
	469
24330d27 KP	470	config = FcConfigGetCurrent ();
	471	if (!config)
	472	goto bail0;
	473	}
	474	FcListHashTableInit (&table);
29874098 BE	475
	476	if (!os)
	477	{
	478	os = FcObjectGetSet ();
	479	destroy_os = 1;
	480	}
	481
24330d27 KP	482	/*
	483	* Walk all available fonts adding those that
	484	* match to the hash table
	485	*/
80c053b7	486	for (set = 0; set < nsets; set++)
24330d27	487	{
80c053b7	488	s = sets[set];
24330d27 KP	489	if (!s)
	490	continue;
	491	for (f = 0; f < s->nfont; f++)
74a623e0 KP	492	if (FcListPatternMatchAny (p, /* pattern */
74a623e0 KP	493	s->fonts[f])) /* font */
24330d27 KP	494	if (!FcListAppend (&table, s->fonts[f], os))
	495	goto bail1;
	496	}
	497	#if 0
	498	{
	499	int max = 0;
	500	int full = 0;
	501	int ents = 0;
	502	int len;
	503	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
	504	{
	505	if ((bucket = table.buckets[i]))
	506	{
	507	len = 0;
	508	for (; bucket; bucket = bucket->next)
	509	{
	510	ents++;
	511	len++;
	512	}
	513	if (len > max)
	514	max = len;
	515	full++;
	516	}
	517	}
594dcef0	518	printf ("used: %d max: %d avg: %g\n", full, max,
24330d27 KP	519	(double) ents / FC_LIST_HASH_SIZE);
	520	}
	521	#endif
	522	/*
	523	* Walk the hash table and build
	524	* a font set
	525	*/
	526	ret = FcFontSetCreate ();
	527	if (!ret)
	528	goto bail0;
	529	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
	530	while ((bucket = table.buckets[i]))
	531	{
	532	if (!FcFontSetAdd (ret, bucket->pattern))
	533	goto bail2;
	534	table.buckets[i] = bucket->next;
	535	FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
	536	free (bucket);
	537	}
594dcef0	538
24330d27 KP	539	return ret;
	540
	541	bail2:
	542	FcFontSetDestroy (ret);
	543	bail1:
	544	FcListHashTableCleanup (&table);
	545	bail0:
29874098 BE	546	if (destroy_os)
29874098 BE	547	FcObjectSetDestroy (os);
24330d27 KP	548	return 0;
24330d27 KP	549	}
80c053b7 KP	550
	551	FcFontSet *
	552	FcFontList (FcConfig *config,
	553	FcPattern *p,
	554	FcObjectSet *os)
	555	{
	556	FcFontSet *sets[2];
	557	int nsets;
	558
	559	if (!config)
	560	{
03dcaaa0 BE	561	if (!FcInitBringUptoDate ())
	562	return 0;
	563
80c053b7 KP	564	config = FcConfigGetCurrent ();
	565	if (!config)
	566	return 0;
	567	}
	568	nsets = 0;
	569	if (config->fonts[FcSetSystem])
	570	sets[nsets++] = config->fonts[FcSetSystem];
	571	if (config->fonts[FcSetApplication])
	572	sets[nsets++] = config->fonts[FcSetApplication];
	573	return FcFontSetList (config, sets, nsets, p, os);
	574	}
23816bf9 KP	575	#define __fclist__
	576	#include "fcaliastail.h"
	577	#undef __fclist__