src/fclist.c

   1 /*
   2  * $RCSId: xc/lib/fontconfig/src/fclist.c,v 1.11tsi Exp $
   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; FcValueListPtrU(pat);
 134          pat = FcValueListPtrU(pat)->next)
 135     {
 136         for (fnt = fntOrig; FcValueListPtrU(fnt);
 137              fnt = FcValueListPtrU(fnt)->next)
 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 (&FcValueListPtrU(fnt)->value,
 145                                       FcOpListing,
 146                                       &FcValueListPtrU(pat)->value))
 147                 break;
 148         }
 149         if (!FcValueListPtrU(fnt))
 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; FcValueListPtrU(v1);
 162          v1 = FcValueListPtrU(v1)->next)
 163     {
 164         for (v2 = v2orig; FcValueListPtrU(v2);
 165              v2 = FcValueListPtrU(v2)->next)
 166             if (FcValueEqual (FcValueCanonicalize(&FcValueListPtrU(v1)->value),
 167                               FcValueCanonicalize(&FcValueListPtrU(v2)->value)))
 168                 break;
 169         if (!FcValueListPtrU(v2))
 170             return FcFalse;
 171     }
 172     for (v2 = v2orig; FcValueListPtrU(v2);
 173          v2 = FcValueListPtrU(v2)->next)
 174     {
 175         for (v1 = v1orig; FcValueListPtrU(v1);
 176              v1 = FcValueListPtrU(v1)->next)
 177             if (FcValueEqual (FcValueCanonicalize(&FcValueListPtrU(v1)->value),
 178                               FcValueCanonicalize(&FcValueListPtrU(v2)->value)))
 179                 break;
 180         if (!FcValueListPtrU(v1))
 181             return FcFalse;
 182     }
 183     return FcTrue;
 184 }
 185
 186 static FcBool
 187 FcListPatternEqual (FcPattern   *p1,
 188                     FcPattern   *p2,
 189                     FcObjectSet *os)
 190 {
 191     int             i;
 192     FcPatternElt    *e1, *e2;
 193
 194     for (i = 0; i < os->nobject; i++)
 195     {
 196         e1 = FcPatternFindElt (p1, os->objects[i]);
 197         e2 = FcPatternFindElt (p2, os->objects[i]);
 198         if (!e1 && !e2)
 199             continue;
 200         if (!e1 || !e2)
 201             return FcFalse;
 202         if (!FcListValueListEqual (e1->values, e2->values))
 203             return FcFalse;
 204     }
 205     return FcTrue;
 206 }
 207
 208 /*
 209  * FcTrue iff all objects in "p" match "font"
 210  */
 211
 212 FcBool
 213 FcListPatternMatchAny (const FcPattern *p,
 214                        const FcPattern *font)
 215 {
 216     int             i;
 217     FcPatternElt   *e;
 218
 219     for (i = 0; i < p->num; i++)
 220     {
 221         e = FcPatternFindElt (font,
 222                               FcObjectPtrU((FcPatternEltU(p->elts)+i)->object));
 223         if (!e)
 224             return FcFalse;
 225         if (!FcListValueListMatchAny ((FcPatternEltU(p->elts)+i)->values,    /* pat elts */
 226                                       e->values))           /* font elts */
 227             return FcFalse;
 228     }
 229     return FcTrue;
 230 }
 231
 232 static FcChar32
 233 FcListMatrixHash (const FcMatrix *m)
 234 {
 235     int     xx = (int) (m->xx * 100),
 236             xy = (int) (m->xy * 100),
 237             yx = (int) (m->yx * 100),
 238             yy = (int) (m->yy * 100);
 239
 240     return ((FcChar32) xx) ^ ((FcChar32) xy) ^ ((FcChar32) yx) ^ ((FcChar32) yy);
 241 }
 242
 243 static FcChar32
 244 FcListValueHash (FcValue    *value)
 245 {
 246     FcValue v = FcValueCanonicalize(value);
 247     switch (v.type) {
 248     case FcTypeVoid:
 249         return 0;
 250     case FcTypeInteger:
 251         return (FcChar32) v.u.i;
 252     case FcTypeDouble:
 253         return (FcChar32) (int) v.u.d;
 254     case FcTypeString:
 255         return FcStrHashIgnoreCase (v.u.s);
 256     case FcTypeBool:
 257         return (FcChar32) v.u.b;
 258     case FcTypeMatrix:
 259         return FcListMatrixHash (v.u.m);
 260     case FcTypeCharSet:
 261         return FcCharSetCount (v.u.c);
 262     case FcTypeFTFace:
 263         return (long) v.u.f;
 264     case FcTypeLangSet:
 265         return FcLangSetHash (v.u.l);
 266     }
 267     return 0;
 268 }
 269
 270 static FcChar32
 271 FcListValueListHash (FcValueListPtr list)
 272 {
 273     FcChar32    h = 0;
 274
 275     while (FcValueListPtrU(list))
 276     {
 277         h = h ^ FcListValueHash (&FcValueListPtrU(list)->value);
 278         list = FcValueListPtrU(list)->next;
 279     }
 280     return h;
 281 }
 282
 283 static FcChar32
 284 FcListPatternHash (FcPattern    *font,
 285                    FcObjectSet  *os)
 286 {
 287     int             n;
 288     FcPatternElt    *e;
 289     FcChar32        h = 0;
 290
 291     for (n = 0; n < os->nobject; n++)
 292     {
 293         e = FcPatternFindElt (font, os->objects[n]);
 294         if (e)
 295             h = h ^ FcListValueListHash (e->values);
 296     }
 297     return h;
 298 }
 299
 300 typedef struct _FcListBucket {
 301     struct _FcListBucket    *next;
 302     FcChar32                hash;
 303     FcPattern               *pattern;
 304 } FcListBucket;
 305
 306 #define FC_LIST_HASH_SIZE   4099
 307
 308 typedef struct _FcListHashTable {
 309     int             entries;
 310     FcListBucket    *buckets[FC_LIST_HASH_SIZE];
 311 } FcListHashTable;
 312
 313 static void
 314 FcListHashTableInit (FcListHashTable *table)
 315 {
 316     table->entries = 0;
 317     memset (table->buckets, '\0', sizeof (table->buckets));
 318 }
 319
 320 static void
 321 FcListHashTableCleanup (FcListHashTable *table)
 322 {
 323     int i;
 324     FcListBucket    *bucket, *next;
 325
 326     for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 327     {
 328         for (bucket = table->buckets[i]; bucket; bucket = next)
 329         {
 330             next = bucket->next;
 331             FcPatternDestroy (bucket->pattern);
 332             FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 333             free (bucket);
 334         }
 335         table->buckets[i] = 0;
 336     }
 337     table->entries = 0;
 338 }
 339
 340 static int
 341 FcGetDefaultObjectLangIndex (FcPattern *font, const char *object)
 342 {
 343     FcChar8        *lang = FcGetDefaultLang ();
 344     FcPatternElt   *e = FcPatternFindElt (font, object);
 345     FcValueListPtr  v;
 346     FcValue         value;
 347     int             idx = -1;
 348     int             i;
 349
 350     if (e)
 351     {
 352         for (v = e->values, i = 0; FcValueListPtrU(v); v = FcValueListPtrU(v)->next, ++i)
 353         {
 354             value = FcValueCanonicalize (&FcValueListPtrU (v)->value);
 355
 356             if (value.type == FcTypeString)
 357             {
 358                 FcLangResult res = FcLangCompare (value.u.s, lang);
 359                 if (res == FcLangEqual || (res == FcLangDifferentCountry && idx < 0))
 360                     idx = i;
 361             }
 362         }
 363     }
 364
 365     return (idx > 0) ? idx : 0;
 366 }
 367
 368 static FcBool
 369 FcListAppend (FcListHashTable   *table,
 370               FcPattern         *font,
 371               FcObjectSet       *os)
 372 {
 373     int             o;
 374     FcPatternElt    *e;
 375     FcValueListPtr  v;
 376     FcChar32        hash;
 377     FcListBucket    **prev, *bucket;
 378     int             familyidx = -1;
 379     int             fullnameidx = -1;
 380     int             styleidx = -1;
 381     int             defidx = 0;
 382     int             idx;
 383
 384     hash = FcListPatternHash (font, os);
 385     for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
 386          (bucket = *prev); prev = &(bucket->next))
 387     {
 388         if (bucket->hash == hash &&
 389             FcListPatternEqual (bucket->pattern, font, os))
 390             return FcTrue;
 391     }
 392     bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
 393     if (!bucket)
 394         goto bail0;
 395     FcMemAlloc (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 396     bucket->next = 0;
 397     bucket->hash = hash;
 398     bucket->pattern = FcPatternCreate ();
 399     if (!bucket->pattern)
 400         goto bail1;
 401
 402     for (o = 0; o < os->nobject; o++)
 403     {
 404         if (!strcmp (os->objects[o], FC_FAMILY) || !strcmp (os->objects[o], FC_FAMILYLANG))
 405         {
 406             if (familyidx < 0)
 407                 familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG);
 408             defidx = familyidx;
 409         }
 410         else if (!strcmp (os->objects[o], FC_FULLNAME) || !strcmp (os->objects[o], FC_FULLNAMELANG))
 411         {
 412             if (fullnameidx < 0)
 413                 fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG);
 414             defidx = fullnameidx;
 415         }
 416         else if (!strcmp (os->objects[o], FC_STYLE) || !strcmp (os->objects[o], FC_STYLELANG))
 417         {
 418             if (styleidx < 0)
 419                 styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG);
 420             defidx = styleidx;
 421         }
 422         else
 423             defidx = 0;
 424
 425         e = FcPatternFindElt (font, os->objects[o]);
 426         if (e)
 427         {
 428             for (v = e->values, idx = 0; FcValueListPtrU(v);
 429                  v = FcValueListPtrU(v)->next, ++idx)
 430             {
 431                 if (!FcPatternAdd (bucket->pattern,
 432                                    os->objects[o],
 433                                    FcValueCanonicalize(&FcValueListPtrU(v)->value), defidx != idx))
 434                     goto bail2;
 435             }
 436         }
 437     }
 438     *prev = bucket;
 439     ++table->entries;
 440
 441     return FcTrue;
 442
 443 bail2:
 444     FcPatternDestroy (bucket->pattern);
 445 bail1:
 446     FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 447     free (bucket);
 448 bail0:
 449     return FcFalse;
 450 }
 451
 452 FcFontSet *
 453 FcFontSetList (FcConfig     *config,
 454                FcFontSet    **sets,
 455                int          nsets,
 456                FcPattern    *p,
 457                FcObjectSet  *os)
 458 {
 459     FcFontSet       *ret;
 460     FcFontSet       *s;
 461     int             f;
 462     int             set;
 463     FcListHashTable table;
 464     int             i;
 465     FcListBucket    *bucket;
 466
 467     if (!config)
 468     {
 469         if (!FcInitBringUptoDate ())
 470             goto bail0;
 471
 472         config = FcConfigGetCurrent ();
 473         if (!config)
 474             goto bail0;
 475     }
 476     FcListHashTableInit (&table);
 477     /*
 478      * Walk all available fonts adding those that
 479      * match to the hash table
 480      */
 481     for (set = 0; set < nsets; set++)
 482     {
 483         s = sets[set];
 484         if (!s)
 485             continue;
 486         for (f = 0; f < s->nfont; f++)
 487             if (FcListPatternMatchAny (p,               /* pattern */
 488                                        s->fonts[f]))    /* font */
 489                 if (!FcListAppend (&table, s->fonts[f], os))
 490                     goto bail1;
 491     }
 492 #if 0
 493     {
 494         int     max = 0;
 495         int     full = 0;
 496         int     ents = 0;
 497         int     len;
 498         for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 499         {
 500             if ((bucket = table.buckets[i]))
 501             {
 502                 len = 0;
 503                 for (; bucket; bucket = bucket->next)
 504                 {
 505                     ents++;
 506                     len++;
 507                 }
 508                 if (len > max)
 509                     max = len;
 510                 full++;
 511             }
 512         }
 513         printf ("used: %d max: %d avg: %g\n", full, max,
 514                 (double) ents / FC_LIST_HASH_SIZE);
 515     }
 516 #endif
 517     /*
 518      * Walk the hash table and build
 519      * a font set
 520      */
 521     ret = FcFontSetCreate ();
 522     if (!ret)
 523         goto bail0;
 524     for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 525         while ((bucket = table.buckets[i]))
 526         {
 527             if (!FcFontSetAdd (ret, bucket->pattern))
 528                 goto bail2;
 529             table.buckets[i] = bucket->next;
 530             FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 531             free (bucket);
 532         }
 533
 534     return ret;
 535
 536 bail2:
 537     FcFontSetDestroy (ret);
 538 bail1:
 539     FcListHashTableCleanup (&table);
 540 bail0:
 541     return 0;
 542 }
 543
 544 FcFontSet *
 545 FcFontList (FcConfig    *config,
 546             FcPattern   *p,
 547             FcObjectSet *os)
 548 {
 549     FcFontSet   *sets[2];
 550     int         nsets;
 551
 552     if (!config)
 553     {
 554         config = FcConfigGetCurrent ();
 555         if (!config)
 556             return 0;
 557     }
 558     nsets = 0;
 559     if (config->fonts[FcSetSystem])
 560         sets[nsets++] = config->fonts[FcSetSystem];
 561     if (config->fonts[FcSetApplication])
 562         sets[nsets++] = config->fonts[FcSetApplication];
 563     return FcFontSetList (config, sets, nsets, p, os);
 564 }