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         return 0;
 403     memset(new, 0, n * sizeof (FcValueList));
 404     FcMemAlloc (FC_MEM_VALLIST, size);
 405     e = &ea->ent;
 406     e->list = FcValueListPtrCreateDynamic(new);
 407     for (l = h; FcValueListPtrU(l);
 408          l = FcValueListPtrU(l)->next, new++)
 409     {
 410         if ((FcValueListPtrU(l)->value.type & ~FC_STORAGE_STATIC) == FcTypeString)
 411         {
 412             new->value.type = FcTypeString;
 413             new->value.u.s = FcStrStaticName
 414                 (fc_value_string(&FcValueListPtrU(l)->value));
 415         }
 416         else
 417         {
 418             new->value = FcValueSave (FcValueCanonicalize
 419                                       (&FcValueListPtrU(l)->value));
 420         }
 421         new->binding = FcValueListPtrU(l)->binding;
 422         if (FcValueListPtrU(FcValueListPtrU(l)->next))
 423         {
 424             new->next = FcValueListPtrCreateDynamic(new + 1);
 425         }
 426         else
 427         {
 428             new->next = FcValueListPtrCreateDynamic(0);
 429         }
 430     }
 431     return e;
 432 }
 433
 434 static void
 435 FcValueListEntDestroy (FcValueListEnt *e)
 436 {
 437     FcValueListPtr      l;
 438
 439     FcValueListFrozenCount[FcValueListPtrU(e->list)->value.type]--;
 440
 441     /* XXX: We should perform these two operations with "size" as
 442        computed in FcValueListEntCreate, but we don't have access to
 443        that value here. Without this, the FcValueListFrozenBytes
 444        values will be wrong as will the FcMemFree counts.
 445
 446        FcValueListFrozenBytes[e->list->value.type] -= size;
 447        FcMemFree (FC_MEM_VALLIST, size);
 448     */
 449
 450     for (l = e->list; FcValueListPtrU(l);
 451          l = FcValueListPtrU(l)->next)
 452     {
 453         if (FcValueListPtrU(l)->value.type != FcTypeString)
 454             FcValueDestroy (FcValueListPtrU(l)->value);
 455     }
 456     /* XXX: Are we being too chummy with the implementation here to
 457        free(e) when it was actually the enclosing FcValueListAlign
 458        that was allocated? */
 459     free (e);
 460 }
 461
 462 static int      FcValueListTotal;
 463 static int      FcValueListUsed;
 464
 465 static FcValueListEnt   *FcValueListHashTable[FC_VALUE_LIST_HASH_SIZE];
 466
 467 static FcValueListPtr
 468 FcValueListFreeze (FcValueListPtr l)
 469 {
 470     FcChar32                hash = FcValueListHash (l);
 471     FcValueListEnt          **bucket = &FcValueListHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
 472     FcValueListEnt          *ent;
 473
 474     FcValueListTotal++;
 475     for (ent = *bucket; ent; ent = ent->next)
 476     {
 477         if (ent->hash == hash && FcValueListEqual (ent->list, l))
 478             return ent->list;
 479     }
 480
 481     ent = FcValueListEntCreate (l);
 482     if (!ent)
 483         return FcValueListPtrCreateDynamic(0);
 484
 485     FcValueListUsed++;
 486     ent->hash = hash;
 487     ent->next = *bucket;
 488     *bucket = ent;
 489     return ent->list;
 490 }
 491
 492 static void
 493 FcValueListThawAll (void)
 494 {
 495     int i;
 496     FcValueListEnt      *ent, *next;
 497
 498     for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
 499     {
 500         for (ent = FcValueListHashTable[i]; ent; ent = next)
 501         {
 502             next = ent->next;
 503             FcValueListEntDestroy (ent);
 504         }
 505         FcValueListHashTable[i] = 0;
 506     }
 507
 508     FcValueListTotal = 0;
 509     FcValueListUsed = 0;
 510 }
 511
 512 static FcChar32
 513 FcPatternBaseHash (FcPattern *b)
 514 {
 515     FcChar32    hash = b->num;
 516     int         i;
 517
 518     for (i = 0; i < b->num; i++)
 519         hash = ((hash << 1) | (hash >> 31)) ^
 520             (long) (FcValueListPtrU((FcPatternEltU(b->elts)+i)->values));
 521     return hash;
 522 }
 523
 524 typedef struct _FcPatternEnt FcPatternEnt;
 525
 526 struct _FcPatternEnt {
 527     FcPatternEnt    *next;
 528     FcChar32        hash;
 529     FcPattern       *pattern;
 530 };
 531
 532 static int      FcPatternTotal;
 533 static int      FcPatternUsed;
 534
 535 static FcPatternEnt     *FcPatternHashTable[FC_VALUE_LIST_HASH_SIZE];
 536
 537 static FcPattern *
 538 FcPatternBaseFreeze (FcPattern *b)
 539 {
 540     FcPattern           *ep;
 541     FcPatternElt        *epp;
 542     FcChar32            hash = FcPatternBaseHash (b);
 543     FcPatternEnt        **bucket = &FcPatternHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
 544     FcPatternEnt        *ent;
 545     int                 i;
 546
 547     FcPatternTotal++;
 548     for (ent = *bucket; ent; ent = ent->next)
 549     {
 550         if (ent->hash == hash && b->num == ent->pattern->num)
 551         {
 552             for (i = 0; i < b->num; i++)
 553             {
 554                 if (FcObjectPtrCompare((FcPatternEltU(b->elts)+i)->object,
 555                                        (FcPatternEltU(ent->pattern->elts)+i)->object) != 0)
 556                     break;
 557                 if (FcValueListPtrU((FcPatternEltU(b->elts)+i)->values) !=
 558                     FcValueListPtrU((FcPatternEltU(ent->pattern->elts)+i)->values))
 559                     break;
 560             }
 561             if (i == b->num)
 562                 return ent->pattern;
 563         }
 564     }
 565
 566     /*
 567      * Compute size of pattern + elts
 568      */
 569     ent = malloc (sizeof (FcPatternEnt));
 570     if (!ent)
 571         return 0;
 572
 573     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPatternEnt));
 574     FcPatternUsed++;
 575
 576     ep = FcPatternCreate();
 577     if (!ep)
 578         return 0;
 579     ent->pattern = ep;
 580     epp = malloc(b->num * sizeof (FcPatternElt));
 581     if (!epp)
 582         goto bail;
 583     ep->elts = FcPatternEltPtrCreateDynamic(epp);
 584
 585     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));
 586
 587     ep->num = b->num;
 588     ep->size = b->num;
 589     ep->ref = FC_REF_CONSTANT;
 590
 591     for (i = 0; i < b->num; i++)
 592     {
 593         (FcPatternEltU(ep->elts)+i)->values =
 594             (FcPatternEltU(b->elts)+i)->values;
 595         (FcPatternEltU(ep->elts)+i)->object =
 596             (FcPatternEltU(b->elts)+i)->object;
 597     }
 598
 599     if (FcPatternFindElt (b, FC_FILE))
 600         FcPatternTransferFullFname (ep, b);
 601
 602     ent->hash = hash;
 603     ent->next = *bucket;
 604     *bucket = ent;
 605     return ent->pattern;
 606  bail:
 607     free(ent);
 608     FcMemFree (FC_MEM_PATTERN, sizeof (FcPatternEnt));
 609     FcPatternUsed--;
 610     return 0;
 611 }
 612
 613 static void
 614 FcPatternBaseThawAll (void)
 615 {
 616     int i;
 617     FcPatternEnt        *ent, *next;
 618
 619     for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
 620     {
 621         for (ent = FcPatternHashTable[i]; ent; ent = next)
 622         {
 623             next = ent->next;
 624             free (ent);
 625         }
 626         FcPatternHashTable[i] = 0;
 627     }
 628
 629     FcPatternTotal = 0;
 630     FcPatternUsed = 0;
 631 }
 632
 633 FcPattern *
 634 FcPatternFreeze (FcPattern *p)
 635 {
 636     FcPattern   *b, *n = 0;
 637     FcPatternElt *e;
 638     int         i;
 639
 640     if (p->ref == FC_REF_CONSTANT)
 641        return p;
 642
 643     b = FcPatternCreate();
 644     if (!b)
 645         return 0;
 646
 647     b->num = p->num;
 648     b->size = b->num;
 649     b->ref = 1;
 650
 651     e = malloc(b->num * sizeof (FcPatternElt));
 652     if (!e)
 653         return 0;
 654     b->elts = FcPatternEltPtrCreateDynamic(e);
 655     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));
 656
 657     /*
 658      * Freeze object lists
 659      */
 660     for (i = 0; i < p->num; i++)
 661     {
 662         (FcPatternEltU(b->elts)+i)->object =
 663             (FcPatternEltU(p->elts)+i)->object;
 664         (FcPatternEltU(b->elts)+i)->values =
 665             FcValueListFreeze((FcPatternEltU(p->elts)+i)->values);
 666         if (!FcValueListPtrU((FcPatternEltU(p->elts)+i)->values))
 667             goto bail;
 668     }
 669
 670     if (FcPatternFindElt (p, FC_FILE))
 671         FcPatternTransferFullFname (b, p);
 672
 673     /*
 674      * Freeze base
 675      */
 676     n = FcPatternBaseFreeze (b);
 677 #ifdef CHATTY
 678     if (FcDebug() & FC_DBG_MEMORY)
 679     {
 680         printf ("ValueLists: total %9d used %9d\n", FcValueListTotal, FcValueListUsed);
 681         printf ("Patterns:   total %9d used %9d\n", FcPatternTotal, FcPatternUsed);
 682     }
 683 #endif
 684  bail:
 685     free(FcPatternEltU(b->elts));
 686     b->elts = FcPatternEltPtrCreateDynamic(0);
 687     FcMemFree (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));
 688     b->num = -1;
 689 #ifdef DEBUG
 690     assert (FcPatternEqual (n, p));
 691 #endif
 692     return n;
 693 }
 694
 695 static int
 696 FcPatternPosition (const FcPattern *p, const char *object)
 697 {
 698     int     low, high, mid, c;
 699     FcObjectPtr obj;
 700
 701     obj = FcObjectToPtr(object);
 702     low = 0;
 703     high = p->num - 1;
 704     c = 1;
 705     mid = 0;
 706     while (low <= high)
 707     {
 708         mid = (low + high) >> 1;
 709         c = FcObjectPtrCompare((FcPatternEltU(p->elts)+mid)->object, obj);
 710         if (c == 0)
 711             return mid;
 712         if (c < 0)
 713             low = mid + 1;
 714         else
 715             high = mid - 1;
 716     }
 717     if (c < 0)
 718         mid++;
 719     return -(mid + 1);
 720 }
 721
 722 FcPatternElt *
 723 FcPatternFindElt (const FcPattern *p, const char *object)
 724 {
 725     int     i = FcPatternPosition (p, object);
 726     if (i < 0)
 727         return 0;
 728     return FcPatternEltU(p->elts)+i;
 729 }
 730
 731 FcPatternElt *
 732 FcPatternInsertElt (FcPattern *p, const char *object)
 733 {
 734     int             i;
 735     FcPatternElt   *e;
 736
 737     i = FcPatternPosition (p, object);
 738     if (i < 0)
 739     {
 740         i = -i - 1;
 741
 742         /* reallocate array */
 743         if (p->num + 1 >= p->size)
 744         {
 745             int s = p->size + 16;
 746             if (FcPatternEltU(p->elts))
 747             {
 748                 FcPatternElt *e0 = FcPatternEltU(p->elts);
 749                 e = (FcPatternElt *) realloc (e0, s * sizeof (FcPatternElt));
 750                 if (!e) /* maybe it was mmapped */
 751                 {
 752                     e = malloc(s * sizeof (FcPatternElt));
 753                     if (e)
 754                         memcpy(e, e0, p->num * sizeof (FcPatternElt));
 755                 }
 756             }
 757             else
 758                 e = (FcPatternElt *) malloc (s * sizeof (FcPatternElt));
 759             if (!e)
 760                 return FcFalse;
 761             p->elts = FcPatternEltPtrCreateDynamic(e);
 762             if (p->size)
 763                 FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
 764             FcMemAlloc (FC_MEM_PATELT, s * sizeof (FcPatternElt));
 765             while (p->size < s)
 766             {
 767                 (FcPatternEltU(p->elts)+p->size)->object = 0;
 768                 (FcPatternEltU(p->elts)+p->size)->values =
 769                     FcValueListPtrCreateDynamic(0);
 770                 p->size++;
 771             }
 772         }
 773
 774         /* move elts up */
 775         memmove (FcPatternEltU(p->elts) + i + 1,
 776                  FcPatternEltU(p->elts) + i,
 777                  sizeof (FcPatternElt) *
 778                  (p->num - i));
 779
 780         /* bump count */
 781         p->num++;
 782
 783         (FcPatternEltU(p->elts)+i)->object = FcObjectToPtr (object);
 784         (FcPatternEltU(p->elts)+i)->values = FcValueListPtrCreateDynamic(0);
 785     }
 786
 787     return FcPatternEltU(p->elts)+i;
 788 }
 789
 790 FcBool
 791 FcPatternEqual (const FcPattern *pa, const FcPattern *pb)
 792 {
 793     int i;
 794
 795     if (pa == pb)
 796         return FcTrue;
 797
 798     if (pa->num != pb->num)
 799         return FcFalse;
 800     for (i = 0; i < pa->num; i++)
 801     {
 802         if (FcObjectPtrCompare((FcPatternEltU(pa->elts)+i)->object,
 803                                (FcPatternEltU(pb->elts)+i)->object) != 0)
 804             return FcFalse;
 805         if (!FcValueListEqual ((FcPatternEltU(pa->elts)+i)->values,
 806                                (FcPatternEltU(pb->elts)+i)->values))
 807             return FcFalse;
 808     }
 809     return FcTrue;
 810 }
 811
 812 FcChar32
 813 FcPatternHash (const FcPattern *p)
 814 {
 815     int         i;
 816     FcChar32    h = 0;
 817
 818     for (i = 0; i < p->num; i++)
 819     {
 820         h = (((h << 1) | (h >> 31)) ^
 821              FcStringHash ((FcChar8 *)FcObjectPtrU ((FcPatternEltU(p->elts)+i)->object)) ^
 822              FcValueListHash ((FcPatternEltU(p->elts)+i)->values));
 823     }
 824     return h;
 825 }
 826
 827 FcBool
 828 FcPatternEqualSubset (const FcPattern *pai, const FcPattern *pbi, const FcObjectSet *os)
 829 {
 830     FcPatternElt    *ea, *eb;
 831     int             i;
 832
 833     for (i = 0; i < os->nobject; i++)
 834     {
 835         ea = FcPatternFindElt (pai, os->objects[i]);
 836         eb = FcPatternFindElt (pbi, os->objects[i]);
 837         if (ea)
 838         {
 839             if (!eb)
 840                 return FcFalse;
 841             if (!FcValueListEqual (ea->values, eb->values))
 842                 return FcFalse;
 843         }
 844         else
 845         {
 846             if (eb)
 847                 return FcFalse;
 848         }
 849     }
 850     return FcTrue;
 851 }
 852
 853 FcBool
 854 FcPatternAddWithBinding  (FcPattern         *p,
 855                           const char        *object,
 856                           FcValue           value,
 857                           FcValueBinding    binding,
 858                           FcBool            append)
 859 {
 860     FcPatternElt   *e;
 861     FcValueListPtr new, *prev;
 862     FcValueList    *newp;
 863     FcObjectPtr    objectPtr;
 864
 865     if (p->ref == FC_REF_CONSTANT)
 866         goto bail0;
 867
 868     newp = malloc (sizeof (FcValueList));
 869     if (!newp)
 870         goto bail0;
 871
 872     memset(newp, 0, sizeof (FcValueList));
 873     new = FcValueListPtrCreateDynamic(newp);
 874     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList));
 875     /* dup string */
 876     if (value.type == FcTypeString)
 877     {
 878         value.u.s = FcStrStaticName (value.u.s);
 879         if (!value.u.s)
 880             value.type = FcTypeVoid;
 881     }
 882     else
 883         value = FcValueSave (value);
 884     if (value.type == FcTypeVoid)
 885         goto bail1;
 886
 887     /* quick and dirty hack to enable FcCompareFamily/FcCompareString
 888      * speedup: only allow strings to be added under the FC_FAMILY,
 889      * FC_FOUNDRY, FC_STYLE, FC_RASTERIZER keys.
 890      * and charsets under FC_CHARSET key.
 891      * This is slightly semantically different from the old behaviour,
 892      * but fonts shouldn't be getting non-strings here anyway.
 893      * a better hack would use FcBaseObjectTypes to check all objects. */
 894     objectPtr = FcObjectToPtr(object);
 895     if ((objectPtr == FcObjectToPtr(FC_FAMILY)
 896          || objectPtr == FcObjectToPtr(FC_FOUNDRY)
 897          || objectPtr == FcObjectToPtr(FC_STYLE)
 898          || objectPtr == FcObjectToPtr(FC_RASTERIZER))
 899         && value.type != FcTypeString)
 900         goto bail1;
 901     if (objectPtr == FcObjectToPtr(FC_CHARSET)
 902         && value.type != FcTypeCharSet)
 903         goto bail1;
 904
 905     FcValueListPtrU(new)->value = value;
 906     FcValueListPtrU(new)->binding = binding;
 907     FcValueListPtrU(new)->next = FcValueListPtrCreateDynamic(0);
 908
 909     e = FcPatternInsertElt (p, object);
 910     if (!e)
 911         goto bail2;
 912
 913     if (append)
 914     {
 915         for (prev = &e->values; FcValueListPtrU(*prev); prev = &FcValueListPtrU(*prev)->next)
 916             ;
 917         *prev = new;
 918     }
 919     else
 920     {
 921         FcValueListPtrU(new)->next = e->values;
 922         e->values = new;
 923     }
 924
 925     return FcTrue;
 926
 927 bail2:
 928     switch (value.type) {
 929     case FcTypeString:
 930         FcStrFree ((FcChar8 *) value.u.s);
 931         break;
 932     case FcTypeMatrix:
 933         FcMatrixFree ((FcMatrix *) value.u.m);
 934         break;
 935     case FcTypeCharSet:
 936         FcCharSetDestroy ((FcCharSet *) value.u.c);
 937         break;
 938     case FcTypeLangSet:
 939         FcLangSetDestroy ((FcLangSet *) value.u.l);
 940         break;
 941     default:
 942         break;
 943     }
 944 bail1:
 945     FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 946     free (FcValueListPtrU(new));
 947 bail0:
 948     return FcFalse;
 949 }
 950
 951 FcBool
 952 FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
 953 {
 954     return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
 955 }
 956
 957 FcBool
 958 FcPatternAddWeak  (FcPattern *p, const char *object, FcValue value, FcBool append)
 959 {
 960     return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
 961 }
 962
 963 FcBool
 964 FcPatternDel (FcPattern *p, const char *object)
 965 {
 966     FcPatternElt   *e;
 967
 968     e = FcPatternFindElt (p, object);
 969     if (!e)
 970         return FcFalse;
 971
 972     /* destroy value */
 973     FcValueListDestroy (e->values);
 974
 975     /* shuffle existing ones down */
 976     memmove (e, e+1,
 977              (FcPatternEltU(p->elts) + p->num - (e + 1)) *
 978              sizeof (FcPatternElt));
 979     p->num--;
 980     (FcPatternEltU(p->elts)+p->num)->object = 0;
 981     (FcPatternEltU(p->elts)+p->num)->values = FcValueListPtrCreateDynamic(0);
 982     return FcTrue;
 983 }
 984
 985 FcBool
 986 FcPatternRemove (FcPattern *p, const char *object, int id)
 987 {
 988     FcPatternElt    *e;
 989     FcValueListPtr  *prev, l;
 990
 991     e = FcPatternFindElt (p, object);
 992     if (!e)
 993         return FcFalse;
 994     for (prev = &e->values;
 995          FcValueListPtrU(l = *prev);
 996          prev = &FcValueListPtrU(l)->next)
 997     {
 998         if (!id)
 999         {
1000             *prev = FcValueListPtrU(l)->next;
1001             FcValueListPtrU(l)->next = FcValueListPtrCreateDynamic(0);
1002             FcValueListDestroy (l);
1003             if (!FcValueListPtrU(e->values))
1004                 FcPatternDel (p, object);
1005             return FcTrue;
1006         }
1007         id--;
1008     }
1009     return FcFalse;
1010 }
1011
1012 FcBool
1013 FcPatternAddInteger (FcPattern *p, const char *object, int i)
1014 {
1015     FcValue     v;
1016
1017     v.type = FcTypeInteger;
1018     v.u.i = i;
1019     return FcPatternAdd (p, object, v, FcTrue);
1020 }
1021
1022 FcBool
1023 FcPatternAddDouble (FcPattern *p, const char *object, double d)
1024 {
1025     FcValue     v;
1026
1027     v.type = FcTypeDouble;
1028     v.u.d = d;
1029     return FcPatternAdd (p, object, v, FcTrue);
1030 }
1031
1032
1033 FcBool
1034 FcPatternAddString (FcPattern *p, const char *object, const FcChar8 *s)
1035 {
1036     FcValue     v;
1037
1038     if (!s)
1039     {
1040         v.type = FcTypeVoid;
1041         v.u.s = 0;
1042         return FcPatternAdd (p, object, v, FcTrue);
1043     }
1044
1045     v.type = FcTypeString;
1046     v.u.s = FcStrStaticName(s);
1047     return FcPatternAdd (p, object, v, FcTrue);
1048 }
1049
1050 FcBool
1051 FcPatternAddMatrix (FcPattern *p, const char *object, const FcMatrix *s)
1052 {
1053     FcValue     v;
1054
1055     v.type = FcTypeMatrix;
1056     v.u.m = s;
1057     return FcPatternAdd (p, object, v, FcTrue);
1058 }
1059
1060
1061 FcBool
1062 FcPatternAddBool (FcPattern *p, const char *object, FcBool b)
1063 {
1064     FcValue     v;
1065
1066     v.type = FcTypeBool;
1067     v.u.b = b;
1068     return FcPatternAdd (p, object, v, FcTrue);
1069 }
1070
1071 FcBool
1072 FcPatternAddCharSet (FcPattern *p, const char *object, const FcCharSet *c)
1073 {
1074     FcValue     v;
1075
1076     v.type = FcTypeCharSet;
1077     v.u.c = (FcCharSet *)c;
1078     return FcPatternAdd (p, object, v, FcTrue);
1079 }
1080
1081 FcBool
1082 FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
1083 {
1084     FcValue     v;
1085
1086     v.type = FcTypeFTFace;
1087     v.u.f = (void *) f;
1088     return FcPatternAdd (p, object, v, FcTrue);
1089 }
1090
1091 FcBool
1092 FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
1093 {
1094     FcValue     v;
1095
1096     v.type = FcTypeLangSet;
1097     v.u.l = (FcLangSet *)ls;
1098     return FcPatternAdd (p, object, v, FcTrue);
1099 }
1100
1101 static FcResult
1102 FcPatternGetFile (const FcPattern *p, const char *object, int id, FcChar8 ** s)
1103 {
1104     const char *fn, *fpath;
1105     FcChar8 *fname;
1106     int size;
1107
1108     fn = FcPatternFindFullFname(p);
1109     if (fn)
1110     {
1111         *s = (FcChar8 *) fn;
1112         return FcResultMatch;
1113     }
1114
1115     if (!p->bank)
1116         return FcResultMatch;
1117
1118     fpath = FcCacheFindBankDir (p->bank);
1119     size = strlen((char *)fpath) + 1 + strlen ((char *)*s) + 1;
1120     fname = malloc (size);
1121     if (!fname)
1122         return FcResultOutOfMemory;
1123
1124     FcMemAlloc (FC_MEM_STRING, size);
1125     strcpy ((char *)fname, (char *)fpath);
1126     strcat ((char *)fname, "/");
1127     strcat ((char *)fname, (char *)*s);
1128
1129     FcPatternAddFullFname (p, (const char *)fname);
1130     *s = (FcChar8 *)fname;
1131     return FcResultMatch;
1132 }
1133
1134 FcResult
1135 FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
1136 {
1137     FcPatternElt   *e;
1138     FcValueListPtr l;
1139
1140     e = FcPatternFindElt (p, object);
1141     if (!e)
1142         return FcResultNoMatch;
1143     for (l = e->values; FcValueListPtrU(l); l = FcValueListPtrU(l)->next)
1144     {
1145         if (!id)
1146         {
1147             *v = FcValueCanonicalize(&FcValueListPtrU(l)->value);
1148
1149             /* Pull the FC_FILE trick here too. */
1150             if (v->type == FcTypeString &&
1151                 FcObjectToPtr(object) == FcObjectToPtr(FC_FILE))
1152                 return FcPatternGetFile (p, object, id, (FcChar8 **)&(v->u.s));
1153
1154             return FcResultMatch;
1155         }
1156         id--;
1157     }
1158     return FcResultNoId;
1159 }
1160
1161 FcResult
1162 FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
1163 {
1164     FcValue     v;
1165     FcResult    r;
1166
1167     r = FcPatternGet (p, object, id, &v);
1168     if (r != FcResultMatch)
1169         return r;
1170     switch (v.type) {
1171     case FcTypeDouble:
1172         *i = (int) v.u.d;
1173         break;
1174     case FcTypeInteger:
1175         *i = v.u.i;
1176         break;
1177     default:
1178         return FcResultTypeMismatch;
1179     }
1180     return FcResultMatch;
1181 }
1182
1183 FcResult
1184 FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
1185 {
1186     FcValue     v;
1187     FcResult    r;
1188
1189     r = FcPatternGet (p, object, id, &v);
1190     if (r != FcResultMatch)
1191         return r;
1192     switch (v.type) {
1193     case FcTypeDouble:
1194         *d = v.u.d;
1195         break;
1196     case FcTypeInteger:
1197         *d = (double) v.u.i;
1198         break;
1199     default:
1200         return FcResultTypeMismatch;
1201     }
1202     return FcResultMatch;
1203 }
1204
1205 FcResult
1206 FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
1207 {
1208     FcValue     v;
1209     FcResult    r;
1210
1211     r = FcPatternGet (p, object, id, &v);
1212     if (r != FcResultMatch)
1213         return r;
1214     if (v.type != FcTypeString)
1215         return FcResultTypeMismatch;
1216
1217     *s = (FcChar8 *) v.u.s;
1218     return FcResultMatch;
1219 }
1220
1221 FcResult
1222 FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
1223 {
1224     FcValue     v;
1225     FcResult    r;
1226
1227     r = FcPatternGet (p, object, id, &v);
1228     if (r != FcResultMatch)
1229         return r;
1230     if (v.type != FcTypeMatrix)
1231         return FcResultTypeMismatch;
1232     *m = (FcMatrix *)v.u.m;
1233     return FcResultMatch;
1234 }
1235
1236
1237 FcResult
1238 FcPatternGetBool(const FcPattern *p, const char *object, int id, FcBool *b)
1239 {
1240     FcValue     v;
1241     FcResult    r;
1242
1243     r = FcPatternGet (p, object, id, &v);
1244     if (r != FcResultMatch)
1245         return r;
1246     if (v.type != FcTypeBool)
1247         return FcResultTypeMismatch;
1248     *b = v.u.b;
1249     return FcResultMatch;
1250 }
1251
1252 FcResult
1253 FcPatternGetCharSet(const FcPattern *p, const char *object, int id, FcCharSet **c)
1254 {
1255     FcValue     v;
1256     FcResult    r;
1257
1258     r = FcPatternGet (p, object, id, &v);
1259     if (r != FcResultMatch)
1260         return r;
1261     if (v.type != FcTypeCharSet)
1262         return FcResultTypeMismatch;
1263     *c = (FcCharSet *)v.u.c;
1264     return FcResultMatch;
1265 }
1266
1267 FcResult
1268 FcPatternGetFTFace(const FcPattern *p, const char *object, int id, FT_Face *f)
1269 {
1270     FcValue     v;
1271     FcResult    r;
1272
1273     r = FcPatternGet (p, object, id, &v);
1274     if (r != FcResultMatch)
1275         return r;
1276     if (v.type != FcTypeFTFace)
1277         return FcResultTypeMismatch;
1278     *f = (FT_Face) v.u.f;
1279     return FcResultMatch;
1280 }
1281
1282 FcResult
1283 FcPatternGetLangSet(const FcPattern *p, const char *object, int id, FcLangSet **ls)
1284 {
1285     FcValue     v;
1286     FcResult    r;
1287
1288     r = FcPatternGet (p, object, id, &v);
1289     if (r != FcResultMatch)
1290         return r;
1291     if (v.type != FcTypeLangSet)
1292         return FcResultTypeMismatch;
1293     *ls = (FcLangSet *)v.u.l;
1294     return FcResultMatch;
1295 }
1296
1297 FcPattern *
1298 FcPatternDuplicate (const FcPattern *orig)
1299 {
1300     FcPattern       *new;
1301     FcPatternElt    *e;
1302     int             i;
1303     FcValueListPtr  l;
1304
1305     new = FcPatternCreate ();
1306     if (!new)
1307         goto bail0;
1308
1309     e = FcPatternEltU(orig->elts);
1310
1311     for (i = 0; i < orig->num; i++)
1312     {
1313         for (l = (e + i)->values;
1314              FcValueListPtrU(l);
1315              l = FcValueListPtrU(l)->next)
1316             if (!FcPatternAdd (new, FcObjectPtrU((e + i)->object),
1317                                FcValueCanonicalize(&FcValueListPtrU(l)->value),
1318                                FcTrue))
1319                 goto bail1;
1320     }
1321     FcPatternTransferFullFname (new, orig);
1322
1323     return new;
1324
1325 bail1:
1326     FcPatternDestroy (new);
1327 bail0:
1328     return 0;
1329 }
1330
1331 void
1332 FcPatternReference (FcPattern *p)
1333 {
1334     if (p->ref != FC_REF_CONSTANT)
1335         p->ref++;
1336 }
1337
1338 FcPattern *
1339 FcPatternVaBuild (FcPattern *orig, va_list va)
1340 {
1341     FcPattern   *ret;
1342
1343     FcPatternVapBuild (ret, orig, va);
1344     return ret;
1345 }
1346
1347 FcPattern *
1348 FcPatternBuild (FcPattern *orig, ...)
1349 {
1350     va_list     va;
1351
1352     va_start (va, orig);
1353     FcPatternVapBuild (orig, orig, va);
1354     va_end (va);
1355     return orig;
1356 }
1357
1358 /*
1359  * Add all of the elements in 's' to 'p'
1360  */
1361 FcBool
1362 FcPatternAppend (FcPattern *p, FcPattern *s)
1363 {
1364     int             i;
1365     FcPatternElt    *e;
1366     FcValueListPtr  v;
1367
1368     for (i = 0; i < s->num; i++)
1369     {
1370         e = FcPatternEltU(s->elts)+i;
1371         for (v = e->values; FcValueListPtrU(v);
1372              v = FcValueListPtrU(v)->next)
1373         {
1374             if (!FcPatternAddWithBinding (p, FcObjectPtrU(e->object),
1375                                           FcValueCanonicalize(&FcValueListPtrU(v)->value),
1376                                           FcValueListPtrU(v)->binding, FcTrue))
1377                 return FcFalse;
1378         }
1379     }
1380     return FcTrue;
1381 }
1382
1383 #define OBJECT_HASH_SIZE    31
1384 static struct objectBucket {
1385     struct objectBucket *next;
1386     FcChar32            hash;
1387 } *FcObjectBuckets[OBJECT_HASH_SIZE];
1388
1389 static FcBool
1390 FcStrHashed (const FcChar8 *name)
1391 {
1392     FcChar32            hash = FcStringHash (name);
1393     struct objectBucket **p;
1394     struct objectBucket *b;
1395
1396     for (p = &FcObjectBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1397         if (b->hash == hash && !strcmp ((char *)name, (char *) (b + 1)))
1398             return FcTrue;
1399     return FcFalse;
1400 }
1401
1402 const FcChar8 *
1403 FcStrStaticName (const FcChar8 *name)
1404 {
1405     FcChar32            hash = FcStringHash (name);
1406     struct objectBucket **p;
1407     struct objectBucket *b;
1408     int                 size;
1409
1410     for (p = &FcObjectBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1411         if (b->hash == hash && !strcmp ((char *)name, (char *) (b + 1)))
1412             return (FcChar8 *) (b + 1);
1413     size = sizeof (struct objectBucket) + strlen ((char *)name) + 1;
1414     b = malloc (size + sizeof (int));
1415     /* workaround glibc bug which reads strlen in groups of 4 */
1416     FcMemAlloc (FC_MEM_STATICSTR, size + sizeof (int));
1417     if (!b)
1418         return NULL;
1419     b->next = 0;
1420     b->hash = hash;
1421     strcpy ((char *) (b + 1), (char *)name);
1422     *p = b;
1423     return (FcChar8 *) (b + 1);
1424 }
1425
1426 static void
1427 FcStrStaticNameFini (void)
1428 {
1429     int i, size;
1430     struct objectBucket *b, *next;
1431     char *name;
1432
1433     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1434     {
1435         for (b = FcObjectBuckets[i]; b; b = next)
1436         {
1437             next = b->next;
1438             name = (char *) (b + 1);
1439             size = sizeof (struct objectBucket) + strlen (name) + 1;
1440             FcMemFree (FC_MEM_STATICSTR, size);
1441             free (b);
1442         }
1443         FcObjectBuckets[i] = 0;
1444     }
1445 }
1446
1447 void
1448 FcPatternFini (void)
1449 {
1450     FcPatternBaseThawAll ();
1451     FcValueListThawAll ();
1452     FcStrStaticNameFini ();
1453     FcObjectStaticNameFini ();
1454 }
1455
1456 static FcPatternEltPtr
1457 FcPatternEltPtrCreateDynamic (FcPatternElt * e)
1458 {
1459     FcPatternEltPtr new;
1460     new.bank = FC_BANK_DYNAMIC;
1461     new.u.dyn = e;
1462     return new;
1463 }
1464
1465 static FcPatternEltPtr
1466 FcPatternEltPtrCreateStatic (int bank, int i)
1467 {
1468     FcPatternEltPtr new;
1469     new.bank = bank;
1470     new.u.stat = i;
1471     return new;
1472 }
1473
1474 static void
1475 FcStrNewBank (void);
1476 static int
1477 FcStrNeededBytes (const FcChar8 * s);
1478 static int
1479 FcStrNeededBytesAlign (void);
1480 static void *
1481 FcStrDistributeBytes (FcCache * metadata, void * block_ptr);
1482 static const FcChar8 *
1483 FcStrSerialize (int bank, const FcChar8 * s);
1484 static void *
1485 FcStrUnserialize (FcCache * metadata, void *block_ptr);
1486
1487 static void
1488 FcValueListNewBank (void);
1489 static int
1490 FcValueListNeededBytes (FcValueList * vl);
1491 static int
1492 FcValueListNeededBytesAlign (void);
1493 static void *
1494 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr);
1495 static FcValueListPtr
1496 FcValueListSerialize(int bank, FcValueList *pi);
1497 static void *
1498 FcValueListUnserialize (FcCache * metadata, void *block_ptr);
1499
1500
1501 void
1502 FcPatternNewBank (void)
1503 {
1504     fcpattern_count = 0;
1505     fcpatternelt_count = 0;
1506
1507     FcStrNewBank();
1508     FcValueListNewBank();
1509 }
1510
1511 int
1512 FcPatternNeededBytes (FcPattern * p)
1513 {
1514     int i, cum = 0, c;
1515
1516     fcpattern_count++;
1517     fcpatternelt_count += p->num;
1518
1519     for (i = 0; i < p->num; i++)
1520     {
1521         c = FcValueListNeededBytes (FcValueListPtrU
1522                                     (((FcPatternEltU(p->elts)+i)->values)));
1523         if (c < 0)
1524             return c;
1525         cum += c;
1526     }
1527
1528     return cum + sizeof (FcPattern) + sizeof(FcPatternElt)*p->num;
1529 }
1530
1531 int
1532 FcPatternNeededBytesAlign (void)
1533 {
1534     return __alignof__ (FcPattern) + __alignof__ (FcPatternElt) +
1535         FcValueListNeededBytesAlign ();
1536 }
1537
1538 static FcBool
1539 FcPatternEnsureBank (int bi)
1540 {
1541     FcPattern **pp;
1542     FcPatternElt **ep;
1543     int i;
1544
1545     if (!_fcPatterns || fcpattern_bank_count <= bi)
1546     {
1547         int new_count = bi + 4;
1548         pp = realloc (_fcPatterns, sizeof (FcPattern *) * new_count);
1549         if (!pp)
1550             return 0;
1551
1552         FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern *) * new_count);
1553         _fcPatterns = pp;
1554
1555         ep = realloc (_fcPatternElts, sizeof (FcPatternElt *) * new_count);
1556         if (!ep)
1557             return 0;
1558
1559         FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt *) * new_count);
1560         _fcPatternElts = ep;
1561
1562         for (i = fcpattern_bank_count; i < new_count; i++)
1563         {
1564             _fcPatterns[i] = 0;
1565             _fcPatternElts[i] = 0;
1566         }
1567
1568         fcpattern_bank_count = new_count;
1569     }
1570
1571     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * fcpattern_count);
1572     return FcTrue;
1573 }
1574
1575 void *
1576 FcPatternDistributeBytes (FcCache * metadata, void * block_ptr)
1577 {
1578     int bi = FcCacheBankToIndex(metadata->bank);
1579
1580     if (!FcPatternEnsureBank(bi))
1581         return 0;
1582
1583     fcpattern_ptr = 0;
1584     block_ptr = ALIGN(block_ptr, FcPattern);
1585     _fcPatterns[bi] = (FcPattern *)block_ptr;
1586     block_ptr = (void *)((char *)block_ptr +
1587                          (sizeof (FcPattern) * fcpattern_count));
1588
1589     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt) * fcpatternelt_count);
1590     fcpatternelt_ptr = 0;
1591     block_ptr = ALIGN(block_ptr, FcPatternElt);
1592     _fcPatternElts[bi] = (FcPatternElt *)block_ptr;
1593     block_ptr = (void *)((char *)block_ptr +
1594                          (sizeof (FcPatternElt) * fcpatternelt_count));
1595
1596     metadata->pattern_count = fcpattern_count;
1597     metadata->patternelt_count = fcpatternelt_count;
1598
1599     block_ptr = FcStrDistributeBytes (metadata, block_ptr);
1600     block_ptr = FcValueListDistributeBytes (metadata, block_ptr);
1601     return block_ptr;
1602 }
1603
1604 FcPattern *
1605 FcPatternSerialize (int bank, FcPattern *old)
1606 {
1607     FcPattern *p;
1608     FcPatternElt *e, *nep;
1609     FcValueList * nv;
1610     FcValueListPtr v, nv_head, nvp;
1611     int i, elts, bi = FcCacheBankToIndex(bank);
1612
1613     p = &_fcPatterns[bi][fcpattern_ptr++];
1614     p->bank = bank;
1615     elts = fcpatternelt_ptr;
1616     nep = &_fcPatternElts[bi][elts];
1617     if (!nep)
1618         return FcFalse;
1619
1620     fcpatternelt_ptr += old->num;
1621
1622     for (e = FcPatternEltU(old->elts), i=0; i < old->num; i++, e++)
1623     {
1624         v = e->values;
1625         nvp = nv_head = FcValueListSerialize(bank, FcValueListPtrU(v));
1626         if (!FcValueListPtrU(nv_head))
1627             return 0;
1628         nv = FcValueListPtrU(nvp);
1629
1630         for (;
1631              FcValueListPtrU(v);
1632              v = FcValueListPtrU(v)->next,
1633                  nv = FcValueListPtrU(nv->next))
1634         {
1635
1636             if (FcValueListPtrU(FcValueListPtrU(v)->next))
1637             {
1638                 nvp = FcValueListSerialize
1639                     (bank, FcValueListPtrU(FcValueListPtrU(v)->next));
1640                 nv->next = nvp;
1641             }
1642         }
1643
1644         nep[i].values = nv_head;
1645         nep[i].object = e->object;
1646     }
1647
1648     p->elts = old->elts;
1649     p->elts = FcPatternEltPtrCreateStatic(bank, elts);
1650     p->size = old->num;
1651     p->num = old->num;
1652     p->ref = FC_REF_CONSTANT;
1653     return p;
1654 }
1655
1656 void *
1657 FcPatternUnserialize (FcCache * metadata, void *block_ptr)
1658 {
1659     int bi = FcCacheBankToIndex(metadata->bank);
1660     if (!FcPatternEnsureBank(bi))
1661         return FcFalse;
1662
1663     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * metadata->pattern_count);
1664     block_ptr = ALIGN(block_ptr, FcPattern);
1665     _fcPatterns[bi] = (FcPattern *)block_ptr;
1666     block_ptr = (void *)((char *)block_ptr +
1667                          (sizeof (FcPattern) * metadata->pattern_count));
1668
1669     FcMemAlloc (FC_MEM_PATELT,
1670                 sizeof (FcPatternElt) * metadata->patternelt_count);
1671     block_ptr = ALIGN(block_ptr, FcPatternElt);
1672     _fcPatternElts[bi] = (FcPatternElt *)block_ptr;
1673     block_ptr = (void *)((char *)block_ptr +
1674                          (sizeof (FcPatternElt) * metadata->patternelt_count));
1675
1676     block_ptr = FcStrUnserialize (metadata, block_ptr);
1677     block_ptr = FcValueListUnserialize (metadata, block_ptr);
1678
1679     return block_ptr;
1680 }
1681
1682 static void
1683 FcValueListNewBank (void)
1684 {
1685     fcvaluelist_count = 0;
1686
1687     FcCharSetNewBank();
1688     FcLangSetNewBank();
1689 }
1690
1691 static int
1692 FcValueListNeededBytes (FcValueList *p)
1693 {
1694     FcValueList *vl;
1695     int cum = 0;
1696
1697     for (vl = p;
1698          vl;
1699          vl = FcValueListPtrU(vl->next))
1700     {
1701         /* unserialize just in case */
1702         FcValue v = FcValueCanonicalize(&vl->value);
1703
1704         switch (v.type)
1705         {
1706         case FcTypeCharSet:
1707             cum += FcCharSetNeededBytes(v.u.c);
1708             break;
1709         case FcTypeLangSet:
1710             cum += FcLangSetNeededBytes(v.u.l);
1711             break;
1712         case FcTypeString:
1713             cum += FcStrNeededBytes(v.u.s);
1714         default:
1715             break;
1716         }
1717         fcvaluelist_count++;
1718         cum += sizeof (FcValueList);
1719     }
1720
1721     return cum;
1722 }
1723
1724 static int
1725 FcValueListNeededBytesAlign (void)
1726 {
1727     return FcCharSetNeededBytesAlign() + FcLangSetNeededBytesAlign() +
1728         FcStrNeededBytesAlign() + __alignof__ (FcValueList);
1729 }
1730
1731 static FcBool
1732 FcValueListEnsureBank (int bi)
1733 {
1734     FcValueList **pvl;
1735
1736     if (!_fcValueLists || fcvaluelist_bank_count <= bi)
1737     {
1738         int new_count = bi + 2, i;
1739
1740         pvl = realloc (_fcValueLists, sizeof (FcValueList *) * new_count);
1741         if (!pvl)
1742             return FcFalse;
1743
1744         FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList *) * new_count);
1745
1746         _fcValueLists = pvl;
1747         for (i = fcvaluelist_bank_count; i < new_count; i++)
1748             _fcValueLists[i] = 0;
1749
1750         fcvaluelist_bank_count = new_count;
1751     }
1752     return FcTrue;
1753 }
1754
1755 static void *
1756 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr)
1757 {
1758     int bi = FcCacheBankToIndex(metadata->bank);
1759
1760     if (!FcValueListEnsureBank(bi))
1761         return 0;
1762
1763     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList) * fcvaluelist_count);
1764     fcvaluelist_ptr = 0;
1765     block_ptr = ALIGN(block_ptr, FcValueList);
1766     _fcValueLists[bi] = (FcValueList *)block_ptr;
1767     block_ptr = (void *)((char *)block_ptr +
1768                          (sizeof (FcValueList) * fcvaluelist_count));
1769     metadata->valuelist_count = fcvaluelist_count;
1770
1771     block_ptr = FcCharSetDistributeBytes(metadata, block_ptr);
1772     block_ptr = FcLangSetDistributeBytes(metadata, block_ptr);
1773
1774     return block_ptr;
1775 }
1776
1777 static FcValueListPtr
1778 FcValueListSerialize(int bank, FcValueList *pi)
1779 {
1780     FcValueListPtr new;
1781     FcValue * v;
1782     int bi = FcCacheBankToIndex(bank);
1783
1784     if (!pi)
1785     {
1786         new.bank = FC_BANK_DYNAMIC;
1787         new.u.dyn = 0;
1788         return new;
1789     }
1790
1791     _fcValueLists[bi][fcvaluelist_ptr] = *pi;
1792     new.bank = bank;
1793     new.u.stat = fcvaluelist_ptr++;
1794     _fcValueLists[bi][new.u.stat].value = FcValueCanonicalize (&pi->value);
1795     v = &_fcValueLists[bi][new.u.stat].value;
1796     switch (v->type)
1797     {
1798     case FcTypeString:
1799         if (v->u.s)
1800         {
1801             const FcChar8 * s = FcStrSerialize(bank, v->u.s);
1802             if (!s)
1803                 return FcValueListPtrCreateDynamic(pi);
1804             v->u.s_off = s - (const FcChar8 *)v;
1805             v->type |= FC_STORAGE_STATIC;
1806         }
1807         break;
1808     case FcTypeMatrix:
1809         break;
1810     case FcTypeCharSet:
1811         if (v->u.c)
1812         {
1813             FcCharSet * c = FcCharSetSerialize(bank, (FcCharSet *)v->u.c);
1814             if (!c)
1815                 return FcValueListPtrCreateDynamic(pi);
1816             v->u.c_off = (char *)c - (char *)v;
1817             v->type |= FC_STORAGE_STATIC;
1818         }
1819         break;
1820     case FcTypeLangSet:
1821         if (v->u.l)
1822         {
1823             FcLangSet * l = FcLangSetSerialize(bank, (FcLangSet *)v->u.l);
1824             if (!l)
1825                 return FcValueListPtrCreateDynamic(pi);
1826             v->u.l_off = (char *)l - (char *)v;
1827             v->type |= FC_STORAGE_STATIC;
1828         }
1829         break;
1830     default:
1831         break;
1832     }
1833     return new;
1834 }
1835
1836 static void *
1837 FcValueListUnserialize (FcCache * metadata, void *block_ptr)
1838 {
1839     int bi = FcCacheBankToIndex(metadata->bank);
1840
1841     if (!FcValueListEnsureBank(bi))
1842         return 0;
1843
1844     FcMemAlloc (FC_MEM_VALLIST,
1845                 sizeof (FcValueList) * metadata->valuelist_count);
1846     block_ptr = ALIGN(block_ptr, FcValueList);
1847     _fcValueLists[bi] = (FcValueList *)block_ptr;
1848     block_ptr = (void *)((char *)block_ptr +
1849                          (sizeof (FcValueList) * metadata->valuelist_count));
1850
1851     block_ptr = FcCharSetUnserialize(metadata, block_ptr);
1852     block_ptr = FcLangSetUnserialize(metadata, block_ptr);
1853
1854     return block_ptr;
1855 }
1856
1857 FcValueListPtr
1858 FcValueListPtrCreateDynamic(FcValueList * p)
1859 {
1860     FcValueListPtr r;
1861
1862     r.bank = FC_BANK_DYNAMIC;
1863     r.u.dyn = p;
1864     return r;
1865 }
1866
1867 static FcChar8 ** static_strs;
1868 static int static_str_bank_count = 0, fcstr_ptr, fcstr_count;
1869
1870 static struct objectBucket *FcStrBuckets[OBJECT_HASH_SIZE];
1871
1872 static void
1873 FcStrNewBank (void)
1874 {
1875     int i, size;
1876     struct objectBucket *b, *next;
1877     char *name;
1878
1879     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1880     {
1881         for (b = FcStrBuckets[i]; b; b = next)
1882         {
1883             next = b->next;
1884             name = (char *) (b + 1);
1885             size = sizeof (struct objectBucket) + strlen (name) + 1;
1886             FcMemFree (FC_MEM_STATICSTR, size);
1887             free (b);
1888         }
1889         FcStrBuckets[i] = 0;
1890     }
1891
1892     fcstr_count = 0;
1893 }
1894
1895 static int
1896 FcStrNeededBytes (const FcChar8 * s)
1897 {
1898     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1899     struct objectBucket **p;
1900     struct objectBucket *b;
1901     int                 size;
1902     FcChar8 *const null = 0;
1903
1904     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1905         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1906             return 0;
1907     size = sizeof (struct objectBucket) + strlen ((char *)s) + 1 + sizeof(char *);
1908     b = malloc (size);
1909     FcMemAlloc (FC_MEM_STATICSTR, size);
1910     if (!b)
1911         return -1;
1912     b->next = 0;
1913     b->hash = hash;
1914     strcpy ((char *) (b + 1), (char *)s);
1915
1916     /* Yes, the following line is convoluted.  However, it is
1917      * incorrect to replace the with a memset, because the C
1918      * specification doesn't guarantee that the null pointer is
1919      * the same as the zero bit pattern. */
1920     /* Misaligned pointers are not guaranteed to work, either! */
1921     memcpy (((char *) (b + 1) + strlen((char *)s) + 1), &null, sizeof (null));
1922     *p = b;
1923
1924     fcstr_count += strlen((char *)s) + 1;
1925     return strlen((char *)s) + 1;
1926 }
1927
1928 static int
1929 FcStrNeededBytesAlign (void)
1930 {
1931     return __alignof__ (char);
1932 }
1933
1934 static FcBool
1935 FcStrEnsureBank (int bi)
1936 {
1937     FcChar8 ** ss;
1938
1939     if (!static_strs || static_str_bank_count <= bi)
1940     {
1941         int new_count = bi + 4, i;
1942         ss = realloc (static_strs, sizeof (const char *) * new_count);
1943         if (!ss)
1944             return FcFalse;
1945
1946         FcMemAlloc (FC_MEM_STRING, sizeof (const char *) * (new_count-static_str_bank_count));
1947         static_strs = ss;
1948
1949         for (i = static_str_bank_count; i < new_count; i++)
1950             static_strs[i] = 0;
1951         static_str_bank_count = new_count;
1952     }
1953     return FcTrue;
1954 }
1955
1956 static void *
1957 FcStrDistributeBytes (FcCache * metadata, void * block_ptr)
1958 {
1959     int bi = FcCacheBankToIndex(metadata->bank);
1960     if (!FcStrEnsureBank(bi))
1961         return 0;
1962
1963     FcMemAlloc (FC_MEM_STRING, sizeof (char) * fcstr_count);
1964     block_ptr = ALIGN (block_ptr, FcChar8);
1965     static_strs[bi] = (FcChar8 *)block_ptr;
1966     block_ptr = (void *)((char *)block_ptr + (sizeof (char) * fcstr_count));
1967     metadata->str_count = fcstr_count;
1968     fcstr_ptr = 0;
1969
1970     return block_ptr;
1971 }
1972
1973 static const FcChar8 *
1974 FcStrSerialize (int bank, const FcChar8 * s)
1975 {
1976     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1977     struct objectBucket **p;
1978     struct objectBucket *b;
1979     int bi = FcCacheBankToIndex(bank);
1980
1981     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1982         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1983         {
1984             FcChar8 * t;
1985             memcpy (&t, ((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1, sizeof (FcChar8 *));
1986             if (!t)
1987             {
1988                 strcpy((char *)(static_strs[bi] + fcstr_ptr), (char *)s);
1989                 t = static_strs[bi] + fcstr_ptr;
1990                 memcpy ((FcChar8 *) (b + 1) + strlen((char *)s) + 1, &t, sizeof (FcChar8 *));
1991                 fcstr_ptr += strlen((char *)s) + 1;
1992                 memcpy (&t, ((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1, sizeof (FcChar8 *));
1993             }
1994             return t;
1995         }
1996     return 0;
1997 }
1998
1999 static void *
2000 FcStrUnserialize (FcCache * metadata, void *block_ptr)
2001 {
2002     int bi = FcCacheBankToIndex(metadata->bank);
2003     if (!FcStrEnsureBank(bi))
2004         return 0;
2005
2006     FcMemAlloc (FC_MEM_STRING, sizeof (char) * metadata->str_count);
2007     block_ptr = ALIGN (block_ptr, FcChar8);
2008     static_strs[bi] = (FcChar8 *)block_ptr;
2009     block_ptr = (void *)((char *)block_ptr +
2010                          (sizeof (char) * metadata->str_count));
2011
2012     return block_ptr;
2013 }
2014
2015 /* we don't store these in the FcPattern itself because
2016  * we don't want to serialize the directory names */
2017
2018 /* I suppose this should be cleaned upon termination, too... */
2019 typedef struct _FcPatternDirMapping {
2020     const FcPattern     *p;
2021     const char *fname;
2022 } FcPatternDirMapping;
2023
2024 #define PATTERNDIR_HASH_SIZE    31
2025 static struct patternDirBucket {
2026     struct patternDirBucket     *next;
2027     FcPatternDirMapping         m;
2028 } FcPatternDirBuckets[PATTERNDIR_HASH_SIZE];
2029
2030 void
2031 FcPatternAddFullFname (const FcPattern *p, const char *fname)
2032 {
2033     struct patternDirBucket     *pb;
2034
2035     /* N.B. FcPatternHash fails, since it's contents-based, not
2036      * address-based, and we're in the process of mutating the FcPattern. */
2037     for (pb = &FcPatternDirBuckets
2038              [((unsigned long)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
2039          pb->m.p != p && pb->next;
2040          pb = pb->next)
2041         ;
2042
2043     if (pb->m.p == p)
2044     {
2045         pb->m.fname = fname;
2046         return;
2047     }
2048
2049     pb->next = malloc (sizeof (struct patternDirBucket));
2050     if (!pb->next)
2051         return;
2052     FcMemAlloc (FC_MEM_CACHE, sizeof (struct patternDirBucket));
2053
2054     pb->next->next = 0;
2055     pb->next->m.p = p;
2056     pb->next->m.fname = fname;
2057 }
2058
2059 static const char *
2060 FcPatternFindFullFname (const FcPattern *p)
2061 {
2062     struct patternDirBucket     *pb;
2063
2064     for (pb = &FcPatternDirBuckets
2065              [((unsigned long)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
2066          pb; pb = pb->next)
2067         if (pb->m.p == p)
2068             return pb->m.fname;
2069
2070     return 0;
2071 }
2072
2073 void
2074 FcPatternTransferFullFname (const FcPattern *new, const FcPattern *orig)
2075 {
2076     FcChar8 * s;
2077     FcPatternGetString (orig, FC_FILE, 0, &s);
2078     FcPatternAddFullFname (new,
2079                            (char *)FcStrCopy
2080                            ((FcChar8 *)FcPatternFindFullFname(orig)));
2081 }