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