src/fcpat.c

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