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[] = {
 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                                FcValueListPtrU(l)->value, FcTrue))
1219                 goto bail1;
1220     }
1221
1222     return new;
1223
1224 bail1:
1225     FcPatternDestroy (new);
1226 bail0:
1227     return 0;
1228 }
1229
1230 void
1231 FcPatternReference (FcPattern *p)
1232 {
1233     if (p->ref != FC_REF_CONSTANT)
1234         p->ref++;
1235 }
1236
1237 FcPattern *
1238 FcPatternVaBuild (FcPattern *orig, va_list va)
1239 {
1240     FcPattern   *ret;
1241
1242     FcPatternVapBuild (ret, orig, va);
1243     return ret;
1244 }
1245
1246 FcPattern *
1247 FcPatternBuild (FcPattern *orig, ...)
1248 {
1249     va_list     va;
1250
1251     va_start (va, orig);
1252     FcPatternVapBuild (orig, orig, va);
1253     va_end (va);
1254     return orig;
1255 }
1256
1257 /*
1258  * Add all of the elements in 's' to 'p'
1259  */
1260 FcBool
1261 FcPatternAppend (FcPattern *p, FcPattern *s)
1262 {
1263     int             i;
1264     FcPatternElt    *e;
1265     FcValueListPtr  v;
1266
1267     for (i = 0; i < s->num; i++)
1268     {
1269         e = FcPatternEltU(s->elts)+i;
1270         for (v = e->values; FcValueListPtrU(v);
1271              v = FcValueListPtrU(v)->next)
1272         {
1273             if (!FcPatternAddWithBinding (p, FcObjectPtrU(e->object),
1274                                           FcValueCanonicalize(&FcValueListPtrU(v)->value),
1275                                           FcValueListPtrU(v)->binding, FcTrue))
1276                 return FcFalse;
1277         }
1278     }
1279     return FcTrue;
1280 }
1281
1282 #define OBJECT_HASH_SIZE    31
1283 static struct objectBucket {
1284     struct objectBucket *next;
1285     FcChar32            hash;
1286 } *FcObjectBuckets[OBJECT_HASH_SIZE];
1287
1288 const FcChar8 *
1289 FcStrStaticName (const FcChar8 *name)
1290 {
1291     FcChar32            hash = FcStringHash (name);
1292     struct objectBucket **p;
1293     struct objectBucket *b;
1294     int                 size;
1295
1296     for (p = &FcObjectBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1297         if (b->hash == hash && !strcmp ((char *)name, (char *) (b + 1)))
1298             return (FcChar8 *) (b + 1);
1299     size = sizeof (struct objectBucket) + strlen ((char *)name) + 1;
1300     b = malloc (size);
1301     FcMemAlloc (FC_MEM_STATICSTR, size);
1302     if (!b)
1303         return NULL;
1304     b->next = 0;
1305     b->hash = hash;
1306     strcpy ((char *) (b + 1), (char *)name);
1307     *p = b;
1308     return (FcChar8 *) (b + 1);
1309 }
1310
1311 static void
1312 FcStrStaticNameFini (void)
1313 {
1314     int i, size;
1315     struct objectBucket *b, *next;
1316     char *name;
1317
1318     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1319     {
1320         for (b = FcObjectBuckets[i]; b; b = next)
1321         {
1322             next = b->next;
1323             name = (char *) (b + 1);
1324             size = sizeof (struct objectBucket) + strlen (name) + 1;
1325             FcMemFree (FC_MEM_STATICSTR, size);
1326             free (b);
1327         }
1328         FcObjectBuckets[i] = 0;
1329     }
1330 }
1331
1332 void
1333 FcPatternFini (void)
1334 {
1335     FcPatternBaseThawAll ();
1336     FcValueListThawAll ();
1337     FcStrStaticNameFini ();
1338     FcObjectStaticNameFini ();
1339 }
1340
1341 FcPatternElt *
1342 FcPatternEltU (FcPatternEltPtr pei)
1343 {
1344     if (pei.bank == FC_BANK_DYNAMIC)
1345         return pei.u.dyn;
1346
1347     return &fcpatternelts[FcCacheBankToIndex(pei.bank)][pei.u.stat];
1348 }
1349
1350 static FcPatternEltPtr
1351 FcPatternEltPtrCreateDynamic (FcPatternElt * e)
1352 {
1353     FcPatternEltPtr new;
1354     new.bank = FC_BANK_DYNAMIC;
1355     new.u.dyn = e;
1356     return new;
1357 }
1358
1359 static FcPatternEltPtr
1360 FcPatternEltPtrCreateStatic (int bank, int i)
1361 {
1362     FcPatternEltPtr new;
1363     new.bank = bank;
1364     new.u.stat = i;
1365     return new;
1366 }
1367
1368 static void
1369 FcStrNewBank (void);
1370 static int
1371 FcStrNeededBytes (const FcChar8 * s);
1372 static void *
1373 FcStrDistributeBytes (FcCache * metadata, void * block_ptr);
1374 static const FcChar8 *
1375 FcStrSerialize (int bank, const FcChar8 * s);
1376 static void *
1377 FcStrUnserialize (FcCache metadata, void *block_ptr);
1378
1379 static void
1380 FcValueListNewBank (void);
1381 static int
1382 FcValueListNeededBytes (FcValueList * vl);
1383 static void *
1384 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr);
1385 static FcValueListPtr
1386 FcValueListSerialize(int bank, FcValueList *pi);
1387 static void *
1388 FcValueListUnserialize (FcCache metadata, void *block_ptr);
1389
1390
1391 void
1392 FcPatternNewBank (void)
1393 {
1394     fcpattern_count = 0;
1395     fcpatternelt_count = 0;
1396
1397     FcStrNewBank();
1398     FcValueListNewBank();
1399 }
1400
1401 int
1402 FcPatternNeededBytes (FcPattern * p)
1403 {
1404     int i, cum = 0, c;
1405
1406     fcpattern_count++;
1407     fcpatternelt_count += p->num;
1408
1409     for (i = 0; i < p->num; i++)
1410     {
1411         c = FcValueListNeededBytes (FcValueListPtrU
1412                                     (((FcPatternEltU(p->elts)+i)->values)));
1413         if (c < 0)
1414             return c;
1415         cum += c;
1416     }
1417
1418     return cum + sizeof (FcPattern) + sizeof(FcPatternElt)*p->num;
1419 }
1420
1421 static FcBool
1422 FcPatternEnsureBank (int bi)
1423 {
1424     FcPattern **pp;
1425     FcPatternElt **ep;
1426     int i;
1427
1428     if (!fcpatterns || fcpattern_bank_count <= bi)
1429     {
1430         int new_count = bi + 4;
1431         pp = realloc (fcpatterns, sizeof (FcPattern *) * new_count);
1432         if (!pp)
1433             return 0;
1434
1435         FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern *) * new_count);
1436         fcpatterns = pp;
1437
1438         ep = realloc (fcpatternelts, sizeof (FcPatternElt *) * new_count);
1439         if (!ep)
1440             return 0;
1441
1442         FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt *) * new_count);
1443         fcpatternelts = ep;
1444
1445         for (i = fcpattern_bank_count; i < new_count; i++)
1446         {
1447             fcpatterns[i] = 0;
1448             fcpatternelts[i] = 0;
1449         }
1450
1451         fcpattern_bank_count = new_count;
1452     }
1453
1454     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * fcpattern_count);
1455     return FcTrue;
1456 }
1457
1458 void *
1459 FcPatternDistributeBytes (FcCache * metadata, void * block_ptr)
1460 {
1461     int bi = FcCacheBankToIndex(metadata->bank);
1462
1463     if (!FcPatternEnsureBank(bi))
1464         return 0;
1465
1466     fcpattern_ptr = 0;
1467     fcpatterns[bi] = (FcPattern *)block_ptr;
1468     block_ptr = (void *)((char *)block_ptr +
1469                          (sizeof (FcPattern) * fcpattern_count));
1470
1471     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt) * fcpatternelt_count);
1472     fcpatternelt_ptr = 0;
1473     fcpatternelts[bi] = (FcPatternElt *)block_ptr;
1474     block_ptr = (void *)((char *)block_ptr +
1475                          (sizeof (FcPatternElt) * fcpatternelt_count));
1476
1477     metadata->pattern_count = fcpattern_count;
1478     metadata->patternelt_count = fcpatternelt_count;
1479
1480     block_ptr = FcStrDistributeBytes (metadata, block_ptr);
1481     block_ptr = FcValueListDistributeBytes (metadata, block_ptr);
1482     return block_ptr;
1483 }
1484
1485 FcPattern *
1486 FcPatternSerialize (int bank, FcPattern *old)
1487 {
1488     FcPattern *p;
1489     FcPatternElt *e, *nep;
1490     FcValueList * nv;
1491     FcValueListPtr v, nv_head, nvp;
1492     int i, elts, bi = FcCacheBankToIndex(bank);
1493
1494     p = &fcpatterns[bi][fcpattern_ptr++];
1495     p->bank = bank;
1496     elts = fcpatternelt_ptr;
1497     nep = &fcpatternelts[bi][elts];
1498     if (!nep)
1499         return FcFalse;
1500
1501     fcpatternelt_ptr += old->num;
1502
1503     for (e = FcPatternEltU(old->elts), i=0; i < old->num; i++, e++)
1504     {
1505         v = e->values;
1506         nvp = nv_head = FcValueListSerialize(bank, FcValueListPtrU(v));
1507         if (!FcValueListPtrU(nv_head))
1508             return 0;
1509         nv = FcValueListPtrU(nvp);
1510
1511         for (;
1512              FcValueListPtrU(v);
1513              v = FcValueListPtrU(v)->next,
1514                  nv = FcValueListPtrU(nv->next))
1515         {
1516
1517             if (FcValueListPtrU(FcValueListPtrU(v)->next))
1518             {
1519                 nvp = FcValueListSerialize
1520                     (bank, FcValueListPtrU(FcValueListPtrU(v)->next));
1521                 nv->next = nvp;
1522             }
1523         }
1524
1525         nep[i].values = nv_head;
1526         nep[i].object = e->object;
1527     }
1528
1529     p->elts = old->elts;
1530     p->elts = FcPatternEltPtrCreateStatic(bank, elts);
1531     p->size = old->num;
1532     p->num = old->num;
1533     p->ref = FC_REF_CONSTANT;
1534     return p;
1535 }
1536
1537 void *
1538 FcPatternUnserialize (FcCache metadata, void *block_ptr)
1539 {
1540     int bi = FcCacheBankToIndex(metadata.bank);
1541     if (!FcPatternEnsureBank(bi))
1542         return FcFalse;
1543
1544     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * metadata.pattern_count);
1545     fcpatterns[bi] = (FcPattern *)block_ptr;
1546     block_ptr = (void *)((char *)block_ptr +
1547                          (sizeof (FcPattern) * metadata.pattern_count));
1548
1549     FcMemAlloc (FC_MEM_PATELT,
1550                 sizeof (FcPatternElt) * metadata.patternelt_count);
1551     fcpatternelts[bi] = (FcPatternElt *)block_ptr;
1552     block_ptr = (void *)((char *)block_ptr +
1553                          (sizeof (FcPatternElt) * metadata.patternelt_count));
1554
1555     block_ptr = FcStrUnserialize (metadata, block_ptr);
1556     block_ptr = FcValueListUnserialize (metadata, block_ptr);
1557
1558     return block_ptr;
1559 }
1560
1561 static void
1562 FcValueListNewBank (void)
1563 {
1564     fcvaluelist_count = 0;
1565
1566     FcCharSetNewBank();
1567     FcLangSetNewBank();
1568 }
1569
1570 static int
1571 FcValueListNeededBytes (FcValueList *p)
1572 {
1573     FcValueList *vl;
1574     int cum = 0;
1575
1576     for (vl = p;
1577          vl;
1578          vl = FcValueListPtrU(vl->next))
1579     {
1580         FcValue v = FcValueCanonicalize(&vl->value); // unserialize just in case
1581
1582         switch (v.type)
1583         {
1584         case FcTypeCharSet:
1585             cum += FcCharSetNeededBytes(v.u.c);
1586             break;
1587         case FcTypeLangSet:
1588             cum += FcLangSetNeededBytes(v.u.l);
1589             break;
1590         case FcTypeString:
1591             cum += FcStrNeededBytes(v.u.s);
1592         default:
1593             break;
1594         }
1595         fcvaluelist_count++;
1596         cum += sizeof (FcValueList);
1597     }
1598
1599     return cum;
1600 }
1601
1602 static FcBool
1603 FcValueListEnsureBank (int bi)
1604 {
1605     FcValueList **pvl;
1606
1607     if (!fcvaluelists || fcvaluelist_bank_count <= bi)
1608     {
1609         int new_count = bi + 2, i;
1610
1611         pvl = realloc (fcvaluelists, sizeof (FcValueList *) * new_count);
1612         if (!pvl)
1613             return FcFalse;
1614
1615         FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList *) * new_count);
1616
1617         fcvaluelists = pvl;
1618         for (i = fcvaluelist_bank_count; i < new_count; i++)
1619             fcvaluelists[i] = 0;
1620
1621         fcvaluelist_bank_count = new_count;
1622     }
1623     return FcTrue;
1624 }
1625
1626 static void *
1627 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr)
1628 {
1629     int bi = FcCacheBankToIndex(metadata->bank);
1630
1631     if (!FcValueListEnsureBank(bi))
1632         return 0;
1633
1634     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList) * fcvaluelist_count);
1635     fcvaluelist_ptr = 0;
1636     fcvaluelists[bi] = (FcValueList *)block_ptr;
1637     block_ptr = (void *)((char *)block_ptr +
1638                          (sizeof (FcValueList) * fcvaluelist_count));
1639     metadata->valuelist_count = fcvaluelist_count;
1640
1641     block_ptr = FcCharSetDistributeBytes(metadata, block_ptr);
1642     block_ptr = FcLangSetDistributeBytes(metadata, block_ptr);
1643
1644     return block_ptr;
1645 }
1646
1647 static FcValueListPtr
1648 FcValueListSerialize(int bank, FcValueList *pi)
1649 {
1650     FcValueListPtr new;
1651     FcValue * v;
1652     int bi = FcCacheBankToIndex(bank);
1653
1654     if (!pi)
1655     {
1656         new.bank = FC_BANK_DYNAMIC;
1657         new.u.dyn = 0;
1658         return new;
1659     }
1660
1661     fcvaluelists[bi][fcvaluelist_ptr] = *pi;
1662     new.bank = bank;
1663     new.u.stat = fcvaluelist_ptr++;
1664     v = &fcvaluelists[bi][new.u.stat].value;
1665     switch (v->type)
1666     {
1667     case FcTypeString:
1668         if (v->u.s)
1669         {
1670             const FcChar8 * s = FcStrSerialize(bank, v->u.s);
1671             if (!s)
1672                 return FcValueListPtrCreateDynamic(pi);
1673             v->u.s_off = s - (const FcChar8 *)v;
1674             v->type |= FC_STORAGE_STATIC;
1675         }
1676         break;
1677     case FcTypeMatrix:
1678         break;
1679     case FcTypeCharSet:
1680         if (v->u.c)
1681         {
1682             FcCharSet * c = FcCharSetSerialize(bank, (FcCharSet *)v->u.c);
1683             if (!c)
1684                 return FcValueListPtrCreateDynamic(pi);
1685             v->u.c_off = (char *)c - (char *)v;
1686             v->type |= FC_STORAGE_STATIC;
1687         }
1688         break;
1689     case FcTypeLangSet:
1690         if (v->u.l)
1691         {
1692             FcLangSet * l = FcLangSetSerialize(bank, (FcLangSet *)v->u.l);
1693             if (!l)
1694                 return FcValueListPtrCreateDynamic(pi);
1695             v->u.l_off = (char *)l - (char *)v;
1696             v->type |= FC_STORAGE_STATIC;
1697         }
1698         break;
1699     default:
1700         break;
1701     }
1702     return new;
1703 }
1704
1705 static void *
1706 FcValueListUnserialize (FcCache metadata, void *block_ptr)
1707 {
1708     int bi = FcCacheBankToIndex(metadata.bank);
1709
1710     if (!FcValueListEnsureBank(bi))
1711         return 0;
1712
1713     FcMemAlloc (FC_MEM_VALLIST,
1714                 sizeof (FcValueList) * metadata.valuelist_count);
1715     fcvaluelists[bi] = (FcValueList *)block_ptr;
1716     block_ptr = (void *)((char *)block_ptr +
1717                          (sizeof (FcValueList) * metadata.valuelist_count));
1718
1719     block_ptr = FcCharSetUnserialize(metadata, block_ptr);
1720     block_ptr = FcLangSetUnserialize(metadata, block_ptr);
1721
1722     return block_ptr;
1723 }
1724
1725 FcValueList *
1726 FcValueListPtrU (FcValueListPtr pi)
1727 {
1728     if (pi.bank == FC_BANK_DYNAMIC)
1729         return pi.u.dyn;
1730
1731     return &fcvaluelists[FcCacheBankToIndex(pi.bank)][pi.u.stat];
1732 }
1733
1734 FcValueListPtr
1735 FcValueListPtrCreateDynamic(FcValueList * p)
1736 {
1737     FcValueListPtr r;
1738
1739     r.bank = FC_BANK_DYNAMIC;
1740     r.u.dyn = p;
1741     return r;
1742 }
1743
1744 static FcChar8 ** static_strs;
1745 static int static_str_bank_count = 0, fcstr_ptr, fcstr_count;
1746
1747 static struct objectBucket *FcStrBuckets[OBJECT_HASH_SIZE];
1748
1749 static void
1750 FcStrNewBank (void)
1751 {
1752     int i, size;
1753     struct objectBucket *b, *next;
1754     char *name;
1755
1756     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1757     {
1758         for (b = FcStrBuckets[i]; b; b = next)
1759         {
1760             next = b->next;
1761             name = (char *) (b + 1);
1762             size = sizeof (struct objectBucket) + strlen (name) + 1;
1763             FcMemFree (FC_MEM_STATICSTR, size);
1764             free (b);
1765         }
1766         FcStrBuckets[i] = 0;
1767     }
1768
1769     fcstr_count = 0;
1770 }
1771
1772 static int
1773 FcStrNeededBytes (const FcChar8 * s)
1774 {
1775     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1776     struct objectBucket **p;
1777     struct objectBucket *b;
1778     int                 size;
1779
1780     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1781         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1782             return 0;
1783     size = sizeof (struct objectBucket) + strlen ((char *)s) + 1 + sizeof(char *);
1784     b = malloc (size);
1785     FcMemAlloc (FC_MEM_STATICSTR, size);
1786     if (!b)
1787         return -1;
1788     b->next = 0;
1789     b->hash = hash;
1790     strcpy ((char *) (b + 1), (char *)s);
1791     *(char **)((char *) (b + 1) + strlen((char *)s) + 1) = 0;
1792     *p = b;
1793
1794     fcstr_count += strlen((char *)s) + 1;
1795     return strlen((char *)s) + 1;
1796 }
1797
1798 static FcBool
1799 FcStrEnsureBank (int bi)
1800 {
1801     FcChar8 ** ss;
1802
1803     if (!static_strs || static_str_bank_count <= bi)
1804     {
1805         int new_count = bi + 4, i;
1806         ss = realloc (static_strs, sizeof (const char *) * new_count);
1807         if (!ss)
1808             return FcFalse;
1809
1810         FcMemAlloc (FC_MEM_STRING, sizeof (const char *) * (new_count-static_str_bank_count));
1811         static_strs = ss;
1812
1813         for (i = static_str_bank_count; i < new_count; i++)
1814             static_strs[i] = 0;
1815         static_str_bank_count = new_count;
1816     }
1817     return FcTrue;
1818 }
1819
1820 static void *
1821 FcStrDistributeBytes (FcCache * metadata, void * block_ptr)
1822 {
1823     int bi = FcCacheBankToIndex(metadata->bank);
1824     if (!FcStrEnsureBank(bi))
1825         return 0;
1826
1827     FcMemAlloc (FC_MEM_STRING, sizeof (char) * fcstr_count);
1828     static_strs[bi] = (FcChar8 *)block_ptr;
1829     block_ptr = (void *)((char *)block_ptr + (sizeof (char) * fcstr_count));
1830     metadata->str_count = fcstr_count;
1831     fcstr_ptr = 0;
1832
1833     return block_ptr;
1834 }
1835
1836 static const FcChar8 *
1837 FcStrSerialize (int bank, const FcChar8 * s)
1838 {
1839     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1840     struct objectBucket **p;
1841     struct objectBucket *b;
1842     int bi = FcCacheBankToIndex(bank);
1843
1844     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1845         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1846         {
1847             FcChar8 * t = *(FcChar8 **)(((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1);
1848             if (!t)
1849             {
1850                 strcpy((char *)(static_strs[bi] + fcstr_ptr), (char *)s);
1851                 *(FcChar8 **)((FcChar8 *) (b + 1) + strlen((char *)s) + 1) = (static_strs[bi] + fcstr_ptr);
1852                 fcstr_ptr += strlen((char *)s) + 1;
1853                 t = *(FcChar8 **)(((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1);
1854             }
1855             return t;
1856         }
1857     return 0;
1858 }
1859
1860 static void *
1861 FcStrUnserialize (FcCache metadata, void *block_ptr)
1862 {
1863     int bi = FcCacheBankToIndex(metadata.bank);
1864     if (!FcStrEnsureBank(bi))
1865         return 0;
1866
1867     FcMemAlloc (FC_MEM_STRING, sizeof (char) * metadata.str_count);
1868     static_strs[bi] = (FcChar8 *)block_ptr;
1869     block_ptr = (void *)((char *)block_ptr +
1870                          (sizeof (char) * metadata.str_count));
1871
1872     return block_ptr;
1873 }
1874