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