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 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 static FcPatternEltPtr
1422 FcPatternEltPtrCreateDynamic (FcPatternElt * e)
1423 {
1424     FcPatternEltPtr new;
1425     new.bank = FC_BANK_DYNAMIC;
1426     new.u.dyn = e;
1427     return new;
1428 }
1429
1430 static FcPatternEltPtr
1431 FcPatternEltPtrCreateStatic (int bank, int i)
1432 {
1433     FcPatternEltPtr new;
1434     new.bank = bank;
1435     new.u.stat = i;
1436     return new;
1437 }
1438
1439 static void
1440 FcStrNewBank (void);
1441 static int
1442 FcStrNeededBytes (const FcChar8 * s);
1443 static int
1444 FcStrNeededBytesAlign (void);
1445 static void *
1446 FcStrDistributeBytes (FcCache * metadata, void * block_ptr);
1447 static const FcChar8 *
1448 FcStrSerialize (int bank, const FcChar8 * s);
1449 static void *
1450 FcStrUnserialize (FcCache * metadata, void *block_ptr);
1451
1452 static void
1453 FcValueListNewBank (void);
1454 static int
1455 FcValueListNeededBytes (FcValueList * vl);
1456 static int
1457 FcValueListNeededBytesAlign (void);
1458 static void *
1459 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr);
1460 static FcValueListPtr
1461 FcValueListSerialize(int bank, FcValueList *pi);
1462 static void *
1463 FcValueListUnserialize (FcCache * metadata, void *block_ptr);
1464
1465
1466 void
1467 FcPatternNewBank (void)
1468 {
1469     fcpattern_count = 0;
1470     fcpatternelt_count = 0;
1471
1472     FcStrNewBank();
1473     FcValueListNewBank();
1474 }
1475
1476 int
1477 FcPatternNeededBytes (FcPattern * p)
1478 {
1479     int i, cum = 0, c;
1480
1481     fcpattern_count++;
1482     fcpatternelt_count += p->num;
1483
1484     for (i = 0; i < p->num; i++)
1485     {
1486         c = FcValueListNeededBytes (FcValueListPtrU
1487                                     (((FcPatternEltU(p->elts)+i)->values)));
1488         if (c < 0)
1489             return c;
1490         cum += c;
1491     }
1492
1493     return cum + sizeof (FcPattern) + sizeof(FcPatternElt)*p->num;
1494 }
1495
1496 int
1497 FcPatternNeededBytesAlign (void)
1498 {
1499     return __alignof__ (FcPattern) + __alignof__ (FcPatternElt) +
1500         FcValueListNeededBytesAlign ();
1501 }
1502
1503 static FcBool
1504 FcPatternEnsureBank (int bi)
1505 {
1506     FcPattern **pp;
1507     FcPatternElt **ep;
1508     int i;
1509
1510     if (!fcpatterns || fcpattern_bank_count <= bi)
1511     {
1512         int new_count = bi + 4;
1513         pp = realloc (fcpatterns, sizeof (FcPattern *) * new_count);
1514         if (!pp)
1515             return 0;
1516
1517         FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern *) * new_count);
1518         fcpatterns = pp;
1519
1520         ep = realloc (fcpatternelts, sizeof (FcPatternElt *) * new_count);
1521         if (!ep)
1522             return 0;
1523
1524         FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt *) * new_count);
1525         fcpatternelts = ep;
1526
1527         for (i = fcpattern_bank_count; i < new_count; i++)
1528         {
1529             fcpatterns[i] = 0;
1530             fcpatternelts[i] = 0;
1531         }
1532
1533         fcpattern_bank_count = new_count;
1534     }
1535
1536     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * fcpattern_count);
1537     return FcTrue;
1538 }
1539
1540 void *
1541 FcPatternDistributeBytes (FcCache * metadata, void * block_ptr)
1542 {
1543     int bi = FcCacheBankToIndex(metadata->bank);
1544
1545     if (!FcPatternEnsureBank(bi))
1546         return 0;
1547
1548     fcpattern_ptr = 0;
1549     block_ptr = ALIGN(block_ptr, FcPattern);
1550     fcpatterns[bi] = (FcPattern *)block_ptr;
1551     block_ptr = (void *)((char *)block_ptr +
1552                          (sizeof (FcPattern) * fcpattern_count));
1553
1554     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt) * fcpatternelt_count);
1555     fcpatternelt_ptr = 0;
1556     block_ptr = ALIGN(block_ptr, FcPatternElt);
1557     fcpatternelts[bi] = (FcPatternElt *)block_ptr;
1558     block_ptr = (void *)((char *)block_ptr +
1559                          (sizeof (FcPatternElt) * fcpatternelt_count));
1560
1561     metadata->pattern_count = fcpattern_count;
1562     metadata->patternelt_count = fcpatternelt_count;
1563
1564     block_ptr = FcStrDistributeBytes (metadata, block_ptr);
1565     block_ptr = FcValueListDistributeBytes (metadata, block_ptr);
1566     return block_ptr;
1567 }
1568
1569 FcPattern *
1570 FcPatternSerialize (int bank, FcPattern *old)
1571 {
1572     FcPattern *p;
1573     FcPatternElt *e, *nep;
1574     FcValueList * nv;
1575     FcValueListPtr v, nv_head, nvp;
1576     int i, elts, bi = FcCacheBankToIndex(bank);
1577
1578     p = &fcpatterns[bi][fcpattern_ptr++];
1579     p->bank = bank;
1580     elts = fcpatternelt_ptr;
1581     nep = &fcpatternelts[bi][elts];
1582     if (!nep)
1583         return FcFalse;
1584
1585     fcpatternelt_ptr += old->num;
1586
1587     for (e = FcPatternEltU(old->elts), i=0; i < old->num; i++, e++)
1588     {
1589         v = e->values;
1590         nvp = nv_head = FcValueListSerialize(bank, FcValueListPtrU(v));
1591         if (!FcValueListPtrU(nv_head))
1592             return 0;
1593         nv = FcValueListPtrU(nvp);
1594
1595         for (;
1596              FcValueListPtrU(v);
1597              v = FcValueListPtrU(v)->next,
1598                  nv = FcValueListPtrU(nv->next))
1599         {
1600
1601             if (FcValueListPtrU(FcValueListPtrU(v)->next))
1602             {
1603                 nvp = FcValueListSerialize
1604                     (bank, FcValueListPtrU(FcValueListPtrU(v)->next));
1605                 nv->next = nvp;
1606             }
1607         }
1608
1609         nep[i].values = nv_head;
1610         nep[i].object = e->object;
1611     }
1612
1613     p->elts = old->elts;
1614     p->elts = FcPatternEltPtrCreateStatic(bank, elts);
1615     p->size = old->num;
1616     p->num = old->num;
1617     p->ref = FC_REF_CONSTANT;
1618     return p;
1619 }
1620
1621 void *
1622 FcPatternUnserialize (FcCache * metadata, void *block_ptr)
1623 {
1624     int bi = FcCacheBankToIndex(metadata->bank);
1625     if (!FcPatternEnsureBank(bi))
1626         return FcFalse;
1627
1628     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * metadata->pattern_count);
1629     block_ptr = ALIGN(block_ptr, FcPattern);
1630     fcpatterns[bi] = (FcPattern *)block_ptr;
1631     block_ptr = (void *)((char *)block_ptr +
1632                          (sizeof (FcPattern) * metadata->pattern_count));
1633
1634     FcMemAlloc (FC_MEM_PATELT,
1635                 sizeof (FcPatternElt) * metadata->patternelt_count);
1636     block_ptr = ALIGN(block_ptr, FcPatternElt);
1637     fcpatternelts[bi] = (FcPatternElt *)block_ptr;
1638     block_ptr = (void *)((char *)block_ptr +
1639                          (sizeof (FcPatternElt) * metadata->patternelt_count));
1640
1641     block_ptr = FcStrUnserialize (metadata, block_ptr);
1642     block_ptr = FcValueListUnserialize (metadata, block_ptr);
1643
1644     return block_ptr;
1645 }
1646
1647 static void
1648 FcValueListNewBank (void)
1649 {
1650     fcvaluelist_count = 0;
1651
1652     FcCharSetNewBank();
1653     FcLangSetNewBank();
1654 }
1655
1656 static int
1657 FcValueListNeededBytes (FcValueList *p)
1658 {
1659     FcValueList *vl;
1660     int cum = 0;
1661
1662     for (vl = p;
1663          vl;
1664          vl = FcValueListPtrU(vl->next))
1665     {
1666         FcValue v = FcValueCanonicalize(&vl->value); // unserialize just in case
1667
1668         switch (v.type)
1669         {
1670         case FcTypeCharSet:
1671             cum += FcCharSetNeededBytes(v.u.c);
1672             break;
1673         case FcTypeLangSet:
1674             cum += FcLangSetNeededBytes(v.u.l);
1675             break;
1676         case FcTypeString:
1677             cum += FcStrNeededBytes(v.u.s);
1678         default:
1679             break;
1680         }
1681         fcvaluelist_count++;
1682         cum += sizeof (FcValueList);
1683     }
1684
1685     return cum;
1686 }
1687
1688 static int
1689 FcValueListNeededBytesAlign (void)
1690 {
1691     return FcCharSetNeededBytesAlign() + FcLangSetNeededBytesAlign() +
1692         FcStrNeededBytesAlign() + __alignof__ (FcValueList);
1693 }
1694
1695 static FcBool
1696 FcValueListEnsureBank (int bi)
1697 {
1698     FcValueList **pvl;
1699
1700     if (!fcvaluelists || fcvaluelist_bank_count <= bi)
1701     {
1702         int new_count = bi + 2, i;
1703
1704         pvl = realloc (fcvaluelists, sizeof (FcValueList *) * new_count);
1705         if (!pvl)
1706             return FcFalse;
1707
1708         FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList *) * new_count);
1709
1710         fcvaluelists = pvl;
1711         for (i = fcvaluelist_bank_count; i < new_count; i++)
1712             fcvaluelists[i] = 0;
1713
1714         fcvaluelist_bank_count = new_count;
1715     }
1716     return FcTrue;
1717 }
1718
1719 static void *
1720 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr)
1721 {
1722     int bi = FcCacheBankToIndex(metadata->bank);
1723
1724     if (!FcValueListEnsureBank(bi))
1725         return 0;
1726
1727     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList) * fcvaluelist_count);
1728     fcvaluelist_ptr = 0;
1729     block_ptr = ALIGN(block_ptr, FcValueList);
1730     fcvaluelists[bi] = (FcValueList *)block_ptr;
1731     block_ptr = (void *)((char *)block_ptr +
1732                          (sizeof (FcValueList) * fcvaluelist_count));
1733     metadata->valuelist_count = fcvaluelist_count;
1734
1735     block_ptr = FcCharSetDistributeBytes(metadata, block_ptr);
1736     block_ptr = FcLangSetDistributeBytes(metadata, block_ptr);
1737
1738     return block_ptr;
1739 }
1740
1741 static FcValueListPtr
1742 FcValueListSerialize(int bank, FcValueList *pi)
1743 {
1744     FcValueListPtr new;
1745     FcValue * v;
1746     int bi = FcCacheBankToIndex(bank);
1747
1748     if (!pi)
1749     {
1750         new.bank = FC_BANK_DYNAMIC;
1751         new.u.dyn = 0;
1752         return new;
1753     }
1754
1755     fcvaluelists[bi][fcvaluelist_ptr] = *pi;
1756     new.bank = bank;
1757     new.u.stat = fcvaluelist_ptr++;
1758     fcvaluelists[bi][new.u.stat].value = FcValueCanonicalize (&pi->value);
1759     v = &fcvaluelists[bi][new.u.stat].value;
1760     switch (v->type)
1761     {
1762     case FcTypeString:
1763         if (v->u.s)
1764         {
1765             const FcChar8 * s = FcStrSerialize(bank, v->u.s);
1766             if (!s)
1767                 return FcValueListPtrCreateDynamic(pi);
1768             v->u.s_off = s - (const FcChar8 *)v;
1769             v->type |= FC_STORAGE_STATIC;
1770         }
1771         break;
1772     case FcTypeMatrix:
1773         break;
1774     case FcTypeCharSet:
1775         if (v->u.c)
1776         {
1777             FcCharSet * c = FcCharSetSerialize(bank, (FcCharSet *)v->u.c);
1778             if (!c)
1779                 return FcValueListPtrCreateDynamic(pi);
1780             v->u.c_off = (char *)c - (char *)v;
1781             v->type |= FC_STORAGE_STATIC;
1782         }
1783         break;
1784     case FcTypeLangSet:
1785         if (v->u.l)
1786         {
1787             FcLangSet * l = FcLangSetSerialize(bank, (FcLangSet *)v->u.l);
1788             if (!l)
1789                 return FcValueListPtrCreateDynamic(pi);
1790             v->u.l_off = (char *)l - (char *)v;
1791             v->type |= FC_STORAGE_STATIC;
1792         }
1793         break;
1794     default:
1795         break;
1796     }
1797     return new;
1798 }
1799
1800 static void *
1801 FcValueListUnserialize (FcCache * metadata, void *block_ptr)
1802 {
1803     int bi = FcCacheBankToIndex(metadata->bank);
1804
1805     if (!FcValueListEnsureBank(bi))
1806         return 0;
1807
1808     FcMemAlloc (FC_MEM_VALLIST,
1809                 sizeof (FcValueList) * metadata->valuelist_count);
1810     block_ptr = ALIGN(block_ptr, FcValueList);
1811     fcvaluelists[bi] = (FcValueList *)block_ptr;
1812     block_ptr = (void *)((char *)block_ptr +
1813                          (sizeof (FcValueList) * metadata->valuelist_count));
1814
1815     block_ptr = FcCharSetUnserialize(metadata, block_ptr);
1816     block_ptr = FcLangSetUnserialize(metadata, block_ptr);
1817
1818     return block_ptr;
1819 }
1820
1821 FcValueListPtr
1822 FcValueListPtrCreateDynamic(FcValueList * p)
1823 {
1824     FcValueListPtr r;
1825
1826     r.bank = FC_BANK_DYNAMIC;
1827     r.u.dyn = p;
1828     return r;
1829 }
1830
1831 static FcChar8 ** static_strs;
1832 static int static_str_bank_count = 0, fcstr_ptr, fcstr_count;
1833
1834 static struct objectBucket *FcStrBuckets[OBJECT_HASH_SIZE];
1835
1836 static void
1837 FcStrNewBank (void)
1838 {
1839     int i, size;
1840     struct objectBucket *b, *next;
1841     char *name;
1842
1843     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1844     {
1845         for (b = FcStrBuckets[i]; b; b = next)
1846         {
1847             next = b->next;
1848             name = (char *) (b + 1);
1849             size = sizeof (struct objectBucket) + strlen (name) + 1;
1850             FcMemFree (FC_MEM_STATICSTR, size);
1851             free (b);
1852         }
1853         FcStrBuckets[i] = 0;
1854     }
1855
1856     fcstr_count = 0;
1857 }
1858
1859 static int
1860 FcStrNeededBytes (const FcChar8 * s)
1861 {
1862     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1863     struct objectBucket **p;
1864     struct objectBucket *b;
1865     int                 size;
1866
1867     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1868         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1869             return 0;
1870     size = sizeof (struct objectBucket) + strlen ((char *)s) + 1 + sizeof(char *);
1871     b = malloc (size);
1872     FcMemAlloc (FC_MEM_STATICSTR, size);
1873     if (!b)
1874         return -1;
1875     b->next = 0;
1876     b->hash = hash;
1877     strcpy ((char *) (b + 1), (char *)s);
1878
1879     /* Yes, the following line is convoluted.  However, it is
1880      * incorrect to replace the with a memset, because the C
1881      * specification doesn't guarantee that the null pointer is
1882      * the same as the zero bit pattern. */
1883     *(char **)((char *) (b + 1) + strlen((char *)s) + 1) = 0;
1884     *p = b;
1885
1886     fcstr_count += strlen((char *)s) + 1;
1887     return strlen((char *)s) + 1;
1888 }
1889
1890 static int
1891 FcStrNeededBytesAlign (void)
1892 {
1893     return __alignof__ (char);
1894 }
1895
1896 static FcBool
1897 FcStrEnsureBank (int bi)
1898 {
1899     FcChar8 ** ss;
1900
1901     if (!static_strs || static_str_bank_count <= bi)
1902     {
1903         int new_count = bi + 4, i;
1904         ss = realloc (static_strs, sizeof (const char *) * new_count);
1905         if (!ss)
1906             return FcFalse;
1907
1908         FcMemAlloc (FC_MEM_STRING, sizeof (const char *) * (new_count-static_str_bank_count));
1909         static_strs = ss;
1910
1911         for (i = static_str_bank_count; i < new_count; i++)
1912             static_strs[i] = 0;
1913         static_str_bank_count = new_count;
1914     }
1915     return FcTrue;
1916 }
1917
1918 static void *
1919 FcStrDistributeBytes (FcCache * metadata, void * block_ptr)
1920 {
1921     int bi = FcCacheBankToIndex(metadata->bank);
1922     if (!FcStrEnsureBank(bi))
1923         return 0;
1924
1925     FcMemAlloc (FC_MEM_STRING, sizeof (char) * fcstr_count);
1926     block_ptr = ALIGN (block_ptr, FcChar8);
1927     static_strs[bi] = (FcChar8 *)block_ptr;
1928     block_ptr = (void *)((char *)block_ptr + (sizeof (char) * fcstr_count));
1929     metadata->str_count = fcstr_count;
1930     fcstr_ptr = 0;
1931
1932     return block_ptr;
1933 }
1934
1935 static const FcChar8 *
1936 FcStrSerialize (int bank, const FcChar8 * s)
1937 {
1938     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1939     struct objectBucket **p;
1940     struct objectBucket *b;
1941     int bi = FcCacheBankToIndex(bank);
1942
1943     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1944         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1945         {
1946             FcChar8 * t = *(FcChar8 **)(((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1);
1947             if (!t)
1948             {
1949                 strcpy((char *)(static_strs[bi] + fcstr_ptr), (char *)s);
1950                 *(FcChar8 **)((FcChar8 *) (b + 1) + strlen((char *)s) + 1) = (static_strs[bi] + fcstr_ptr);
1951                 fcstr_ptr += strlen((char *)s) + 1;
1952                 t = *(FcChar8 **)(((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1);
1953             }
1954             return t;
1955         }
1956     return 0;
1957 }
1958
1959 static void *
1960 FcStrUnserialize (FcCache * metadata, void *block_ptr)
1961 {
1962     int bi = FcCacheBankToIndex(metadata->bank);
1963     if (!FcStrEnsureBank(bi))
1964         return 0;
1965
1966     FcMemAlloc (FC_MEM_STRING, sizeof (char) * metadata->str_count);
1967     block_ptr = ALIGN (block_ptr, FcChar8);
1968     static_strs[bi] = (FcChar8 *)block_ptr;
1969     block_ptr = (void *)((char *)block_ptr +
1970                          (sizeof (char) * metadata->str_count));
1971
1972     return block_ptr;
1973 }
1974
1975 /* we don't store these in the FcPattern itself because
1976  * we don't want to serialize the directory names */
1977
1978 /* I suppose this should be cleaned, too... */
1979 typedef struct _FcPatternDirMapping {
1980     const FcPattern     *p;
1981     const char *fname;
1982 } FcPatternDirMapping;
1983
1984 #define PATTERNDIR_HASH_SIZE    31
1985 static struct patternDirBucket {
1986     struct patternDirBucket     *next;
1987     FcPatternDirMapping         m;
1988 } FcPatternDirBuckets[PATTERNDIR_HASH_SIZE];
1989
1990 void
1991 FcPatternAddFullFname (const FcPattern *p, const char *fname)
1992 {
1993     struct patternDirBucket     *pb;
1994
1995     /* N.B. FcPatternHash fails, since it's contents-based, not
1996      * address-based, and we're in the process of mutating the FcPattern. */
1997     for (pb = &FcPatternDirBuckets
1998              [((int)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
1999          pb->m.p != p && pb->next;
2000          pb = pb->next)
2001         ;
2002
2003     if (pb->m.p == p)
2004     {
2005         pb->m.fname = fname;
2006         return;
2007     }
2008
2009     pb->next = malloc (sizeof (struct patternDirBucket));
2010     if (!pb->next)
2011         return;
2012     FcMemAlloc (FC_MEM_CACHE, sizeof (struct patternDirBucket));
2013
2014     pb->next->next = 0;
2015     pb->next->m.p = p;
2016     pb->next->m.fname = fname;
2017 }
2018
2019 static const char *
2020 FcPatternFindFullFname (const FcPattern *p)
2021 {
2022     struct patternDirBucket     *pb;
2023
2024     for (pb = &FcPatternDirBuckets
2025              [((int)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
2026          pb; pb = pb->next)
2027         if (pb->m.p == p)
2028             return pb->m.fname;
2029
2030     return 0;
2031 }
2032
2033 void
2034 FcPatternTransferFullFname (const FcPattern *new, const FcPattern *orig)
2035 {
2036     FcChar8 * s;
2037     FcPatternGetString (orig, FC_FILE, 0, &s);
2038     FcPatternAddFullFname (new,
2039                            (char *)FcStrCopy
2040                            ((FcChar8 *)FcPatternFindFullFname(orig)));
2041 }