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