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