fclist.c revision 2c393a42 
1/*
2 * $RCSId: xc/lib/fontconfig/src/fclist.c,v 1.11tsi Exp $
3 *
4 * Copyright © 2000 Keith Packard
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 "fcint.h"
26#include <stdlib.h>
27
28FcObjectSet *
29FcObjectSetCreate (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
43FcBool
44FcObjectSetAdd (FcObjectSet *os, const char *object)
45{
46    int		s;
47    const char	**objects;
48    int		high, low, mid, c;
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    }
66    high = os->nobject - 1;
67    low = 0;
68    mid = 0;
69    c = 1;
70    object = (char *)FcStrStaticName ((FcChar8 *)object);
71    while (low <= high)
72    {
73	mid = (low + high) >> 1;
74	c = os->objects[mid] - object;
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++;
84    memmove (os->objects + mid + 1, os->objects + mid,
85	     (os->nobject - mid) * sizeof (const char *));
86    os->objects[mid] = object;
87    os->nobject++;
88    return FcTrue;
89}
90
91void
92FcObjectSetDestroy (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
103FcObjectSet *
104FcObjectSetVaBuild (const char *first, va_list va)
105{
106    FcObjectSet    *ret;
107
108    FcObjectSetVapBuild (ret, first, va);
109    return ret;
110}
111
112FcObjectSet *
113FcObjectSetBuild (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
124/*
125 * Font must have a containing value for every value in the pattern
126 */
127static FcBool
128FcListValueListMatchAny (FcValueListPtr patOrig,	    /* pattern */
129			 FcValueListPtr fntOrig)	    /* font */
130{
131    FcValueListPtr	 pat, fnt;
132
133    for (pat = patOrig; pat != NULL; pat = FcValueListNext(pat))
134    {
135	for (fnt = fntOrig; fnt != NULL; fnt = FcValueListNext(fnt))
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	     */
142	    if (FcConfigCompareValue (&fnt->value,
143				      FcOpListing,
144				      &pat->value))
145		break;
146	}
147	if (fnt == NULL)
148	    return FcFalse;
149    }
150    return FcTrue;
151}
152
153static FcBool
154FcListValueListEqual (FcValueListPtr v1orig,
155		      FcValueListPtr v2orig)
156{
157    FcValueListPtr	    v1, v2;
158
159    for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext(v1))
160    {
161	for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext(v2))
162	    if (FcValueEqual (FcValueCanonicalize(&(v1)->value),
163			      FcValueCanonicalize(&(v2)->value)))
164		break;
165	if (v2 == NULL)
166	    return FcFalse;
167    }
168    for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext(v2))
169    {
170	for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext(v1))
171	    if (FcValueEqual (FcValueCanonicalize(&v1->value),
172			      FcValueCanonicalize(&v2->value)))
173		break;
174	if (v1 == NULL)
175	    return FcFalse;
176    }
177    return FcTrue;
178}
179
180static FcBool
181FcListPatternEqual (FcPattern	*p1,
182		    FcPattern	*p2,
183		    FcObjectSet	*os)
184{
185    int		    i;
186    FcPatternElt    *e1, *e2;
187
188    for (i = 0; i < os->nobject; i++)
189    {
190	e1 = FcPatternObjectFindElt (p1, FcObjectFromName (os->objects[i]));
191	e2 = FcPatternObjectFindElt (p2, FcObjectFromName (os->objects[i]));
192	if (!e1 && !e2)
193	    continue;
194	if (!e1 || !e2)
195	    return FcFalse;
196	if (!FcListValueListEqual (FcPatternEltValues(e1),
197				   FcPatternEltValues(e2)))
198	    return FcFalse;
199    }
200    return FcTrue;
201}
202
203/*
204 * FcTrue iff all objects in "p" match "font"
205 */
206
207FcBool
208FcListPatternMatchAny (const FcPattern *p,
209		       const FcPattern *font)
210{
211    int		    i;
212
213    for (i = 0; i < p->num; i++)
214    {
215	FcPatternElt	*pe = &FcPatternElts(p)[i];
216	FcPatternElt	*fe = FcPatternObjectFindElt (font, pe->object);
217	if (!fe)
218	    return FcFalse;
219	if (!FcListValueListMatchAny (FcPatternEltValues(pe),    /* pat elts */
220				      FcPatternEltValues(fe)))   /* font elts */
221	    return FcFalse;
222    }
223    return FcTrue;
224}
225
226static FcChar32
227FcListMatrixHash (const FcMatrix *m)
228{
229    int	    xx = (int) (m->xx * 100),
230	    xy = (int) (m->xy * 100),
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
237static FcChar32
238FcListValueHash (FcValue    *value)
239{
240    FcValue v = FcValueCanonicalize(value);
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:
249	return FcStrHashIgnoreCase (v.u.s);
250    case FcTypeBool:
251	return (FcChar32) v.u.b;
252    case FcTypeMatrix:
253	return FcListMatrixHash (v.u.m);
254    case FcTypeCharSet:
255	return FcCharSetCount (v.u.c);
256    case FcTypeFTFace:
257	return (long) v.u.f;
258    case FcTypeLangSet:
259	return FcLangSetHash (v.u.l);
260    }
261    return 0;
262}
263
264static FcChar32
265FcListValueListHash (FcValueListPtr list)
266{
267    FcChar32	h = 0;
268
269    while (list != NULL)
270    {
271	h = h ^ FcListValueHash (&list->value);
272	list = FcValueListNext(list);
273    }
274    return h;
275}
276
277static FcChar32
278FcListPatternHash (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    {
287	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[n]));
288	if (e)
289	    h = h ^ FcListValueListHash (FcPatternEltValues(e));
290    }
291    return h;
292}
293
294typedef struct _FcListBucket {
295    struct _FcListBucket    *next;
296    FcChar32		    hash;
297    FcPattern		    *pattern;
298} FcListBucket;
299
300#define FC_LIST_HASH_SIZE   4099
301
302typedef struct _FcListHashTable {
303    int		    entries;
304    FcListBucket    *buckets[FC_LIST_HASH_SIZE];
305} FcListHashTable;
306
307static void
308FcListHashTableInit (FcListHashTable *table)
309{
310    table->entries = 0;
311    memset (table->buckets, '\0', sizeof (table->buckets));
312}
313
314static void
315FcListHashTableCleanup (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
334static int
335FcGetDefaultObjectLangIndex (FcPattern *font, FcObject object)
336{
337    FcChar8	   *lang = FcGetDefaultLang ();
338    FcPatternElt   *e = FcPatternObjectFindElt (font, object);
339    FcValueListPtr  v;
340    FcValue         value;
341    int             idx = -1;
342    int             i;
343
344    if (e)
345    {
346	for (v = FcPatternEltValues(e), i = 0; v; v = FcValueListNext(v), ++i)
347	{
348	    value = FcValueCanonicalize (&v->value);
349
350	    if (value.type == FcTypeString)
351	    {
352		FcLangResult res = FcLangCompare (value.u.s, lang);
353		if (res == FcLangEqual || (res == FcLangDifferentCountry && idx < 0))
354		    idx = i;
355	    }
356	}
357    }
358
359    return (idx > 0) ? idx : 0;
360}
361
362static FcBool
363FcListAppend (FcListHashTable	*table,
364	      FcPattern		*font,
365	      FcObjectSet	*os)
366{
367    int		    o;
368    FcPatternElt    *e;
369    FcValueListPtr  v;
370    FcChar32	    hash;
371    FcListBucket    **prev, *bucket;
372    int             familyidx = -1;
373    int             fullnameidx = -1;
374    int             styleidx = -1;
375    int             defidx = 0;
376    int             idx;
377
378    hash = FcListPatternHash (font, os);
379    for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
380	 (bucket = *prev); prev = &(bucket->next))
381    {
382	if (bucket->hash == hash &&
383	    FcListPatternEqual (bucket->pattern, font, os))
384	    return FcTrue;
385    }
386    bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
387    if (!bucket)
388	goto bail0;
389    FcMemAlloc (FC_MEM_LISTBUCK, sizeof (FcListBucket));
390    bucket->next = 0;
391    bucket->hash = hash;
392    bucket->pattern = FcPatternCreate ();
393    if (!bucket->pattern)
394	goto bail1;
395
396    for (o = 0; o < os->nobject; o++)
397    {
398	if (!strcmp (os->objects[o], FC_FAMILY) || !strcmp (os->objects[o], FC_FAMILYLANG))
399	{
400	    if (familyidx < 0)
401		familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG_OBJECT);
402	    defidx = familyidx;
403	}
404	else if (!strcmp (os->objects[o], FC_FULLNAME) || !strcmp (os->objects[o], FC_FULLNAMELANG))
405	{
406	    if (fullnameidx < 0)
407		fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG_OBJECT);
408	    defidx = fullnameidx;
409	}
410	else if (!strcmp (os->objects[o], FC_STYLE) || !strcmp (os->objects[o], FC_STYLELANG))
411	{
412	    if (styleidx < 0)
413		styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG_OBJECT);
414	    defidx = styleidx;
415	}
416	else
417	    defidx = 0;
418
419	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[o]));
420	if (e)
421	{
422	    for (v = FcPatternEltValues(e), idx = 0; v;
423		 v = FcValueListNext(v), ++idx)
424	    {
425		if (!FcPatternAdd (bucket->pattern,
426				   os->objects[o],
427				   FcValueCanonicalize(&v->value), defidx != idx))
428		    goto bail2;
429	    }
430	}
431    }
432    *prev = bucket;
433    ++table->entries;
434
435    return FcTrue;
436
437bail2:
438    FcPatternDestroy (bucket->pattern);
439bail1:
440    FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
441    free (bucket);
442bail0:
443    return FcFalse;
444}
445
446FcFontSet *
447FcFontSetList (FcConfig	    *config,
448	       FcFontSet    **sets,
449	       int	    nsets,
450	       FcPattern    *p,
451	       FcObjectSet  *os)
452{
453    FcFontSet	    *ret;
454    FcFontSet	    *s;
455    int		    f;
456    int		    set;
457    FcListHashTable table;
458    int		    i;
459    FcListBucket    *bucket;
460
461    if (!config)
462    {
463	if (!FcInitBringUptoDate ())
464	    goto bail0;
465
466	config = FcConfigGetCurrent ();
467	if (!config)
468	    goto bail0;
469    }
470    FcListHashTableInit (&table);
471    /*
472     * Walk all available fonts adding those that
473     * match to the hash table
474     */
475    for (set = 0; set < nsets; set++)
476    {
477	s = sets[set];
478	if (!s)
479	    continue;
480	for (f = 0; f < s->nfont; f++)
481	    if (FcListPatternMatchAny (p,		/* pattern */
482				       s->fonts[f]))	/* font */
483		if (!FcListAppend (&table, s->fonts[f], os))
484		    goto bail1;
485    }
486#if 0
487    {
488	int	max = 0;
489	int	full = 0;
490	int	ents = 0;
491	int	len;
492	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
493	{
494	    if ((bucket = table.buckets[i]))
495	    {
496		len = 0;
497		for (; bucket; bucket = bucket->next)
498		{
499		    ents++;
500		    len++;
501		}
502		if (len > max)
503		    max = len;
504		full++;
505	    }
506	}
507	printf ("used: %d max: %d avg: %g\n", full, max,
508		(double) ents / FC_LIST_HASH_SIZE);
509    }
510#endif
511    /*
512     * Walk the hash table and build
513     * a font set
514     */
515    ret = FcFontSetCreate ();
516    if (!ret)
517	goto bail0;
518    for (i = 0; i < FC_LIST_HASH_SIZE; i++)
519	while ((bucket = table.buckets[i]))
520	{
521	    if (!FcFontSetAdd (ret, bucket->pattern))
522		goto bail2;
523	    table.buckets[i] = bucket->next;
524	    FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
525	    free (bucket);
526	}
527
528    return ret;
529
530bail2:
531    FcFontSetDestroy (ret);
532bail1:
533    FcListHashTableCleanup (&table);
534bail0:
535    return 0;
536}
537
538FcFontSet *
539FcFontList (FcConfig	*config,
540	    FcPattern	*p,
541	    FcObjectSet *os)
542{
543    FcFontSet	*sets[2];
544    int		nsets;
545
546    if (!config)
547    {
548	config = FcConfigGetCurrent ();
549	if (!config)
550	    return 0;
551    }
552    nsets = 0;
553    if (config->fonts[FcSetSystem])
554	sets[nsets++] = config->fonts[FcSetSystem];
555    if (config->fonts[FcSetApplication])
556	sets[nsets++] = config->fonts[FcSetApplication];
557    return FcFontSetList (config, sets, nsets, p, os);
558}
559#define __fclist__
560#include "fcaliastail.h"
561#undef __fclist__
562