src/fcpat.c

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