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