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     if (value.type == FcTypeString)
 878     {
 879         value.u.s = FcStrStaticName (value.u.s);
 880         if (!value.u.s)
 881             value.type = FcTypeVoid;
 882     }
 883     else
 884         value = FcValueSave (value);
 885     if (value.type == FcTypeVoid)
 886         goto bail1;
 887
 888     /* quick and dirty hack to enable FcCompareFamily/FcCompareString
 889      * speedup: only allow strings to be added under the FC_FAMILY,
 890      * FC_FOUNDRY, FC_STYLE, FC_RASTERIZER keys.
 891      * and charsets under FC_CHARSET key.
 892      * This is slightly semantically different from the old behaviour,
 893      * but fonts shouldn't be getting non-strings here anyway.
 894      * a better hack would use FcBaseObjectTypes to check all objects. */
 895     objectPtr = FcObjectToPtr(object);
 896     if ((objectPtr == FcObjectToPtr(FC_FAMILY)
 897          || objectPtr == FcObjectToPtr(FC_FOUNDRY)
 898          || objectPtr == FcObjectToPtr(FC_STYLE)
 899          || objectPtr == FcObjectToPtr(FC_RASTERIZER))
 900         && value.type != FcTypeString)
 901         goto bail1;
 902     if (objectPtr == FcObjectToPtr(FC_CHARSET)
 903         && value.type != FcTypeCharSet)
 904         goto bail1;
 905
 906     FcValueListPtrU(new)->value = value;
 907     FcValueListPtrU(new)->binding = binding;
 908     FcValueListPtrU(new)->next = FcValueListPtrCreateDynamic(0);
 909
 910     e = FcPatternInsertElt (p, object);
 911     if (!e)
 912         goto bail2;
 913
 914     if (append)
 915     {
 916         for (prev = &e->values; FcValueListPtrU(*prev); prev = &FcValueListPtrU(*prev)->next)
 917             ;
 918         *prev = new;
 919     }
 920     else
 921     {
 922         FcValueListPtrU(new)->next = e->values;
 923         e->values = new;
 924     }
 925
 926     return FcTrue;
 927
 928 bail2:
 929     switch (value.type) {
 930     case FcTypeString:
 931         FcStrFree ((FcChar8 *) value.u.s);
 932         break;
 933     case FcTypeMatrix:
 934         FcMatrixFree ((FcMatrix *) value.u.m);
 935         break;
 936     case FcTypeCharSet:
 937         FcCharSetDestroy ((FcCharSet *) value.u.c);
 938         break;
 939     case FcTypeLangSet:
 940         FcLangSetDestroy ((FcLangSet *) value.u.l);
 941         break;
 942     default:
 943         break;
 944     }
 945 bail1:
 946     FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 947     free (FcValueListPtrU(new));
 948 bail0:
 949     return FcFalse;
 950 }
 951
 952 FcBool
 953 FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
 954 {
 955     return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
 956 }
 957
 958 FcBool
 959 FcPatternAddWeak  (FcPattern *p, const char *object, FcValue value, FcBool append)
 960 {
 961     return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
 962 }
 963
 964 FcBool
 965 FcPatternDel (FcPattern *p, const char *object)
 966 {
 967     FcPatternElt   *e;
 968
 969     e = FcPatternFindElt (p, object);
 970     if (!e)
 971         return FcFalse;
 972
 973     /* destroy value */
 974     FcValueListDestroy (e->values);
 975
 976     /* shuffle existing ones down */
 977     memmove (e, e+1,
 978              (FcPatternEltU(p->elts) + p->num - (e + 1)) *
 979              sizeof (FcPatternElt));
 980     p->num--;
 981     (FcPatternEltU(p->elts)+p->num)->object = 0;
 982     (FcPatternEltU(p->elts)+p->num)->values = FcValueListPtrCreateDynamic(0);
 983     return FcTrue;
 984 }
 985
 986 FcBool
 987 FcPatternRemove (FcPattern *p, const char *object, int id)
 988 {
 989     FcPatternElt    *e;
 990     FcValueListPtr  *prev, l;
 991
 992     e = FcPatternFindElt (p, object);
 993     if (!e)
 994         return FcFalse;
 995     for (prev = &e->values;
 996          FcValueListPtrU(l = *prev);
 997          prev = &FcValueListPtrU(l)->next)
 998     {
 999         if (!id)
1000         {
1001             *prev = FcValueListPtrU(l)->next;
1002             FcValueListPtrU(l)->next = FcValueListPtrCreateDynamic(0);
1003             FcValueListDestroy (l);
1004             if (!FcValueListPtrU(e->values))
1005                 FcPatternDel (p, object);
1006             return FcTrue;
1007         }
1008         id--;
1009     }
1010     return FcFalse;
1011 }
1012
1013 FcBool
1014 FcPatternAddInteger (FcPattern *p, const char *object, int i)
1015 {
1016     FcValue     v;
1017
1018     v.type = FcTypeInteger;
1019     v.u.i = i;
1020     return FcPatternAdd (p, object, v, FcTrue);
1021 }
1022
1023 FcBool
1024 FcPatternAddDouble (FcPattern *p, const char *object, double d)
1025 {
1026     FcValue     v;
1027
1028     v.type = FcTypeDouble;
1029     v.u.d = d;
1030     return FcPatternAdd (p, object, v, FcTrue);
1031 }
1032
1033
1034 FcBool
1035 FcPatternAddString (FcPattern *p, const char *object, const FcChar8 *s)
1036 {
1037     FcValue     v;
1038
1039     if (!s)
1040     {
1041         v.type = FcTypeVoid;
1042         v.u.s = 0;
1043         return FcPatternAdd (p, object, v, FcTrue);
1044     }
1045
1046     v.type = FcTypeString;
1047     v.u.s = FcStrStaticName(s);
1048     return FcPatternAdd (p, object, v, FcTrue);
1049 }
1050
1051 FcBool
1052 FcPatternAddMatrix (FcPattern *p, const char *object, const FcMatrix *s)
1053 {
1054     FcValue     v;
1055
1056     v.type = FcTypeMatrix;
1057     v.u.m = s;
1058     return FcPatternAdd (p, object, v, FcTrue);
1059 }
1060
1061
1062 FcBool
1063 FcPatternAddBool (FcPattern *p, const char *object, FcBool b)
1064 {
1065     FcValue     v;
1066
1067     v.type = FcTypeBool;
1068     v.u.b = b;
1069     return FcPatternAdd (p, object, v, FcTrue);
1070 }
1071
1072 FcBool
1073 FcPatternAddCharSet (FcPattern *p, const char *object, const FcCharSet *c)
1074 {
1075     FcValue     v;
1076
1077     v.type = FcTypeCharSet;
1078     v.u.c = (FcCharSet *)c;
1079     return FcPatternAdd (p, object, v, FcTrue);
1080 }
1081
1082 FcBool
1083 FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
1084 {
1085     FcValue     v;
1086
1087     v.type = FcTypeFTFace;
1088     v.u.f = (void *) f;
1089     return FcPatternAdd (p, object, v, FcTrue);
1090 }
1091
1092 FcBool
1093 FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
1094 {
1095     FcValue     v;
1096
1097     v.type = FcTypeLangSet;
1098     v.u.l = (FcLangSet *)ls;
1099     return FcPatternAdd (p, object, v, FcTrue);
1100 }
1101
1102 FcResult
1103 FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
1104 {
1105     FcPatternElt   *e;
1106     FcValueListPtr l;
1107
1108     e = FcPatternFindElt (p, object);
1109     if (!e)
1110         return FcResultNoMatch;
1111     for (l = e->values; FcValueListPtrU(l); l = FcValueListPtrU(l)->next)
1112     {
1113         if (!id)
1114         {
1115             *v = FcValueCanonicalize(&FcValueListPtrU(l)->value);
1116             return FcResultMatch;
1117         }
1118         id--;
1119     }
1120     return FcResultNoId;
1121 }
1122
1123 FcResult
1124 FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
1125 {
1126     FcValue     v;
1127     FcResult    r;
1128
1129     r = FcPatternGet (p, object, id, &v);
1130     if (r != FcResultMatch)
1131         return r;
1132     switch (v.type) {
1133     case FcTypeDouble:
1134         *i = (int) v.u.d;
1135         break;
1136     case FcTypeInteger:
1137         *i = v.u.i;
1138         break;
1139     default:
1140         return FcResultTypeMismatch;
1141     }
1142     return FcResultMatch;
1143 }
1144
1145 FcResult
1146 FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
1147 {
1148     FcValue     v;
1149     FcResult    r;
1150
1151     r = FcPatternGet (p, object, id, &v);
1152     if (r != FcResultMatch)
1153         return r;
1154     switch (v.type) {
1155     case FcTypeDouble:
1156         *d = v.u.d;
1157         break;
1158     case FcTypeInteger:
1159         *d = (double) v.u.i;
1160         break;
1161     default:
1162         return FcResultTypeMismatch;
1163     }
1164     return FcResultMatch;
1165 }
1166
1167 FcResult
1168 FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
1169 {
1170     FcValue     v;
1171     FcResult    r;
1172
1173     r = FcPatternGet (p, object, id, &v);
1174     if (r != FcResultMatch)
1175         return r;
1176     if (v.type != FcTypeString)
1177         return FcResultTypeMismatch;
1178
1179     if (FcObjectToPtr(object) == FcObjectToPtr(FC_FILE))
1180     {
1181         const char *fn, *fpath;
1182         FcChar8 *fname;
1183         int size;
1184
1185         fn = FcPatternFindFullFname(p);
1186         if (fn)
1187         {
1188             *s = (FcChar8 *) fn;
1189             return FcResultMatch;
1190         }
1191
1192         if (!p->bank)
1193         {
1194             *s = (FcChar8 *) v.u.s;
1195             return FcResultMatch;
1196         }
1197
1198         fpath = FcCacheFindBankDir (p->bank);
1199         size = strlen((char*)fpath) + 1 + strlen ((char *)v.u.s) + 1;
1200         fname = malloc (size);
1201         if (!fname)
1202             return FcResultOutOfMemory;
1203
1204         FcMemAlloc (FC_MEM_STRING, size);
1205         strcpy ((char *)fname, (char *)fpath);
1206         strcat ((char *)fname, "/");
1207         strcat ((char *)fname, (char *)v.u.s);
1208
1209         FcPatternAddFullFname (p, (const char *)fname);
1210         *s = (FcChar8 *)fname;
1211         return FcResultMatch;
1212     }
1213
1214     *s = (FcChar8 *) v.u.s;
1215     return FcResultMatch;
1216 }
1217
1218 FcResult
1219 FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
1220 {
1221     FcValue     v;
1222     FcResult    r;
1223
1224     r = FcPatternGet (p, object, id, &v);
1225     if (r != FcResultMatch)
1226         return r;
1227     if (v.type != FcTypeMatrix)
1228         return FcResultTypeMismatch;
1229     *m = (FcMatrix *)v.u.m;
1230     return FcResultMatch;
1231 }
1232
1233
1234 FcResult
1235 FcPatternGetBool(const FcPattern *p, const char *object, int id, FcBool *b)
1236 {
1237     FcValue     v;
1238     FcResult    r;
1239
1240     r = FcPatternGet (p, object, id, &v);
1241     if (r != FcResultMatch)
1242         return r;
1243     if (v.type != FcTypeBool)
1244         return FcResultTypeMismatch;
1245     *b = v.u.b;
1246     return FcResultMatch;
1247 }
1248
1249 FcResult
1250 FcPatternGetCharSet(const FcPattern *p, const char *object, int id, FcCharSet **c)
1251 {
1252     FcValue     v;
1253     FcResult    r;
1254
1255     r = FcPatternGet (p, object, id, &v);
1256     if (r != FcResultMatch)
1257         return r;
1258     if (v.type != FcTypeCharSet)
1259         return FcResultTypeMismatch;
1260     *c = (FcCharSet *)v.u.c;
1261     return FcResultMatch;
1262 }
1263
1264 FcResult
1265 FcPatternGetFTFace(const FcPattern *p, const char *object, int id, FT_Face *f)
1266 {
1267     FcValue     v;
1268     FcResult    r;
1269
1270     r = FcPatternGet (p, object, id, &v);
1271     if (r != FcResultMatch)
1272         return r;
1273     if (v.type != FcTypeFTFace)
1274         return FcResultTypeMismatch;
1275     *f = (FT_Face) v.u.f;
1276     return FcResultMatch;
1277 }
1278
1279 FcResult
1280 FcPatternGetLangSet(const FcPattern *p, const char *object, int id, FcLangSet **ls)
1281 {
1282     FcValue     v;
1283     FcResult    r;
1284
1285     r = FcPatternGet (p, object, id, &v);
1286     if (r != FcResultMatch)
1287         return r;
1288     if (v.type != FcTypeLangSet)
1289         return FcResultTypeMismatch;
1290     *ls = (FcLangSet *)v.u.l;
1291     return FcResultMatch;
1292 }
1293
1294 FcPattern *
1295 FcPatternDuplicate (const FcPattern *orig)
1296 {
1297     FcPattern       *new;
1298     FcPatternElt    *e;
1299     int             i;
1300     FcValueListPtr  l;
1301
1302     new = FcPatternCreate ();
1303     if (!new)
1304         goto bail0;
1305
1306     e = FcPatternEltU(orig->elts);
1307
1308     for (i = 0; i < orig->num; i++)
1309     {
1310         for (l = (e + i)->values;
1311              FcValueListPtrU(l);
1312              l = FcValueListPtrU(l)->next)
1313             if (!FcPatternAdd (new, FcObjectPtrU((e + i)->object),
1314                                FcValueCanonicalize(&FcValueListPtrU(l)->value),
1315                                FcTrue))
1316                 goto bail1;
1317     }
1318     FcPatternTransferFullFname (new, orig);
1319
1320     return new;
1321
1322 bail1:
1323     FcPatternDestroy (new);
1324 bail0:
1325     return 0;
1326 }
1327
1328 void
1329 FcPatternReference (FcPattern *p)
1330 {
1331     if (p->ref != FC_REF_CONSTANT)
1332         p->ref++;
1333 }
1334
1335 FcPattern *
1336 FcPatternVaBuild (FcPattern *orig, va_list va)
1337 {
1338     FcPattern   *ret;
1339
1340     FcPatternVapBuild (ret, orig, va);
1341     return ret;
1342 }
1343
1344 FcPattern *
1345 FcPatternBuild (FcPattern *orig, ...)
1346 {
1347     va_list     va;
1348
1349     va_start (va, orig);
1350     FcPatternVapBuild (orig, orig, va);
1351     va_end (va);
1352     return orig;
1353 }
1354
1355 /*
1356  * Add all of the elements in 's' to 'p'
1357  */
1358 FcBool
1359 FcPatternAppend (FcPattern *p, FcPattern *s)
1360 {
1361     int             i;
1362     FcPatternElt    *e;
1363     FcValueListPtr  v;
1364
1365     for (i = 0; i < s->num; i++)
1366     {
1367         e = FcPatternEltU(s->elts)+i;
1368         for (v = e->values; FcValueListPtrU(v);
1369              v = FcValueListPtrU(v)->next)
1370         {
1371             if (!FcPatternAddWithBinding (p, FcObjectPtrU(e->object),
1372                                           FcValueCanonicalize(&FcValueListPtrU(v)->value),
1373                                           FcValueListPtrU(v)->binding, FcTrue))
1374                 return FcFalse;
1375         }
1376     }
1377     return FcTrue;
1378 }
1379
1380 #define OBJECT_HASH_SIZE    31
1381 static struct objectBucket {
1382     struct objectBucket *next;
1383     FcChar32            hash;
1384 } *FcObjectBuckets[OBJECT_HASH_SIZE];
1385
1386 static FcBool
1387 FcStrHashed (const FcChar8 *name)
1388 {
1389     FcChar32            hash = FcStringHash (name);
1390     struct objectBucket **p;
1391     struct objectBucket *b;
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 FcTrue;
1396     return FcFalse;
1397 }
1398
1399 const FcChar8 *
1400 FcStrStaticName (const FcChar8 *name)
1401 {
1402     FcChar32            hash = FcStringHash (name);
1403     struct objectBucket **p;
1404     struct objectBucket *b;
1405     int                 size;
1406
1407     for (p = &FcObjectBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1408         if (b->hash == hash && !strcmp ((char *)name, (char *) (b + 1)))
1409             return (FcChar8 *) (b + 1);
1410     size = sizeof (struct objectBucket) + strlen ((char *)name) + 1;
1411     b = malloc (size + sizeof (int));
1412     /* workaround glibc bug which reads strlen in groups of 4 */
1413     FcMemAlloc (FC_MEM_STATICSTR, size + sizeof (int));
1414     if (!b)
1415         return NULL;
1416     b->next = 0;
1417     b->hash = hash;
1418     strcpy ((char *) (b + 1), (char *)name);
1419     *p = b;
1420     return (FcChar8 *) (b + 1);
1421 }
1422
1423 static void
1424 FcStrStaticNameFini (void)
1425 {
1426     int i, size;
1427     struct objectBucket *b, *next;
1428     char *name;
1429
1430     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1431     {
1432         for (b = FcObjectBuckets[i]; b; b = next)
1433         {
1434             next = b->next;
1435             name = (char *) (b + 1);
1436             size = sizeof (struct objectBucket) + strlen (name) + 1;
1437             FcMemFree (FC_MEM_STATICSTR, size);
1438             free (b);
1439         }
1440         FcObjectBuckets[i] = 0;
1441     }
1442 }
1443
1444 void
1445 FcPatternFini (void)
1446 {
1447     FcPatternBaseThawAll ();
1448     FcValueListThawAll ();
1449     FcStrStaticNameFini ();
1450     FcObjectStaticNameFini ();
1451 }
1452
1453 static FcPatternEltPtr
1454 FcPatternEltPtrCreateDynamic (FcPatternElt * e)
1455 {
1456     FcPatternEltPtr new;
1457     new.bank = FC_BANK_DYNAMIC;
1458     new.u.dyn = e;
1459     return new;
1460 }
1461
1462 static FcPatternEltPtr
1463 FcPatternEltPtrCreateStatic (int bank, int i)
1464 {
1465     FcPatternEltPtr new;
1466     new.bank = bank;
1467     new.u.stat = i;
1468     return new;
1469 }
1470
1471 static void
1472 FcStrNewBank (void);
1473 static int
1474 FcStrNeededBytes (const FcChar8 * s);
1475 static int
1476 FcStrNeededBytesAlign (void);
1477 static void *
1478 FcStrDistributeBytes (FcCache * metadata, void * block_ptr);
1479 static const FcChar8 *
1480 FcStrSerialize (int bank, const FcChar8 * s);
1481 static void *
1482 FcStrUnserialize (FcCache * metadata, void *block_ptr);
1483
1484 static void
1485 FcValueListNewBank (void);
1486 static int
1487 FcValueListNeededBytes (FcValueList * vl);
1488 static int
1489 FcValueListNeededBytesAlign (void);
1490 static void *
1491 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr);
1492 static FcValueListPtr
1493 FcValueListSerialize(int bank, FcValueList *pi);
1494 static void *
1495 FcValueListUnserialize (FcCache * metadata, void *block_ptr);
1496
1497
1498 void
1499 FcPatternNewBank (void)
1500 {
1501     fcpattern_count = 0;
1502     fcpatternelt_count = 0;
1503
1504     FcStrNewBank();
1505     FcValueListNewBank();
1506 }
1507
1508 int
1509 FcPatternNeededBytes (FcPattern * p)
1510 {
1511     int i, cum = 0, c;
1512
1513     fcpattern_count++;
1514     fcpatternelt_count += p->num;
1515
1516     for (i = 0; i < p->num; i++)
1517     {
1518         c = FcValueListNeededBytes (FcValueListPtrU
1519                                     (((FcPatternEltU(p->elts)+i)->values)));
1520         if (c < 0)
1521             return c;
1522         cum += c;
1523     }
1524
1525     return cum + sizeof (FcPattern) + sizeof(FcPatternElt)*p->num;
1526 }
1527
1528 int
1529 FcPatternNeededBytesAlign (void)
1530 {
1531     return __alignof__ (FcPattern) + __alignof__ (FcPatternElt) +
1532         FcValueListNeededBytesAlign ();
1533 }
1534
1535 static FcBool
1536 FcPatternEnsureBank (int bi)
1537 {
1538     FcPattern **pp;
1539     FcPatternElt **ep;
1540     int i;
1541
1542     if (!_fcPatterns || fcpattern_bank_count <= bi)
1543     {
1544         int new_count = bi + 4;
1545         pp = realloc (_fcPatterns, sizeof (FcPattern *) * new_count);
1546         if (!pp)
1547             return 0;
1548
1549         FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern *) * new_count);
1550         _fcPatterns = pp;
1551
1552         ep = realloc (_fcPatternElts, sizeof (FcPatternElt *) * new_count);
1553         if (!ep)
1554             return 0;
1555
1556         FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt *) * new_count);
1557         _fcPatternElts = ep;
1558
1559         for (i = fcpattern_bank_count; i < new_count; i++)
1560         {
1561             _fcPatterns[i] = 0;
1562             _fcPatternElts[i] = 0;
1563         }
1564
1565         fcpattern_bank_count = new_count;
1566     }
1567
1568     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * fcpattern_count);
1569     return FcTrue;
1570 }
1571
1572 void *
1573 FcPatternDistributeBytes (FcCache * metadata, void * block_ptr)
1574 {
1575     int bi = FcCacheBankToIndex(metadata->bank);
1576
1577     if (!FcPatternEnsureBank(bi))
1578         return 0;
1579
1580     fcpattern_ptr = 0;
1581     block_ptr = ALIGN(block_ptr, FcPattern);
1582     _fcPatterns[bi] = (FcPattern *)block_ptr;
1583     block_ptr = (void *)((char *)block_ptr +
1584                          (sizeof (FcPattern) * fcpattern_count));
1585
1586     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt) * fcpatternelt_count);
1587     fcpatternelt_ptr = 0;
1588     block_ptr = ALIGN(block_ptr, FcPatternElt);
1589     _fcPatternElts[bi] = (FcPatternElt *)block_ptr;
1590     block_ptr = (void *)((char *)block_ptr +
1591                          (sizeof (FcPatternElt) * fcpatternelt_count));
1592
1593     metadata->pattern_count = fcpattern_count;
1594     metadata->patternelt_count = fcpatternelt_count;
1595
1596     block_ptr = FcStrDistributeBytes (metadata, block_ptr);
1597     block_ptr = FcValueListDistributeBytes (metadata, block_ptr);
1598     return block_ptr;
1599 }
1600
1601 FcPattern *
1602 FcPatternSerialize (int bank, FcPattern *old)
1603 {
1604     FcPattern *p;
1605     FcPatternElt *e, *nep;
1606     FcValueList * nv;
1607     FcValueListPtr v, nv_head, nvp;
1608     int i, elts, bi = FcCacheBankToIndex(bank);
1609
1610     p = &_fcPatterns[bi][fcpattern_ptr++];
1611     p->bank = bank;
1612     elts = fcpatternelt_ptr;
1613     nep = &_fcPatternElts[bi][elts];
1614     if (!nep)
1615         return FcFalse;
1616
1617     fcpatternelt_ptr += old->num;
1618
1619     for (e = FcPatternEltU(old->elts), i=0; i < old->num; i++, e++)
1620     {
1621         v = e->values;
1622         nvp = nv_head = FcValueListSerialize(bank, FcValueListPtrU(v));
1623         if (!FcValueListPtrU(nv_head))
1624             return 0;
1625         nv = FcValueListPtrU(nvp);
1626
1627         for (;
1628              FcValueListPtrU(v);
1629              v = FcValueListPtrU(v)->next,
1630                  nv = FcValueListPtrU(nv->next))
1631         {
1632
1633             if (FcValueListPtrU(FcValueListPtrU(v)->next))
1634             {
1635                 nvp = FcValueListSerialize
1636                     (bank, FcValueListPtrU(FcValueListPtrU(v)->next));
1637                 nv->next = nvp;
1638             }
1639         }
1640
1641         nep[i].values = nv_head;
1642         nep[i].object = e->object;
1643     }
1644
1645     p->elts = old->elts;
1646     p->elts = FcPatternEltPtrCreateStatic(bank, elts);
1647     p->size = old->num;
1648     p->num = old->num;
1649     p->ref = FC_REF_CONSTANT;
1650     return p;
1651 }
1652
1653 void *
1654 FcPatternUnserialize (FcCache * metadata, void *block_ptr)
1655 {
1656     int bi = FcCacheBankToIndex(metadata->bank);
1657     if (!FcPatternEnsureBank(bi))
1658         return FcFalse;
1659
1660     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * metadata->pattern_count);
1661     block_ptr = ALIGN(block_ptr, FcPattern);
1662     _fcPatterns[bi] = (FcPattern *)block_ptr;
1663     block_ptr = (void *)((char *)block_ptr +
1664                          (sizeof (FcPattern) * metadata->pattern_count));
1665
1666     FcMemAlloc (FC_MEM_PATELT,
1667                 sizeof (FcPatternElt) * metadata->patternelt_count);
1668     block_ptr = ALIGN(block_ptr, FcPatternElt);
1669     _fcPatternElts[bi] = (FcPatternElt *)block_ptr;
1670     block_ptr = (void *)((char *)block_ptr +
1671                          (sizeof (FcPatternElt) * metadata->patternelt_count));
1672
1673     block_ptr = FcStrUnserialize (metadata, block_ptr);
1674     block_ptr = FcValueListUnserialize (metadata, block_ptr);
1675
1676     return block_ptr;
1677 }
1678
1679 static void
1680 FcValueListNewBank (void)
1681 {
1682     fcvaluelist_count = 0;
1683
1684     FcCharSetNewBank();
1685     FcLangSetNewBank();
1686 }
1687
1688 static int
1689 FcValueListNeededBytes (FcValueList *p)
1690 {
1691     FcValueList *vl;
1692     int cum = 0;
1693
1694     for (vl = p;
1695          vl;
1696          vl = FcValueListPtrU(vl->next))
1697     {
1698         FcValue v = FcValueCanonicalize(&vl->value); // unserialize just in case
1699
1700         switch (v.type)
1701         {
1702         case FcTypeCharSet:
1703             cum += FcCharSetNeededBytes(v.u.c);
1704             break;
1705         case FcTypeLangSet:
1706             cum += FcLangSetNeededBytes(v.u.l);
1707             break;
1708         case FcTypeString:
1709             cum += FcStrNeededBytes(v.u.s);
1710         default:
1711             break;
1712         }
1713         fcvaluelist_count++;
1714         cum += sizeof (FcValueList);
1715     }
1716
1717     return cum;
1718 }
1719
1720 static int
1721 FcValueListNeededBytesAlign (void)
1722 {
1723     return FcCharSetNeededBytesAlign() + FcLangSetNeededBytesAlign() +
1724         FcStrNeededBytesAlign() + __alignof__ (FcValueList);
1725 }
1726
1727 static FcBool
1728 FcValueListEnsureBank (int bi)
1729 {
1730     FcValueList **pvl;
1731
1732     if (!_fcValueLists || fcvaluelist_bank_count <= bi)
1733     {
1734         int new_count = bi + 2, i;
1735
1736         pvl = realloc (_fcValueLists, sizeof (FcValueList *) * new_count);
1737         if (!pvl)
1738             return FcFalse;
1739
1740         FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList *) * new_count);
1741
1742         _fcValueLists = pvl;
1743         for (i = fcvaluelist_bank_count; i < new_count; i++)
1744             _fcValueLists[i] = 0;
1745
1746         fcvaluelist_bank_count = new_count;
1747     }
1748     return FcTrue;
1749 }
1750
1751 static void *
1752 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr)
1753 {
1754     int bi = FcCacheBankToIndex(metadata->bank);
1755
1756     if (!FcValueListEnsureBank(bi))
1757         return 0;
1758
1759     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList) * fcvaluelist_count);
1760     fcvaluelist_ptr = 0;
1761     block_ptr = ALIGN(block_ptr, FcValueList);
1762     _fcValueLists[bi] = (FcValueList *)block_ptr;
1763     block_ptr = (void *)((char *)block_ptr +
1764                          (sizeof (FcValueList) * fcvaluelist_count));
1765     metadata->valuelist_count = fcvaluelist_count;
1766
1767     block_ptr = FcCharSetDistributeBytes(metadata, block_ptr);
1768     block_ptr = FcLangSetDistributeBytes(metadata, block_ptr);
1769
1770     return block_ptr;
1771 }
1772
1773 static FcValueListPtr
1774 FcValueListSerialize(int bank, FcValueList *pi)
1775 {
1776     FcValueListPtr new;
1777     FcValue * v;
1778     int bi = FcCacheBankToIndex(bank);
1779
1780     if (!pi)
1781     {
1782         new.bank = FC_BANK_DYNAMIC;
1783         new.u.dyn = 0;
1784         return new;
1785     }
1786
1787     _fcValueLists[bi][fcvaluelist_ptr] = *pi;
1788     new.bank = bank;
1789     new.u.stat = fcvaluelist_ptr++;
1790     _fcValueLists[bi][new.u.stat].value = FcValueCanonicalize (&pi->value);
1791     v = &_fcValueLists[bi][new.u.stat].value;
1792     switch (v->type)
1793     {
1794     case FcTypeString:
1795         if (v->u.s)
1796         {
1797             const FcChar8 * s = FcStrSerialize(bank, v->u.s);
1798             if (!s)
1799                 return FcValueListPtrCreateDynamic(pi);
1800             v->u.s_off = s - (const FcChar8 *)v;
1801             v->type |= FC_STORAGE_STATIC;
1802         }
1803         break;
1804     case FcTypeMatrix:
1805         break;
1806     case FcTypeCharSet:
1807         if (v->u.c)
1808         {
1809             FcCharSet * c = FcCharSetSerialize(bank, (FcCharSet *)v->u.c);
1810             if (!c)
1811                 return FcValueListPtrCreateDynamic(pi);
1812             v->u.c_off = (char *)c - (char *)v;
1813             v->type |= FC_STORAGE_STATIC;
1814         }
1815         break;
1816     case FcTypeLangSet:
1817         if (v->u.l)
1818         {
1819             FcLangSet * l = FcLangSetSerialize(bank, (FcLangSet *)v->u.l);
1820             if (!l)
1821                 return FcValueListPtrCreateDynamic(pi);
1822             v->u.l_off = (char *)l - (char *)v;
1823             v->type |= FC_STORAGE_STATIC;
1824         }
1825         break;
1826     default:
1827         break;
1828     }
1829     return new;
1830 }
1831
1832 static void *
1833 FcValueListUnserialize (FcCache * metadata, void *block_ptr)
1834 {
1835     int bi = FcCacheBankToIndex(metadata->bank);
1836
1837     if (!FcValueListEnsureBank(bi))
1838         return 0;
1839
1840     FcMemAlloc (FC_MEM_VALLIST,
1841                 sizeof (FcValueList) * metadata->valuelist_count);
1842     block_ptr = ALIGN(block_ptr, FcValueList);
1843     _fcValueLists[bi] = (FcValueList *)block_ptr;
1844     block_ptr = (void *)((char *)block_ptr +
1845                          (sizeof (FcValueList) * metadata->valuelist_count));
1846
1847     block_ptr = FcCharSetUnserialize(metadata, block_ptr);
1848     block_ptr = FcLangSetUnserialize(metadata, block_ptr);
1849
1850     return block_ptr;
1851 }
1852
1853 FcValueListPtr
1854 FcValueListPtrCreateDynamic(FcValueList * p)
1855 {
1856     FcValueListPtr r;
1857
1858     r.bank = FC_BANK_DYNAMIC;
1859     r.u.dyn = p;
1860     return r;
1861 }
1862
1863 static FcChar8 ** static_strs;
1864 static int static_str_bank_count = 0, fcstr_ptr, fcstr_count;
1865
1866 static struct objectBucket *FcStrBuckets[OBJECT_HASH_SIZE];
1867
1868 static void
1869 FcStrNewBank (void)
1870 {
1871     int i, size;
1872     struct objectBucket *b, *next;
1873     char *name;
1874
1875     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1876     {
1877         for (b = FcStrBuckets[i]; b; b = next)
1878         {
1879             next = b->next;
1880             name = (char *) (b + 1);
1881             size = sizeof (struct objectBucket) + strlen (name) + 1;
1882             FcMemFree (FC_MEM_STATICSTR, size);
1883             free (b);
1884         }
1885         FcStrBuckets[i] = 0;
1886     }
1887
1888     fcstr_count = 0;
1889 }
1890
1891 static int
1892 FcStrNeededBytes (const FcChar8 * s)
1893 {
1894     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1895     struct objectBucket **p;
1896     struct objectBucket *b;
1897     int                 size;
1898     FcChar8 *const null = 0;
1899
1900     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1901         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1902             return 0;
1903     size = sizeof (struct objectBucket) + strlen ((char *)s) + 1 + sizeof(char *);
1904     b = malloc (size);
1905     FcMemAlloc (FC_MEM_STATICSTR, size);
1906     if (!b)
1907         return -1;
1908     b->next = 0;
1909     b->hash = hash;
1910     strcpy ((char *) (b + 1), (char *)s);
1911
1912     /* Yes, the following line is convoluted.  However, it is
1913      * incorrect to replace the with a memset, because the C
1914      * specification doesn't guarantee that the null pointer is
1915      * the same as the zero bit pattern. */
1916     /* Misaligned pointers are not guaranteed to work, either! */
1917     memcpy (((char *) (b + 1) + strlen((char *)s) + 1), &null, sizeof (null));
1918     *p = b;
1919
1920     fcstr_count += strlen((char *)s) + 1;
1921     return strlen((char *)s) + 1;
1922 }
1923
1924 static int
1925 FcStrNeededBytesAlign (void)
1926 {
1927     return __alignof__ (char);
1928 }
1929
1930 static FcBool
1931 FcStrEnsureBank (int bi)
1932 {
1933     FcChar8 ** ss;
1934
1935     if (!static_strs || static_str_bank_count <= bi)
1936     {
1937         int new_count = bi + 4, i;
1938         ss = realloc (static_strs, sizeof (const char *) * new_count);
1939         if (!ss)
1940             return FcFalse;
1941
1942         FcMemAlloc (FC_MEM_STRING, sizeof (const char *) * (new_count-static_str_bank_count));
1943         static_strs = ss;
1944
1945         for (i = static_str_bank_count; i < new_count; i++)
1946             static_strs[i] = 0;
1947         static_str_bank_count = new_count;
1948     }
1949     return FcTrue;
1950 }
1951
1952 static void *
1953 FcStrDistributeBytes (FcCache * metadata, void * block_ptr)
1954 {
1955     int bi = FcCacheBankToIndex(metadata->bank);
1956     if (!FcStrEnsureBank(bi))
1957         return 0;
1958
1959     FcMemAlloc (FC_MEM_STRING, sizeof (char) * fcstr_count);
1960     block_ptr = ALIGN (block_ptr, FcChar8);
1961     static_strs[bi] = (FcChar8 *)block_ptr;
1962     block_ptr = (void *)((char *)block_ptr + (sizeof (char) * fcstr_count));
1963     metadata->str_count = fcstr_count;
1964     fcstr_ptr = 0;
1965
1966     return block_ptr;
1967 }
1968
1969 static const FcChar8 *
1970 FcStrSerialize (int bank, const FcChar8 * s)
1971 {
1972     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1973     struct objectBucket **p;
1974     struct objectBucket *b;
1975     int bi = FcCacheBankToIndex(bank);
1976
1977     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1978         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1979         {
1980             FcChar8 * t;
1981             memcpy (&t, ((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1, sizeof (FcChar8 *));
1982             if (!t)
1983             {
1984                 strcpy((char *)(static_strs[bi] + fcstr_ptr), (char *)s);
1985                 t = static_strs[bi] + fcstr_ptr;
1986                 memcpy ((FcChar8 *) (b + 1) + strlen((char *)s) + 1, &t, sizeof (FcChar8 *));
1987                 fcstr_ptr += strlen((char *)s) + 1;
1988                 memcpy (&t, ((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1, sizeof (FcChar8 *));
1989             }
1990             return t;
1991         }
1992     return 0;
1993 }
1994
1995 static void *
1996 FcStrUnserialize (FcCache * metadata, void *block_ptr)
1997 {
1998     int bi = FcCacheBankToIndex(metadata->bank);
1999     if (!FcStrEnsureBank(bi))
2000         return 0;
2001
2002     FcMemAlloc (FC_MEM_STRING, sizeof (char) * metadata->str_count);
2003     block_ptr = ALIGN (block_ptr, FcChar8);
2004     static_strs[bi] = (FcChar8 *)block_ptr;
2005     block_ptr = (void *)((char *)block_ptr +
2006                          (sizeof (char) * metadata->str_count));
2007
2008     return block_ptr;
2009 }
2010
2011 /* we don't store these in the FcPattern itself because
2012  * we don't want to serialize the directory names */
2013
2014 /* I suppose this should be cleaned upon termination, too... */
2015 typedef struct _FcPatternDirMapping {
2016     const FcPattern     *p;
2017     const char *fname;
2018 } FcPatternDirMapping;
2019
2020 #define PATTERNDIR_HASH_SIZE    31
2021 static struct patternDirBucket {
2022     struct patternDirBucket     *next;
2023     FcPatternDirMapping         m;
2024 } FcPatternDirBuckets[PATTERNDIR_HASH_SIZE];
2025
2026 void
2027 FcPatternAddFullFname (const FcPattern *p, const char *fname)
2028 {
2029     struct patternDirBucket     *pb;
2030
2031     /* N.B. FcPatternHash fails, since it's contents-based, not
2032      * address-based, and we're in the process of mutating the FcPattern. */
2033     for (pb = &FcPatternDirBuckets
2034              [((unsigned long)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
2035          pb->m.p != p && pb->next;
2036          pb = pb->next)
2037         ;
2038
2039     if (pb->m.p == p)
2040     {
2041         pb->m.fname = fname;
2042         return;
2043     }
2044
2045     pb->next = malloc (sizeof (struct patternDirBucket));
2046     if (!pb->next)
2047         return;
2048     FcMemAlloc (FC_MEM_CACHE, sizeof (struct patternDirBucket));
2049
2050     pb->next->next = 0;
2051     pb->next->m.p = p;
2052     pb->next->m.fname = fname;
2053 }
2054
2055 static const char *
2056 FcPatternFindFullFname (const FcPattern *p)
2057 {
2058     struct patternDirBucket     *pb;
2059
2060     for (pb = &FcPatternDirBuckets
2061              [((unsigned long)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
2062          pb; pb = pb->next)
2063         if (pb->m.p == p)
2064             return pb->m.fname;
2065
2066     return 0;
2067 }
2068
2069 void
2070 FcPatternTransferFullFname (const FcPattern *new, const FcPattern *orig)
2071 {
2072     FcChar8 * s;
2073     FcPatternGetString (orig, FC_FILE, 0, &s);
2074     FcPatternAddFullFname (new,
2075                            (char *)FcStrCopy
2076                            ((FcChar8 *)FcPatternFindFullFname(orig)));
2077 }