src/fcpat.c

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