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