fclist.c revision 953daeba 
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    if (!p)
216	return FcFalse;
217    for (i = 0; i < p->num; i++)
218    {
219	FcPatternElt	*pe = &FcPatternElts(p)[i];
220	FcPatternElt	*fe;
221
222	if (pe->object == FC_NAMELANG_OBJECT)
223	{
224	    /* "namelang" object is the alias object to change "familylang",
225	     * "stylelang" and "fullnamelang" object alltogether. it won't be
226	     * available on the font pattern. so checking its availability
227	     * causes no results. we should ignore it here.
228	     */
229	    continue;
230	}
231	fe = FcPatternObjectFindElt (font, pe->object);
232	if (!fe)
233	    return FcFalse;
234	if (!FcListValueListMatchAny (FcPatternEltValues(pe),    /* pat elts */
235				      FcPatternEltValues(fe)))   /* font elts */
236	    return FcFalse;
237    }
238    return FcTrue;
239}
240
241static FcChar32
242FcListMatrixHash (const FcMatrix *m)
243{
244    int	    xx = (int) (m->xx * 100),
245	    xy = (int) (m->xy * 100),
246	    yx = (int) (m->yx * 100),
247	    yy = (int) (m->yy * 100);
248
249    return ((FcChar32) xx) ^ ((FcChar32) xy) ^ ((FcChar32) yx) ^ ((FcChar32) yy);
250}
251
252static FcChar32
253FcListValueHash (FcValue    *value)
254{
255    FcValue v = FcValueCanonicalize(value);
256    switch (v.type) {
257    case FcTypeUnknown:
258    case FcTypeVoid:
259	return 0;
260    case FcTypeInteger:
261	return (FcChar32) v.u.i;
262    case FcTypeDouble:
263	return (FcChar32) (int) v.u.d;
264    case FcTypeString:
265	return FcStrHashIgnoreCase (v.u.s);
266    case FcTypeBool:
267	return (FcChar32) v.u.b;
268    case FcTypeMatrix:
269	return FcListMatrixHash (v.u.m);
270    case FcTypeCharSet:
271	return FcCharSetCount (v.u.c);
272    case FcTypeFTFace:
273	return (intptr_t) v.u.f;
274    case FcTypeLangSet:
275	return FcLangSetHash (v.u.l);
276    case FcTypeRange:
277	return FcRangeHash (v.u.r);
278    }
279    return 0;
280}
281
282static FcChar32
283FcListValueListHash (FcValueListPtr list)
284{
285    FcChar32	h = 0;
286
287    while (list != NULL)
288    {
289	h = h ^ FcListValueHash (&list->value);
290	list = FcValueListNext(list);
291    }
292    return h;
293}
294
295static FcChar32
296FcListPatternHash (FcPattern	*font,
297		   FcObjectSet	*os)
298{
299    int		    n;
300    FcPatternElt    *e;
301    FcChar32	    h = 0;
302
303    for (n = 0; n < os->nobject; n++)
304    {
305	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[n]));
306	if (e)
307	    h = h ^ FcListValueListHash (FcPatternEltValues(e));
308    }
309    return h;
310}
311
312typedef struct _FcListBucket {
313    struct _FcListBucket    *next;
314    FcChar32		    hash;
315    FcPattern		    *pattern;
316} FcListBucket;
317
318#define FC_LIST_HASH_SIZE   4099
319
320typedef struct _FcListHashTable {
321    int		    entries;
322    FcListBucket    *buckets[FC_LIST_HASH_SIZE];
323} FcListHashTable;
324
325static void
326FcListHashTableInit (FcListHashTable *table)
327{
328    table->entries = 0;
329    memset (table->buckets, '\0', sizeof (table->buckets));
330}
331
332static void
333FcListHashTableCleanup (FcListHashTable *table)
334{
335    int	i;
336    FcListBucket    *bucket, *next;
337
338    for (i = 0; i < FC_LIST_HASH_SIZE; i++)
339    {
340	for (bucket = table->buckets[i]; bucket; bucket = next)
341	{
342	    next = bucket->next;
343	    FcPatternDestroy (bucket->pattern);
344	    free (bucket);
345	}
346	table->buckets[i] = 0;
347    }
348    table->entries = 0;
349}
350
351static int
352FcGetDefaultObjectLangIndex (FcPattern *font, FcObject object, const FcChar8 *lang)
353{
354    FcPatternElt   *e = FcPatternObjectFindElt (font, object);
355    FcValueListPtr  v;
356    FcValue         value;
357    int             idx = -1;
358    int             defidx = -1;
359    int             i;
360
361    if (e)
362    {
363	for (v = FcPatternEltValues(e), i = 0; v; v = FcValueListNext(v), ++i)
364	{
365	    value = FcValueCanonicalize (&v->value);
366
367	    if (value.type == FcTypeString)
368	    {
369		FcLangResult res = FcLangCompare (value.u.s, lang);
370		if (res == FcLangEqual)
371		    return i;
372
373		if (res == FcLangDifferentCountry && idx < 0)
374		    idx = i;
375		if (defidx < 0)
376		{
377		    /* workaround for fonts that has non-English value
378		     * at the head of values.
379		     */
380		    res = FcLangCompare (value.u.s, (FcChar8 *)"en");
381		    if (res == FcLangEqual)
382			defidx = i;
383		}
384	    }
385	}
386    }
387
388    return (idx > 0) ? idx : (defidx > 0) ? defidx : 0;
389}
390
391static FcBool
392FcListAppend (FcListHashTable	*table,
393	      FcPattern		*font,
394	      FcObjectSet	*os,
395	      const FcChar8	*lang)
396{
397    int		    o;
398    FcPatternElt    *e;
399    FcValueListPtr  v;
400    FcChar32	    hash;
401    FcListBucket    **prev, *bucket;
402    int             familyidx = -1;
403    int             fullnameidx = -1;
404    int             styleidx = -1;
405    int             defidx = 0;
406    int             idx;
407
408    hash = FcListPatternHash (font, os);
409    for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
410	 (bucket = *prev); prev = &(bucket->next))
411    {
412	if (bucket->hash == hash &&
413	    FcListPatternEqual (bucket->pattern, font, os))
414	    return FcTrue;
415    }
416    bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
417    if (!bucket)
418	goto bail0;
419    bucket->next = 0;
420    bucket->hash = hash;
421    bucket->pattern = FcPatternCreate ();
422    if (!bucket->pattern)
423	goto bail1;
424
425    for (o = 0; o < os->nobject; o++)
426    {
427	if (!strcmp (os->objects[o], FC_FAMILY) || !strcmp (os->objects[o], FC_FAMILYLANG))
428	{
429	    if (familyidx < 0)
430		familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG_OBJECT, lang);
431	    defidx = familyidx;
432	}
433	else if (!strcmp (os->objects[o], FC_FULLNAME) || !strcmp (os->objects[o], FC_FULLNAMELANG))
434	{
435	    if (fullnameidx < 0)
436		fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG_OBJECT, lang);
437	    defidx = fullnameidx;
438	}
439	else if (!strcmp (os->objects[o], FC_STYLE) || !strcmp (os->objects[o], FC_STYLELANG))
440	{
441	    if (styleidx < 0)
442		styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG_OBJECT, lang);
443	    defidx = styleidx;
444	}
445	else
446	    defidx = 0;
447
448	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[o]));
449	if (e)
450	{
451	    for (v = FcPatternEltValues(e), idx = 0; v;
452		 v = FcValueListNext(v), ++idx)
453	    {
454		if (!FcPatternAdd (bucket->pattern,
455				   os->objects[o],
456				   FcValueCanonicalize(&v->value), defidx != idx))
457		    goto bail2;
458	    }
459	}
460    }
461    *prev = bucket;
462    ++table->entries;
463
464    return FcTrue;
465
466bail2:
467    FcPatternDestroy (bucket->pattern);
468bail1:
469    free (bucket);
470bail0:
471    return FcFalse;
472}
473
474FcFontSet *
475FcFontSetList (FcConfig	    *config,
476	       FcFontSet    **sets,
477	       int	    nsets,
478	       FcPattern    *p,
479	       FcObjectSet  *os)
480{
481    FcFontSet	    *ret;
482    FcFontSet	    *s;
483    int		    f;
484    int		    set;
485    FcListHashTable table;
486    int		    i;
487    FcListBucket    *bucket;
488    int             destroy_os = 0;
489
490    if (!config)
491    {
492	if (!FcInitBringUptoDate ())
493	    goto bail0;
494
495	config = FcConfigGetCurrent ();
496	if (!config)
497	    goto bail0;
498    }
499    FcListHashTableInit (&table);
500
501    if (!os)
502    {
503	os = FcObjectGetSet ();
504	destroy_os = 1;
505    }
506
507    /*
508     * Walk all available fonts adding those that
509     * match to the hash table
510     */
511    for (set = 0; set < nsets; set++)
512    {
513	s = sets[set];
514	if (!s)
515	    continue;
516	for (f = 0; f < s->nfont; f++)
517	    if (FcListPatternMatchAny (p,		/* pattern */
518				       s->fonts[f]))	/* font */
519	    {
520		FcChar8 *lang;
521
522		if (FcPatternObjectGetString (p, FC_NAMELANG_OBJECT, 0, &lang) != FcResultMatch)
523		{
524			lang = FcGetDefaultLang ();
525		}
526		if (!FcListAppend (&table, s->fonts[f], os, lang))
527		    goto bail1;
528	    }
529    }
530#if 0
531    {
532	int	max = 0;
533	int	full = 0;
534	int	ents = 0;
535	int	len;
536	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
537	{
538	    if ((bucket = table.buckets[i]))
539	    {
540		len = 0;
541		for (; bucket; bucket = bucket->next)
542		{
543		    ents++;
544		    len++;
545		}
546		if (len > max)
547		    max = len;
548		full++;
549	    }
550	}
551	printf ("used: %d max: %d avg: %g\n", full, max,
552		(double) ents / FC_LIST_HASH_SIZE);
553    }
554#endif
555    /*
556     * Walk the hash table and build
557     * a font set
558     */
559    ret = FcFontSetCreate ();
560    if (!ret)
561	goto bail0;
562    for (i = 0; i < FC_LIST_HASH_SIZE; i++)
563	while ((bucket = table.buckets[i]))
564	{
565	    if (!FcFontSetAdd (ret, bucket->pattern))
566		goto bail2;
567	    table.buckets[i] = bucket->next;
568	    free (bucket);
569	}
570
571    return ret;
572
573bail2:
574    FcFontSetDestroy (ret);
575bail1:
576    FcListHashTableCleanup (&table);
577bail0:
578    if (destroy_os)
579	FcObjectSetDestroy (os);
580    return 0;
581}
582
583FcFontSet *
584FcFontList (FcConfig	*config,
585	    FcPattern	*p,
586	    FcObjectSet *os)
587{
588    FcFontSet	*sets[2];
589    int		nsets;
590
591    if (!config)
592    {
593	if (!FcInitBringUptoDate ())
594	    return 0;
595
596	config = FcConfigGetCurrent ();
597	if (!config)
598	    return 0;
599    }
600    nsets = 0;
601    if (config->fonts[FcSetSystem])
602	sets[nsets++] = config->fonts[FcSetSystem];
603    if (config->fonts[FcSetApplication])
604	sets[nsets++] = config->fonts[FcSetApplication];
605    return FcFontSetList (config, sets, nsets, p, os);
606}
607#define __fclist__
608#include "fcaliastail.h"
609#undef __fclist__
610