src/fclist.c

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