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