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