src/fcpat.c

   1 /*
   2  * $RCSId: xc/lib/fontconfig/src/fcpat.c,v 1.18 2002/09/18 17:11:46 tsi 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 <string.h>
  27 #include <assert.h>
  28 #include "fcint.h"
  29
  30 static FcPattern ** _fcPatterns = 0;
  31 static int fcpattern_bank_count = 0, fcpattern_ptr, fcpattern_count;
  32 FcPatternElt ** _fcPatternElts = 0;
  33 static int fcpatternelt_ptr, fcpatternelt_count;
  34 FcValueList ** _fcValueLists = 0;
  35 static int fcvaluelist_bank_count = 0, fcvaluelist_ptr, fcvaluelist_count;
  36
  37 static FcPatternEltPtr
  38 FcPatternEltPtrCreateDynamic (FcPatternElt * e);
  39 static FcBool
  40 FcStrHashed (const FcChar8 *name);
  41
  42 static const char *
  43 FcPatternFindFullFname (const FcPattern *p);
  44
  45 /* If you are trying to duplicate an FcPattern which will be used for
  46  * rendering, be aware that (internally) you also have to use
  47  * FcPatternTransferFullFname to transfer the associated filename.  If
  48  * you are copying the font (externally) using FcPatternGetString,
  49  * then everything's fine; this caveat only applies if you're copying
  50  * the bits individually.  */
  51
  52 FcPattern *
  53 FcPatternCreate (void)
  54 {
  55     FcPattern   *p;
  56
  57     p = (FcPattern *) malloc (sizeof (FcPattern));
  58     if (!p)
  59         return 0;
  60     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern));
  61     p->num = 0;
  62     p->size = 0;
  63     p->elts = FcPatternEltPtrCreateDynamic(0);
  64     p->bank = FC_BANK_DYNAMIC;
  65     p->ref = 1;
  66     return p;
  67 }
  68
  69 void
  70 FcValueDestroy (FcValue v)
  71 {
  72     switch (v.type) {
  73     case FcTypeString:
  74         if (!FcStrHashed (v.u.s))
  75             FcStrFree ((FcChar8 *) v.u.s);
  76         break;
  77     case FcTypeMatrix:
  78         FcMatrixFree ((FcMatrix *) v.u.m);
  79         break;
  80     case FcTypeCharSet:
  81         FcCharSetDestroy ((FcCharSet *) v.u.c);
  82         break;
  83     case FcTypeLangSet:
  84         FcLangSetDestroy ((FcLangSet *) v.u.l);
  85         break;
  86     default:
  87         break;
  88     }
  89 }
  90
  91 FcValue
  92 FcValueCanonicalize (const FcValue *v)
  93 {
  94     if (v->type & FC_STORAGE_STATIC)
  95     {
  96         FcValue new = *v;
  97
  98         switch (v->type & ~FC_STORAGE_STATIC)
  99         {
 100         case FcTypeString:
 101             new.u.s = fc_value_string(v);
 102             new.type = FcTypeString;
 103             break;
 104         case FcTypeCharSet:
 105             new.u.c = fc_value_charset(v);
 106             new.type = FcTypeCharSet;
 107             break;
 108         case FcTypeLangSet:
 109             new.u.l = fc_value_langset(v);
 110             new.type = FcTypeLangSet;
 111             break;
 112         }
 113         return new;
 114     }
 115     return *v;
 116 }
 117
 118 FcValue
 119 FcValueSave (FcValue v)
 120 {
 121     switch (v.type) {
 122     case FcTypeString:
 123         v.u.s = FcStrCopy (v.u.s);
 124         if (!v.u.s)
 125             v.type = FcTypeVoid;
 126         break;
 127     case FcTypeMatrix:
 128         v.u.m = FcMatrixCopy (v.u.m);
 129         if (!v.u.m)
 130             v.type = FcTypeVoid;
 131         break;
 132     case FcTypeCharSet:
 133         v.u.c = FcCharSetCopy ((FcCharSet *) v.u.c);
 134         if (!v.u.c)
 135             v.type = FcTypeVoid;
 136         break;
 137     case FcTypeLangSet:
 138         v.u.l = FcLangSetCopy (v.u.l);
 139         if (!v.u.l)
 140             v.type = FcTypeVoid;
 141         break;
 142     default:
 143         break;
 144     }
 145     return v;
 146 }
 147
 148 void
 149 FcValueListDestroy (FcValueListPtr l)
 150 {
 151     FcValueListPtr next;
 152     for (; FcValueListPtrU(l); l = next)
 153     {
 154         switch (FcValueListPtrU(l)->value.type) {
 155         case FcTypeString:
 156             if (!FcStrHashed ((FcChar8 *)FcValueListPtrU(l)->value.u.s))
 157                 FcStrFree ((FcChar8 *)FcValueListPtrU(l)->value.u.s);
 158             break;
 159         case FcTypeMatrix:
 160             FcMatrixFree ((FcMatrix *)FcValueListPtrU(l)->value.u.m);
 161             break;
 162         case FcTypeCharSet:
 163             FcCharSetDestroy
 164                 ((FcCharSet *) (FcValueListPtrU(l)->value.u.c));
 165             break;
 166         case FcTypeLangSet:
 167             FcLangSetDestroy
 168                 ((FcLangSet *) (FcValueListPtrU(l)->value.u.l));
 169             break;
 170         default:
 171             break;
 172         }
 173         next = FcValueListPtrU(l)->next;
 174         FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 175         if (l.bank == FC_BANK_DYNAMIC)
 176             free(l.u.dyn);
 177     }
 178 }
 179
 180 FcBool
 181 FcValueEqual (FcValue va, FcValue vb)
 182 {
 183     if (va.type != vb.type)
 184     {
 185         if (va.type == FcTypeInteger)
 186         {
 187             va.type = FcTypeDouble;
 188             va.u.d = va.u.i;
 189         }
 190         if (vb.type == FcTypeInteger)
 191         {
 192             vb.type = FcTypeDouble;
 193             vb.u.d = vb.u.i;
 194         }
 195         if (va.type != vb.type)
 196             return FcFalse;
 197     }
 198     switch (va.type) {
 199     case FcTypeVoid:
 200         return FcTrue;
 201     case FcTypeInteger:
 202         return va.u.i == vb.u.i;
 203     case FcTypeDouble:
 204         return va.u.d == vb.u.d;
 205     case FcTypeString:
 206         return FcStrCmpIgnoreCase (va.u.s, vb.u.s) == 0;
 207     case FcTypeBool:
 208         return va.u.b == vb.u.b;
 209     case FcTypeMatrix:
 210         return FcMatrixEqual (va.u.m, vb.u.m);
 211     case FcTypeCharSet:
 212         return FcCharSetEqual (va.u.c, vb.u.c);
 213     case FcTypeFTFace:
 214         return va.u.f == vb.u.f;
 215     case FcTypeLangSet:
 216         return FcLangSetEqual (va.u.l, vb.u.l);
 217     }
 218     return FcFalse;
 219 }
 220
 221 static FcChar32
 222 FcDoubleHash (double d)
 223 {
 224     if (d < 0)
 225         d = -d;
 226     if (d > 0xffffffff)
 227         d = 0xffffffff;
 228     return (FcChar32) d;
 229 }
 230
 231 FcChar32
 232 FcStringHash (const FcChar8 *s)
 233 {
 234     FcChar8     c;
 235     FcChar32    h = 0;
 236
 237     if (s)
 238         while ((c = *s++))
 239             h = ((h << 1) | (h >> 31)) ^ c;
 240     return h;
 241 }
 242
 243 static FcChar32
 244 FcValueHash (const FcValue *v0)
 245 {
 246     FcValue v = FcValueCanonicalize(v0);
 247     switch (v.type) {
 248     case FcTypeVoid:
 249         return 0;
 250     case FcTypeInteger:
 251         return (FcChar32) v.u.i;
 252     case FcTypeDouble:
 253         return FcDoubleHash (v.u.d);
 254     case FcTypeString:
 255         return FcStringHash (v.u.s);
 256     case FcTypeBool:
 257         return (FcChar32) v.u.b;
 258     case FcTypeMatrix:
 259         return (FcDoubleHash (v.u.m->xx) ^
 260                 FcDoubleHash (v.u.m->xy) ^
 261                 FcDoubleHash (v.u.m->yx) ^
 262                 FcDoubleHash (v.u.m->yy));
 263     case FcTypeCharSet:
 264         return (FcChar32) v.u.c->num;
 265     case FcTypeFTFace:
 266         return FcStringHash ((const FcChar8 *) ((FT_Face) v.u.f)->family_name) ^
 267                FcStringHash ((const FcChar8 *) ((FT_Face) v.u.f)->style_name);
 268     case FcTypeLangSet:
 269         return FcLangSetHash (v.u.l);
 270     }
 271     return FcFalse;
 272 }
 273
 274 static FcBool
 275 FcValueListEqual (FcValueListPtr la, FcValueListPtr lb)
 276 {
 277     if (FcValueListPtrU(la) == FcValueListPtrU(lb))
 278         return FcTrue;
 279
 280     while (FcValueListPtrU(la) && FcValueListPtrU(lb))
 281     {
 282         if (!FcValueEqual (FcValueListPtrU(la)->value,
 283                            FcValueListPtrU(lb)->value))
 284             return FcFalse;
 285         la = FcValueListPtrU(la)->next;
 286         lb = FcValueListPtrU(lb)->next;
 287     }
 288     if (FcValueListPtrU(la) || FcValueListPtrU(lb))
 289         return FcFalse;
 290     return FcTrue;
 291 }
 292
 293 static FcChar32
 294 FcValueListHash (FcValueListPtr l)
 295 {
 296     FcChar32    hash = 0;
 297
 298     while (FcValueListPtrU(l))
 299     {
 300         hash = ((hash << 1) | (hash >> 31)) ^
 301             FcValueHash (&FcValueListPtrU(l)->value);
 302         l = FcValueListPtrU(l)->next;
 303     }
 304     return hash;
 305 }
 306
 307 void
 308 FcPatternDestroy (FcPattern *p)
 309 {
 310     int             i;
 311
 312     if (p->ref == FC_REF_CONSTANT || --p->ref > 0)
 313         return;
 314
 315     if (FcPatternFindFullFname (p))
 316     {
 317         FcStrFree ((FcChar8 *)FcPatternFindFullFname (p));
 318         FcPatternAddFullFname (p, 0);
 319     }
 320
 321     for (i = 0; i < p->num; i++)
 322         FcValueListDestroy ((FcPatternEltU(p->elts)+i)->values);
 323
 324     p->num = 0;
 325     if (FcPatternEltU(p->elts) && p->elts.bank == FC_BANK_DYNAMIC)
 326     {
 327         FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
 328         free (FcPatternEltU(p->elts));
 329         p->elts = FcPatternEltPtrCreateDynamic(0);
 330     }
 331     p->size = 0;
 332     FcMemFree (FC_MEM_PATTERN, sizeof (FcPattern));
 333     free (p);
 334 }
 335
 336 #define FC_VALUE_LIST_HASH_SIZE     257
 337 #define FC_PATTERN_HASH_SIZE        67
 338
 339 typedef struct _FcValueListEnt FcValueListEnt;
 340
 341 struct _FcValueListEnt {
 342     FcValueListEnt  *next;
 343     FcValueListPtr  list;
 344     FcChar32        hash, pad;
 345 };
 346
 347 typedef union _FcValueListAlign {
 348     FcValueListEnt  ent;
 349     FcValueList     list;
 350 } FcValueListAlign;
 351
 352 static int          FcValueListFrozenCount[FcTypeLangSet + 1];
 353 static int          FcValueListFrozenBytes[FcTypeLangSet + 1];
 354 static char         FcValueListFrozenName[][8] = {
 355     "Void",
 356     "Integer",
 357     "Double",
 358     "String",
 359     "Bool",
 360     "Matrix",
 361     "CharSet",
 362     "FTFace",
 363     "LangSet"
 364 };
 365
 366 void
 367 FcValueListReport (void);
 368
 369 void
 370 FcValueListReport (void)
 371 {
 372     FcType  t;
 373
 374     printf ("Fc Frozen Values:\n");
 375     printf ("\t%8s %9s %9s\n", "Type", "Count", "Bytes");
 376     for (t = FcTypeVoid; t <= FcTypeLangSet; t++)
 377         printf ("\t%8s %9d %9d\n", FcValueListFrozenName[t],
 378                 FcValueListFrozenCount[t], FcValueListFrozenBytes[t]);
 379 }
 380
 381 static FcValueListEnt *
 382 FcValueListEntCreate (FcValueListPtr h)
 383 {
 384     FcValueListAlign    *ea;
 385     FcValueListEnt  *e;
 386     FcValueListPtr  l;
 387     FcValueList     *new;
 388     int             n;
 389     int             size;
 390
 391     n = 0;
 392     for (l = h; FcValueListPtrU(l); l = FcValueListPtrU(l)->next)
 393         n++;
 394     size = sizeof (FcValueListAlign) + n * sizeof (FcValueList);
 395     FcValueListFrozenCount[FcValueListPtrU(h)->value.type]++;
 396     FcValueListFrozenBytes[FcValueListPtrU(h)->value.type] += size;
 397     // this leaks for some reason
 398     ea = malloc (sizeof (FcValueListAlign));
 399     if (!ea)
 400         return 0;
 401     new = malloc (n * sizeof (FcValueList));
 402     if (!new)
 403         return 0;
 404     memset(new, 0, n * sizeof (FcValueList));
 405     FcMemAlloc (FC_MEM_VALLIST, size);
 406     e = &ea->ent;
 407     e->list = (FcValueListPtr) FcValueListPtrCreateDynamic(new);
 408     for (l = h; FcValueListPtrU(l);
 409          l = FcValueListPtrU(l)->next, new++)
 410     {
 411         if ((FcValueListPtrU(l)->value.type & ~FC_STORAGE_STATIC) == FcTypeString)
 412         {
 413             new->value.type = FcTypeString;
 414             new->value.u.s = FcStrStaticName
 415                 (fc_value_string(&FcValueListPtrU(l)->value));
 416         }
 417         else
 418         {
 419             new->value = FcValueSave (FcValueCanonicalize
 420                                       (&FcValueListPtrU(l)->value));
 421         }
 422         new->binding = FcValueListPtrU(l)->binding;
 423         if (FcValueListPtrU(FcValueListPtrU(l)->next))
 424         {
 425             new->next = FcValueListPtrCreateDynamic(new + 1);
 426         }
 427         else
 428         {
 429             new->next = FcValueListPtrCreateDynamic(0);
 430         }
 431     }
 432     return e;
 433 }
 434
 435 static void
 436 FcValueListEntDestroy (FcValueListEnt *e)
 437 {
 438     FcValueListPtr      l;
 439
 440     FcValueListFrozenCount[FcValueListPtrU(e->list)->value.type]--;
 441
 442     /* XXX: We should perform these two operations with "size" as
 443        computed in FcValueListEntCreate, but we don't have access to
 444        that value here. Without this, the FcValueListFrozenBytes
 445        values will be wrong as will the FcMemFree counts.
 446
 447        FcValueListFrozenBytes[e->list->value.type] -= size;
 448        FcMemFree (FC_MEM_VALLIST, size);
 449     */
 450
 451     for (l = e->list; FcValueListPtrU(l);
 452          l = FcValueListPtrU(l)->next)
 453     {
 454         if (FcValueListPtrU(l)->value.type != FcTypeString)
 455             FcValueDestroy (FcValueListPtrU(l)->value);
 456     }
 457     /* XXX: Are we being too chummy with the implementation here to
 458        free(e) when it was actually the enclosing FcValueListAlign
 459        that was allocated? */
 460     free (e);
 461 }
 462
 463 static int      FcValueListTotal;
 464 static int      FcValueListUsed;
 465
 466 static FcValueListEnt   *FcValueListHashTable[FC_VALUE_LIST_HASH_SIZE];
 467
 468 static FcValueListPtr
 469 FcValueListFreeze (FcValueListPtr l)
 470 {
 471     FcChar32                hash = FcValueListHash (l);
 472     FcValueListEnt          **bucket = &FcValueListHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
 473     FcValueListEnt          *ent;
 474
 475     FcValueListTotal++;
 476     for (ent = *bucket; ent; ent = ent->next)
 477     {
 478         if (ent->hash == hash && FcValueListEqual (ent->list, l))
 479             return ent->list;
 480     }
 481
 482     ent = FcValueListEntCreate (l);
 483     if (!ent)
 484         return FcValueListPtrCreateDynamic(0);
 485
 486     FcValueListUsed++;
 487     ent->hash = hash;
 488     ent->next = *bucket;
 489     *bucket = ent;
 490     return ent->list;
 491 }
 492
 493 static void
 494 FcValueListThawAll (void)
 495 {
 496     int i;
 497     FcValueListEnt      *ent, *next;
 498
 499     for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
 500     {
 501         for (ent = FcValueListHashTable[i]; ent; ent = next)
 502         {
 503             next = ent->next;
 504             FcValueListEntDestroy (ent);
 505         }
 506         FcValueListHashTable[i] = 0;
 507     }
 508
 509     FcValueListTotal = 0;
 510     FcValueListUsed = 0;
 511 }
 512
 513 static FcChar32
 514 FcPatternBaseHash (FcPattern *b)
 515 {
 516     FcChar32    hash = b->num;
 517     int         i;
 518
 519     for (i = 0; i < b->num; i++)
 520         hash = ((hash << 1) | (hash >> 31)) ^
 521             (long) (FcValueListPtrU((FcPatternEltU(b->elts)+i)->values));
 522     return hash;
 523 }
 524
 525 typedef struct _FcPatternEnt FcPatternEnt;
 526
 527 struct _FcPatternEnt {
 528     FcPatternEnt    *next;
 529     FcChar32        hash;
 530     FcPattern       *pattern;
 531 };
 532
 533 static int      FcPatternTotal;
 534 static int      FcPatternUsed;
 535
 536 static FcPatternEnt     *FcPatternHashTable[FC_VALUE_LIST_HASH_SIZE];
 537
 538 static FcPattern *
 539 FcPatternBaseFreeze (FcPattern *b)
 540 {
 541     FcPattern           *ep;
 542     FcPatternElt        *epp;
 543     FcChar32            hash = FcPatternBaseHash (b);
 544     FcPatternEnt        **bucket = &FcPatternHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
 545     FcPatternEnt        *ent;
 546     int                 i;
 547
 548     FcPatternTotal++;
 549     for (ent = *bucket; ent; ent = ent->next)
 550     {
 551         if (ent->hash == hash && b->num == ent->pattern->num)
 552         {
 553             for (i = 0; i < b->num; i++)
 554             {
 555                 if (FcObjectPtrCompare((FcPatternEltU(b->elts)+i)->object,
 556                                        (FcPatternEltU(ent->pattern->elts)+i)->object) != 0)
 557                     break;
 558                 if (FcValueListPtrU((FcPatternEltU(b->elts)+i)->values) !=
 559                     FcValueListPtrU((FcPatternEltU(ent->pattern->elts)+i)->values))
 560                     break;
 561             }
 562             if (i == b->num)
 563                 return ent->pattern;
 564         }
 565     }
 566
 567     /*
 568      * Compute size of pattern + elts
 569      */
 570     ent = malloc (sizeof (FcPatternEnt));
 571     if (!ent)
 572         return 0;
 573
 574     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPatternEnt));
 575     FcPatternUsed++;
 576
 577     ep = FcPatternCreate();
 578     if (!ep)
 579         return 0;
 580     ent->pattern = ep;
 581     epp = malloc(b->num * sizeof (FcPatternElt));
 582     if (!epp)
 583         goto bail;
 584     ep->elts = FcPatternEltPtrCreateDynamic(epp);
 585
 586     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));
 587
 588     ep->num = b->num;
 589     ep->size = b->num;
 590     ep->ref = FC_REF_CONSTANT;
 591
 592     for (i = 0; i < b->num; i++)
 593     {
 594         (FcPatternEltU(ep->elts)+i)->values =
 595             (FcPatternEltU(b->elts)+i)->values;
 596         (FcPatternEltU(ep->elts)+i)->object =
 597             (FcPatternEltU(b->elts)+i)->object;
 598     }
 599
 600     if (FcPatternFindElt (b, FC_FILE))
 601         FcPatternTransferFullFname (ep, b);
 602
 603     ent->hash = hash;
 604     ent->next = *bucket;
 605     *bucket = ent;
 606     return ent->pattern;
 607  bail:
 608     free(ent);
 609     FcMemFree (FC_MEM_PATTERN, sizeof (FcPatternEnt));
 610     FcPatternUsed--;
 611     return 0;
 612 }
 613
 614 static void
 615 FcPatternBaseThawAll (void)
 616 {
 617     int i;
 618     FcPatternEnt        *ent, *next;
 619
 620     for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
 621     {
 622         for (ent = FcPatternHashTable[i]; ent; ent = next)
 623         {
 624             next = ent->next;
 625             free (ent);
 626         }
 627         FcPatternHashTable[i] = 0;
 628     }
 629
 630     FcPatternTotal = 0;
 631     FcPatternUsed = 0;
 632 }
 633
 634 FcPattern *
 635 FcPatternFreeze (FcPattern *p)
 636 {
 637     FcPattern   *b, *n = 0;
 638     FcPatternElt *e;
 639     int         i;
 640
 641     if (p->ref == FC_REF_CONSTANT)
 642        return p;
 643
 644     b = FcPatternCreate();
 645     if (!b)
 646         return 0;
 647
 648     b->num = p->num;
 649     b->size = b->num;
 650     b->ref = 1;
 651
 652     e = malloc(b->num * sizeof (FcPatternElt));
 653     if (!e)
 654         return 0;
 655     b->elts = FcPatternEltPtrCreateDynamic(e);
 656     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));
 657
 658     /*
 659      * Freeze object lists
 660      */
 661     for (i = 0; i < p->num; i++)
 662     {
 663         (FcPatternEltU(b->elts)+i)->object =
 664             (FcPatternEltU(p->elts)+i)->object;
 665         (FcPatternEltU(b->elts)+i)->values =
 666             FcValueListFreeze((FcPatternEltU(p->elts)+i)->values);
 667         if (!FcValueListPtrU((FcPatternEltU(p->elts)+i)->values))
 668             goto bail;
 669     }
 670
 671     if (FcPatternFindElt (p, FC_FILE))
 672         FcPatternTransferFullFname (b, p);
 673
 674     /*
 675      * Freeze base
 676      */
 677     n = FcPatternBaseFreeze (b);
 678 #ifdef CHATTY
 679     if (FcDebug() & FC_DBG_MEMORY)
 680     {
 681         printf ("ValueLists: total %9d used %9d\n", FcValueListTotal, FcValueListUsed);
 682         printf ("Patterns:   total %9d used %9d\n", FcPatternTotal, FcPatternUsed);
 683     }
 684 #endif
 685  bail:
 686     free(FcPatternEltU(b->elts));
 687     b->elts = FcPatternEltPtrCreateDynamic(0);
 688     FcMemFree (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));
 689     b->num = -1;
 690 #ifdef DEBUG
 691     assert (FcPatternEqual (n, p));
 692 #endif
 693     return n;
 694 }
 695
 696 static int
 697 FcPatternPosition (const FcPattern *p, const char *object)
 698 {
 699     int     low, high, mid, c;
 700     FcObjectPtr obj;
 701
 702     obj = FcObjectToPtr(object);
 703     low = 0;
 704     high = p->num - 1;
 705     c = 1;
 706     mid = 0;
 707     while (low <= high)
 708     {
 709         mid = (low + high) >> 1;
 710         c = FcObjectPtrCompare((FcPatternEltU(p->elts)+mid)->object, obj);
 711         if (c == 0)
 712             return mid;
 713         if (c < 0)
 714             low = mid + 1;
 715         else
 716             high = mid - 1;
 717     }
 718     if (c < 0)
 719         mid++;
 720     return -(mid + 1);
 721 }
 722
 723 FcPatternElt *
 724 FcPatternFindElt (const FcPattern *p, const char *object)
 725 {
 726     int     i = FcPatternPosition (p, object);
 727     if (i < 0)
 728         return 0;
 729     return FcPatternEltU(p->elts)+i;
 730 }
 731
 732 FcPatternElt *
 733 FcPatternInsertElt (FcPattern *p, const char *object)
 734 {
 735     int             i;
 736     FcPatternElt   *e;
 737
 738     i = FcPatternPosition (p, object);
 739     if (i < 0)
 740     {
 741         i = -i - 1;
 742
 743         /* reallocate array */
 744         if (p->num + 1 >= p->size)
 745         {
 746             int s = p->size + 16;
 747             if (FcPatternEltU(p->elts))
 748             {
 749                 FcPatternElt *e0 = FcPatternEltU(p->elts);
 750                 e = (FcPatternElt *) realloc (e0, s * sizeof (FcPatternElt));
 751                 if (!e) /* maybe it was mmapped */
 752                 {
 753                     e = malloc(s * sizeof (FcPatternElt));
 754                     if (e)
 755                         memcpy(e, e0, p->num * sizeof (FcPatternElt));
 756                 }
 757             }
 758             else
 759                 e = (FcPatternElt *) malloc (s * sizeof (FcPatternElt));
 760             if (!e)
 761                 return FcFalse;
 762             p->elts = FcPatternEltPtrCreateDynamic(e);
 763             if (p->size)
 764                 FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
 765             FcMemAlloc (FC_MEM_PATELT, s * sizeof (FcPatternElt));
 766             while (p->size < s)
 767             {
 768                 (FcPatternEltU(p->elts)+p->size)->object = 0;
 769                 (FcPatternEltU(p->elts)+p->size)->values =
 770                     FcValueListPtrCreateDynamic(0);
 771                 p->size++;
 772             }
 773         }
 774
 775         /* move elts up */
 776         memmove (FcPatternEltU(p->elts) + i + 1,
 777                  FcPatternEltU(p->elts) + i,
 778                  sizeof (FcPatternElt) *
 779                  (p->num - i));
 780
 781         /* bump count */
 782         p->num++;
 783
 784         (FcPatternEltU(p->elts)+i)->object = FcObjectToPtr (object);
 785         (FcPatternEltU(p->elts)+i)->values = FcValueListPtrCreateDynamic(0);
 786     }
 787
 788     return FcPatternEltU(p->elts)+i;
 789 }
 790
 791 FcBool
 792 FcPatternEqual (const FcPattern *pa, const FcPattern *pb)
 793 {
 794     int i;
 795
 796     if (pa == pb)
 797         return FcTrue;
 798
 799     if (pa->num != pb->num)
 800         return FcFalse;
 801     for (i = 0; i < pa->num; i++)
 802     {
 803         if (FcObjectPtrCompare((FcPatternEltU(pa->elts)+i)->object,
 804                                (FcPatternEltU(pb->elts)+i)->object) != 0)
 805             return FcFalse;
 806         if (!FcValueListEqual ((FcPatternEltU(pa->elts)+i)->values,
 807                                (FcPatternEltU(pb->elts)+i)->values))
 808             return FcFalse;
 809     }
 810     return FcTrue;
 811 }
 812
 813 FcChar32
 814 FcPatternHash (const FcPattern *p)
 815 {
 816     int         i;
 817     FcChar32    h = 0;
 818
 819     for (i = 0; i < p->num; i++)
 820     {
 821         h = (((h << 1) | (h >> 31)) ^
 822              FcStringHash ((FcChar8 *)FcObjectPtrU ((FcPatternEltU(p->elts)+i)->object)) ^
 823              FcValueListHash ((FcPatternEltU(p->elts)+i)->values));
 824     }
 825     return h;
 826 }
 827
 828 FcBool
 829 FcPatternEqualSubset (const FcPattern *pai, const FcPattern *pbi, const FcObjectSet *os)
 830 {
 831     FcPatternElt    *ea, *eb;
 832     int             i;
 833
 834     for (i = 0; i < os->nobject; i++)
 835     {
 836         ea = FcPatternFindElt (pai, os->objects[i]);
 837         eb = FcPatternFindElt (pbi, os->objects[i]);
 838         if (ea)
 839         {
 840             if (!eb)
 841                 return FcFalse;
 842             if (!FcValueListEqual (ea->values, eb->values))
 843                 return FcFalse;
 844         }
 845         else
 846         {
 847             if (eb)
 848                 return FcFalse;
 849         }
 850     }
 851     return FcTrue;
 852 }
 853
 854 FcBool
 855 FcPatternAddWithBinding  (FcPattern         *p,
 856                           const char        *object,
 857                           FcValue           value,
 858                           FcValueBinding    binding,
 859                           FcBool            append)
 860 {
 861     FcPatternElt   *e;
 862     FcValueListPtr new, *prev;
 863     FcValueList    *newp;
 864     FcObjectPtr    objectPtr;
 865
 866     if (p->ref == FC_REF_CONSTANT)
 867         goto bail0;
 868
 869     newp = malloc (sizeof (FcValueList));
 870     if (!newp)
 871         goto bail0;
 872
 873     memset(newp, 0, sizeof (FcValueList));
 874     new = FcValueListPtrCreateDynamic(newp);
 875     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList));
 876     /* dup string */
 877     value = FcValueSave (value);
 878     if (value.type == FcTypeVoid)
 879         goto bail1;
 880
 881     /* quick and dirty hack to enable FcCompareFamily/FcCompareString
 882      * speedup: only allow strings to be added under the FC_FAMILY,
 883      * FC_FOUNDRY, FC_STYLE, FC_RASTERIZER keys.
 884      * and charsets under FC_CHARSET key.
 885      * This is slightly semantically different from the old behaviour,
 886      * but fonts shouldn't be getting non-strings here anyway.
 887      * a better hack would use FcBaseObjectTypes to check all objects. */
 888     objectPtr = FcObjectToPtr(object);
 889     if ((objectPtr == FcObjectToPtr(FC_FAMILY)
 890          || objectPtr == FcObjectToPtr(FC_FOUNDRY)
 891          || objectPtr == FcObjectToPtr(FC_STYLE)
 892          || objectPtr == FcObjectToPtr(FC_RASTERIZER))
 893         && value.type != FcTypeString)
 894         goto bail1;
 895     if (objectPtr == FcObjectToPtr(FC_CHARSET)
 896         && value.type != FcTypeCharSet)
 897         goto bail1;
 898
 899     FcValueListPtrU(new)->value = value;
 900     FcValueListPtrU(new)->binding = binding;
 901     FcValueListPtrU(new)->next = FcValueListPtrCreateDynamic(0);
 902
 903     e = FcPatternInsertElt (p, object);
 904     if (!e)
 905         goto bail2;
 906
 907     if (append)
 908     {
 909         for (prev = &e->values; FcValueListPtrU(*prev); prev = &FcValueListPtrU(*prev)->next)
 910             ;
 911         *prev = new;
 912     }
 913     else
 914     {
 915         FcValueListPtrU(new)->next = e->values;
 916         e->values = new;
 917     }
 918
 919     return FcTrue;
 920
 921 bail2:
 922     switch (value.type) {
 923     case FcTypeString:
 924         FcStrFree ((FcChar8 *) value.u.s);
 925         break;
 926     case FcTypeMatrix:
 927         FcMatrixFree ((FcMatrix *) value.u.m);
 928         break;
 929     case FcTypeCharSet:
 930         FcCharSetDestroy ((FcCharSet *) value.u.c);
 931         break;
 932     case FcTypeLangSet:
 933         FcLangSetDestroy ((FcLangSet *) value.u.l);
 934         break;
 935     default:
 936         break;
 937     }
 938 bail1:
 939     FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 940     free (FcValueListPtrU(new));
 941 bail0:
 942     return FcFalse;
 943 }
 944
 945 FcBool
 946 FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
 947 {
 948     return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
 949 }
 950
 951 FcBool
 952 FcPatternAddWeak  (FcPattern *p, const char *object, FcValue value, FcBool append)
 953 {
 954     return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
 955 }
 956
 957 FcBool
 958 FcPatternDel (FcPattern *p, const char *object)
 959 {
 960     FcPatternElt   *e;
 961
 962     e = FcPatternFindElt (p, object);
 963     if (!e)
 964         return FcFalse;
 965
 966     /* destroy value */
 967     FcValueListDestroy (e->values);
 968
 969     /* shuffle existing ones down */
 970     memmove (e, e+1,
 971              (FcPatternEltU(p->elts) + p->num - (e + 1)) *
 972              sizeof (FcPatternElt));
 973     p->num--;
 974     (FcPatternEltU(p->elts)+p->num)->object = 0;
 975     (FcPatternEltU(p->elts)+p->num)->values = FcValueListPtrCreateDynamic(0);
 976     return FcTrue;
 977 }
 978
 979 FcBool
 980 FcPatternRemove (FcPattern *p, const char *object, int id)
 981 {
 982     FcPatternElt    *e;
 983     FcValueListPtr  *prev, l;
 984
 985     e = FcPatternFindElt (p, object);
 986     if (!e)
 987         return FcFalse;
 988     for (prev = &e->values;
 989          FcValueListPtrU(l = *prev);
 990          prev = &FcValueListPtrU(l)->next)
 991     {
 992         if (!id)
 993         {
 994             *prev = FcValueListPtrU(l)->next;
 995             FcValueListPtrU(l)->next = FcValueListPtrCreateDynamic(0);
 996             FcValueListDestroy (l);
 997             if (!FcValueListPtrU(e->values))
 998                 FcPatternDel (p, object);
 999             return FcTrue;
1000         }
1001         id--;
1002     }
1003     return FcFalse;
1004 }
1005
1006 FcBool
1007 FcPatternAddInteger (FcPattern *p, const char *object, int i)
1008 {
1009     FcValue     v;
1010
1011     v.type = FcTypeInteger;
1012     v.u.i = i;
1013     return FcPatternAdd (p, object, v, FcTrue);
1014 }
1015
1016 FcBool
1017 FcPatternAddDouble (FcPattern *p, const char *object, double d)
1018 {
1019     FcValue     v;
1020
1021     v.type = FcTypeDouble;
1022     v.u.d = d;
1023     return FcPatternAdd (p, object, v, FcTrue);
1024 }
1025
1026
1027 FcBool
1028 FcPatternAddString (FcPattern *p, const char *object, const FcChar8 *s)
1029 {
1030     FcValue     v;
1031
1032     v.type = FcTypeString;
1033     v.u.s = FcStrStaticName(s);
1034     return FcPatternAdd (p, object, v, FcTrue);
1035 }
1036
1037 FcBool
1038 FcPatternAddMatrix (FcPattern *p, const char *object, const FcMatrix *s)
1039 {
1040     FcValue     v;
1041
1042     v.type = FcTypeMatrix;
1043     v.u.m = s;
1044     return FcPatternAdd (p, object, v, FcTrue);
1045 }
1046
1047
1048 FcBool
1049 FcPatternAddBool (FcPattern *p, const char *object, FcBool b)
1050 {
1051     FcValue     v;
1052
1053     v.type = FcTypeBool;
1054     v.u.b = b;
1055     return FcPatternAdd (p, object, v, FcTrue);
1056 }
1057
1058 FcBool
1059 FcPatternAddCharSet (FcPattern *p, const char *object, const FcCharSet *c)
1060 {
1061     FcValue     v;
1062
1063     v.type = FcTypeCharSet;
1064     v.u.c = (FcCharSet *)c;
1065     return FcPatternAdd (p, object, v, FcTrue);
1066 }
1067
1068 FcBool
1069 FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
1070 {
1071     FcValue     v;
1072
1073     v.type = FcTypeFTFace;
1074     v.u.f = (void *) f;
1075     return FcPatternAdd (p, object, v, FcTrue);
1076 }
1077
1078 FcBool
1079 FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
1080 {
1081     FcValue     v;
1082
1083     v.type = FcTypeLangSet;
1084     v.u.l = (FcLangSet *)ls;
1085     return FcPatternAdd (p, object, v, FcTrue);
1086 }
1087
1088 FcResult
1089 FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
1090 {
1091     FcPatternElt   *e;
1092     FcValueListPtr l;
1093
1094     e = FcPatternFindElt (p, object);
1095     if (!e)
1096         return FcResultNoMatch;
1097     for (l = e->values; FcValueListPtrU(l); l = FcValueListPtrU(l)->next)
1098     {
1099         if (!id)
1100         {
1101             *v = FcValueCanonicalize(&FcValueListPtrU(l)->value);
1102             return FcResultMatch;
1103         }
1104         id--;
1105     }
1106     return FcResultNoId;
1107 }
1108
1109 FcResult
1110 FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
1111 {
1112     FcValue     v;
1113     FcResult    r;
1114
1115     r = FcPatternGet (p, object, id, &v);
1116     if (r != FcResultMatch)
1117         return r;
1118     switch (v.type) {
1119     case FcTypeDouble:
1120         *i = (int) v.u.d;
1121         break;
1122     case FcTypeInteger:
1123         *i = v.u.i;
1124         break;
1125     default:
1126         return FcResultTypeMismatch;
1127     }
1128     return FcResultMatch;
1129 }
1130
1131 FcResult
1132 FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
1133 {
1134     FcValue     v;
1135     FcResult    r;
1136
1137     r = FcPatternGet (p, object, id, &v);
1138     if (r != FcResultMatch)
1139         return r;
1140     switch (v.type) {
1141     case FcTypeDouble:
1142         *d = v.u.d;
1143         break;
1144     case FcTypeInteger:
1145         *d = (double) v.u.i;
1146         break;
1147     default:
1148         return FcResultTypeMismatch;
1149     }
1150     return FcResultMatch;
1151 }
1152
1153 FcResult
1154 FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
1155 {
1156     FcValue     v;
1157     FcResult    r;
1158
1159     r = FcPatternGet (p, object, id, &v);
1160     if (r != FcResultMatch)
1161         return r;
1162     if (v.type != FcTypeString)
1163         return FcResultTypeMismatch;
1164
1165     if (FcObjectToPtr(object) == FcObjectToPtr(FC_FILE))
1166     {
1167         const char *fn, *fpath;
1168         FcChar8 *fname;
1169         int size;
1170
1171         fn = FcPatternFindFullFname(p);
1172         if (fn)
1173         {
1174             *s = (FcChar8 *) fn;
1175             return FcResultMatch;
1176         }
1177
1178         if (!p->bank)
1179         {
1180             *s = (FcChar8 *) v.u.s;
1181             return FcResultMatch;
1182         }
1183
1184         fpath = FcCacheFindBankDir (p->bank);
1185         size = strlen((char*)fpath) + 1 + strlen ((char *)v.u.s) + 1;
1186         fname = malloc (size);
1187         if (!fname)
1188             return FcResultOutOfMemory;
1189
1190         FcMemAlloc (FC_MEM_STRING, size);
1191         strcpy ((char *)fname, (char *)fpath);
1192         strcat ((char *)fname, "/");
1193         strcat ((char *)fname, (char *)v.u.s);
1194
1195         FcPatternAddFullFname (p, (const char *)fname);
1196         *s = (FcChar8 *)fname;
1197         return FcResultMatch;
1198     }
1199
1200     *s = (FcChar8 *) v.u.s;
1201     return FcResultMatch;
1202 }
1203
1204 FcResult
1205 FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
1206 {
1207     FcValue     v;
1208     FcResult    r;
1209
1210     r = FcPatternGet (p, object, id, &v);
1211     if (r != FcResultMatch)
1212         return r;
1213     if (v.type != FcTypeMatrix)
1214         return FcResultTypeMismatch;
1215     *m = (FcMatrix *)v.u.m;
1216     return FcResultMatch;
1217 }
1218
1219
1220 FcResult
1221 FcPatternGetBool(const FcPattern *p, const char *object, int id, FcBool *b)
1222 {
1223     FcValue     v;
1224     FcResult    r;
1225
1226     r = FcPatternGet (p, object, id, &v);
1227     if (r != FcResultMatch)
1228         return r;
1229     if (v.type != FcTypeBool)
1230         return FcResultTypeMismatch;
1231     *b = v.u.b;
1232     return FcResultMatch;
1233 }
1234
1235 FcResult
1236 FcPatternGetCharSet(const FcPattern *p, const char *object, int id, FcCharSet **c)
1237 {
1238     FcValue     v;
1239     FcResult    r;
1240
1241     r = FcPatternGet (p, object, id, &v);
1242     if (r != FcResultMatch)
1243         return r;
1244     if (v.type != FcTypeCharSet)
1245         return FcResultTypeMismatch;
1246     *c = (FcCharSet *)v.u.c;
1247     return FcResultMatch;
1248 }
1249
1250 FcResult
1251 FcPatternGetFTFace(const FcPattern *p, const char *object, int id, FT_Face *f)
1252 {
1253     FcValue     v;
1254     FcResult    r;
1255
1256     r = FcPatternGet (p, object, id, &v);
1257     if (r != FcResultMatch)
1258         return r;
1259     if (v.type != FcTypeFTFace)
1260         return FcResultTypeMismatch;
1261     *f = (FT_Face) v.u.f;
1262     return FcResultMatch;
1263 }
1264
1265 FcResult
1266 FcPatternGetLangSet(const FcPattern *p, const char *object, int id, FcLangSet **ls)
1267 {
1268     FcValue     v;
1269     FcResult    r;
1270
1271     r = FcPatternGet (p, object, id, &v);
1272     if (r != FcResultMatch)
1273         return r;
1274     if (v.type != FcTypeLangSet)
1275         return FcResultTypeMismatch;
1276     *ls = (FcLangSet *)v.u.l;
1277     return FcResultMatch;
1278 }
1279
1280 FcPattern *
1281 FcPatternDuplicate (const FcPattern *orig)
1282 {
1283     FcPattern       *new;
1284     FcPatternElt    *e;
1285     int             i;
1286     FcValueListPtr  l;
1287
1288     new = FcPatternCreate ();
1289     if (!new)
1290         goto bail0;
1291
1292     e = FcPatternEltU(orig->elts);
1293
1294     for (i = 0; i < orig->num; i++)
1295     {
1296         for (l = (e + i)->values;
1297              FcValueListPtrU(l);
1298              l = FcValueListPtrU(l)->next)
1299             if (!FcPatternAdd (new, FcObjectPtrU((e + i)->object),
1300                                FcValueCanonicalize(&FcValueListPtrU(l)->value),
1301                                FcTrue))
1302                 goto bail1;
1303     }
1304     FcPatternTransferFullFname (new, orig);
1305
1306     return new;
1307
1308 bail1:
1309     FcPatternDestroy (new);
1310 bail0:
1311     return 0;
1312 }
1313
1314 void
1315 FcPatternReference (FcPattern *p)
1316 {
1317     if (p->ref != FC_REF_CONSTANT)
1318         p->ref++;
1319 }
1320
1321 FcPattern *
1322 FcPatternVaBuild (FcPattern *orig, va_list va)
1323 {
1324     FcPattern   *ret;
1325
1326     FcPatternVapBuild (ret, orig, va);
1327     return ret;
1328 }
1329
1330 FcPattern *
1331 FcPatternBuild (FcPattern *orig, ...)
1332 {
1333     va_list     va;
1334
1335     va_start (va, orig);
1336     FcPatternVapBuild (orig, orig, va);
1337     va_end (va);
1338     return orig;
1339 }
1340
1341 /*
1342  * Add all of the elements in 's' to 'p'
1343  */
1344 FcBool
1345 FcPatternAppend (FcPattern *p, FcPattern *s)
1346 {
1347     int             i;
1348     FcPatternElt    *e;
1349     FcValueListPtr  v;
1350
1351     for (i = 0; i < s->num; i++)
1352     {
1353         e = FcPatternEltU(s->elts)+i;
1354         for (v = e->values; FcValueListPtrU(v);
1355              v = FcValueListPtrU(v)->next)
1356         {
1357             if (!FcPatternAddWithBinding (p, FcObjectPtrU(e->object),
1358                                           FcValueCanonicalize(&FcValueListPtrU(v)->value),
1359                                           FcValueListPtrU(v)->binding, FcTrue))
1360                 return FcFalse;
1361         }
1362     }
1363     return FcTrue;
1364 }
1365
1366 #define OBJECT_HASH_SIZE    31
1367 static struct objectBucket {
1368     struct objectBucket *next;
1369     FcChar32            hash;
1370 } *FcObjectBuckets[OBJECT_HASH_SIZE];
1371
1372 static FcBool
1373 FcStrHashed (const FcChar8 *name)
1374 {
1375     FcChar32            hash = FcStringHash (name);
1376     struct objectBucket **p;
1377     struct objectBucket *b;
1378
1379     for (p = &FcObjectBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1380         if (b->hash == hash && !strcmp ((char *)name, (char *) (b + 1)))
1381             return FcTrue;
1382     return FcFalse;
1383 }
1384
1385 const FcChar8 *
1386 FcStrStaticName (const FcChar8 *name)
1387 {
1388     FcChar32            hash = FcStringHash (name);
1389     struct objectBucket **p;
1390     struct objectBucket *b;
1391     int                 size;
1392
1393     for (p = &FcObjectBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1394         if (b->hash == hash && !strcmp ((char *)name, (char *) (b + 1)))
1395             return (FcChar8 *) (b + 1);
1396     size = sizeof (struct objectBucket) + strlen ((char *)name) + 1;
1397     b = malloc (size + sizeof (int));
1398     /* workaround glibc bug which reads strlen in groups of 4 */
1399     FcMemAlloc (FC_MEM_STATICSTR, size + sizeof (int));
1400     if (!b)
1401         return NULL;
1402     b->next = 0;
1403     b->hash = hash;
1404     strcpy ((char *) (b + 1), (char *)name);
1405     *p = b;
1406     return (FcChar8 *) (b + 1);
1407 }
1408
1409 static void
1410 FcStrStaticNameFini (void)
1411 {
1412     int i, size;
1413     struct objectBucket *b, *next;
1414     char *name;
1415
1416     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1417     {
1418         for (b = FcObjectBuckets[i]; b; b = next)
1419         {
1420             next = b->next;
1421             name = (char *) (b + 1);
1422             size = sizeof (struct objectBucket) + strlen (name) + 1;
1423             FcMemFree (FC_MEM_STATICSTR, size);
1424             free (b);
1425         }
1426         FcObjectBuckets[i] = 0;
1427     }
1428 }
1429
1430 void
1431 FcPatternFini (void)
1432 {
1433     FcPatternBaseThawAll ();
1434     FcValueListThawAll ();
1435     FcStrStaticNameFini ();
1436     FcObjectStaticNameFini ();
1437 }
1438
1439 static FcPatternEltPtr
1440 FcPatternEltPtrCreateDynamic (FcPatternElt * e)
1441 {
1442     FcPatternEltPtr new;
1443     new.bank = FC_BANK_DYNAMIC;
1444     new.u.dyn = e;
1445     return new;
1446 }
1447
1448 static FcPatternEltPtr
1449 FcPatternEltPtrCreateStatic (int bank, int i)
1450 {
1451     FcPatternEltPtr new;
1452     new.bank = bank;
1453     new.u.stat = i;
1454     return new;
1455 }
1456
1457 static void
1458 FcStrNewBank (void);
1459 static int
1460 FcStrNeededBytes (const FcChar8 * s);
1461 static int
1462 FcStrNeededBytesAlign (void);
1463 static void *
1464 FcStrDistributeBytes (FcCache * metadata, void * block_ptr);
1465 static const FcChar8 *
1466 FcStrSerialize (int bank, const FcChar8 * s);
1467 static void *
1468 FcStrUnserialize (FcCache * metadata, void *block_ptr);
1469
1470 static void
1471 FcValueListNewBank (void);
1472 static int
1473 FcValueListNeededBytes (FcValueList * vl);
1474 static int
1475 FcValueListNeededBytesAlign (void);
1476 static void *
1477 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr);
1478 static FcValueListPtr
1479 FcValueListSerialize(int bank, FcValueList *pi);
1480 static void *
1481 FcValueListUnserialize (FcCache * metadata, void *block_ptr);
1482
1483
1484 void
1485 FcPatternNewBank (void)
1486 {
1487     fcpattern_count = 0;
1488     fcpatternelt_count = 0;
1489
1490     FcStrNewBank();
1491     FcValueListNewBank();
1492 }
1493
1494 int
1495 FcPatternNeededBytes (FcPattern * p)
1496 {
1497     int i, cum = 0, c;
1498
1499     fcpattern_count++;
1500     fcpatternelt_count += p->num;
1501
1502     for (i = 0; i < p->num; i++)
1503     {
1504         c = FcValueListNeededBytes (FcValueListPtrU
1505                                     (((FcPatternEltU(p->elts)+i)->values)));
1506         if (c < 0)
1507             return c;
1508         cum += c;
1509     }
1510
1511     return cum + sizeof (FcPattern) + sizeof(FcPatternElt)*p->num;
1512 }
1513
1514 int
1515 FcPatternNeededBytesAlign (void)
1516 {
1517     return __alignof__ (FcPattern) + __alignof__ (FcPatternElt) +
1518         FcValueListNeededBytesAlign ();
1519 }
1520
1521 static FcBool
1522 FcPatternEnsureBank (int bi)
1523 {
1524     FcPattern **pp;
1525     FcPatternElt **ep;
1526     int i;
1527
1528     if (!_fcPatterns || fcpattern_bank_count <= bi)
1529     {
1530         int new_count = bi + 4;
1531         pp = realloc (_fcPatterns, sizeof (FcPattern *) * new_count);
1532         if (!pp)
1533             return 0;
1534
1535         FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern *) * new_count);
1536         _fcPatterns = pp;
1537
1538         ep = realloc (_fcPatternElts, sizeof (FcPatternElt *) * new_count);
1539         if (!ep)
1540             return 0;
1541
1542         FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt *) * new_count);
1543         _fcPatternElts = ep;
1544
1545         for (i = fcpattern_bank_count; i < new_count; i++)
1546         {
1547             _fcPatterns[i] = 0;
1548             _fcPatternElts[i] = 0;
1549         }
1550
1551         fcpattern_bank_count = new_count;
1552     }
1553
1554     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * fcpattern_count);
1555     return FcTrue;
1556 }
1557
1558 void *
1559 FcPatternDistributeBytes (FcCache * metadata, void * block_ptr)
1560 {
1561     int bi = FcCacheBankToIndex(metadata->bank);
1562
1563     if (!FcPatternEnsureBank(bi))
1564         return 0;
1565
1566     fcpattern_ptr = 0;
1567     block_ptr = ALIGN(block_ptr, FcPattern);
1568     _fcPatterns[bi] = (FcPattern *)block_ptr;
1569     block_ptr = (void *)((char *)block_ptr +
1570                          (sizeof (FcPattern) * fcpattern_count));
1571
1572     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt) * fcpatternelt_count);
1573     fcpatternelt_ptr = 0;
1574     block_ptr = ALIGN(block_ptr, FcPatternElt);
1575     _fcPatternElts[bi] = (FcPatternElt *)block_ptr;
1576     block_ptr = (void *)((char *)block_ptr +
1577                          (sizeof (FcPatternElt) * fcpatternelt_count));
1578
1579     metadata->pattern_count = fcpattern_count;
1580     metadata->patternelt_count = fcpatternelt_count;
1581
1582     block_ptr = FcStrDistributeBytes (metadata, block_ptr);
1583     block_ptr = FcValueListDistributeBytes (metadata, block_ptr);
1584     return block_ptr;
1585 }
1586
1587 FcPattern *
1588 FcPatternSerialize (int bank, FcPattern *old)
1589 {
1590     FcPattern *p;
1591     FcPatternElt *e, *nep;
1592     FcValueList * nv;
1593     FcValueListPtr v, nv_head, nvp;
1594     int i, elts, bi = FcCacheBankToIndex(bank);
1595
1596     p = &_fcPatterns[bi][fcpattern_ptr++];
1597     p->bank = bank;
1598     elts = fcpatternelt_ptr;
1599     nep = &_fcPatternElts[bi][elts];
1600     if (!nep)
1601         return FcFalse;
1602
1603     fcpatternelt_ptr += old->num;
1604
1605     for (e = FcPatternEltU(old->elts), i=0; i < old->num; i++, e++)
1606     {
1607         v = e->values;
1608         nvp = nv_head = FcValueListSerialize(bank, FcValueListPtrU(v));
1609         if (!FcValueListPtrU(nv_head))
1610             return 0;
1611         nv = FcValueListPtrU(nvp);
1612
1613         for (;
1614              FcValueListPtrU(v);
1615              v = FcValueListPtrU(v)->next,
1616                  nv = FcValueListPtrU(nv->next))
1617         {
1618
1619             if (FcValueListPtrU(FcValueListPtrU(v)->next))
1620             {
1621                 nvp = FcValueListSerialize
1622                     (bank, FcValueListPtrU(FcValueListPtrU(v)->next));
1623                 nv->next = nvp;
1624             }
1625         }
1626
1627         nep[i].values = nv_head;
1628         nep[i].object = e->object;
1629     }
1630
1631     p->elts = old->elts;
1632     p->elts = FcPatternEltPtrCreateStatic(bank, elts);
1633     p->size = old->num;
1634     p->num = old->num;
1635     p->ref = FC_REF_CONSTANT;
1636     return p;
1637 }
1638
1639 void *
1640 FcPatternUnserialize (FcCache * metadata, void *block_ptr)
1641 {
1642     int bi = FcCacheBankToIndex(metadata->bank);
1643     if (!FcPatternEnsureBank(bi))
1644         return FcFalse;
1645
1646     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * metadata->pattern_count);
1647     block_ptr = ALIGN(block_ptr, FcPattern);
1648     _fcPatterns[bi] = (FcPattern *)block_ptr;
1649     block_ptr = (void *)((char *)block_ptr +
1650                          (sizeof (FcPattern) * metadata->pattern_count));
1651
1652     FcMemAlloc (FC_MEM_PATELT,
1653                 sizeof (FcPatternElt) * metadata->patternelt_count);
1654     block_ptr = ALIGN(block_ptr, FcPatternElt);
1655     _fcPatternElts[bi] = (FcPatternElt *)block_ptr;
1656     block_ptr = (void *)((char *)block_ptr +
1657                          (sizeof (FcPatternElt) * metadata->patternelt_count));
1658
1659     block_ptr = FcStrUnserialize (metadata, block_ptr);
1660     block_ptr = FcValueListUnserialize (metadata, block_ptr);
1661
1662     return block_ptr;
1663 }
1664
1665 static void
1666 FcValueListNewBank (void)
1667 {
1668     fcvaluelist_count = 0;
1669
1670     FcCharSetNewBank();
1671     FcLangSetNewBank();
1672 }
1673
1674 static int
1675 FcValueListNeededBytes (FcValueList *p)
1676 {
1677     FcValueList *vl;
1678     int cum = 0;
1679
1680     for (vl = p;
1681          vl;
1682          vl = FcValueListPtrU(vl->next))
1683     {
1684         FcValue v = FcValueCanonicalize(&vl->value); // unserialize just in case
1685
1686         switch (v.type)
1687         {
1688         case FcTypeCharSet:
1689             cum += FcCharSetNeededBytes(v.u.c);
1690             break;
1691         case FcTypeLangSet:
1692             cum += FcLangSetNeededBytes(v.u.l);
1693             break;
1694         case FcTypeString:
1695             cum += FcStrNeededBytes(v.u.s);
1696         default:
1697             break;
1698         }
1699         fcvaluelist_count++;
1700         cum += sizeof (FcValueList);
1701     }
1702
1703     return cum;
1704 }
1705
1706 static int
1707 FcValueListNeededBytesAlign (void)
1708 {
1709     return FcCharSetNeededBytesAlign() + FcLangSetNeededBytesAlign() +
1710         FcStrNeededBytesAlign() + __alignof__ (FcValueList);
1711 }
1712
1713 static FcBool
1714 FcValueListEnsureBank (int bi)
1715 {
1716     FcValueList **pvl;
1717
1718     if (!_fcValueLists || fcvaluelist_bank_count <= bi)
1719     {
1720         int new_count = bi + 2, i;
1721
1722         pvl = realloc (_fcValueLists, sizeof (FcValueList *) * new_count);
1723         if (!pvl)
1724             return FcFalse;
1725
1726         FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList *) * new_count);
1727
1728         _fcValueLists = pvl;
1729         for (i = fcvaluelist_bank_count; i < new_count; i++)
1730             _fcValueLists[i] = 0;
1731
1732         fcvaluelist_bank_count = new_count;
1733     }
1734     return FcTrue;
1735 }
1736
1737 static void *
1738 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr)
1739 {
1740     int bi = FcCacheBankToIndex(metadata->bank);
1741
1742     if (!FcValueListEnsureBank(bi))
1743         return 0;
1744
1745     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList) * fcvaluelist_count);
1746     fcvaluelist_ptr = 0;
1747     block_ptr = ALIGN(block_ptr, FcValueList);
1748     _fcValueLists[bi] = (FcValueList *)block_ptr;
1749     block_ptr = (void *)((char *)block_ptr +
1750                          (sizeof (FcValueList) * fcvaluelist_count));
1751     metadata->valuelist_count = fcvaluelist_count;
1752
1753     block_ptr = FcCharSetDistributeBytes(metadata, block_ptr);
1754     block_ptr = FcLangSetDistributeBytes(metadata, block_ptr);
1755
1756     return block_ptr;
1757 }
1758
1759 static FcValueListPtr
1760 FcValueListSerialize(int bank, FcValueList *pi)
1761 {
1762     FcValueListPtr new;
1763     FcValue * v;
1764     int bi = FcCacheBankToIndex(bank);
1765
1766     if (!pi)
1767     {
1768         new.bank = FC_BANK_DYNAMIC;
1769         new.u.dyn = 0;
1770         return new;
1771     }
1772
1773     _fcValueLists[bi][fcvaluelist_ptr] = *pi;
1774     new.bank = bank;
1775     new.u.stat = fcvaluelist_ptr++;
1776     _fcValueLists[bi][new.u.stat].value = FcValueCanonicalize (&pi->value);
1777     v = &_fcValueLists[bi][new.u.stat].value;
1778     switch (v->type)
1779     {
1780     case FcTypeString:
1781         if (v->u.s)
1782         {
1783             const FcChar8 * s = FcStrSerialize(bank, v->u.s);
1784             if (!s)
1785                 return FcValueListPtrCreateDynamic(pi);
1786             v->u.s_off = s - (const FcChar8 *)v;
1787             v->type |= FC_STORAGE_STATIC;
1788         }
1789         break;
1790     case FcTypeMatrix:
1791         break;
1792     case FcTypeCharSet:
1793         if (v->u.c)
1794         {
1795             FcCharSet * c = FcCharSetSerialize(bank, (FcCharSet *)v->u.c);
1796             if (!c)
1797                 return FcValueListPtrCreateDynamic(pi);
1798             v->u.c_off = (char *)c - (char *)v;
1799             v->type |= FC_STORAGE_STATIC;
1800         }
1801         break;
1802     case FcTypeLangSet:
1803         if (v->u.l)
1804         {
1805             FcLangSet * l = FcLangSetSerialize(bank, (FcLangSet *)v->u.l);
1806             if (!l)
1807                 return FcValueListPtrCreateDynamic(pi);
1808             v->u.l_off = (char *)l - (char *)v;
1809             v->type |= FC_STORAGE_STATIC;
1810         }
1811         break;
1812     default:
1813         break;
1814     }
1815     return new;
1816 }
1817
1818 static void *
1819 FcValueListUnserialize (FcCache * metadata, void *block_ptr)
1820 {
1821     int bi = FcCacheBankToIndex(metadata->bank);
1822
1823     if (!FcValueListEnsureBank(bi))
1824         return 0;
1825
1826     FcMemAlloc (FC_MEM_VALLIST,
1827                 sizeof (FcValueList) * metadata->valuelist_count);
1828     block_ptr = ALIGN(block_ptr, FcValueList);
1829     _fcValueLists[bi] = (FcValueList *)block_ptr;
1830     block_ptr = (void *)((char *)block_ptr +
1831                          (sizeof (FcValueList) * metadata->valuelist_count));
1832
1833     block_ptr = FcCharSetUnserialize(metadata, block_ptr);
1834     block_ptr = FcLangSetUnserialize(metadata, block_ptr);
1835
1836     return block_ptr;
1837 }
1838
1839 FcValueListPtr
1840 FcValueListPtrCreateDynamic(FcValueList * p)
1841 {
1842     FcValueListPtr r;
1843
1844     r.bank = FC_BANK_DYNAMIC;
1845     r.u.dyn = p;
1846     return r;
1847 }
1848
1849 static FcChar8 ** static_strs;
1850 static int static_str_bank_count = 0, fcstr_ptr, fcstr_count;
1851
1852 static struct objectBucket *FcStrBuckets[OBJECT_HASH_SIZE];
1853
1854 static void
1855 FcStrNewBank (void)
1856 {
1857     int i, size;
1858     struct objectBucket *b, *next;
1859     char *name;
1860
1861     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1862     {
1863         for (b = FcStrBuckets[i]; b; b = next)
1864         {
1865             next = b->next;
1866             name = (char *) (b + 1);
1867             size = sizeof (struct objectBucket) + strlen (name) + 1;
1868             FcMemFree (FC_MEM_STATICSTR, size);
1869             free (b);
1870         }
1871         FcStrBuckets[i] = 0;
1872     }
1873
1874     fcstr_count = 0;
1875 }
1876
1877 static int
1878 FcStrNeededBytes (const FcChar8 * s)
1879 {
1880     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1881     struct objectBucket **p;
1882     struct objectBucket *b;
1883     int                 size;
1884
1885     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1886         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1887             return 0;
1888     size = sizeof (struct objectBucket) + strlen ((char *)s) + 1 + sizeof(char *);
1889     b = malloc (size);
1890     FcMemAlloc (FC_MEM_STATICSTR, size);
1891     if (!b)
1892         return -1;
1893     b->next = 0;
1894     b->hash = hash;
1895     strcpy ((char *) (b + 1), (char *)s);
1896
1897     /* Yes, the following line is convoluted.  However, it is
1898      * incorrect to replace the with a memset, because the C
1899      * specification doesn't guarantee that the null pointer is
1900      * the same as the zero bit pattern. */
1901     *(char **)((char *) (b + 1) + strlen((char *)s) + 1) = 0;
1902     *p = b;
1903
1904     fcstr_count += strlen((char *)s) + 1;
1905     return strlen((char *)s) + 1;
1906 }
1907
1908 static int
1909 FcStrNeededBytesAlign (void)
1910 {
1911     return __alignof__ (char);
1912 }
1913
1914 static FcBool
1915 FcStrEnsureBank (int bi)
1916 {
1917     FcChar8 ** ss;
1918
1919     if (!static_strs || static_str_bank_count <= bi)
1920     {
1921         int new_count = bi + 4, i;
1922         ss = realloc (static_strs, sizeof (const char *) * new_count);
1923         if (!ss)
1924             return FcFalse;
1925
1926         FcMemAlloc (FC_MEM_STRING, sizeof (const char *) * (new_count-static_str_bank_count));
1927         static_strs = ss;
1928
1929         for (i = static_str_bank_count; i < new_count; i++)
1930             static_strs[i] = 0;
1931         static_str_bank_count = new_count;
1932     }
1933     return FcTrue;
1934 }
1935
1936 static void *
1937 FcStrDistributeBytes (FcCache * metadata, void * block_ptr)
1938 {
1939     int bi = FcCacheBankToIndex(metadata->bank);
1940     if (!FcStrEnsureBank(bi))
1941         return 0;
1942
1943     FcMemAlloc (FC_MEM_STRING, sizeof (char) * fcstr_count);
1944     block_ptr = ALIGN (block_ptr, FcChar8);
1945     static_strs[bi] = (FcChar8 *)block_ptr;
1946     block_ptr = (void *)((char *)block_ptr + (sizeof (char) * fcstr_count));
1947     metadata->str_count = fcstr_count;
1948     fcstr_ptr = 0;
1949
1950     return block_ptr;
1951 }
1952
1953 static const FcChar8 *
1954 FcStrSerialize (int bank, const FcChar8 * s)
1955 {
1956     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1957     struct objectBucket **p;
1958     struct objectBucket *b;
1959     int bi = FcCacheBankToIndex(bank);
1960
1961     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1962         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1963         {
1964             FcChar8 * t = *(FcChar8 **)(((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1);
1965             if (!t)
1966             {
1967                 strcpy((char *)(static_strs[bi] + fcstr_ptr), (char *)s);
1968                 *(FcChar8 **)((FcChar8 *) (b + 1) + strlen((char *)s) + 1) = (static_strs[bi] + fcstr_ptr);
1969                 fcstr_ptr += strlen((char *)s) + 1;
1970                 t = *(FcChar8 **)(((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1);
1971             }
1972             return t;
1973         }
1974     return 0;
1975 }
1976
1977 static void *
1978 FcStrUnserialize (FcCache * metadata, void *block_ptr)
1979 {
1980     int bi = FcCacheBankToIndex(metadata->bank);
1981     if (!FcStrEnsureBank(bi))
1982         return 0;
1983
1984     FcMemAlloc (FC_MEM_STRING, sizeof (char) * metadata->str_count);
1985     block_ptr = ALIGN (block_ptr, FcChar8);
1986     static_strs[bi] = (FcChar8 *)block_ptr;
1987     block_ptr = (void *)((char *)block_ptr +
1988                          (sizeof (char) * metadata->str_count));
1989
1990     return block_ptr;
1991 }
1992
1993 /* we don't store these in the FcPattern itself because
1994  * we don't want to serialize the directory names */
1995
1996 /* I suppose this should be cleaned, too... */
1997 typedef struct _FcPatternDirMapping {
1998     const FcPattern     *p;
1999     const char *fname;
2000 } FcPatternDirMapping;
2001
2002 #define PATTERNDIR_HASH_SIZE    31
2003 static struct patternDirBucket {
2004     struct patternDirBucket     *next;
2005     FcPatternDirMapping         m;
2006 } FcPatternDirBuckets[PATTERNDIR_HASH_SIZE];
2007
2008 void
2009 FcPatternAddFullFname (const FcPattern *p, const char *fname)
2010 {
2011     struct patternDirBucket     *pb;
2012
2013     /* N.B. FcPatternHash fails, since it's contents-based, not
2014      * address-based, and we're in the process of mutating the FcPattern. */
2015     for (pb = &FcPatternDirBuckets
2016              [((int)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
2017          pb->m.p != p && pb->next;
2018          pb = pb->next)
2019         ;
2020
2021     if (pb->m.p == p)
2022     {
2023         pb->m.fname = fname;
2024         return;
2025     }
2026
2027     pb->next = malloc (sizeof (struct patternDirBucket));
2028     if (!pb->next)
2029         return;
2030     FcMemAlloc (FC_MEM_CACHE, sizeof (struct patternDirBucket));
2031
2032     pb->next->next = 0;
2033     pb->next->m.p = p;
2034     pb->next->m.fname = fname;
2035 }
2036
2037 static const char *
2038 FcPatternFindFullFname (const FcPattern *p)
2039 {
2040     struct patternDirBucket     *pb;
2041
2042     for (pb = &FcPatternDirBuckets
2043              [((int)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
2044          pb; pb = pb->next)
2045         if (pb->m.p == p)
2046             return pb->m.fname;
2047
2048     return 0;
2049 }
2050
2051 void
2052 FcPatternTransferFullFname (const FcPattern *new, const FcPattern *orig)
2053 {
2054     FcChar8 * s;
2055     FcPatternGetString (orig, FC_FILE, 0, &s);
2056     FcPatternAddFullFname (new,
2057                            (char *)FcStrCopy
2058                            ((FcChar8 *)FcPatternFindFullFname(orig)));
2059 }