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