src/fclist.c

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