[fontconfig.git] / src / fclist.c

/*
 * $RCSId: xc/lib/fontconfig/src/fclist.c,v 1.11tsi Exp $
 *
 * 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 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.
 */

#include <stdlib.h>
#include "fcint.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;
    while (low <= high)
    {
	mid = (low + high) >> 1;
	c = strcmp (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] = FcObjectStaticName (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 (FcValueList *patOrig,	    /* pattern */
			 FcValueList *fntOrig)	    /* font */
{
    FcValueList	    *pat, *fnt;

    for (pat = patOrig; pat; pat = pat->next)
    {
	for (fnt = fntOrig; fnt; fnt = fnt->next)
	{
	    /*
	     * 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)
	    return FcFalse;
    }
    return FcTrue;
}

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

    for (v1 = v1orig; v1; v1 = v1->next)
    {
	for (v2 = v2orig; v2; v2 = v2->next)
	    if (FcValueEqual (v1->value, v2->value))
		break;
	if (!v2)
	    return FcFalse;
    }
    for (v2 = v2orig; v2; v2 = v2->next)
    {
	for (v1 = v1orig; v1; v1 = v1->next)
	    if (FcValueEqual (v1->value, v2->value))
		break;
	if (!v1)
	    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 = FcPatternFindElt (p1, os->objects[i]);
	e2 = FcPatternFindElt (p2, os->objects[i]);
	if (!e1 && !e2)
	    continue;
	if (!e1 || !e2)
	    return FcFalse;
	if (!FcListValueListEqual (e1->values, e2->values))
	    return FcFalse;
    }
    return FcTrue;
}

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

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

    for (i = 0; i < p->num; i++)
    {
	e = FcPatternFindElt (font, p->elts[i].object);
	if (!e)
	    return FcFalse;
	if (!FcListValueListMatchAny (p->elts[i].values,    /* pat elts */
				      e->values))	    /* font elts */
	    return FcFalse;
    }
    return FcTrue;
}

static FcChar32
FcListStringHash (const FcChar8	*s)
{
    FcChar32	h = 0;
    FcChar8	c;

    while ((c = *s++))
    {
	c = FcToLower (c);
	h = ((h << 3) ^ (h >> 3)) ^ c;
    }
    return h;
}

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    v)
{
    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 FcListStringHash (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 (FcValueList    *list)
{
    FcChar32	h = 0;
    
    while (list)
    {
	h = h ^ FcListValueHash (list->value);
	list = list->next;
    }
    return h;
}

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

    for (n = 0; n < os->nobject; n++)
    {
	e = FcPatternFindElt (font, os->objects[n]);
	if (e)
	    h = h ^ FcListValueListHash (e->values);
    }
    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 FcBool
FcListAppend (FcListHashTable	*table,
	      FcPattern		*font,
	      FcObjectSet	*os)
{
    int		    o;
    FcPatternElt    *e;
    FcValueList	    *v;
    FcChar32	    hash;
    FcListBucket    **prev, *bucket;

    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++)
    {
	e = FcPatternFindElt (font, os->objects[o]);
	if (e)
	{
	    for (v = e->values; v; v = v->next)
	    {
		if (!FcPatternAdd (bucket->pattern, 
				   os->objects[o], 
				   v->value, FcTrue))
		    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;

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

	config = FcConfigGetCurrent ();
	if (!config)
	    goto bail0;
    }
    FcListHashTableInit (&table);
    /*
     * 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:
    return 0;
}

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

    if (!config)
    {
	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);
}
Commit	Line	Data
24330d27	1	/*
793e946c	2	* $RCSId: xc/lib/fontconfig/src/fclist.c,v 1.11tsi Exp $
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
	10	* documentation, and that the name of Keith Packard not be used in
	11	* advertising or publicity pertaining to distribution of the software without
	12	* specific, written prior permission. Keith Packard makes no
	13	* representations about the suitability of this software for any purpose. It
	14	* is provided "as is" without express or implied warranty.
	15	*
	16	* KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
	17	* INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
	18	* EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
	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
	25	#include <stdlib.h>
	26	#include "fcint.h"
	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;
	47	const char **objects;
e9be9cd1	48	int high, low, mid, c;
24330d27 KP	49
	50	if (os->nobject == os->sobject)
	51	{
	52	s = os->sobject + 4;
	53	if (os->objects)
	54	objects = (const char *) realloc ((void ) os->objects,
	55	s * sizeof (const char *));
	56	else
	57	objects = (const char *) malloc (s sizeof (const char *));
	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;
	70	while (low <= high)
	71	{
	72	mid = (low + high) >> 1;
	73	c = strcmp (os->objects[mid], object);
	74	if (c == 0)
	75	return FcTrue;
	76	if (c < 0)
	77	low = mid + 1;
	78	else
	79	high = mid - 1;
	80	}
	81	if (c < 0)
	82	mid++;
5b1bfa5d KP	83	memmove (os->objects + mid + 1, os->objects + mid,
5b1bfa5d KP	84	(os->nobject - mid) * sizeof (const char *));
1c52c0f0	85	os->objects[mid] = FcObjectStaticName (object);
e9be9cd1	86	os->nobject++;
24330d27 KP	87	return FcTrue;
	88	}
	89
	90	void
	91	FcObjectSetDestroy (FcObjectSet *os)
	92	{
	93	if (os->objects)
	94	{
	95	FcMemFree (FC_MEM_OBJECTPTR, os->sobject * sizeof (const char *));
	96	free ((void *) os->objects);
	97	}
	98	FcMemFree (FC_MEM_OBJECTSET, sizeof (FcObjectSet));
	99	free (os);
	100	}
	101
	102	FcObjectSet *
	103	FcObjectSetVaBuild (const char *first, va_list va)
	104	{
	105	FcObjectSet *ret;
	106
	107	FcObjectSetVapBuild (ret, first, va);
	108	return ret;
	109	}
	110
	111	FcObjectSet *
	112	FcObjectSetBuild (const char *first, ...)
	113	{
	114	va_list va;
	115	FcObjectSet *os;
	116
	117	va_start (va, first);
	118	FcObjectSetVapBuild (os, first, va);
	119	va_end (va);
	120	return os;
	121	}
	122
74a623e0 KP	123	/*
	124	* Font must have a containing value for every value in the pattern
	125	*/
24330d27	126	static FcBool
74a623e0 KP	127	FcListValueListMatchAny (FcValueList patOrig, / pattern */
74a623e0 KP	128	FcValueList fntOrig) / font */
24330d27	129	{
74a623e0	130	FcValueList pat, fnt;
24330d27	131
74a623e0 KP	132	for (pat = patOrig; pat; pat = pat->next)
	133	{
	134	for (fnt = fntOrig; fnt; fnt = fnt->next)
	135	{
	136	/*
	137	* make sure the font 'contains' the pattern.
	138	* (OpListing is OpContains except for strings
	139	* where it requires an exact match)
	140	*/
	141	if (FcConfigCompareValue (fnt->value,
	142	FcOpListing,
	143	pat->value))
	144	break;
	145	}
	146	if (!fnt)
	147	return FcFalse;
	148	}
	149	return FcTrue;
24330d27 KP	150	}
	151
	152	static FcBool
	153	FcListValueListEqual (FcValueList *v1orig,
	154	FcValueList *v2orig)
	155	{
	156	FcValueList v1, v2;
	157
	158	for (v1 = v1orig; v1; v1 = v1->next)
	159	{
	160	for (v2 = v2orig; v2; v2 = v2->next)
47d4f950	161	if (FcValueEqual (v1->value, v2->value))
24330d27 KP	162	break;
	163	if (!v2)
	164	return FcFalse;
	165	}
	166	for (v2 = v2orig; v2; v2 = v2->next)
	167	{
	168	for (v1 = v1orig; v1; v1 = v1->next)
47d4f950	169	if (FcValueEqual (v1->value, v2->value))
24330d27 KP	170	break;
	171	if (!v1)
	172	return FcFalse;
	173	}
	174	return FcTrue;
	175	}
	176
24330d27	177	static FcBool
e9be9cd1 KP	178	FcListPatternEqual (FcPattern *p1,
	179	FcPattern *p2,
	180	FcObjectSet *os)
24330d27 KP	181	{
24330d27 KP	182	int i;
e9be9cd1	183	FcPatternElt e1, e2;
24330d27	184
e9be9cd1	185	for (i = 0; i < os->nobject; i++)
24330d27	186	{
e9be9cd1 KP	187	e1 = FcPatternFindElt (p1, os->objects[i]);
	188	e2 = FcPatternFindElt (p2, os->objects[i]);
	189	if (!e1 && !e2)
47d4f950	190	continue;
e9be9cd1	191	if (!e1 \|\| !e2)
24330d27	192	return FcFalse;
e9be9cd1	193	if (!FcListValueListEqual (e1->values, e2->values))
24330d27 KP	194	return FcFalse;
	195	}
	196	return FcTrue;
	197	}
	198
e9be9cd1 KP	199	/*
	200	* FcTrue iff all objects in "p" match "font"
	201	*/
	202
4f27c1c0 KP	203	FcBool
	204	FcListPatternMatchAny (const FcPattern *p,
	205	const FcPattern *font)
24330d27 KP	206	{
24330d27 KP	207	int i;
e9be9cd1	208	FcPatternElt *e;
24330d27	209
e9be9cd1	210	for (i = 0; i < p->num; i++)
24330d27	211	{
e9be9cd1 KP	212	e = FcPatternFindElt (font, p->elts[i].object);
e9be9cd1 KP	213	if (!e)
24330d27	214	return FcFalse;
74a623e0 KP	215	if (!FcListValueListMatchAny (p->elts[i].values, /* pat elts */
74a623e0 KP	216	e->values)) /* font elts */
24330d27 KP	217	return FcFalse;
	218	}
	219	return FcTrue;
	220	}
	221
	222	static FcChar32
	223	FcListStringHash (const FcChar8 *s)
	224	{
	225	FcChar32 h = 0;
	226	FcChar8 c;
	227
	228	while ((c = *s++))
	229	{
	230	c = FcToLower (c);
	231	h = ((h << 3) ^ (h >> 3)) ^ c;
	232	}
	233	return h;
	234	}
	235
	236	static FcChar32
	237	FcListMatrixHash (const FcMatrix *m)
	238	{
	239	int xx = (int) (m->xx * 100),
	240	xy = (int) (m->xy * 100),
	241	yx = (int) (m->yx * 100),
	242	yy = (int) (m->yy * 100);
	243
	244	return ((FcChar32) xx) ^ ((FcChar32) xy) ^ ((FcChar32) yx) ^ ((FcChar32) yy);
	245	}
	246
	247	static FcChar32
	248	FcListValueHash (FcValue v)
	249	{
	250	switch (v.type) {
	251	case FcTypeVoid:
	252	return 0;
	253	case FcTypeInteger:
	254	return (FcChar32) v.u.i;
	255	case FcTypeDouble:
	256	return (FcChar32) (int) v.u.d;
	257	case FcTypeString:
	258	return FcListStringHash (v.u.s);
	259	case FcTypeBool:
	260	return (FcChar32) v.u.b;
	261	case FcTypeMatrix:
	262	return FcListMatrixHash (v.u.m);
	263	case FcTypeCharSet:
	264	return FcCharSetCount (v.u.c);
88c747e2	265	case FcTypeFTFace:
d1bec8c6	266	return (long) v.u.f;
d8d73958 KP	267	case FcTypeLangSet:
d8d73958 KP	268	return FcLangSetHash (v.u.l);
24330d27 KP	269	}
	270	return 0;
	271	}
	272
	273	static FcChar32
	274	FcListValueListHash (FcValueList *list)
	275	{
	276	FcChar32 h = 0;
	277
	278	while (list)
	279	{
	280	h = h ^ FcListValueHash (list->value);
	281	list = list->next;
	282	}
	283	return h;
	284	}
	285
	286	static FcChar32
	287	FcListPatternHash (FcPattern *font,
	288	FcObjectSet *os)
	289	{
	290	int n;
	291	FcPatternElt *e;
	292	FcChar32 h = 0;
	293
	294	for (n = 0; n < os->nobject; n++)
	295	{
e9be9cd1	296	e = FcPatternFindElt (font, os->objects[n]);
24330d27 KP	297	if (e)
	298	h = h ^ FcListValueListHash (e->values);
	299	}
	300	return h;
	301	}
	302
	303	typedef struct _FcListBucket {
	304	struct _FcListBucket *next;
	305	FcChar32 hash;
	306	FcPattern *pattern;
	307	} FcListBucket;
	308
	309	#define FC_LIST_HASH_SIZE 4099
	310
	311	typedef struct _FcListHashTable {
	312	int entries;
	313	FcListBucket *buckets[FC_LIST_HASH_SIZE];
	314	} FcListHashTable;
	315
	316	static void
	317	FcListHashTableInit (FcListHashTable *table)
	318	{
	319	table->entries = 0;
	320	memset (table->buckets, '\0', sizeof (table->buckets));
	321	}
	322
	323	static void
	324	FcListHashTableCleanup (FcListHashTable *table)
	325	{
	326	int i;
	327	FcListBucket bucket, next;
	328
	329	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
	330	{
	331	for (bucket = table->buckets[i]; bucket; bucket = next)
	332	{
	333	next = bucket->next;
	334	FcPatternDestroy (bucket->pattern);
	335	FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
	336	free (bucket);
	337	}
	338	table->buckets[i] = 0;
	339	}
	340	table->entries = 0;
	341	}
	342
	343	static FcBool
	344	FcListAppend (FcListHashTable *table,
	345	FcPattern *font,
	346	FcObjectSet *os)
	347	{
	348	int o;
	349	FcPatternElt *e;
	350	FcValueList *v;
	351	FcChar32 hash;
	352	FcListBucket *prev, bucket;
	353
	354	hash = FcListPatternHash (font, os);
	355	for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
	356	(bucket = *prev); prev = &(bucket->next))
	357	{
	358	if (bucket->hash == hash &&
	359	FcListPatternEqual (bucket->pattern, font, os))
	360	return FcTrue;
361	}
362	bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
363	if (!bucket)
364	goto bail0;
365	FcMemAlloc (FC_MEM_LISTBUCK, sizeof (FcListBucket));
366	bucket->next = 0;
367	bucket->hash = hash;
368	bucket->pattern = FcPatternCreate ();
369	if (!bucket->pattern)
370	goto bail1;
371
372	for (o = 0; o < os->nobject; o++)
373	{
e9be9cd1	374	e = FcPatternFindElt (font, os->objects[o]);
24330d27 KP	375	if (e)
	376	{
	377	for (v = e->values; v; v = v->next)
	378	{
	379	if (!FcPatternAdd (bucket->pattern,
	380	os->objects[o],
	381	v->value, FcTrue))
	382	goto bail2;
	383	}
	384	}
	385	}
	386	*prev = bucket;
	387	++table->entries;
	388
	389	return FcTrue;
	390
	391	bail2:
	392	FcPatternDestroy (bucket->pattern);
	393	bail1:
	394	FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
	395	free (bucket);
	396	bail0:
	397	return FcFalse;
	398	}
	399
	400	FcFontSet *
80c053b7 KP	401	FcFontSetList (FcConfig *config,
	402	FcFontSet **sets,
	403	int nsets,
	404	FcPattern *p,
	405	FcObjectSet *os)
24330d27 KP	406	{
	407	FcFontSet *ret;
	408	FcFontSet *s;
	409	int f;
80c053b7	410	int set;
24330d27 KP	411	FcListHashTable table;
	412	int i;
	413	FcListBucket *bucket;
	414
	415	if (!config)
	416	{
179c3995 KP	417	if (!FcInitBringUptoDate ())
	418	goto bail0;
	419
24330d27 KP	420	config = FcConfigGetCurrent ();
	421	if (!config)
	422	goto bail0;
	423	}
	424	FcListHashTableInit (&table);
	425	/*
	426	* Walk all available fonts adding those that
	427	* match to the hash table
	428	*/
80c053b7	429	for (set = 0; set < nsets; set++)
24330d27	430	{
80c053b7	431	s = sets[set];
24330d27 KP	432	if (!s)
	433	continue;
	434	for (f = 0; f < s->nfont; f++)
74a623e0 KP	435	if (FcListPatternMatchAny (p, /* pattern */
74a623e0 KP	436	s->fonts[f])) /* font */
24330d27 KP	437	if (!FcListAppend (&table, s->fonts[f], os))
	438	goto bail1;
	439	}
	440	#if 0
	441	{
	442	int max = 0;
	443	int full = 0;
	444	int ents = 0;
	445	int len;
	446	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
	447	{
	448	if ((bucket = table.buckets[i]))
	449	{
	450	len = 0;
	451	for (; bucket; bucket = bucket->next)
	452	{
	453	ents++;
	454	len++;
	455	}
	456	if (len > max)
	457	max = len;
	458	full++;
	459	}
	460	}
	461	printf ("used: %d max: %d avg: %g\n", full, max,
	462	(double) ents / FC_LIST_HASH_SIZE);
	463	}
	464	#endif
	465	/*
	466	* Walk the hash table and build
	467	* a font set
	468	*/
	469	ret = FcFontSetCreate ();
	470	if (!ret)
	471	goto bail0;
	472	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
	473	while ((bucket = table.buckets[i]))
	474	{
	475	if (!FcFontSetAdd (ret, bucket->pattern))
	476	goto bail2;
	477	table.buckets[i] = bucket->next;
	478	FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
	479	free (bucket);
	480	}
	481
	482	return ret;
	483
	484	bail2:
	485	FcFontSetDestroy (ret);
	486	bail1:
	487	FcListHashTableCleanup (&table);
	488	bail0:
	489	return 0;
	490	}
80c053b7 KP	491
	492	FcFontSet *
	493	FcFontList (FcConfig *config,
	494	FcPattern *p,
	495	FcObjectSet *os)
	496	{
	497	FcFontSet *sets[2];
	498	int nsets;
	499
	500	if (!config)
	501	{
	502	config = FcConfigGetCurrent ();
	503	if (!config)
	504	return 0;
	505	}
	506	nsets = 0;
	507	if (config->fonts[FcSetSystem])
	508	sets[nsets++] = config->fonts[FcSetSystem];
	509	if (config->fonts[FcSetApplication])
	510	sets[nsets++] = config->fonts[FcSetApplication];
	511	return FcFontSetList (config, sets, nsets, p, os);
	512	}