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