src/fclist.c

   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__