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