src/fcpat.c

   1 /*
   2  * $RCSId: xc/lib/fontconfig/src/fcpat.c,v 1.18 2002/09/18 17:11:46 tsi Exp $
   3  *
   4  * Copyright © 2000 Keith Packard
   5  *
   6  * Permission to use, copy, modify, distribute, and sell this software and its
   7  * documentation for any purpose is hereby granted without fee, provided that
   8  * the above copyright notice appear in all copies and that both that
   9  * copyright notice and this permission notice appear in supporting
  10  * documentation, and that the name of Keith Packard not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  Keith Packard makes no
  13  * representations about the suitability of this software for any purpose.  It
  14  * is provided "as is" without express or implied warranty.
  15  *
  16  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  18  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  19  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  20  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  21  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  22  * PERFORMANCE OF THIS SOFTWARE.
  23  */
  24
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <assert.h>
  28 #include "fcint.h"
  29
  30 static FcPattern ** fcpatterns = 0;
  31 static int fcpattern_bank_count = 0, fcpattern_ptr, fcpattern_count;
  32 static FcPatternElt ** fcpatternelts = 0;
  33 static int fcpatternelt_ptr, fcpatternelt_count;
  34 static FcValueList ** fcvaluelists = 0;
  35 static int fcvaluelist_bank_count = 0, fcvaluelist_ptr, fcvaluelist_count;
  36
  37 static const char *
  38 FcPatternFindFullFname (const FcPattern *p);
  39 static FcPatternEltPtr
  40 FcPatternEltPtrCreateDynamic (FcPatternElt * e);
  41
  42 /* If you are trying to duplicate an FcPattern which will be used for
  43  * rendering, be aware that (internally) you also have to use
  44  * FcPatternTransferFullFname to transfer the associated filename.  If
  45  * you are copying the font (externally) using FcPatternGetString,
  46  * then everything's fine; this caveat only applies if you're copying
  47  * the bits individually.  */
  48
  49 FcPattern *
  50 FcPatternCreate (void)
  51 {
  52     FcPattern   *p;
  53
  54     p = (FcPattern *) malloc (sizeof (FcPattern));
  55     if (!p)
  56         return 0;
  57     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern));
  58     p->num = 0;
  59     p->size = 0;
  60     p->elts = FcPatternEltPtrCreateDynamic(0);
  61     p->bank = FC_BANK_DYNAMIC;
  62     p->ref = 1;
  63     return p;
  64 }
  65
  66 void
  67 FcValueDestroy (FcValue v)
  68 {
  69     switch (v.type) {
  70     case FcTypeString:
  71         FcStrFree ((FcChar8 *) v.u.s);
  72         break;
  73     case FcTypeMatrix:
  74         FcMatrixFree ((FcMatrix *) v.u.m);
  75         break;
  76     case FcTypeCharSet:
  77         FcCharSetDestroy ((FcCharSet *) v.u.c);
  78         break;
  79     case FcTypeLangSet:
  80         FcLangSetDestroy ((FcLangSet *) v.u.l);
  81         break;
  82     default:
  83         break;
  84     }
  85 }
  86
  87 FcValue
  88 FcValueCanonicalize (const FcValue *v)
  89 {
  90     if (v->type & FC_STORAGE_STATIC)
  91     {
  92         FcValue new = *v;
  93
  94         switch (v->type & ~FC_STORAGE_STATIC)
  95         {
  96         case FcTypeString:
  97             new.u.s = fc_value_string(v);
  98             new.type = FcTypeString;
  99             break;
 100         case FcTypeCharSet:
 101             new.u.c = fc_value_charset(v);
 102             new.type = FcTypeCharSet;
 103             break;
 104         case FcTypeLangSet:
 105             new.u.l = fc_value_langset(v);
 106             new.type = FcTypeLangSet;
 107             break;
 108         }
 109         return new;
 110     }
 111     return *v;
 112 }
 113
 114 FcValue
 115 FcValueSave (FcValue v)
 116 {
 117     switch (v.type) {
 118     case FcTypeString:
 119         v.u.s = FcStrCopy (v.u.s);
 120         if (!v.u.s)
 121             v.type = FcTypeVoid;
 122         break;
 123     case FcTypeMatrix:
 124         v.u.m = FcMatrixCopy (v.u.m);
 125         if (!v.u.m)
 126             v.type = FcTypeVoid;
 127         break;
 128     case FcTypeCharSet:
 129         v.u.c = FcCharSetCopy ((FcCharSet *) v.u.c);
 130         if (!v.u.c)
 131             v.type = FcTypeVoid;
 132         break;
 133     case FcTypeLangSet:
 134         v.u.l = FcLangSetCopy (v.u.l);
 135         if (!v.u.l)
 136             v.type = FcTypeVoid;
 137         break;
 138     default:
 139         break;
 140     }
 141     return v;
 142 }
 143
 144 void
 145 FcValueListDestroy (FcValueListPtr l)
 146 {
 147     FcValueListPtr next;
 148     for (; FcValueListPtrU(l); l = next)
 149     {
 150         switch (FcValueListPtrU(l)->value.type) {
 151         case FcTypeString:
 152             FcStrFree ((FcChar8 *)FcValueListPtrU(l)->value.u.s);
 153             break;
 154         case FcTypeMatrix:
 155             FcMatrixFree ((FcMatrix *)FcValueListPtrU(l)->value.u.m);
 156             break;
 157         case FcTypeCharSet:
 158             FcCharSetDestroy
 159                 ((FcCharSet *) (FcValueListPtrU(l)->value.u.c));
 160             break;
 161         case FcTypeLangSet:
 162             FcLangSetDestroy
 163                 ((FcLangSet *) (FcValueListPtrU(l)->value.u.l));
 164             break;
 165         default:
 166             break;
 167         }
 168         next = FcValueListPtrU(l)->next;
 169         FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 170         if (l.bank == FC_BANK_DYNAMIC)
 171             free(l.u.dyn);
 172     }
 173 }
 174
 175 FcBool
 176 FcValueEqual (FcValue va, FcValue vb)
 177 {
 178     if (va.type != vb.type)
 179     {
 180         if (va.type == FcTypeInteger)
 181         {
 182             va.type = FcTypeDouble;
 183             va.u.d = va.u.i;
 184         }
 185         if (vb.type == FcTypeInteger)
 186         {
 187             vb.type = FcTypeDouble;
 188             vb.u.d = vb.u.i;
 189         }
 190         if (va.type != vb.type)
 191             return FcFalse;
 192     }
 193     switch (va.type) {
 194     case FcTypeVoid:
 195         return FcTrue;
 196     case FcTypeInteger:
 197         return va.u.i == vb.u.i;
 198     case FcTypeDouble:
 199         return va.u.d == vb.u.d;
 200     case FcTypeString:
 201         return FcStrCmpIgnoreCase (va.u.s, vb.u.s) == 0;
 202     case FcTypeBool:
 203         return va.u.b == vb.u.b;
 204     case FcTypeMatrix:
 205         return FcMatrixEqual (va.u.m, vb.u.m);
 206     case FcTypeCharSet:
 207         return FcCharSetEqual (va.u.c, vb.u.c);
 208     case FcTypeFTFace:
 209         return va.u.f == vb.u.f;
 210     case FcTypeLangSet:
 211         return FcLangSetEqual (va.u.l, vb.u.l);
 212     }
 213     return FcFalse;
 214 }
 215
 216 static FcChar32
 217 FcDoubleHash (double d)
 218 {
 219     if (d < 0)
 220         d = -d;
 221     if (d > 0xffffffff)
 222         d = 0xffffffff;
 223     return (FcChar32) d;
 224 }
 225
 226 FcChar32
 227 FcStringHash (const FcChar8 *s)
 228 {
 229     FcChar8     c;
 230     FcChar32    h = 0;
 231
 232     if (s)
 233         while ((c = *s++))
 234             h = ((h << 1) | (h >> 31)) ^ c;
 235     return h;
 236 }
 237
 238 static FcChar32
 239 FcValueHash (const FcValue *v0)
 240 {
 241     FcValue v = FcValueCanonicalize(v0);
 242     switch (v.type) {
 243     case FcTypeVoid:
 244         return 0;
 245     case FcTypeInteger:
 246         return (FcChar32) v.u.i;
 247     case FcTypeDouble:
 248         return FcDoubleHash (v.u.d);
 249     case FcTypeString:
 250         return FcStringHash (v.u.s);
 251     case FcTypeBool:
 252         return (FcChar32) v.u.b;
 253     case FcTypeMatrix:
 254         return (FcDoubleHash (v.u.m->xx) ^
 255                 FcDoubleHash (v.u.m->xy) ^
 256                 FcDoubleHash (v.u.m->yx) ^
 257                 FcDoubleHash (v.u.m->yy));
 258     case FcTypeCharSet:
 259         return (FcChar32) v.u.c->num;
 260     case FcTypeFTFace:
 261         return FcStringHash ((const FcChar8 *) ((FT_Face) v.u.f)->family_name) ^
 262                FcStringHash ((const FcChar8 *) ((FT_Face) v.u.f)->style_name);
 263     case FcTypeLangSet:
 264         return FcLangSetHash (v.u.l);
 265     }
 266     return FcFalse;
 267 }
 268
 269 static FcBool
 270 FcValueListEqual (FcValueListPtr la, FcValueListPtr lb)
 271 {
 272     if (FcValueListPtrU(la) == FcValueListPtrU(lb))
 273         return FcTrue;
 274
 275     while (FcValueListPtrU(la) && FcValueListPtrU(lb))
 276     {
 277         if (!FcValueEqual (FcValueListPtrU(la)->value,
 278                            FcValueListPtrU(lb)->value))
 279             return FcFalse;
 280         la = FcValueListPtrU(la)->next;
 281         lb = FcValueListPtrU(lb)->next;
 282     }
 283     if (FcValueListPtrU(la) || FcValueListPtrU(lb))
 284         return FcFalse;
 285     return FcTrue;
 286 }
 287
 288 static FcChar32
 289 FcValueListHash (FcValueListPtr l)
 290 {
 291     FcChar32    hash = 0;
 292
 293     while (FcValueListPtrU(l))
 294     {
 295         hash = ((hash << 1) | (hash >> 31)) ^
 296             FcValueHash (&FcValueListPtrU(l)->value);
 297         l = FcValueListPtrU(l)->next;
 298     }
 299     return hash;
 300 }
 301
 302 void
 303 FcPatternDestroy (FcPattern *p)
 304 {
 305     int             i;
 306
 307     if (p->ref == FC_REF_CONSTANT || --p->ref > 0)
 308         return;
 309
 310     if (FcPatternFindFullFname (p))
 311     {
 312         FcStrFree (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
 860     if (p->ref == FC_REF_CONSTANT)
 861         goto bail0;
 862
 863     newp = malloc (sizeof (FcValueList));
 864     if (!newp)
 865         goto bail0;
 866
 867     memset(newp, 0, sizeof (FcValueList));
 868     new = FcValueListPtrCreateDynamic(newp);
 869     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList));
 870     /* dup string */
 871     value = FcValueSave (value);
 872     if (value.type == FcTypeVoid)
 873         goto bail1;
 874
 875     FcValueListPtrU(new)->value = value;
 876     FcValueListPtrU(new)->binding = binding;
 877     FcValueListPtrU(new)->next = FcValueListPtrCreateDynamic(0);
 878
 879     e = FcPatternInsertElt (p, object);
 880     if (!e)
 881         goto bail2;
 882
 883     if (append)
 884     {
 885         for (prev = &e->values; FcValueListPtrU(*prev); prev = &FcValueListPtrU(*prev)->next)
 886             ;
 887         *prev = new;
 888     }
 889     else
 890     {
 891         FcValueListPtrU(new)->next = e->values;
 892         e->values = new;
 893     }
 894
 895     return FcTrue;
 896
 897 bail2:
 898     switch (value.type) {
 899     case FcTypeString:
 900         FcStrFree ((FcChar8 *) value.u.s);
 901         break;
 902     case FcTypeMatrix:
 903         FcMatrixFree ((FcMatrix *) value.u.m);
 904         break;
 905     case FcTypeCharSet:
 906         FcCharSetDestroy ((FcCharSet *) value.u.c);
 907         break;
 908     case FcTypeLangSet:
 909         FcLangSetDestroy ((FcLangSet *) value.u.l);
 910         break;
 911     default:
 912         break;
 913     }
 914 bail1:
 915     FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 916     free (FcValueListPtrU(new));
 917 bail0:
 918     return FcFalse;
 919 }
 920
 921 FcBool
 922 FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
 923 {
 924     return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
 925 }
 926
 927 FcBool
 928 FcPatternAddWeak  (FcPattern *p, const char *object, FcValue value, FcBool append)
 929 {
 930     return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
 931 }
 932
 933 FcBool
 934 FcPatternDel (FcPattern *p, const char *object)
 935 {
 936     FcPatternElt   *e;
 937
 938     e = FcPatternFindElt (p, object);
 939     if (!e)
 940         return FcFalse;
 941
 942     /* destroy value */
 943     FcValueListDestroy (e->values);
 944
 945     /* shuffle existing ones down */
 946     memmove (e, e+1,
 947              (FcPatternEltU(p->elts) + p->num - (e + 1)) *
 948              sizeof (FcPatternElt));
 949     p->num--;
 950     (FcPatternEltU(p->elts)+p->num)->object = 0;
 951     (FcPatternEltU(p->elts)+p->num)->values = FcValueListPtrCreateDynamic(0);
 952     return FcTrue;
 953 }
 954
 955 FcBool
 956 FcPatternRemove (FcPattern *p, const char *object, int id)
 957 {
 958     FcPatternElt    *e;
 959     FcValueListPtr  *prev, l;
 960
 961     e = FcPatternFindElt (p, object);
 962     if (!e)
 963         return FcFalse;
 964     for (prev = &e->values;
 965          FcValueListPtrU(l = *prev);
 966          prev = &FcValueListPtrU(l)->next)
 967     {
 968         if (!id)
 969         {
 970             *prev = FcValueListPtrU(l)->next;
 971             FcValueListPtrU(l)->next = FcValueListPtrCreateDynamic(0);
 972             FcValueListDestroy (l);
 973             if (!FcValueListPtrU(e->values))
 974                 FcPatternDel (p, object);
 975             return FcTrue;
 976         }
 977         id--;
 978     }
 979     return FcFalse;
 980 }
 981
 982 FcBool
 983 FcPatternAddInteger (FcPattern *p, const char *object, int i)
 984 {
 985     FcValue     v;
 986
 987     v.type = FcTypeInteger;
 988     v.u.i = i;
 989     return FcPatternAdd (p, object, v, FcTrue);
 990 }
 991
 992 FcBool
 993 FcPatternAddDouble (FcPattern *p, const char *object, double d)
 994 {
 995     FcValue     v;
 996
 997     v.type = FcTypeDouble;
 998     v.u.d = d;
 999     return FcPatternAdd (p, object, v, FcTrue);
1000 }
1001
1002
1003 FcBool
1004 FcPatternAddString (FcPattern *p, const char *object, const FcChar8 *s)
1005 {
1006     FcValue     v;
1007
1008     v.type = FcTypeString;
1009     v.u.s = FcStrStaticName(s);
1010     return FcPatternAdd (p, object, v, FcTrue);
1011 }
1012
1013 FcBool
1014 FcPatternAddMatrix (FcPattern *p, const char *object, const FcMatrix *s)
1015 {
1016     FcValue     v;
1017
1018     v.type = FcTypeMatrix;
1019     v.u.m = s;
1020     return FcPatternAdd (p, object, v, FcTrue);
1021 }
1022
1023
1024 FcBool
1025 FcPatternAddBool (FcPattern *p, const char *object, FcBool b)
1026 {
1027     FcValue     v;
1028
1029     v.type = FcTypeBool;
1030     v.u.b = b;
1031     return FcPatternAdd (p, object, v, FcTrue);
1032 }
1033
1034 FcBool
1035 FcPatternAddCharSet (FcPattern *p, const char *object, const FcCharSet *c)
1036 {
1037     FcValue     v;
1038
1039     v.type = FcTypeCharSet;
1040     v.u.c = (FcCharSet *)c;
1041     return FcPatternAdd (p, object, v, FcTrue);
1042 }
1043
1044 FcBool
1045 FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
1046 {
1047     FcValue     v;
1048
1049     v.type = FcTypeFTFace;
1050     v.u.f = (void *) f;
1051     return FcPatternAdd (p, object, v, FcTrue);
1052 }
1053
1054 FcBool
1055 FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
1056 {
1057     FcValue     v;
1058
1059     v.type = FcTypeLangSet;
1060     v.u.l = (FcLangSet *)ls;
1061     return FcPatternAdd (p, object, v, FcTrue);
1062 }
1063
1064 FcResult
1065 FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
1066 {
1067     FcPatternElt   *e;
1068     FcValueListPtr l;
1069
1070     e = FcPatternFindElt (p, object);
1071     if (!e)
1072         return FcResultNoMatch;
1073     for (l = e->values; FcValueListPtrU(l); l = FcValueListPtrU(l)->next)
1074     {
1075         if (!id)
1076         {
1077             *v = FcValueCanonicalize(&FcValueListPtrU(l)->value);
1078             return FcResultMatch;
1079         }
1080         id--;
1081     }
1082     return FcResultNoId;
1083 }
1084
1085 FcResult
1086 FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
1087 {
1088     FcValue     v;
1089     FcResult    r;
1090
1091     r = FcPatternGet (p, object, id, &v);
1092     if (r != FcResultMatch)
1093         return r;
1094     switch (v.type) {
1095     case FcTypeDouble:
1096         *i = (int) v.u.d;
1097         break;
1098     case FcTypeInteger:
1099         *i = v.u.i;
1100         break;
1101     default:
1102         return FcResultTypeMismatch;
1103     }
1104     return FcResultMatch;
1105 }
1106
1107 FcResult
1108 FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
1109 {
1110     FcValue     v;
1111     FcResult    r;
1112
1113     r = FcPatternGet (p, object, id, &v);
1114     if (r != FcResultMatch)
1115         return r;
1116     switch (v.type) {
1117     case FcTypeDouble:
1118         *d = v.u.d;
1119         break;
1120     case FcTypeInteger:
1121         *d = (double) v.u.i;
1122         break;
1123     default:
1124         return FcResultTypeMismatch;
1125     }
1126     return FcResultMatch;
1127 }
1128
1129 FcResult
1130 FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
1131 {
1132     FcValue     v;
1133     FcResult    r;
1134
1135     r = FcPatternGet (p, object, id, &v);
1136     if (r != FcResultMatch)
1137         return r;
1138     if (v.type != FcTypeString)
1139         return FcResultTypeMismatch;
1140
1141     if (FcObjectToPtr(object) == FcObjectToPtr(FC_FILE))
1142     {
1143         const char *fn, *fpath;
1144         FcChar8 *fname;
1145         int size;
1146
1147         fn = FcPatternFindFullFname(p);
1148         if (fn)
1149         {
1150             *s = (FcChar8 *) fn;
1151             return FcResultMatch;
1152         }
1153
1154         if (!p->bank)
1155         {
1156             *s = (FcChar8 *) v.u.s;
1157             return FcResultMatch;
1158         }
1159
1160         fpath = FcCacheFindBankDir (p->bank);
1161         size = strlen((char*)fpath) + 1 + strlen ((char *)v.u.s) + 1;
1162         fname = malloc (size);
1163         if (!fname)
1164             return FcResultOutOfMemory;
1165
1166         FcMemAlloc (FC_MEM_STRING, size);
1167         strcpy ((char *)fname, (char *)fpath);
1168         strcat ((char *)fname, "/");
1169         strcat ((char *)fname, (char *)v.u.s);
1170
1171         FcPatternAddFullFname (p, (const char *)fname);
1172         *s = (FcChar8 *)fname;
1173         return FcResultMatch;
1174     }
1175
1176     *s = (FcChar8 *) v.u.s;
1177     return FcResultMatch;
1178 }
1179
1180 FcResult
1181 FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
1182 {
1183     FcValue     v;
1184     FcResult    r;
1185
1186     r = FcPatternGet (p, object, id, &v);
1187     if (r != FcResultMatch)
1188         return r;
1189     if (v.type != FcTypeMatrix)
1190         return FcResultTypeMismatch;
1191     *m = (FcMatrix *)v.u.m;
1192     return FcResultMatch;
1193 }
1194
1195
1196 FcResult
1197 FcPatternGetBool(const FcPattern *p, const char *object, int id, FcBool *b)
1198 {
1199     FcValue     v;
1200     FcResult    r;
1201
1202     r = FcPatternGet (p, object, id, &v);
1203     if (r != FcResultMatch)
1204         return r;
1205     if (v.type != FcTypeBool)
1206         return FcResultTypeMismatch;
1207     *b = v.u.b;
1208     return FcResultMatch;
1209 }
1210
1211 FcResult
1212 FcPatternGetCharSet(const FcPattern *p, const char *object, int id, FcCharSet **c)
1213 {
1214     FcValue     v;
1215     FcResult    r;
1216
1217     r = FcPatternGet (p, object, id, &v);
1218     if (r != FcResultMatch)
1219         return r;
1220     if (v.type != FcTypeCharSet)
1221         return FcResultTypeMismatch;
1222     *c = (FcCharSet *)v.u.c;
1223     return FcResultMatch;
1224 }
1225
1226 FcResult
1227 FcPatternGetFTFace(const FcPattern *p, const char *object, int id, FT_Face *f)
1228 {
1229     FcValue     v;
1230     FcResult    r;
1231
1232     r = FcPatternGet (p, object, id, &v);
1233     if (r != FcResultMatch)
1234         return r;
1235     if (v.type != FcTypeFTFace)
1236         return FcResultTypeMismatch;
1237     *f = (FT_Face) v.u.f;
1238     return FcResultMatch;
1239 }
1240
1241 FcResult
1242 FcPatternGetLangSet(const FcPattern *p, const char *object, int id, FcLangSet **ls)
1243 {
1244     FcValue     v;
1245     FcResult    r;
1246
1247     r = FcPatternGet (p, object, id, &v);
1248     if (r != FcResultMatch)
1249         return r;
1250     if (v.type != FcTypeLangSet)
1251         return FcResultTypeMismatch;
1252     *ls = (FcLangSet *)v.u.l;
1253     return FcResultMatch;
1254 }
1255
1256 FcPattern *
1257 FcPatternDuplicate (const FcPattern *orig)
1258 {
1259     FcPattern       *new;
1260     FcPatternElt    *e;
1261     int             i;
1262     FcValueListPtr  l;
1263
1264     new = FcPatternCreate ();
1265     if (!new)
1266         goto bail0;
1267
1268     e = FcPatternEltU(orig->elts);
1269
1270     for (i = 0; i < orig->num; i++)
1271     {
1272         for (l = (e + i)->values;
1273              FcValueListPtrU(l);
1274              l = FcValueListPtrU(l)->next)
1275             if (!FcPatternAdd (new, FcObjectPtrU((e + i)->object),
1276                                FcValueCanonicalize(&FcValueListPtrU(l)->value),
1277                                FcTrue))
1278                 goto bail1;
1279
1280         if (!strcmp ((char *)FcObjectPtrU((e + i)->object), FC_FILE))
1281         {
1282             FcChar8 * s;
1283             FcPatternGetString (orig, FC_FILE, 0, &s);
1284             FcPatternAddFullFname (new, FcPatternFindFullFname(orig));
1285         }
1286     }
1287
1288     return new;
1289
1290 bail1:
1291     FcPatternDestroy (new);
1292 bail0:
1293     return 0;
1294 }
1295
1296 void
1297 FcPatternReference (FcPattern *p)
1298 {
1299     if (p->ref != FC_REF_CONSTANT)
1300         p->ref++;
1301 }
1302
1303 FcPattern *
1304 FcPatternVaBuild (FcPattern *orig, va_list va)
1305 {
1306     FcPattern   *ret;
1307
1308     FcPatternVapBuild (ret, orig, va);
1309     return ret;
1310 }
1311
1312 FcPattern *
1313 FcPatternBuild (FcPattern *orig, ...)
1314 {
1315     va_list     va;
1316
1317     va_start (va, orig);
1318     FcPatternVapBuild (orig, orig, va);
1319     va_end (va);
1320     return orig;
1321 }
1322
1323 /*
1324  * Add all of the elements in 's' to 'p'
1325  */
1326 FcBool
1327 FcPatternAppend (FcPattern *p, FcPattern *s)
1328 {
1329     int             i;
1330     FcPatternElt    *e;
1331     FcValueListPtr  v;
1332
1333     for (i = 0; i < s->num; i++)
1334     {
1335         e = FcPatternEltU(s->elts)+i;
1336         for (v = e->values; FcValueListPtrU(v);
1337              v = FcValueListPtrU(v)->next)
1338         {
1339             if (!FcPatternAddWithBinding (p, FcObjectPtrU(e->object),
1340                                           FcValueCanonicalize(&FcValueListPtrU(v)->value),
1341                                           FcValueListPtrU(v)->binding, FcTrue))
1342                 return FcFalse;
1343         }
1344     }
1345     return FcTrue;
1346 }
1347
1348 #define OBJECT_HASH_SIZE    31
1349 static struct objectBucket {
1350     struct objectBucket *next;
1351     FcChar32            hash;
1352 } *FcObjectBuckets[OBJECT_HASH_SIZE];
1353
1354 const FcChar8 *
1355 FcStrStaticName (const FcChar8 *name)
1356 {
1357     FcChar32            hash = FcStringHash (name);
1358     struct objectBucket **p;
1359     struct objectBucket *b;
1360     int                 size;
1361
1362     for (p = &FcObjectBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1363         if (b->hash == hash && !strcmp ((char *)name, (char *) (b + 1)))
1364             return (FcChar8 *) (b + 1);
1365     size = sizeof (struct objectBucket) + strlen ((char *)name) + 1;
1366     b = malloc (size + sizeof (int));
1367     /* workaround glibc bug which reads strlen in groups of 4 */
1368     FcMemAlloc (FC_MEM_STATICSTR, size + sizeof (int));
1369     if (!b)
1370         return NULL;
1371     b->next = 0;
1372     b->hash = hash;
1373     strcpy ((char *) (b + 1), (char *)name);
1374     *p = b;
1375     return (FcChar8 *) (b + 1);
1376 }
1377
1378 static void
1379 FcStrStaticNameFini (void)
1380 {
1381     int i, size;
1382     struct objectBucket *b, *next;
1383     char *name;
1384
1385     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1386     {
1387         for (b = FcObjectBuckets[i]; b; b = next)
1388         {
1389             next = b->next;
1390             name = (char *) (b + 1);
1391             size = sizeof (struct objectBucket) + strlen (name) + 1;
1392             FcMemFree (FC_MEM_STATICSTR, size);
1393             free (b);
1394         }
1395         FcObjectBuckets[i] = 0;
1396     }
1397 }
1398
1399 void
1400 FcPatternFini (void)
1401 {
1402     FcPatternBaseThawAll ();
1403     FcValueListThawAll ();
1404     FcStrStaticNameFini ();
1405     FcObjectStaticNameFini ();
1406 }
1407
1408 FcPatternElt *
1409 FcPatternEltU (FcPatternEltPtr pei)
1410 {
1411     if (pei.bank == FC_BANK_DYNAMIC)
1412         return pei.u.dyn;
1413
1414     return &fcpatternelts[FcCacheBankToIndex(pei.bank)][pei.u.stat];
1415 }
1416
1417 static FcPatternEltPtr
1418 FcPatternEltPtrCreateDynamic (FcPatternElt * e)
1419 {
1420     FcPatternEltPtr new;
1421     new.bank = FC_BANK_DYNAMIC;
1422     new.u.dyn = e;
1423     return new;
1424 }
1425
1426 static FcPatternEltPtr
1427 FcPatternEltPtrCreateStatic (int bank, int i)
1428 {
1429     FcPatternEltPtr new;
1430     new.bank = bank;
1431     new.u.stat = i;
1432     return new;
1433 }
1434
1435 static void
1436 FcStrNewBank (void);
1437 static int
1438 FcStrNeededBytes (const FcChar8 * s);
1439 static void *
1440 FcStrDistributeBytes (FcCache * metadata, void * block_ptr);
1441 static const FcChar8 *
1442 FcStrSerialize (int bank, const FcChar8 * s);
1443 static void *
1444 FcStrUnserialize (FcCache metadata, void *block_ptr);
1445
1446 static void
1447 FcValueListNewBank (void);
1448 static int
1449 FcValueListNeededBytes (FcValueList * vl);
1450 static void *
1451 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr);
1452 static FcValueListPtr
1453 FcValueListSerialize(int bank, FcValueList *pi);
1454 static void *
1455 FcValueListUnserialize (FcCache metadata, void *block_ptr);
1456
1457
1458 void
1459 FcPatternNewBank (void)
1460 {
1461     fcpattern_count = 0;
1462     fcpatternelt_count = 0;
1463
1464     FcStrNewBank();
1465     FcValueListNewBank();
1466 }
1467
1468 int
1469 FcPatternNeededBytes (FcPattern * p)
1470 {
1471     int i, cum = 0, c;
1472
1473     fcpattern_count++;
1474     fcpatternelt_count += p->num;
1475
1476     for (i = 0; i < p->num; i++)
1477     {
1478         c = FcValueListNeededBytes (FcValueListPtrU
1479                                     (((FcPatternEltU(p->elts)+i)->values)));
1480         if (c < 0)
1481             return c;
1482         cum += c;
1483     }
1484
1485     return cum + sizeof (FcPattern) + sizeof(FcPatternElt)*p->num;
1486 }
1487
1488 static FcBool
1489 FcPatternEnsureBank (int bi)
1490 {
1491     FcPattern **pp;
1492     FcPatternElt **ep;
1493     int i;
1494
1495     if (!fcpatterns || fcpattern_bank_count <= bi)
1496     {
1497         int new_count = bi + 4;
1498         pp = realloc (fcpatterns, sizeof (FcPattern *) * new_count);
1499         if (!pp)
1500             return 0;
1501
1502         FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern *) * new_count);
1503         fcpatterns = pp;
1504
1505         ep = realloc (fcpatternelts, sizeof (FcPatternElt *) * new_count);
1506         if (!ep)
1507             return 0;
1508
1509         FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt *) * new_count);
1510         fcpatternelts = ep;
1511
1512         for (i = fcpattern_bank_count; i < new_count; i++)
1513         {
1514             fcpatterns[i] = 0;
1515             fcpatternelts[i] = 0;
1516         }
1517
1518         fcpattern_bank_count = new_count;
1519     }
1520
1521     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * fcpattern_count);
1522     return FcTrue;
1523 }
1524
1525 void *
1526 FcPatternDistributeBytes (FcCache * metadata, void * block_ptr)
1527 {
1528     int bi = FcCacheBankToIndex(metadata->bank);
1529
1530     if (!FcPatternEnsureBank(bi))
1531         return 0;
1532
1533     fcpattern_ptr = 0;
1534     fcpatterns[bi] = (FcPattern *)block_ptr;
1535     block_ptr = (void *)((char *)block_ptr +
1536                          (sizeof (FcPattern) * fcpattern_count));
1537
1538     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt) * fcpatternelt_count);
1539     fcpatternelt_ptr = 0;
1540     fcpatternelts[bi] = (FcPatternElt *)block_ptr;
1541     block_ptr = (void *)((char *)block_ptr +
1542                          (sizeof (FcPatternElt) * fcpatternelt_count));
1543
1544     metadata->pattern_count = fcpattern_count;
1545     metadata->patternelt_count = fcpatternelt_count;
1546
1547     block_ptr = FcStrDistributeBytes (metadata, block_ptr);
1548     block_ptr = FcValueListDistributeBytes (metadata, block_ptr);
1549     return block_ptr;
1550 }
1551
1552 FcPattern *
1553 FcPatternSerialize (int bank, FcPattern *old)
1554 {
1555     FcPattern *p;
1556     FcPatternElt *e, *nep;
1557     FcValueList * nv;
1558     FcValueListPtr v, nv_head, nvp;
1559     int i, elts, bi = FcCacheBankToIndex(bank);
1560
1561     p = &fcpatterns[bi][fcpattern_ptr++];
1562     p->bank = bank;
1563     elts = fcpatternelt_ptr;
1564     nep = &fcpatternelts[bi][elts];
1565     if (!nep)
1566         return FcFalse;
1567
1568     fcpatternelt_ptr += old->num;
1569
1570     for (e = FcPatternEltU(old->elts), i=0; i < old->num; i++, e++)
1571     {
1572         v = e->values;
1573         nvp = nv_head = FcValueListSerialize(bank, FcValueListPtrU(v));
1574         if (!FcValueListPtrU(nv_head))
1575             return 0;
1576         nv = FcValueListPtrU(nvp);
1577
1578         for (;
1579              FcValueListPtrU(v);
1580              v = FcValueListPtrU(v)->next,
1581                  nv = FcValueListPtrU(nv->next))
1582         {
1583
1584             if (FcValueListPtrU(FcValueListPtrU(v)->next))
1585             {
1586                 nvp = FcValueListSerialize
1587                     (bank, FcValueListPtrU(FcValueListPtrU(v)->next));
1588                 nv->next = nvp;
1589             }
1590         }
1591
1592         nep[i].values = nv_head;
1593         nep[i].object = e->object;
1594     }
1595
1596     p->elts = old->elts;
1597     p->elts = FcPatternEltPtrCreateStatic(bank, elts);
1598     p->size = old->num;
1599     p->num = old->num;
1600     p->ref = FC_REF_CONSTANT;
1601     return p;
1602 }
1603
1604 void *
1605 FcPatternUnserialize (FcCache metadata, void *block_ptr)
1606 {
1607     int bi = FcCacheBankToIndex(metadata.bank);
1608     if (!FcPatternEnsureBank(bi))
1609         return FcFalse;
1610
1611     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * metadata.pattern_count);
1612     fcpatterns[bi] = (FcPattern *)block_ptr;
1613     block_ptr = (void *)((char *)block_ptr +
1614                          (sizeof (FcPattern) * metadata.pattern_count));
1615
1616     FcMemAlloc (FC_MEM_PATELT,
1617                 sizeof (FcPatternElt) * metadata.patternelt_count);
1618     fcpatternelts[bi] = (FcPatternElt *)block_ptr;
1619     block_ptr = (void *)((char *)block_ptr +
1620                          (sizeof (FcPatternElt) * metadata.patternelt_count));
1621
1622     block_ptr = FcStrUnserialize (metadata, block_ptr);
1623     block_ptr = FcValueListUnserialize (metadata, block_ptr);
1624
1625     return block_ptr;
1626 }
1627
1628 static void
1629 FcValueListNewBank (void)
1630 {
1631     fcvaluelist_count = 0;
1632
1633     FcCharSetNewBank();
1634     FcLangSetNewBank();
1635 }
1636
1637 static int
1638 FcValueListNeededBytes (FcValueList *p)
1639 {
1640     FcValueList *vl;
1641     int cum = 0;
1642
1643     for (vl = p;
1644          vl;
1645          vl = FcValueListPtrU(vl->next))
1646     {
1647         FcValue v = FcValueCanonicalize(&vl->value); // unserialize just in case
1648
1649         switch (v.type)
1650         {
1651         case FcTypeCharSet:
1652             cum += FcCharSetNeededBytes(v.u.c);
1653             break;
1654         case FcTypeLangSet:
1655             cum += FcLangSetNeededBytes(v.u.l);
1656             break;
1657         case FcTypeString:
1658             cum += FcStrNeededBytes(v.u.s);
1659         default:
1660             break;
1661         }
1662         fcvaluelist_count++;
1663         cum += sizeof (FcValueList);
1664     }
1665
1666     return cum;
1667 }
1668
1669 static FcBool
1670 FcValueListEnsureBank (int bi)
1671 {
1672     FcValueList **pvl;
1673
1674     if (!fcvaluelists || fcvaluelist_bank_count <= bi)
1675     {
1676         int new_count = bi + 2, i;
1677
1678         pvl = realloc (fcvaluelists, sizeof (FcValueList *) * new_count);
1679         if (!pvl)
1680             return FcFalse;
1681
1682         FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList *) * new_count);
1683
1684         fcvaluelists = pvl;
1685         for (i = fcvaluelist_bank_count; i < new_count; i++)
1686             fcvaluelists[i] = 0;
1687
1688         fcvaluelist_bank_count = new_count;
1689     }
1690     return FcTrue;
1691 }
1692
1693 static void *
1694 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr)
1695 {
1696     int bi = FcCacheBankToIndex(metadata->bank);
1697
1698     if (!FcValueListEnsureBank(bi))
1699         return 0;
1700
1701     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList) * fcvaluelist_count);
1702     fcvaluelist_ptr = 0;
1703     fcvaluelists[bi] = (FcValueList *)block_ptr;
1704     block_ptr = (void *)((char *)block_ptr +
1705                          (sizeof (FcValueList) * fcvaluelist_count));
1706     metadata->valuelist_count = fcvaluelist_count;
1707
1708     block_ptr = FcCharSetDistributeBytes(metadata, block_ptr);
1709     block_ptr = FcLangSetDistributeBytes(metadata, block_ptr);
1710
1711     return block_ptr;
1712 }
1713
1714 static FcValueListPtr
1715 FcValueListSerialize(int bank, FcValueList *pi)
1716 {
1717     FcValueListPtr new;
1718     FcValue * v;
1719     int bi = FcCacheBankToIndex(bank);
1720
1721     if (!pi)
1722     {
1723         new.bank = FC_BANK_DYNAMIC;
1724         new.u.dyn = 0;
1725         return new;
1726     }
1727
1728     fcvaluelists[bi][fcvaluelist_ptr] = *pi;
1729     new.bank = bank;
1730     new.u.stat = fcvaluelist_ptr++;
1731     fcvaluelists[bi][new.u.stat].value = FcValueCanonicalize (&pi->value);
1732     v = &fcvaluelists[bi][new.u.stat].value;
1733     switch (v->type)
1734     {
1735     case FcTypeString:
1736         if (v->u.s)
1737         {
1738             const FcChar8 * s = FcStrSerialize(bank, v->u.s);
1739             if (!s)
1740                 return FcValueListPtrCreateDynamic(pi);
1741             v->u.s_off = s - (const FcChar8 *)v;
1742             v->type |= FC_STORAGE_STATIC;
1743         }
1744         break;
1745     case FcTypeMatrix:
1746         break;
1747     case FcTypeCharSet:
1748         if (v->u.c)
1749         {
1750             FcCharSet * c = FcCharSetSerialize(bank, (FcCharSet *)v->u.c);
1751             if (!c)
1752                 return FcValueListPtrCreateDynamic(pi);
1753             v->u.c_off = (char *)c - (char *)v;
1754             v->type |= FC_STORAGE_STATIC;
1755         }
1756         break;
1757     case FcTypeLangSet:
1758         if (v->u.l)
1759         {
1760             FcLangSet * l = FcLangSetSerialize(bank, (FcLangSet *)v->u.l);
1761             if (!l)
1762                 return FcValueListPtrCreateDynamic(pi);
1763             v->u.l_off = (char *)l - (char *)v;
1764             v->type |= FC_STORAGE_STATIC;
1765         }
1766         break;
1767     default:
1768         break;
1769     }
1770     return new;
1771 }
1772
1773 static void *
1774 FcValueListUnserialize (FcCache metadata, void *block_ptr)
1775 {
1776     int bi = FcCacheBankToIndex(metadata.bank);
1777
1778     if (!FcValueListEnsureBank(bi))
1779         return 0;
1780
1781     FcMemAlloc (FC_MEM_VALLIST,
1782                 sizeof (FcValueList) * metadata.valuelist_count);
1783     fcvaluelists[bi] = (FcValueList *)block_ptr;
1784     block_ptr = (void *)((char *)block_ptr +
1785                          (sizeof (FcValueList) * metadata.valuelist_count));
1786
1787     block_ptr = FcCharSetUnserialize(metadata, block_ptr);
1788     block_ptr = FcLangSetUnserialize(metadata, block_ptr);
1789
1790     return block_ptr;
1791 }
1792
1793 FcValueList *
1794 FcValueListPtrU (FcValueListPtr pi)
1795 {
1796     if (pi.bank == FC_BANK_DYNAMIC)
1797         return pi.u.dyn;
1798
1799     return &fcvaluelists[FcCacheBankToIndex(pi.bank)][pi.u.stat];
1800 }
1801
1802 FcValueListPtr
1803 FcValueListPtrCreateDynamic(FcValueList * p)
1804 {
1805     FcValueListPtr r;
1806
1807     r.bank = FC_BANK_DYNAMIC;
1808     r.u.dyn = p;
1809     return r;
1810 }
1811
1812 static FcChar8 ** static_strs;
1813 static int static_str_bank_count = 0, fcstr_ptr, fcstr_count;
1814
1815 static struct objectBucket *FcStrBuckets[OBJECT_HASH_SIZE];
1816
1817 static void
1818 FcStrNewBank (void)
1819 {
1820     int i, size;
1821     struct objectBucket *b, *next;
1822     char *name;
1823
1824     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1825     {
1826         for (b = FcStrBuckets[i]; b; b = next)
1827         {
1828             next = b->next;
1829             name = (char *) (b + 1);
1830             size = sizeof (struct objectBucket) + strlen (name) + 1;
1831             FcMemFree (FC_MEM_STATICSTR, size);
1832             free (b);
1833         }
1834         FcStrBuckets[i] = 0;
1835     }
1836
1837     fcstr_count = 0;
1838 }
1839
1840 static int
1841 FcStrNeededBytes (const FcChar8 * s)
1842 {
1843     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1844     struct objectBucket **p;
1845     struct objectBucket *b;
1846     int                 size;
1847
1848     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1849         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1850             return 0;
1851     size = sizeof (struct objectBucket) + strlen ((char *)s) + 1 + sizeof(char *);
1852     b = malloc (size);
1853     FcMemAlloc (FC_MEM_STATICSTR, size);
1854     if (!b)
1855         return -1;
1856     b->next = 0;
1857     b->hash = hash;
1858     strcpy ((char *) (b + 1), (char *)s);
1859     *(char **)((char *) (b + 1) + strlen((char *)s) + 1) = 0;
1860     *p = b;
1861
1862     fcstr_count += strlen((char *)s) + 1;
1863     return strlen((char *)s) + 1;
1864 }
1865
1866 static FcBool
1867 FcStrEnsureBank (int bi)
1868 {
1869     FcChar8 ** ss;
1870
1871     if (!static_strs || static_str_bank_count <= bi)
1872     {
1873         int new_count = bi + 4, i;
1874         ss = realloc (static_strs, sizeof (const char *) * new_count);
1875         if (!ss)
1876             return FcFalse;
1877
1878         FcMemAlloc (FC_MEM_STRING, sizeof (const char *) * (new_count-static_str_bank_count));
1879         static_strs = ss;
1880
1881         for (i = static_str_bank_count; i < new_count; i++)
1882             static_strs[i] = 0;
1883         static_str_bank_count = new_count;
1884     }
1885     return FcTrue;
1886 }
1887
1888 static void *
1889 FcStrDistributeBytes (FcCache * metadata, void * block_ptr)
1890 {
1891     int bi = FcCacheBankToIndex(metadata->bank);
1892     if (!FcStrEnsureBank(bi))
1893         return 0;
1894
1895     FcMemAlloc (FC_MEM_STRING, sizeof (char) * fcstr_count);
1896     static_strs[bi] = (FcChar8 *)block_ptr;
1897     block_ptr = (void *)((char *)block_ptr + (sizeof (char) * fcstr_count));
1898     metadata->str_count = fcstr_count;
1899     fcstr_ptr = 0;
1900
1901     return block_ptr;
1902 }
1903
1904 static const FcChar8 *
1905 FcStrSerialize (int bank, const FcChar8 * s)
1906 {
1907     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1908     struct objectBucket **p;
1909     struct objectBucket *b;
1910     int bi = FcCacheBankToIndex(bank);
1911
1912     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1913         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1914         {
1915             FcChar8 * t = *(FcChar8 **)(((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1);
1916             if (!t)
1917             {
1918                 strcpy((char *)(static_strs[bi] + fcstr_ptr), (char *)s);
1919                 *(FcChar8 **)((FcChar8 *) (b + 1) + strlen((char *)s) + 1) = (static_strs[bi] + fcstr_ptr);
1920                 fcstr_ptr += strlen((char *)s) + 1;
1921                 t = *(FcChar8 **)(((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1);
1922             }
1923             return t;
1924         }
1925     return 0;
1926 }
1927
1928 static void *
1929 FcStrUnserialize (FcCache metadata, void *block_ptr)
1930 {
1931     int bi = FcCacheBankToIndex(metadata.bank);
1932     if (!FcStrEnsureBank(bi))
1933         return 0;
1934
1935     FcMemAlloc (FC_MEM_STRING, sizeof (char) * metadata.str_count);
1936     static_strs[bi] = (FcChar8 *)block_ptr;
1937     block_ptr = (void *)((char *)block_ptr +
1938                          (sizeof (char) * metadata.str_count));
1939
1940     return block_ptr;
1941 }
1942
1943 /* we don't store these in the FcPattern itself because
1944  * we don't want to serialize the directory names */
1945
1946 /* I suppose this should be cleaned, too... */
1947 typedef struct _FcPatternDirMapping {
1948     const FcPattern     *p;
1949     const char *fname;
1950 } FcPatternDirMapping;
1951
1952 #define PATTERNDIR_HASH_SIZE    31
1953 static struct patternDirBucket {
1954     struct patternDirBucket     *next;
1955     FcPatternDirMapping         m;
1956 } FcPatternDirBuckets[PATTERNDIR_HASH_SIZE];
1957
1958 void
1959 FcPatternAddFullFname (const FcPattern *p, const char *fname)
1960 {
1961     struct patternDirBucket     *pb;
1962
1963     /* N.B. FcPatternHash fails, since it's contents-based, not
1964      * address-based, and we're in the process of mutating the FcPattern. */
1965     for (pb = &FcPatternDirBuckets
1966              [((int)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
1967          pb->m.p != p && pb->next;
1968          pb = pb->next)
1969         ;
1970
1971     if (pb->m.p == p)
1972     {
1973         pb->m.fname = fname;
1974         return;
1975     }
1976
1977     pb->next = malloc (sizeof (struct patternDirBucket));
1978     if (!pb->next)
1979         return;
1980     FcMemAlloc (FC_MEM_CACHE, sizeof (struct patternDirBucket));
1981
1982     pb->next->next = 0;
1983     pb->next->m.p = p;
1984     pb->next->m.fname = fname;
1985 }
1986
1987 static const char *
1988 FcPatternFindFullFname (const FcPattern *p)
1989 {
1990     struct patternDirBucket     *pb;
1991
1992     for (pb = &FcPatternDirBuckets
1993              [((int)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
1994          pb; pb = pb->next)
1995         if (pb->m.p == p)
1996             return pb->m.fname;
1997
1998     return 0;
1999 }
2000
2001 void
2002 FcPatternTransferFullFname (const FcPattern *new, const FcPattern *orig)
2003 {
2004     FcChar8 * s;
2005     FcPatternGetString (orig, FC_FILE, 0, &s);
2006     FcPatternAddFullFname (new, FcStrCopy (FcPatternFindFullFname(orig)));
2007 }