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