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