src/fclist.c

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