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 (long) v.u.f;
 274     case FcTypeLangSet:
 275         return FcLangSetHash (v.u.l);
 276     }
 277     return 0;
 278 }
 279
 280 static FcChar32
 281 FcListValueListHash (FcValueListPtr list)
 282 {
 283     FcChar32    h = 0;
 284
 285     while (list != NULL)
 286     {
 287         h = h ^ FcListValueHash (&list->value);
 288         list = FcValueListNext(list);
 289     }
 290     return h;
 291 }
 292
 293 static FcChar32
 294 FcListPatternHash (FcPattern    *font,
 295                    FcObjectSet  *os)
 296 {
 297     int             n;
 298     FcPatternElt    *e;
 299     FcChar32        h = 0;
 300
 301     for (n = 0; n < os->nobject; n++)
 302     {
 303         e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[n]));
 304         if (e)
 305             h = h ^ FcListValueListHash (FcPatternEltValues(e));
 306     }
 307     return h;
 308 }
 309
 310 typedef struct _FcListBucket {
 311     struct _FcListBucket    *next;
 312     FcChar32                hash;
 313     FcPattern               *pattern;
 314 } FcListBucket;
 315
 316 #define FC_LIST_HASH_SIZE   4099
 317
 318 typedef struct _FcListHashTable {
 319     int             entries;
 320     FcListBucket    *buckets[FC_LIST_HASH_SIZE];
 321 } FcListHashTable;
 322
 323 static void
 324 FcListHashTableInit (FcListHashTable *table)
 325 {
 326     table->entries = 0;
 327     memset (table->buckets, '\0', sizeof (table->buckets));
 328 }
 329
 330 static void
 331 FcListHashTableCleanup (FcListHashTable *table)
 332 {
 333     int i;
 334     FcListBucket    *bucket, *next;
 335
 336     for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 337     {
 338         for (bucket = table->buckets[i]; bucket; bucket = next)
 339         {
 340             next = bucket->next;
 341             FcPatternDestroy (bucket->pattern);
 342             free (bucket);
 343         }
 344         table->buckets[i] = 0;
 345     }
 346     table->entries = 0;
 347 }
 348
 349 static int
 350 FcGetDefaultObjectLangIndex (FcPattern *font, FcObject object, const FcChar8 *lang)
 351 {
 352     FcPatternElt   *e = FcPatternObjectFindElt (font, object);
 353     FcValueListPtr  v;
 354     FcValue         value;
 355     int             idx = -1;
 356     int             defidx = -1;
 357     int             i;
 358
 359     if (e)
 360     {
 361         for (v = FcPatternEltValues(e), i = 0; v; v = FcValueListNext(v), ++i)
 362         {
 363             value = FcValueCanonicalize (&v->value);
 364
 365             if (value.type == FcTypeString)
 366             {
 367                 FcLangResult res = FcLangCompare (value.u.s, lang);
 368                 if (res == FcLangEqual)
 369                     return i;
 370
 371                 if (res == FcLangDifferentCountry && idx < 0)
 372                     idx = i;
 373                 if (defidx < 0)
 374                 {
 375                     /* workaround for fonts that has non-English value
 376                      * at the head of values.
 377                      */
 378                     res = FcLangCompare (value.u.s, (FcChar8 *)"en");
 379                     if (res == FcLangEqual)
 380                         defidx = i;
 381                 }
 382             }
 383         }
 384     }
 385
 386     return (idx > 0) ? idx : (defidx > 0) ? defidx : 0;
 387 }
 388
 389 static FcBool
 390 FcListAppend (FcListHashTable   *table,
 391               FcPattern         *font,
 392               FcObjectSet       *os,
 393               const FcChar8     *lang)
 394 {
 395     int             o;
 396     FcPatternElt    *e;
 397     FcValueListPtr  v;
 398     FcChar32        hash;
 399     FcListBucket    **prev, *bucket;
 400     int             familyidx = -1;
 401     int             fullnameidx = -1;
 402     int             styleidx = -1;
 403     int             defidx = 0;
 404     int             idx;
 405
 406     hash = FcListPatternHash (font, os);
 407     for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
 408          (bucket = *prev); prev = &(bucket->next))
 409     {
 410         if (bucket->hash == hash &&
 411             FcListPatternEqual (bucket->pattern, font, os))
 412             return FcTrue;
 413     }
 414     bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
 415     if (!bucket)
 416         goto bail0;
 417     bucket->next = 0;
 418     bucket->hash = hash;
 419     bucket->pattern = FcPatternCreate ();
 420     if (!bucket->pattern)
 421         goto bail1;
 422
 423     for (o = 0; o < os->nobject; o++)
 424     {
 425         if (!strcmp (os->objects[o], FC_FAMILY) || !strcmp (os->objects[o], FC_FAMILYLANG))
 426         {
 427             if (familyidx < 0)
 428                 familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG_OBJECT, lang);
 429             defidx = familyidx;
 430         }
 431         else if (!strcmp (os->objects[o], FC_FULLNAME) || !strcmp (os->objects[o], FC_FULLNAMELANG))
 432         {
 433             if (fullnameidx < 0)
 434                 fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG_OBJECT, lang);
 435             defidx = fullnameidx;
 436         }
 437         else if (!strcmp (os->objects[o], FC_STYLE) || !strcmp (os->objects[o], FC_STYLELANG))
 438         {
 439             if (styleidx < 0)
 440                 styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG_OBJECT, lang);
 441             defidx = styleidx;
 442         }
 443         else
 444             defidx = 0;
 445
 446         e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[o]));
 447         if (e)
 448         {
 449             for (v = FcPatternEltValues(e), idx = 0; v;
 450                  v = FcValueListNext(v), ++idx)
 451             {
 452                 if (!FcPatternAdd (bucket->pattern,
 453                                    os->objects[o],
 454                                    FcValueCanonicalize(&v->value), defidx != idx))
 455                     goto bail2;
 456             }
 457         }
 458     }
 459     *prev = bucket;
 460     ++table->entries;
 461
 462     return FcTrue;
 463
 464 bail2:
 465     FcPatternDestroy (bucket->pattern);
 466 bail1:
 467     free (bucket);
 468 bail0:
 469     return FcFalse;
 470 }
 471
 472 FcFontSet *
 473 FcFontSetList (FcConfig     *config,
 474                FcFontSet    **sets,
 475                int          nsets,
 476                FcPattern    *p,
 477                FcObjectSet  *os)
 478 {
 479     FcFontSet       *ret;
 480     FcFontSet       *s;
 481     int             f;
 482     int             set;
 483     FcListHashTable table;
 484     int             i;
 485     FcListBucket    *bucket;
 486     int             destroy_os = 0;
 487
 488     if (!config)
 489     {
 490         if (!FcInitBringUptoDate ())
 491             goto bail0;
 492
 493         config = FcConfigGetCurrent ();
 494         if (!config)
 495             goto bail0;
 496     }
 497     FcListHashTableInit (&table);
 498
 499     if (!os)
 500     {
 501         os = FcObjectGetSet ();
 502         destroy_os = 1;
 503     }
 504
 505     /*
 506      * Walk all available fonts adding those that
 507      * match to the hash table
 508      */
 509     for (set = 0; set < nsets; set++)
 510     {
 511         s = sets[set];
 512         if (!s)
 513             continue;
 514         for (f = 0; f < s->nfont; f++)
 515             if (FcListPatternMatchAny (p,               /* pattern */
 516                                        s->fonts[f]))    /* font */
 517             {
 518                 FcChar8 *lang;
 519
 520                 if (FcPatternObjectGetString (p, FC_NAMELANG_OBJECT, 0, &lang) != FcResultMatch)
 521                 {
 522                         lang = FcGetDefaultLang ();
 523                 }
 524                 if (!FcListAppend (&table, s->fonts[f], os, lang))
 525                     goto bail1;
 526             }
 527     }
 528 #if 0
 529     {
 530         int     max = 0;
 531         int     full = 0;
 532         int     ents = 0;
 533         int     len;
 534         for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 535         {
 536             if ((bucket = table.buckets[i]))
 537             {
 538                 len = 0;
 539                 for (; bucket; bucket = bucket->next)
 540                 {
 541                     ents++;
 542                     len++;
 543                 }
 544                 if (len > max)
 545                     max = len;
 546                 full++;
 547             }
 548         }
 549         printf ("used: %d max: %d avg: %g\n", full, max,
 550                 (double) ents / FC_LIST_HASH_SIZE);
 551     }
 552 #endif
 553     /*
 554      * Walk the hash table and build
 555      * a font set
 556      */
 557     ret = FcFontSetCreate ();
 558     if (!ret)
 559         goto bail0;
 560     for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 561         while ((bucket = table.buckets[i]))
 562         {
 563             if (!FcFontSetAdd (ret, bucket->pattern))
 564                 goto bail2;
 565             table.buckets[i] = bucket->next;
 566             free (bucket);
 567         }
 568
 569     return ret;
 570
 571 bail2:
 572     FcFontSetDestroy (ret);
 573 bail1:
 574     FcListHashTableCleanup (&table);
 575 bail0:
 576     if (destroy_os)
 577         FcObjectSetDestroy (os);
 578     return 0;
 579 }
 580
 581 FcFontSet *
 582 FcFontList (FcConfig    *config,
 583             FcPattern   *p,
 584             FcObjectSet *os)
 585 {
 586     FcFontSet   *sets[2];
 587     int         nsets;
 588
 589     if (!config)
 590     {
 591         if (!FcInitBringUptoDate ())
 592             return 0;
 593
 594         config = FcConfigGetCurrent ();
 595         if (!config)
 596             return 0;
 597     }
 598     nsets = 0;
 599     if (config->fonts[FcSetSystem])
 600         sets[nsets++] = config->fonts[FcSetSystem];
 601     if (config->fonts[FcSetApplication])
 602         sets[nsets++] = config->fonts[FcSetApplication];
 603     return FcFontSetList (config, sets, nsets, p, os);
 604 }
 605 #define __fclist__
 606 #include "fcaliastail.h"
 607 #undef __fclist__