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