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