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