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