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 "fcint.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     while (low <= high)
  71     {
  72         mid = (low + high) >> 1;
  73         c = strcmp (os->objects[mid], object);
  74         if (c == 0)
  75             return FcTrue;
  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     if (os->objects)
  94     {
  95         FcMemFree (FC_MEM_OBJECTPTR, os->sobject * sizeof (const char *));
  96         free ((void *) os->objects);
  97     }
  98     FcMemFree (FC_MEM_OBJECTSET, sizeof (FcObjectSet));
  99     free (os);
 100 }
 101
 102 FcObjectSet *
 103 FcObjectSetVaBuild (const char *first, va_list va)
 104 {
 105     FcObjectSet    *ret;
 106
 107     FcObjectSetVapBuild (ret, first, va);
 108     return ret;
 109 }
 110
 111 FcObjectSet *
 112 FcObjectSetBuild (const char *first, ...)
 113 {
 114     va_list         va;
 115     FcObjectSet    *os;
 116
 117     va_start (va, first);
 118     FcObjectSetVapBuild (os, first, va);
 119     va_end (va);
 120     return os;
 121 }
 122
 123 /*
 124  * Font must have a containing value for every value in the pattern
 125  */
 126 static FcBool
 127 FcListValueListMatchAny (FcValueList *patOrig,      /* pattern */
 128                          FcValueList *fntOrig)      /* font */
 129 {
 130     FcValueList     *pat, *fnt;
 131
 132     for (pat = patOrig; pat; pat = pat->next)
 133     {
 134         for (fnt = fntOrig; fnt; fnt = fnt->next)
 135         {
 136             /*
 137              * make sure the font 'contains' the pattern.
 138              * (OpListing is OpContains except for strings
 139              *  where it requires an exact match)
 140              */
 141             if (FcConfigCompareValue (fnt->value,
 142                                       FcOpListing,
 143                                       pat->value))
 144                 break;
 145         }
 146         if (!fnt)
 147             return FcFalse;
 148     }
 149     return FcTrue;
 150 }
 151
 152 static FcBool
 153 FcListValueListEqual (FcValueList   *v1orig,
 154                       FcValueList   *v2orig)
 155 {
 156     FcValueList     *v1, *v2;
 157
 158     for (v1 = v1orig; v1; v1 = v1->next)
 159     {
 160         for (v2 = v2orig; v2; v2 = v2->next)
 161             if (FcValueEqual (v1->value, v2->value))
 162                 break;
 163         if (!v2)
 164             return FcFalse;
 165     }
 166     for (v2 = v2orig; v2; v2 = v2->next)
 167     {
 168         for (v1 = v1orig; v1; v1 = v1->next)
 169             if (FcValueEqual (v1->value, v2->value))
 170                 break;
 171         if (!v1)
 172             return FcFalse;
 173     }
 174     return FcTrue;
 175 }
 176
 177 static FcBool
 178 FcListPatternEqual (FcPattern   *p1,
 179                     FcPattern   *p2,
 180                     FcObjectSet *os)
 181 {
 182     int             i;
 183     FcPatternElt    *e1, *e2;
 184
 185     for (i = 0; i < os->nobject; i++)
 186     {
 187         e1 = FcPatternFindElt (p1, os->objects[i]);
 188         e2 = FcPatternFindElt (p2, os->objects[i]);
 189         if (!e1 && !e2)
 190             continue;
 191         if (!e1 || !e2)
 192             return FcFalse;
 193         if (!FcListValueListEqual (e1->values, e2->values))
 194             return FcFalse;
 195     }
 196     return FcTrue;
 197 }
 198
 199 /*
 200  * FcTrue iff all objects in "p" match "font"
 201  */
 202
 203 FcBool
 204 FcListPatternMatchAny (const FcPattern *p,
 205                        const FcPattern *font)
 206 {
 207     int             i;
 208     FcPatternElt   *e;
 209
 210     for (i = 0; i < p->num; i++)
 211     {
 212         e = FcPatternFindElt (font, p->elts[i].object);
 213         if (!e)
 214             return FcFalse;
 215         if (!FcListValueListMatchAny (p->elts[i].values,    /* pat elts */
 216                                       e->values))           /* font elts */
 217             return FcFalse;
 218     }
 219     return FcTrue;
 220 }
 221
 222 static FcChar32
 223 FcListStringHash (const FcChar8 *s)
 224 {
 225     FcChar32    h = 0;
 226     FcChar8     c;
 227
 228     while ((c = *s++))
 229     {
 230         c = FcToLower (c);
 231         h = ((h << 3) ^ (h >> 3)) ^ c;
 232     }
 233     return h;
 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 FcListStringHash (v.u.s);
 259     case FcTypeBool:
 260         return (FcChar32) v.u.b;
 261     case FcTypeMatrix:
 262         return FcListMatrixHash (v.u.m);
 263     case FcTypeCharSet:
 264         return FcCharSetCount (v.u.c);
 265     case FcTypeFTFace:
 266         return (long) v.u.f;
 267     case FcTypeLangSet:
 268         return FcLangSetHash (v.u.l);
 269     }
 270     return 0;
 271 }
 272
 273 static FcChar32
 274 FcListValueListHash (FcValueList    *list)
 275 {
 276     FcChar32    h = 0;
 277
 278     while (list)
 279     {
 280         h = h ^ FcListValueHash (list->value);
 281         list = 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, 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     FcValueList     *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, os->objects[o]);
 375         if (e)
 376         {
 377             for (v = e->values; v; v = v->next)
 378             {
 379                 if (!FcPatternAdd (bucket->pattern,
 380                                    os->objects[o],
 381                                    v->value, FcTrue))
 382                     goto bail2;
 383             }
 384         }
 385     }
 386     *prev = bucket;
 387     ++table->entries;
 388
 389     return FcTrue;
 390
 391 bail2:
 392     FcPatternDestroy (bucket->pattern);
 393 bail1:
 394     FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 395     free (bucket);
 396 bail0:
 397     return FcFalse;
 398 }
 399
 400 FcFontSet *
 401 FcFontSetList (FcConfig     *config,
 402                FcFontSet    **sets,
 403                int          nsets,
 404                FcPattern    *p,
 405                FcObjectSet  *os)
 406 {
 407     FcFontSet       *ret;
 408     FcFontSet       *s;
 409     int             f;
 410     int             set;
 411     FcListHashTable table;
 412     int             i;
 413     FcListBucket    *bucket;
 414
 415     if (!config)
 416     {
 417         if (!FcInitBringUptoDate ())
 418             goto bail0;
 419
 420         config = FcConfigGetCurrent ();
 421         if (!config)
 422             goto bail0;
 423     }
 424     FcListHashTableInit (&table);
 425     /*
 426      * Walk all available fonts adding those that
 427      * match to the hash table
 428      */
 429     for (set = 0; set < nsets; set++)
 430     {
 431         s = sets[set];
 432         if (!s)
 433             continue;
 434         for (f = 0; f < s->nfont; f++)
 435             if (FcListPatternMatchAny (p,               /* pattern */
 436                                        s->fonts[f]))    /* font */
 437                 if (!FcListAppend (&table, s->fonts[f], os))
 438                     goto bail1;
 439     }
 440 #if 0
 441     {
 442         int     max = 0;
 443         int     full = 0;
 444         int     ents = 0;
 445         int     len;
 446         for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 447         {
 448             if ((bucket = table.buckets[i]))
 449             {
 450                 len = 0;
 451                 for (; bucket; bucket = bucket->next)
 452                 {
 453                     ents++;
 454                     len++;
 455                 }
 456                 if (len > max)
 457                     max = len;
 458                 full++;
 459             }
 460         }
 461         printf ("used: %d max: %d avg: %g\n", full, max,
 462                 (double) ents / FC_LIST_HASH_SIZE);
 463     }
 464 #endif
 465     /*
 466      * Walk the hash table and build
 467      * a font set
 468      */
 469     ret = FcFontSetCreate ();
 470     if (!ret)
 471         goto bail0;
 472     for (i = 0; i < FC_LIST_HASH_SIZE; i++)
 473         while ((bucket = table.buckets[i]))
 474         {
 475             if (!FcFontSetAdd (ret, bucket->pattern))
 476                 goto bail2;
 477             table.buckets[i] = bucket->next;
 478             FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
 479             free (bucket);
 480         }
 481
 482     return ret;
 483
 484 bail2:
 485     FcFontSetDestroy (ret);
 486 bail1:
 487     FcListHashTableCleanup (&table);
 488 bail0:
 489     return 0;
 490 }
 491
 492 FcFontSet *
 493 FcFontList (FcConfig    *config,
 494             FcPattern   *p,
 495             FcObjectSet *os)
 496 {
 497     FcFontSet   *sets[2];
 498     int         nsets;
 499
 500     if (!config)
 501     {
 502         config = FcConfigGetCurrent ();
 503         if (!config)
 504             return 0;
 505     }
 506     nsets = 0;
 507     if (config->fonts[FcSetSystem])
 508         sets[nsets++] = config->fonts[FcSetSystem];
 509     if (config->fonts[FcSetApplication])
 510         sets[nsets++] = config->fonts[FcSetApplication];
 511     return FcFontSetList (config, sets, nsets, p, os);
 512 }