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