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