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