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
28 FcObjectSet *
29 FcObjectSetCreate (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
42 FcBool
43 FcObjectSetAdd (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
90 void
91 FcObjectSetDestroy (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
108 FcObjectSet *
109 FcObjectSetVaBuild (const char *first, va_list va)
110 {
111 FcObjectSet *ret;
112
113 FcObjectSetVapBuild (ret, first, va);
114 return ret;
115 }
116
117 FcObjectSet *
118 FcObjectSetBuild (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 */
132 static FcBool
133 FcListValueListMatchAny (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
158 static FcBool
159 FcListValueListEqual (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
185 static FcBool
186 FcListPatternEqual (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
212 FcBool
213 FcListPatternMatchAny (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
244 static FcChar32
245 FcListMatrixHash (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
255 static FcChar32
256 FcListValueHash (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
285 static FcChar32
286 FcListValueListHash (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
298 static FcChar32
299 FcListPatternHash (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
315 typedef struct _FcListBucket {
316 struct _FcListBucket *next;
317 FcChar32 hash;
318 FcPattern *pattern;
319 } FcListBucket;
320
321 #define FC_LIST_HASH_SIZE 4099
322
323 typedef struct _FcListHashTable {
324 int entries;
325 FcListBucket *buckets[FC_LIST_HASH_SIZE];
326 } FcListHashTable;
327
328 static void
329 FcListHashTableInit (FcListHashTable *table)
330 {
331 table->entries = 0;
332 memset (table->buckets, '\0', sizeof (table->buckets));
333 }
334
335 static void
336 FcListHashTableCleanup (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
354 static int
355 FcGetDefaultObjectLangIndex (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
394 static FcBool
395 FcListAppend (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
469 bail2:
470 FcPatternDestroy (bucket->pattern);
471 bail1:
472 free (bucket);
473 bail0:
474 return FcFalse;
475 }
476
477 FcFontSet *
478 FcFontSetList (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
579 bail2:
580 FcFontSetDestroy (ret);
581 bail1:
582 FcListHashTableCleanup (&table);
583 FcConfigDestroy (config);
584 bail0:
585 if (destroy_os)
586 FcObjectSetDestroy (os);
587 return 0;
588 }
589
590 FcFontSet *
591 FcFontList (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__