fclist.c revision a6844aab 
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 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 * 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 *)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)
354		    return i;
355
356		if (res == FcLangDifferentCountry && idx < 0)
357		    idx = i;
358	    }
359	}
360    }
361
362    return (idx > 0) ? idx : 0;
363}
364
365static FcBool
366FcListAppend (FcListHashTable	*table,
367	      FcPattern		*font,
368	      FcObjectSet	*os)
369{
370    int		    o;
371    FcPatternElt    *e;
372    FcValueListPtr  v;
373    FcChar32	    hash;
374    FcListBucket    **prev, *bucket;
375    int             familyidx = -1;
376    int             fullnameidx = -1;
377    int             styleidx = -1;
378    int             defidx = 0;
379    int             idx;
380
381    hash = FcListPatternHash (font, os);
382    for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
383	 (bucket = *prev); prev = &(bucket->next))
384    {
385	if (bucket->hash == hash &&
386	    FcListPatternEqual (bucket->pattern, font, os))
387	    return FcTrue;
388    }
389    bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
390    if (!bucket)
391	goto bail0;
392    FcMemAlloc (FC_MEM_LISTBUCK, sizeof (FcListBucket));
393    bucket->next = 0;
394    bucket->hash = hash;
395    bucket->pattern = FcPatternCreate ();
396    if (!bucket->pattern)
397	goto bail1;
398
399    for (o = 0; o < os->nobject; o++)
400    {
401	if (!strcmp (os->objects[o], FC_FAMILY) || !strcmp (os->objects[o], FC_FAMILYLANG))
402	{
403	    if (familyidx < 0)
404		familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG_OBJECT);
405	    defidx = familyidx;
406	}
407	else if (!strcmp (os->objects[o], FC_FULLNAME) || !strcmp (os->objects[o], FC_FULLNAMELANG))
408	{
409	    if (fullnameidx < 0)
410		fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG_OBJECT);
411	    defidx = fullnameidx;
412	}
413	else if (!strcmp (os->objects[o], FC_STYLE) || !strcmp (os->objects[o], FC_STYLELANG))
414	{
415	    if (styleidx < 0)
416		styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG_OBJECT);
417	    defidx = styleidx;
418	}
419	else
420	    defidx = 0;
421
422	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[o]));
423	if (e)
424	{
425	    for (v = FcPatternEltValues(e), idx = 0; v;
426		 v = FcValueListNext(v), ++idx)
427	    {
428		if (!FcPatternAdd (bucket->pattern,
429				   os->objects[o],
430				   FcValueCanonicalize(&v->value), defidx != idx))
431		    goto bail2;
432	    }
433	}
434    }
435    *prev = bucket;
436    ++table->entries;
437
438    return FcTrue;
439
440bail2:
441    FcPatternDestroy (bucket->pattern);
442bail1:
443    FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
444    free (bucket);
445bail0:
446    return FcFalse;
447}
448
449FcFontSet *
450FcFontSetList (FcConfig	    *config,
451	       FcFontSet    **sets,
452	       int	    nsets,
453	       FcPattern    *p,
454	       FcObjectSet  *os)
455{
456    FcFontSet	    *ret;
457    FcFontSet	    *s;
458    int		    f;
459    int		    set;
460    FcListHashTable table;
461    int		    i;
462    FcListBucket    *bucket;
463    int             destroy_os = 0;
464
465    if (!config)
466    {
467	if (!FcInitBringUptoDate ())
468	    goto bail0;
469
470	config = FcConfigGetCurrent ();
471	if (!config)
472	    goto bail0;
473    }
474    FcListHashTableInit (&table);
475
476    if (!os)
477    {
478	os = FcObjectGetSet ();
479	destroy_os = 1;
480    }
481
482    /*
483     * Walk all available fonts adding those that
484     * match to the hash table
485     */
486    for (set = 0; set < nsets; set++)
487    {
488	s = sets[set];
489	if (!s)
490	    continue;
491	for (f = 0; f < s->nfont; f++)
492	    if (FcListPatternMatchAny (p,		/* pattern */
493				       s->fonts[f]))	/* font */
494		if (!FcListAppend (&table, s->fonts[f], os))
495		    goto bail1;
496    }
497#if 0
498    {
499	int	max = 0;
500	int	full = 0;
501	int	ents = 0;
502	int	len;
503	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
504	{
505	    if ((bucket = table.buckets[i]))
506	    {
507		len = 0;
508		for (; bucket; bucket = bucket->next)
509		{
510		    ents++;
511		    len++;
512		}
513		if (len > max)
514		    max = len;
515		full++;
516	    }
517	}
518	printf ("used: %d max: %d avg: %g\n", full, max,
519		(double) ents / FC_LIST_HASH_SIZE);
520    }
521#endif
522    /*
523     * Walk the hash table and build
524     * a font set
525     */
526    ret = FcFontSetCreate ();
527    if (!ret)
528	goto bail0;
529    for (i = 0; i < FC_LIST_HASH_SIZE; i++)
530	while ((bucket = table.buckets[i]))
531	{
532	    if (!FcFontSetAdd (ret, bucket->pattern))
533		goto bail2;
534	    table.buckets[i] = bucket->next;
535	    FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
536	    free (bucket);
537	}
538
539    return ret;
540
541bail2:
542    FcFontSetDestroy (ret);
543bail1:
544    FcListHashTableCleanup (&table);
545bail0:
546    if (destroy_os)
547	FcObjectSetDestroy (os);
548    return 0;
549}
550
551FcFontSet *
552FcFontList (FcConfig	*config,
553	    FcPattern	*p,
554	    FcObjectSet *os)
555{
556    FcFontSet	*sets[2];
557    int		nsets;
558
559    if (!config)
560    {
561	if (!FcInitBringUptoDate ())
562	    return 0;
563
564	config = FcConfigGetCurrent ();
565	if (!config)
566	    return 0;
567    }
568    nsets = 0;
569    if (config->fonts[FcSetSystem])
570	sets[nsets++] = config->fonts[FcSetSystem];
571    if (config->fonts[FcSetApplication])
572	sets[nsets++] = config->fonts[FcSetApplication];
573    return FcFontSetList (config, sets, nsets, p, os);
574}
575#define __fclist__
576#include "fcaliastail.h"
577#undef __fclist__
578