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