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