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         /* unserialize just in case */
1698         FcValue v = FcValueCanonicalize(&vl->value);
1699
1700         switch (v.type)
1701         {
1702         case FcTypeCharSet:
1703             cum += FcCharSetNeededBytes(v.u.c);
1704             break;
1705         case FcTypeLangSet:
1706             cum += FcLangSetNeededBytes(v.u.l);
1707             break;
1708         case FcTypeString:
1709             cum += FcStrNeededBytes(v.u.s);
1710         default:
1711             break;
1712         }
1713         fcvaluelist_count++;
1714         cum += sizeof (FcValueList);
1715     }
1716
1717     return cum;
1718 }
1719
1720 static int
1721 FcValueListNeededBytesAlign (void)
1722 {
1723     return FcCharSetNeededBytesAlign() + FcLangSetNeededBytesAlign() +
1724         FcStrNeededBytesAlign() + __alignof__ (FcValueList);
1725 }
1726
1727 static FcBool
1728 FcValueListEnsureBank (int bi)
1729 {
1730     FcValueList **pvl;
1731
1732     if (!_fcValueLists || fcvaluelist_bank_count <= bi)
1733     {
1734         int new_count = bi + 2, i;
1735
1736         pvl = realloc (_fcValueLists, sizeof (FcValueList *) * new_count);
1737         if (!pvl)
1738             return FcFalse;
1739
1740         FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList *) * new_count);
1741
1742         _fcValueLists = pvl;
1743         for (i = fcvaluelist_bank_count; i < new_count; i++)
1744             _fcValueLists[i] = 0;
1745
1746         fcvaluelist_bank_count = new_count;
1747     }
1748     return FcTrue;
1749 }
1750
1751 static void *
1752 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr)
1753 {
1754     int bi = FcCacheBankToIndex(metadata->bank);
1755
1756     if (!FcValueListEnsureBank(bi))
1757         return 0;
1758
1759     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList) * fcvaluelist_count);
1760     fcvaluelist_ptr = 0;
1761     block_ptr = ALIGN(block_ptr, FcValueList);
1762     _fcValueLists[bi] = (FcValueList *)block_ptr;
1763     block_ptr = (void *)((char *)block_ptr +
1764                          (sizeof (FcValueList) * fcvaluelist_count));
1765     metadata->valuelist_count = fcvaluelist_count;
1766
1767     block_ptr = FcCharSetDistributeBytes(metadata, block_ptr);
1768     block_ptr = FcLangSetDistributeBytes(metadata, block_ptr);
1769
1770     return block_ptr;
1771 }
1772
1773 static FcValueListPtr
1774 FcValueListSerialize(int bank, FcValueList *pi)
1775 {
1776     FcValueListPtr new;
1777     FcValue * v;
1778     int bi = FcCacheBankToIndex(bank);
1779
1780     if (!pi)
1781     {
1782         new.bank = FC_BANK_DYNAMIC;
1783         new.u.dyn = 0;
1784         return new;
1785     }
1786
1787     _fcValueLists[bi][fcvaluelist_ptr] = *pi;
1788     new.bank = bank;
1789     new.u.stat = fcvaluelist_ptr++;
1790     _fcValueLists[bi][new.u.stat].value = FcValueCanonicalize (&pi->value);
1791     v = &_fcValueLists[bi][new.u.stat].value;
1792     switch (v->type)
1793     {
1794     case FcTypeString:
1795         if (v->u.s)
1796         {
1797             const FcChar8 * s = FcStrSerialize(bank, v->u.s);
1798             if (!s)
1799                 return FcValueListPtrCreateDynamic(pi);
1800             v->u.s_off = s - (const FcChar8 *)v;
1801             v->type |= FC_STORAGE_STATIC;
1802         }
1803         break;
1804     case FcTypeMatrix:
1805         break;
1806     case FcTypeCharSet:
1807         if (v->u.c)
1808         {
1809             FcCharSet * c = FcCharSetSerialize(bank, (FcCharSet *)v->u.c);
1810             if (!c)
1811                 return FcValueListPtrCreateDynamic(pi);
1812             v->u.c_off = (char *)c - (char *)v;
1813             v->type |= FC_STORAGE_STATIC;
1814         }
1815         break;
1816     case FcTypeLangSet:
1817         if (v->u.l)
1818         {
1819             FcLangSet * l = FcLangSetSerialize(bank, (FcLangSet *)v->u.l);
1820             if (!l)
1821                 return FcValueListPtrCreateDynamic(pi);
1822             v->u.l_off = (char *)l - (char *)v;
1823             v->type |= FC_STORAGE_STATIC;
1824         }
1825         break;
1826     default:
1827         break;
1828     }
1829     return new;
1830 }
1831
1832 static void *
1833 FcValueListUnserialize (FcCache * metadata, void *block_ptr)
1834 {
1835     int bi = FcCacheBankToIndex(metadata->bank);
1836
1837     if (!FcValueListEnsureBank(bi))
1838         return 0;
1839
1840     FcMemAlloc (FC_MEM_VALLIST,
1841                 sizeof (FcValueList) * metadata->valuelist_count);
1842     block_ptr = ALIGN(block_ptr, FcValueList);
1843     _fcValueLists[bi] = (FcValueList *)block_ptr;
1844     block_ptr = (void *)((char *)block_ptr +
1845                          (sizeof (FcValueList) * metadata->valuelist_count));
1846
1847     block_ptr = FcCharSetUnserialize(metadata, block_ptr);
1848     block_ptr = FcLangSetUnserialize(metadata, block_ptr);
1849
1850     return block_ptr;
1851 }
1852
1853 FcValueListPtr
1854 FcValueListPtrCreateDynamic(FcValueList * p)
1855 {
1856     FcValueListPtr r;
1857
1858     r.bank = FC_BANK_DYNAMIC;
1859     r.u.dyn = p;
1860     return r;
1861 }
1862
1863 static FcChar8 ** static_strs;
1864 static int static_str_bank_count = 0, fcstr_ptr, fcstr_count;
1865
1866 static struct objectBucket *FcStrBuckets[OBJECT_HASH_SIZE];
1867
1868 static void
1869 FcStrNewBank (void)
1870 {
1871     int i, size;
1872     struct objectBucket *b, *next;
1873     char *name;
1874
1875     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1876     {
1877         for (b = FcStrBuckets[i]; b; b = next)
1878         {
1879             next = b->next;
1880             name = (char *) (b + 1);
1881             size = sizeof (struct objectBucket) + strlen (name) + 1;
1882             FcMemFree (FC_MEM_STATICSTR, size);
1883             free (b);
1884         }
1885         FcStrBuckets[i] = 0;
1886     }
1887
1888     fcstr_count = 0;
1889 }
1890
1891 static int
1892 FcStrNeededBytes (const FcChar8 * s)
1893 {
1894     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1895     struct objectBucket **p;
1896     struct objectBucket *b;
1897     int                 size;
1898     FcChar8 *const null = 0;
1899
1900     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1901         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1902             return 0;
1903     size = sizeof (struct objectBucket) + strlen ((char *)s) + 1 + sizeof(char *);
1904     b = malloc (size);
1905     FcMemAlloc (FC_MEM_STATICSTR, size);
1906     if (!b)
1907         return -1;
1908     b->next = 0;
1909     b->hash = hash;
1910     strcpy ((char *) (b + 1), (char *)s);
1911
1912     /* Yes, the following line is convoluted.  However, it is
1913      * incorrect to replace the with a memset, because the C
1914      * specification doesn't guarantee that the null pointer is
1915      * the same as the zero bit pattern. */
1916     /* Misaligned pointers are not guaranteed to work, either! */
1917     memcpy (((char *) (b + 1) + strlen((char *)s) + 1), &null, sizeof (null));
1918     *p = b;
1919
1920     fcstr_count += strlen((char *)s) + 1;
1921     return strlen((char *)s) + 1;
1922 }
1923
1924 static int
1925 FcStrNeededBytesAlign (void)
1926 {
1927     return __alignof__ (char);
1928 }
1929
1930 static FcBool
1931 FcStrEnsureBank (int bi)
1932 {
1933     FcChar8 ** ss;
1934
1935     if (!static_strs || static_str_bank_count <= bi)
1936     {
1937         int new_count = bi + 4, i;
1938         ss = realloc (static_strs, sizeof (const char *) * new_count);
1939         if (!ss)
1940             return FcFalse;
1941
1942         FcMemAlloc (FC_MEM_STRING, sizeof (const char *) * (new_count-static_str_bank_count));
1943         static_strs = ss;
1944
1945         for (i = static_str_bank_count; i < new_count; i++)
1946             static_strs[i] = 0;
1947         static_str_bank_count = new_count;
1948     }
1949     return FcTrue;
1950 }
1951
1952 static void *
1953 FcStrDistributeBytes (FcCache * metadata, void * block_ptr)
1954 {
1955     int bi = FcCacheBankToIndex(metadata->bank);
1956     if (!FcStrEnsureBank(bi))
1957         return 0;
1958
1959     FcMemAlloc (FC_MEM_STRING, sizeof (char) * fcstr_count);
1960     block_ptr = ALIGN (block_ptr, FcChar8);
1961     static_strs[bi] = (FcChar8 *)block_ptr;
1962     block_ptr = (void *)((char *)block_ptr + (sizeof (char) * fcstr_count));
1963     metadata->str_count = fcstr_count;
1964     fcstr_ptr = 0;
1965
1966     return block_ptr;
1967 }
1968
1969 static const FcChar8 *
1970 FcStrSerialize (int bank, const FcChar8 * s)
1971 {
1972     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1973     struct objectBucket **p;
1974     struct objectBucket *b;
1975     int bi = FcCacheBankToIndex(bank);
1976
1977     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1978         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1979         {
1980             FcChar8 * t;
1981             memcpy (&t, ((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1, sizeof (FcChar8 *));
1982             if (!t)
1983             {
1984                 strcpy((char *)(static_strs[bi] + fcstr_ptr), (char *)s);
1985                 t = static_strs[bi] + fcstr_ptr;
1986                 memcpy ((FcChar8 *) (b + 1) + strlen((char *)s) + 1, &t, sizeof (FcChar8 *));
1987                 fcstr_ptr += strlen((char *)s) + 1;
1988                 memcpy (&t, ((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1, sizeof (FcChar8 *));
1989             }
1990             return t;
1991         }
1992     return 0;
1993 }
1994
1995 static void *
1996 FcStrUnserialize (FcCache * metadata, void *block_ptr)
1997 {
1998     int bi = FcCacheBankToIndex(metadata->bank);
1999     if (!FcStrEnsureBank(bi))
2000         return 0;
2001
2002     FcMemAlloc (FC_MEM_STRING, sizeof (char) * metadata->str_count);
2003     block_ptr = ALIGN (block_ptr, FcChar8);
2004     static_strs[bi] = (FcChar8 *)block_ptr;
2005     block_ptr = (void *)((char *)block_ptr +
2006                          (sizeof (char) * metadata->str_count));
2007
2008     return block_ptr;
2009 }
2010
2011 /* we don't store these in the FcPattern itself because
2012  * we don't want to serialize the directory names */
2013
2014 /* I suppose this should be cleaned upon termination, too... */
2015 typedef struct _FcPatternDirMapping {
2016     const FcPattern     *p;
2017     const char *fname;
2018 } FcPatternDirMapping;
2019
2020 #define PATTERNDIR_HASH_SIZE    31
2021 static struct patternDirBucket {
2022     struct patternDirBucket     *next;
2023     FcPatternDirMapping         m;
2024 } FcPatternDirBuckets[PATTERNDIR_HASH_SIZE];
2025
2026 void
2027 FcPatternAddFullFname (const FcPattern *p, const char *fname)
2028 {
2029     struct patternDirBucket     *pb;
2030
2031     /* N.B. FcPatternHash fails, since it's contents-based, not
2032      * address-based, and we're in the process of mutating the FcPattern. */
2033     for (pb = &FcPatternDirBuckets
2034              [((unsigned long)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
2035          pb->m.p != p && pb->next;
2036          pb = pb->next)
2037         ;
2038
2039     if (pb->m.p == p)
2040     {
2041         pb->m.fname = fname;
2042         return;
2043     }
2044
2045     pb->next = malloc (sizeof (struct patternDirBucket));
2046     if (!pb->next)
2047         return;
2048     FcMemAlloc (FC_MEM_CACHE, sizeof (struct patternDirBucket));
2049
2050     pb->next->next = 0;
2051     pb->next->m.p = p;
2052     pb->next->m.fname = fname;
2053 }
2054
2055 static const char *
2056 FcPatternFindFullFname (const FcPattern *p)
2057 {
2058     struct patternDirBucket     *pb;
2059
2060     for (pb = &FcPatternDirBuckets
2061              [((unsigned long)p / sizeof (FcPattern *)) % PATTERNDIR_HASH_SIZE];
2062          pb; pb = pb->next)
2063         if (pb->m.p == p)
2064             return pb->m.fname;
2065
2066     return 0;
2067 }
2068
2069 void
2070 FcPatternTransferFullFname (const FcPattern *new, const FcPattern *orig)
2071 {
2072     FcChar8 * s;
2073     FcPatternGetString (orig, FC_FILE, 0, &s);
2074     FcPatternAddFullFname (new,
2075                            (char *)FcStrCopy
2076                            ((FcChar8 *)FcPatternFindFullFname(orig)));
2077 }