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 Keith Packard not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  Keith Packard makes 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  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  18  * EVENT SHALL KEITH PACKARD 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     FcMemAlloc (FC_MEM_OBJECTSET, sizeof (FcObjectSet));
  37     os->nobject = 0;
  38     os->sobject = 0;
  39     os->objects = 0;
  40     return os;
  41 }
  42
  43 FcBool
  44 FcObjectSetAdd (FcObjectSet *os, const char *object)
  45 {
  46     int         s;
  47     const char  **objects;
  48     int         high, low, mid, c;
  49
  50     if (os->nobject == os->sobject)
  51     {
  52         s = os->sobject + 4;
  53         if (os->objects)
  54             objects = (const char **) realloc ((void *) os->objects,
  55                                                s * sizeof (const char *));
  56         else
  57             objects = (const char **) malloc (s * sizeof (const char *));
  58         if (!objects)
  59             return FcFalse;
  60         if (os->sobject)
  61             FcMemFree (FC_MEM_OBJECTPTR, os->sobject * sizeof (const char *));
  62         FcMemAlloc (FC_MEM_OBJECTPTR, s * sizeof (const char *));
  63         os->objects = objects;
  64         os->sobject = s;
  65     }
  66     high = os->nobject - 1;
  67     low = 0;
  68     mid = 0;
  69     c = 1;
  70     object = (char *)FcStrStaticName ((FcChar8 *)object);
  71     while (low <= high)
  72     {
  73         mid = (low + high) >> 1;
  74         c = os->objects[mid] - object;
  75         if (c == 0)
  76             return FcTrue;
  77         if (c < 0)
  78             low = mid + 1;
  79         else
  80             high = mid - 1;
  81     }
  82     if (c < 0)
  83         mid++;
  84     memmove (os->objects + mid + 1, os->objects + mid,
  85              (os->nobject - mid) * sizeof (const char *));
  86     os->objects[mid] = object;
  87     os->nobject++;
  88     return FcTrue;
  89 }
  90
  91 void
  92 FcObjectSetDestroy (FcObjectSet *os)
  93 {
  94     if (os->objects)
  95     {
  96         FcMemFree (FC_MEM_OBJECTPTR, os->sobject * sizeof (const char *));
  97         free ((void *) os->objects);
  98     }
  99     FcMemFree (FC_MEM_OBJECTSET, sizeof (FcObjectSet));
 100     free (os);
 101 }
 102
 103 FcObjectSet *
 104 FcObjectSetVaBuild (const char *first, va_list va)
 105 {
 106     FcObjectSet    *ret;
 107
 108     FcObjectSetVapBuild (ret, first, va);
 109     return ret;
 110 }
 111
 112 FcObjectSet *
 113 FcObjectSetBuild (const char *first, ...)
 114 {
 115     va_list         va;
 116     FcObjectSet    *os;
 117
 118     va_start (va, first);
 119     FcObjectSetVapBuild (os, first, va);
 120     va_end (va);
 121     return os;
 122 }
 123
 124 /*
 125  * Font must have a containing value for every value in the pattern
 126  */
 127 static FcBool
 128 FcListValueListMatchAny (FcValueListPtr patOrig,            /* pattern */
 129                          FcValueListPtr fntOrig)            /* font */
 130 {
 131     FcValueListPtr       pat, fnt;
 132
 133     for (pat = patOrig; pat != NULL; pat = FcValueListNext(pat))
 134     {
 135         for (fnt = fntOrig; fnt != NULL; fnt = FcValueListNext(fnt))
 136         {
 137             /*
 138              * make sure the font 'contains' the pattern.
 139              * (OpListing is OpContains except for strings
 140              *  where it requires an exact match)
 141              */
 142             if (FcConfigCompareValue (&fnt->value,
 143                                       FcOpListing,
 144                                       &pat->value))
 145                 break;
 146         }
 147         if (fnt == NULL)
 148             return FcFalse;
 149     }
 150     return FcTrue;
 151 }
 152
 153 static FcBool
 154 FcListValueListEqual (FcValueListPtr v1orig,
 155                       FcValueListPtr v2orig)
 156 {
 157     FcValueListPtr          v1, v2;
 158
 159     for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext(v1))
 160     {
 161         for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext(v2))
 162             if (FcValueEqual (FcValueCanonicalize(&(v1)->value),
 163                               FcValueCanonicalize(&(v2)->value)))
 164                 break;
 165         if (v2 == NULL)
 166             return FcFalse;
 167     }
 168     for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext(v2))
 169     {
 170         for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext(v1))
 171             if (FcValueEqual (FcValueCanonicalize(&v1->value),
 172                               FcValueCanonicalize(&v2->value)))
 173                 break;
 174         if (v1 == NULL)
 175             return FcFalse;
 176     }
 177     return FcTrue;
 178 }
 179
 180 static FcBool
 181 FcListPatternEqual (FcPattern   *p1,
 182                     FcPattern   *p2,
 183                     FcObjectSet *os)
 184 {
 185     int             i;
 186     FcPatternElt    *e1, *e2;
 187
 188     for (i = 0; i < os->nobject; i++)
 189     {
 190         e1 = FcPatternObjectFindElt (p1, FcObjectFromName (os->objects[i]));
 191         e2 = FcPatternObjectFindElt (p2, FcObjectFromName (os->objects[i]));
 192         if (!e1 && !e2)
 193             continue;
 194         if (!e1 || !e2)
 195             return FcFalse;
 196         if (!FcListValueListEqual (FcPatternEltValues(e1),
 197                                    FcPatternEltValues(e2)))
 198             return FcFalse;
 199     }
 200     return FcTrue;
 201 }
 202
 203 /*
 204  * FcTrue iff all objects in "p" match "font"
 205  */
 206
 207 FcBool
 208 FcListPatternMatchAny (const FcPattern *p,
 209                        const FcPattern *font)
 210 {
 211     int             i;
 212
 213     for (i = 0; i < p->num; i++)
 214     {
 215         FcPatternElt    *pe = &FcPatternElts(p)[i];
 216         FcPatternElt    *fe = FcPatternObjectFindElt (font, pe->object);
 217         if (!fe)
 218             return FcFalse;
 219         if (!FcListValueListMatchAny (FcPatternEltValues(pe),    /* pat elts */
 220                                       FcPatternEltValues(fe)))   /* font elts */
 221             return FcFalse;
 222     }
 223     return FcTrue;
 224 }
 225
 226 static FcChar32
 227 FcListMatrixHash (const FcMatrix *m)
 228 {
 229     int     xx = (int) (m->xx * 100),
 230             xy = (int) (m->xy * 100),
 231             yx = (int) (m->yx * 100),
 232             yy = (int) (m->yy * 100);
 233
 234     return ((FcChar32) xx) ^ ((FcChar32) xy) ^ ((FcChar32) yx) ^ ((FcChar32) yy);
 235 }
 236
 237 static FcChar32
 238 FcListValueHash (FcValue    *value)
 239 {
 240     FcValue v = FcValueCanonicalize(value);
 241     switch (v.type) {
 242     case FcTypeVoid:
 243         return 0;
 244     case FcTypeInteger:
 245         return (FcChar32) v.u.i;
 246     case FcTypeDouble:
 247         return (FcChar32) (int) v.u.d;
 248     case FcTypeString:
 249         return FcStrHashIgnoreCase (v.u.s);
 250     case FcTypeBool:
 251         return (FcChar32) v.u.b;
 252     case FcTypeMatrix:
 253         return FcListMatrixHash (v.u.m);
 254     case FcTypeCharSet:
 255         return FcCharSetCount (v.u.c);
 256     case FcTypeFTFace:
 257         return (long) v.u.f;
 258     case FcTypeLangSet:
 259         return FcLangSetHash (v.u.l);
 260     }
 261     return 0;
 262 }
 263
 264 static FcChar32
 265 FcListValueListHash (FcValueListPtr list)
 266 {
 267     FcChar32    h = 0;
 268
 269     while (list != NULL)
 270     {
 271         h = h ^ FcListValueHash (&list->value);
 272         list = FcValueListNext(list);
 273     }
 274     return h;
 275 }
 276
 277 static FcChar32
 278 FcListPatternHash (FcPattern    *font,
 279                    FcObjectSet  *os)
 280 {
 281     int             n;
 282     FcPatternElt    *e;
 283     FcChar32        h = 0;
 284
 285     for (n = 0; n < os->nobject; n++)
 286     {
 287         e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[n]));
 288         if (e)
 289             h = h ^ FcListValueListHash (FcPatternEltValues(e));
 290     }
 291     return h;
 292 }
 293
 294 typedef struct _FcListBucket {
 295     struct _FcListBucket    *next;
 296     FcChar32                hash;
 297     FcPattern               *pattern;
 298 } FcListBucket;
 299
 300 #define FC_LIST_HASH_SIZE   4099
 301
 302 typedef struct _FcListHashTable {
 303     int             entries;
 304     FcListBucket    *buckets[FC_LIST_HASH_SIZE];
 305 } FcListHashTable;
 306
 307 static void
 308 FcListHashTableInit (FcListHashTable *table)
 309 {
 310     table->entries = 0;
 311     memset (table->buckets, '\0', sizeof (table->buckets));
 312 }
 313
 314 static void
 315 FcListHashTableCleanup (FcListHashTable *table)
 316 {
 317     int i;
 318     FcListBucket    *bucket, *next;
 319
 320     for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 321     {
 322         for (bucket = table->buckets[i]; bucket; bucket = next)
 323         {
 324             next = bucket->next;
 325             FcPatternDestroy (bucket->pattern);
 326             FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 327             free (bucket);
 328         }
 329         table->buckets[i] = 0;
 330     }
 331     table->entries = 0;
 332 }
 333
 334 static int
 335 FcGetDefaultObjectLangIndex (FcPattern *font, FcObject object)
 336 {
 337     FcChar8        *lang = FcGetDefaultLang ();
 338     FcPatternElt   *e = FcPatternObjectFindElt (font, object);
 339     FcValueListPtr  v;
 340     FcValue         value;
 341     int             idx = -1;
 342     int             i;
 343
 344     if (e)
 345     {
 346         for (v = FcPatternEltValues(e), i = 0; v; v = FcValueListNext(v), ++i)
 347         {
 348             value = FcValueCanonicalize (&v->value);
 349
 350             if (value.type == FcTypeString)
 351             {
 352                 FcLangResult res = FcLangCompare (value.u.s, lang);
 353                 if (res == FcLangEqual || (res == FcLangDifferentCountry && idx < 0))
 354                     idx = i;
 355             }
 356         }
 357     }
 358
 359     return (idx > 0) ? idx : 0;
 360 }
 361
 362 static FcBool
 363 FcListAppend (FcListHashTable   *table,
 364               FcPattern         *font,
 365               FcObjectSet       *os)
 366 {
 367     int             o;
 368     FcPatternElt    *e;
 369     FcValueListPtr  v;
 370     FcChar32        hash;
 371     FcListBucket    **prev, *bucket;
 372     int             familyidx = -1;
 373     int             fullnameidx = -1;
 374     int             styleidx = -1;
 375     int             defidx = 0;
 376     int             idx;
 377
 378     hash = FcListPatternHash (font, os);
 379     for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
 380          (bucket = *prev); prev = &(bucket->next))
 381     {
 382         if (bucket->hash == hash &&
 383             FcListPatternEqual (bucket->pattern, font, os))
 384             return FcTrue;
 385     }
 386     bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
 387     if (!bucket)
 388         goto bail0;
 389     FcMemAlloc (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 390     bucket->next = 0;
 391     bucket->hash = hash;
 392     bucket->pattern = FcPatternCreate ();
 393     if (!bucket->pattern)
 394         goto bail1;
 395
 396     for (o = 0; o < os->nobject; o++)
 397     {
 398         if (!strcmp (os->objects[o], FC_FAMILY) || !strcmp (os->objects[o], FC_FAMILYLANG))
 399         {
 400             if (familyidx < 0)
 401                 familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG_OBJECT);
 402             defidx = familyidx;
 403         }
 404         else if (!strcmp (os->objects[o], FC_FULLNAME) || !strcmp (os->objects[o], FC_FULLNAMELANG))
 405         {
 406             if (fullnameidx < 0)
 407                 fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG_OBJECT);
 408             defidx = fullnameidx;
 409         }
 410         else if (!strcmp (os->objects[o], FC_STYLE) || !strcmp (os->objects[o], FC_STYLELANG))
 411         {
 412             if (styleidx < 0)
 413                 styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG_OBJECT);
 414             defidx = styleidx;
 415         }
 416         else
 417             defidx = 0;
 418
 419         e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[o]));
 420         if (e)
 421         {
 422             for (v = FcPatternEltValues(e), idx = 0; v;
 423                  v = FcValueListNext(v), ++idx)
 424             {
 425                 if (!FcPatternAdd (bucket->pattern,
 426                                    os->objects[o],
 427                                    FcValueCanonicalize(&v->value), defidx != idx))
 428                     goto bail2;
 429             }
 430         }
 431     }
 432     *prev = bucket;
 433     ++table->entries;
 434
 435     return FcTrue;
 436
 437 bail2:
 438     FcPatternDestroy (bucket->pattern);
 439 bail1:
 440     FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 441     free (bucket);
 442 bail0:
 443     return FcFalse;
 444 }
 445
 446 FcFontSet *
 447 FcFontSetList (FcConfig     *config,
 448                FcFontSet    **sets,
 449                int          nsets,
 450                FcPattern    *p,
 451                FcObjectSet  *os)
 452 {
 453     FcFontSet       *ret;
 454     FcFontSet       *s;
 455     int             f;
 456     int             set;
 457     FcListHashTable table;
 458     int             i;
 459     FcListBucket    *bucket;
 460     int             destroy_os = 0;
 461
 462     if (!config)
 463     {
 464         if (!FcInitBringUptoDate ())
 465             goto bail0;
 466
 467         config = FcConfigGetCurrent ();
 468         if (!config)
 469             goto bail0;
 470     }
 471     FcListHashTableInit (&table);
 472
 473     if (!os)
 474     {
 475         os = FcObjectGetSet ();
 476         destroy_os = 1;
 477     }
 478
 479     /*
 480      * Walk all available fonts adding those that
 481      * match to the hash table
 482      */
 483     for (set = 0; set < nsets; set++)
 484     {
 485         s = sets[set];
 486         if (!s)
 487             continue;
 488         for (f = 0; f < s->nfont; f++)
 489             if (FcListPatternMatchAny (p,               /* pattern */
 490                                        s->fonts[f]))    /* font */
 491                 if (!FcListAppend (&table, s->fonts[f], os))
 492                     goto bail1;
 493     }
 494 #if 0
 495     {
 496         int     max = 0;
 497         int     full = 0;
 498         int     ents = 0;
 499         int     len;
 500         for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 501         {
 502             if ((bucket = table.buckets[i]))
 503             {
 504                 len = 0;
 505                 for (; bucket; bucket = bucket->next)
 506                 {
 507                     ents++;
 508                     len++;
 509                 }
 510                 if (len > max)
 511                     max = len;
 512                 full++;
 513             }
 514         }
 515         printf ("used: %d max: %d avg: %g\n", full, max,
 516                 (double) ents / FC_LIST_HASH_SIZE);
 517     }
 518 #endif
 519     /*
 520      * Walk the hash table and build
 521      * a font set
 522      */
 523     ret = FcFontSetCreate ();
 524     if (!ret)
 525         goto bail0;
 526     for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 527         while ((bucket = table.buckets[i]))
 528         {
 529             if (!FcFontSetAdd (ret, bucket->pattern))
 530                 goto bail2;
 531             table.buckets[i] = bucket->next;
 532             FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 533             free (bucket);
 534         }
 535
 536     return ret;
 537
 538 bail2:
 539     FcFontSetDestroy (ret);
 540 bail1:
 541     FcListHashTableCleanup (&table);
 542 bail0:
 543     if (destroy_os)
 544         FcObjectSetDestroy (os);
 545     return 0;
 546 }
 547
 548 FcFontSet *
 549 FcFontList (FcConfig    *config,
 550             FcPattern   *p,
 551             FcObjectSet *os)
 552 {
 553     FcFontSet   *sets[2];
 554     int         nsets;
 555
 556     if (!config)
 557     {
 558         if (!FcInitBringUptoDate ())
 559             return 0;
 560
 561         config = FcConfigGetCurrent ();
 562         if (!config)
 563             return 0;
 564     }
 565     nsets = 0;
 566     if (config->fonts[FcSetSystem])
 567         sets[nsets++] = config->fonts[FcSetSystem];
 568     if (config->fonts[FcSetApplication])
 569         sets[nsets++] = config->fonts[FcSetApplication];
 570     return FcFontSetList (config, sets, nsets, p, os);
 571 }
 572 #define __fclist__
 573 #include "fcaliastail.h"
 574 #undef __fclist__