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     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)
 354                     return i;
 355
 356                 if (res == FcLangDifferentCountry && idx < 0)
 357                     idx = i;
 358             }
 359         }
 360     }
 361
 362     return (idx > 0) ? idx : 0;
 363 }
 364
 365 static FcBool
 366 FcListAppend (FcListHashTable   *table,
 367               FcPattern         *font,
 368               FcObjectSet       *os)
 369 {
 370     int             o;
 371     FcPatternElt    *e;
 372     FcValueListPtr  v;
 373     FcChar32        hash;
 374     FcListBucket    **prev, *bucket;
 375     int             familyidx = -1;
 376     int             fullnameidx = -1;
 377     int             styleidx = -1;
 378     int             defidx = 0;
 379     int             idx;
 380
 381     hash = FcListPatternHash (font, os);
 382     for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
 383          (bucket = *prev); prev = &(bucket->next))
 384     {
 385         if (bucket->hash == hash &&
 386             FcListPatternEqual (bucket->pattern, font, os))
 387             return FcTrue;
 388     }
 389     bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
 390     if (!bucket)
 391         goto bail0;
 392     FcMemAlloc (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 393     bucket->next = 0;
 394     bucket->hash = hash;
 395     bucket->pattern = FcPatternCreate ();
 396     if (!bucket->pattern)
 397         goto bail1;
 398
 399     for (o = 0; o < os->nobject; o++)
 400     {
 401         if (!strcmp (os->objects[o], FC_FAMILY) || !strcmp (os->objects[o], FC_FAMILYLANG))
 402         {
 403             if (familyidx < 0)
 404                 familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG_OBJECT);
 405             defidx = familyidx;
 406         }
 407         else if (!strcmp (os->objects[o], FC_FULLNAME) || !strcmp (os->objects[o], FC_FULLNAMELANG))
 408         {
 409             if (fullnameidx < 0)
 410                 fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG_OBJECT);
 411             defidx = fullnameidx;
 412         }
 413         else if (!strcmp (os->objects[o], FC_STYLE) || !strcmp (os->objects[o], FC_STYLELANG))
 414         {
 415             if (styleidx < 0)
 416                 styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG_OBJECT);
 417             defidx = styleidx;
 418         }
 419         else
 420             defidx = 0;
 421
 422         e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[o]));
 423         if (e)
 424         {
 425             for (v = FcPatternEltValues(e), idx = 0; v;
 426                  v = FcValueListNext(v), ++idx)
 427             {
 428                 if (!FcPatternAdd (bucket->pattern,
 429                                    os->objects[o],
 430                                    FcValueCanonicalize(&v->value), defidx != idx))
 431                     goto bail2;
 432             }
 433         }
 434     }
 435     *prev = bucket;
 436     ++table->entries;
 437
 438     return FcTrue;
 439
 440 bail2:
 441     FcPatternDestroy (bucket->pattern);
 442 bail1:
 443     FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 444     free (bucket);
 445 bail0:
 446     return FcFalse;
 447 }
 448
 449 FcFontSet *
 450 FcFontSetList (FcConfig     *config,
 451                FcFontSet    **sets,
 452                int          nsets,
 453                FcPattern    *p,
 454                FcObjectSet  *os)
 455 {
 456     FcFontSet       *ret;
 457     FcFontSet       *s;
 458     int             f;
 459     int             set;
 460     FcListHashTable table;
 461     int             i;
 462     FcListBucket    *bucket;
 463     int             destroy_os = 0;
 464
 465     if (!config)
 466     {
 467         if (!FcInitBringUptoDate ())
 468             goto bail0;
 469
 470         config = FcConfigGetCurrent ();
 471         if (!config)
 472             goto bail0;
 473     }
 474     FcListHashTableInit (&table);
 475
 476     if (!os)
 477     {
 478         os = FcObjectGetSet ();
 479         destroy_os = 1;
 480     }
 481
 482     /*
 483      * Walk all available fonts adding those that
 484      * match to the hash table
 485      */
 486     for (set = 0; set < nsets; set++)
 487     {
 488         s = sets[set];
 489         if (!s)
 490             continue;
 491         for (f = 0; f < s->nfont; f++)
 492             if (FcListPatternMatchAny (p,               /* pattern */
 493                                        s->fonts[f]))    /* font */
 494                 if (!FcListAppend (&table, s->fonts[f], os))
 495                     goto bail1;
 496     }
 497 #if 0
 498     {
 499         int     max = 0;
 500         int     full = 0;
 501         int     ents = 0;
 502         int     len;
 503         for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 504         {
 505             if ((bucket = table.buckets[i]))
 506             {
 507                 len = 0;
 508                 for (; bucket; bucket = bucket->next)
 509                 {
 510                     ents++;
 511                     len++;
 512                 }
 513                 if (len > max)
 514                     max = len;
 515                 full++;
 516             }
 517         }
 518         printf ("used: %d max: %d avg: %g\n", full, max,
 519                 (double) ents / FC_LIST_HASH_SIZE);
 520     }
 521 #endif
 522     /*
 523      * Walk the hash table and build
 524      * a font set
 525      */
 526     ret = FcFontSetCreate ();
 527     if (!ret)
 528         goto bail0;
 529     for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 530         while ((bucket = table.buckets[i]))
 531         {
 532             if (!FcFontSetAdd (ret, bucket->pattern))
 533                 goto bail2;
 534             table.buckets[i] = bucket->next;
 535             FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 536             free (bucket);
 537         }
 538
 539     return ret;
 540
 541 bail2:
 542     FcFontSetDestroy (ret);
 543 bail1:
 544     FcListHashTableCleanup (&table);
 545 bail0:
 546     if (destroy_os)
 547         FcObjectSetDestroy (os);
 548     return 0;
 549 }
 550
 551 FcFontSet *
 552 FcFontList (FcConfig    *config,
 553             FcPattern   *p,
 554             FcObjectSet *os)
 555 {
 556     FcFontSet   *sets[2];
 557     int         nsets;
 558
 559     if (!config)
 560     {
 561         if (!FcInitBringUptoDate ())
 562             return 0;
 563
 564         config = FcConfigGetCurrent ();
 565         if (!config)
 566             return 0;
 567     }
 568     nsets = 0;
 569     if (config->fonts[FcSetSystem])
 570         sets[nsets++] = config->fonts[FcSetSystem];
 571     if (config->fonts[FcSetApplication])
 572         sets[nsets++] = config->fonts[FcSetApplication];
 573     return FcFontSetList (config, sets, nsets, p, os);
 574 }
 575 #define __fclist__
 576 #include "fcaliastail.h"
 577 #undef __fclist__