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