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 void
 655 FcPatternThawAll (void)
 656 {
 657     FcPatternBaseThawAll ();
 658     FcValueListThawAll ();
 659 }
 660
 661 static int
 662 FcPatternPosition (const FcPattern *p, const char *object)
 663 {
 664     int     low, high, mid, c;
 665     FcObjectPtr obj;
 666
 667     obj = FcObjectStaticName(object);
 668     low = 0;
 669     high = p->num - 1;
 670     c = 1;
 671     mid = 0;
 672     while (low <= high)
 673     {
 674         mid = (low + high) >> 1;
 675         c = FcObjectPtrCompare((FcPatternEltU(p->elts)+mid)->object, obj);
 676         if (c == 0)
 677             return mid;
 678         if (c < 0)
 679             low = mid + 1;
 680         else
 681             high = mid - 1;
 682     }
 683     if (c < 0)
 684         mid++;
 685     return -(mid + 1);
 686 }
 687
 688 FcPatternElt *
 689 FcPatternFindElt (const FcPattern *p, const char *object)
 690 {
 691     int     i = FcPatternPosition (p, object);
 692     if (i < 0)
 693         return 0;
 694     return FcPatternEltU(p->elts)+i;
 695 }
 696
 697 FcPatternElt *
 698 FcPatternInsertElt (FcPattern *p, const char *object)
 699 {
 700     int             i;
 701     FcPatternElt   *e;
 702
 703     i = FcPatternPosition (p, object);
 704     if (i < 0)
 705     {
 706         i = -i - 1;
 707
 708         /* reallocate array */
 709         if (p->num + 1 >= p->size)
 710         {
 711             int s = p->size + 16;
 712             if (FcPatternEltU(p->elts))
 713             {
 714                 FcPatternElt *e0 = FcPatternEltU(p->elts);
 715                 e = (FcPatternElt *) realloc (e0, s * sizeof (FcPatternElt));
 716                 if (!e) /* maybe it was mmapped */
 717                 {
 718                     e = malloc(s * sizeof (FcPatternElt));
 719                     if (e)
 720                         memcpy(e, e0, p->num * sizeof (FcPatternElt));
 721                 }
 722             }
 723             else
 724                 e = (FcPatternElt *) malloc (s * sizeof (FcPatternElt));
 725             if (!e)
 726                 return FcFalse;
 727             p->elts = FcPatternEltPtrCreateDynamic(e);
 728             if (p->size)
 729                 FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
 730             FcMemAlloc (FC_MEM_PATELT, s * sizeof (FcPatternElt));
 731             while (p->size < s)
 732             {
 733                 (FcPatternEltU(p->elts)+p->size)->object = 0;
 734                 (FcPatternEltU(p->elts)+p->size)->values =
 735                     FcValueListPtrCreateDynamic(0);
 736                 p->size++;
 737             }
 738         }
 739
 740         /* move elts up */
 741         memmove (FcPatternEltU(p->elts) + i + 1,
 742                  FcPatternEltU(p->elts) + i,
 743                  sizeof (FcPatternElt) *
 744                  (p->num - i));
 745
 746         /* bump count */
 747         p->num++;
 748
 749         (FcPatternEltU(p->elts)+i)->object = FcObjectStaticName (object);
 750         (FcPatternEltU(p->elts)+i)->values = FcValueListPtrCreateDynamic(0);
 751     }
 752
 753     return FcPatternEltU(p->elts)+i;
 754 }
 755
 756 FcBool
 757 FcPatternEqual (const FcPattern *pa, const FcPattern *pb)
 758 {
 759     int i;
 760
 761     if (pa == pb)
 762         return FcTrue;
 763
 764     if (pa->num != pb->num)
 765         return FcFalse;
 766     for (i = 0; i < pa->num; i++)
 767     {
 768         if (FcObjectPtrCompare((FcPatternEltU(pa->elts)+i)->object,
 769                                (FcPatternEltU(pb->elts)+i)->object) != 0)
 770             return FcFalse;
 771         if (!FcValueListEqual ((FcPatternEltU(pa->elts)+i)->values,
 772                                (FcPatternEltU(pb->elts)+i)->values))
 773             return FcFalse;
 774     }
 775     return FcTrue;
 776 }
 777
 778 FcChar32
 779 FcPatternHash (const FcPattern *p)
 780 {
 781     int         i;
 782     FcChar32    h = 0;
 783
 784     for (i = 0; i < p->num; i++)
 785     {
 786         h = (((h << 1) | (h >> 31)) ^
 787              FcStringHash ((const FcChar8 *) FcObjectPtrU(((FcPatternEltU(p->elts)+i)->object))) ^
 788              FcValueListHash ((FcPatternEltU(p->elts)+i)->values));
 789     }
 790     return h;
 791 }
 792
 793 FcBool
 794 FcPatternEqualSubset (const FcPattern *pai, const FcPattern *pbi, const FcObjectSet *os)
 795 {
 796     FcPatternElt    *ea, *eb;
 797     int             i;
 798
 799     for (i = 0; i < os->nobject; i++)
 800     {
 801         ea = FcPatternFindElt (pai, FcObjectPtrU(os->objects[i]));
 802         eb = FcPatternFindElt (pbi, FcObjectPtrU(os->objects[i]));
 803         if (ea)
 804         {
 805             if (!eb)
 806                 return FcFalse;
 807             if (!FcValueListEqual (ea->values, eb->values))
 808                 return FcFalse;
 809         }
 810         else
 811         {
 812             if (eb)
 813                 return FcFalse;
 814         }
 815     }
 816     return FcTrue;
 817 }
 818
 819 FcBool
 820 FcPatternAddWithBinding  (FcPattern         *p,
 821                           const char        *object,
 822                           FcValue           value,
 823                           FcValueBinding    binding,
 824                           FcBool            append)
 825 {
 826     FcPatternElt   *e;
 827     FcValueListPtr new, *prev;
 828     FcValueList *  newp;
 829
 830     if (p->ref == FC_REF_CONSTANT)
 831         goto bail0;
 832
 833     newp = malloc (sizeof (FcValueList));
 834     if (!newp)
 835         goto bail0;
 836
 837     memset(newp, 0, sizeof (FcValueList));
 838     new = FcValueListPtrCreateDynamic(newp);
 839     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList));
 840     /* dup string */
 841     value = FcValueSave (value);
 842     if (value.type == FcTypeVoid)
 843         goto bail1;
 844
 845     FcValueListPtrU(new)->value = value;
 846     FcValueListPtrU(new)->binding = binding;
 847     FcValueListPtrU(new)->next = FcValueListPtrCreateDynamic(0);
 848
 849     e = FcPatternInsertElt (p, object);
 850     if (!e)
 851         goto bail2;
 852
 853     if (append)
 854     {
 855         for (prev = &e->values; FcValueListPtrU(*prev); prev = &FcValueListPtrU(*prev)->next)
 856             ;
 857         *prev = new;
 858     }
 859     else
 860     {
 861         FcValueListPtrU(new)->next = e->values;
 862         e->values = new;
 863     }
 864
 865     return FcTrue;
 866
 867 bail2:
 868     switch (value.type) {
 869     case FcTypeString:
 870         FcStrFree ((FcChar8 *) FcObjectPtrU(value.u.si));
 871         break;
 872     case FcTypeMatrix:
 873         FcMatrixFree (FcMatrixPtrU(value.u.mi));
 874         break;
 875     case FcTypeCharSet:
 876         FcCharSetDestroy (FcCharSetPtrU(value.u.ci));
 877         break;
 878     case FcTypeLangSet:
 879         FcLangSetDestroy (FcLangSetPtrU(value.u.li));
 880         break;
 881     default:
 882         break;
 883     }
 884 bail1:
 885     FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 886     free (FcValueListPtrU(new));
 887 bail0:
 888     return FcFalse;
 889 }
 890
 891 FcBool
 892 FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
 893 {
 894     return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
 895 }
 896
 897 FcBool
 898 FcPatternAddWeak  (FcPattern *p, const char *object, FcValue value, FcBool append)
 899 {
 900     return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
 901 }
 902
 903 FcBool
 904 FcPatternDel (FcPattern *p, const char *object)
 905 {
 906     FcPatternElt   *e;
 907
 908     e = FcPatternFindElt (p, object);
 909     if (!e)
 910         return FcFalse;
 911
 912     /* destroy value */
 913     FcValueListDestroy (e->values);
 914
 915     /* shuffle existing ones down */
 916     memmove (e, e+1,
 917              (FcPatternEltU(p->elts) + p->num - (e + 1)) *
 918              sizeof (FcPatternElt));
 919     p->num--;
 920     (FcPatternEltU(p->elts)+p->num)->object = 0;
 921     (FcPatternEltU(p->elts)+p->num)->values = FcValueListPtrCreateDynamic(0);
 922     return FcTrue;
 923 }
 924
 925 FcBool
 926 FcPatternRemove (FcPattern *p, const char *object, int id)
 927 {
 928     FcPatternElt    *e;
 929     FcValueListPtr  *prev, l;
 930
 931     e = FcPatternFindElt (p, object);
 932     if (!e)
 933         return FcFalse;
 934     for (prev = &e->values;
 935          FcValueListPtrU(l = *prev);
 936          prev = &FcValueListPtrU(l)->next)
 937     {
 938         if (!id)
 939         {
 940             *prev = FcValueListPtrU(l)->next;
 941             FcValueListPtrU(l)->next = FcValueListPtrCreateDynamic(0);
 942             FcValueListDestroy (l);
 943             if (!FcValueListPtrU(e->values))
 944                 FcPatternDel (p, object);
 945             return FcTrue;
 946         }
 947         id--;
 948     }
 949     return FcFalse;
 950 }
 951
 952 FcBool
 953 FcPatternAddInteger (FcPattern *p, const char *object, int i)
 954 {
 955     FcValue     v;
 956
 957     v.type = FcTypeInteger;
 958     v.u.i = i;
 959     return FcPatternAdd (p, object, v, FcTrue);
 960 }
 961
 962 FcBool
 963 FcPatternAddDouble (FcPattern *p, const char *object, double d)
 964 {
 965     FcValue     v;
 966
 967     v.type = FcTypeDouble;
 968     v.u.d = d;
 969     return FcPatternAdd (p, object, v, FcTrue);
 970 }
 971
 972
 973 FcBool
 974 FcPatternAddString (FcPattern *p, const char *object, const FcChar8 *s)
 975 {
 976     FcValue     v;
 977
 978     v.type = FcTypeString;
 979     v.u.si = FcObjectStaticName(s);
 980     return FcPatternAdd (p, object, v, FcTrue);
 981 }
 982
 983 FcBool
 984 FcPatternAddMatrix (FcPattern *p, const char *object, const FcMatrix *s)
 985 {
 986     FcValue     v;
 987
 988     v.type = FcTypeMatrix;
 989     v.u.mi = FcMatrixPtrCreateDynamic((FcMatrix *) s);
 990     return FcPatternAdd (p, object, v, FcTrue);
 991 }
 992
 993
 994 FcBool
 995 FcPatternAddBool (FcPattern *p, const char *object, FcBool b)
 996 {
 997     FcValue     v;
 998
 999     v.type = FcTypeBool;
1000     v.u.b = b;
1001     return FcPatternAdd (p, object, v, FcTrue);
1002 }
1003
1004 FcBool
1005 FcPatternAddCharSet (FcPattern *p, const char *object, const FcCharSet *c)
1006 {
1007     FcValue     v;
1008
1009     v.type = FcTypeCharSet;
1010     v.u.ci = FcCharSetPtrCreateDynamic((FcCharSet *)c);
1011     return FcPatternAdd (p, object, v, FcTrue);
1012 }
1013
1014 FcBool
1015 FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
1016 {
1017     FcValue     v;
1018
1019     v.type = FcTypeFTFace;
1020     v.u.f = (void *) f;
1021     return FcPatternAdd (p, object, v, FcTrue);
1022 }
1023
1024 FcBool
1025 FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
1026 {
1027     FcValue     v;
1028
1029     v.type = FcTypeLangSet;
1030     v.u.li = FcLangSetPtrCreateDynamic((FcLangSet *)ls);
1031     return FcPatternAdd (p, object, v, FcTrue);
1032 }
1033
1034 FcResult
1035 FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
1036 {
1037     FcPatternElt   *e;
1038     FcValueListPtr l;
1039
1040     e = FcPatternFindElt (p, object);
1041     if (!e)
1042         return FcResultNoMatch;
1043     for (l = e->values; FcValueListPtrU(l); l = FcValueListPtrU(l)->next)
1044     {
1045         if (!id)
1046         {
1047             *v = FcValueListPtrU(l)->value;
1048             return FcResultMatch;
1049         }
1050         id--;
1051     }
1052     return FcResultNoId;
1053 }
1054
1055 FcResult
1056 FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
1057 {
1058     FcValue     v;
1059     FcResult    r;
1060
1061     r = FcPatternGet (p, object, id, &v);
1062     if (r != FcResultMatch)
1063         return r;
1064     switch (v.type) {
1065     case FcTypeDouble:
1066         *i = (int) v.u.d;
1067         break;
1068     case FcTypeInteger:
1069         *i = v.u.i;
1070         break;
1071     default:
1072         return FcResultTypeMismatch;
1073     }
1074     return FcResultMatch;
1075 }
1076
1077 FcResult
1078 FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
1079 {
1080     FcValue     v;
1081     FcResult    r;
1082
1083     r = FcPatternGet (p, object, id, &v);
1084     if (r != FcResultMatch)
1085         return r;
1086     switch (v.type) {
1087     case FcTypeDouble:
1088         *d = v.u.d;
1089         break;
1090     case FcTypeInteger:
1091         *d = (double) v.u.i;
1092         break;
1093     default:
1094         return FcResultTypeMismatch;
1095     }
1096     return FcResultMatch;
1097 }
1098
1099 FcResult
1100 FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
1101 {
1102     FcValue     v;
1103     FcResult    r;
1104
1105     r = FcPatternGet (p, object, id, &v);
1106     if (r != FcResultMatch)
1107         return r;
1108     if (v.type != FcTypeString)
1109         return FcResultTypeMismatch;
1110     *s = (FcChar8 *) FcObjectPtrU(v.u.si);
1111     return FcResultMatch;
1112 }
1113
1114 FcResult
1115 FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
1116 {
1117     FcValue     v;
1118     FcResult    r;
1119
1120     r = FcPatternGet (p, object, id, &v);
1121     if (r != FcResultMatch)
1122         return r;
1123     if (v.type != FcTypeMatrix)
1124         return FcResultTypeMismatch;
1125     *m = FcMatrixPtrU(v.u.mi);
1126     return FcResultMatch;
1127 }
1128
1129
1130 FcResult
1131 FcPatternGetBool(const FcPattern *p, const char *object, int id, FcBool *b)
1132 {
1133     FcValue     v;
1134     FcResult    r;
1135
1136     r = FcPatternGet (p, object, id, &v);
1137     if (r != FcResultMatch)
1138         return r;
1139     if (v.type != FcTypeBool)
1140         return FcResultTypeMismatch;
1141     *b = v.u.b;
1142     return FcResultMatch;
1143 }
1144
1145 FcResult
1146 FcPatternGetCharSet(const FcPattern *p, const char *object, int id, FcCharSet **c)
1147 {
1148     FcValue     v;
1149     FcResult    r;
1150
1151     r = FcPatternGet (p, object, id, &v);
1152     if (r != FcResultMatch)
1153         return r;
1154     if (v.type != FcTypeCharSet)
1155         return FcResultTypeMismatch;
1156     *c = FcCharSetPtrU(v.u.ci);
1157     return FcResultMatch;
1158 }
1159
1160 FcResult
1161 FcPatternGetFTFace(const FcPattern *p, const char *object, int id, FT_Face *f)
1162 {
1163     FcValue     v;
1164     FcResult    r;
1165
1166     r = FcPatternGet (p, object, id, &v);
1167     if (r != FcResultMatch)
1168         return r;
1169     if (v.type != FcTypeFTFace)
1170         return FcResultTypeMismatch;
1171     *f = (FT_Face) v.u.f;
1172     return FcResultMatch;
1173 }
1174
1175 FcResult
1176 FcPatternGetLangSet(const FcPattern *p, const char *object, int id, FcLangSet **ls)
1177 {
1178     FcValue     v;
1179     FcResult    r;
1180
1181     r = FcPatternGet (p, object, id, &v);
1182     if (r != FcResultMatch)
1183         return r;
1184     if (v.type != FcTypeLangSet)
1185         return FcResultTypeMismatch;
1186     *ls = FcLangSetPtrU(v.u.li);
1187     return FcResultMatch;
1188 }
1189
1190 FcPattern *
1191 FcPatternDuplicate (const FcPattern *orig)
1192 {
1193     FcPattern       *new;
1194     FcPatternElt    *e;
1195     int             i;
1196     FcValueListPtr  l;
1197
1198     new = FcPatternCreate ();
1199     if (!new)
1200         goto bail0;
1201
1202     e = FcPatternEltU(orig->elts);
1203
1204     for (i = 0; i < orig->num; i++)
1205     {
1206         for (l = (e + i)->values;
1207              FcValueListPtrU(l);
1208              l = FcValueListPtrU(l)->next)
1209             if (!FcPatternAdd (new, FcObjectPtrU((e + i)->object),
1210                                FcValueListPtrU(l)->value, FcTrue))
1211                 goto bail1;
1212     }
1213
1214     return new;
1215
1216 bail1:
1217     FcPatternDestroy (new);
1218 bail0:
1219     return 0;
1220 }
1221
1222 void
1223 FcPatternReference (FcPattern *p)
1224 {
1225     if (p->ref != FC_REF_CONSTANT)
1226         p->ref++;
1227 }
1228
1229 FcPattern *
1230 FcPatternVaBuild (FcPattern *orig, va_list va)
1231 {
1232     FcPattern   *ret;
1233
1234     FcPatternVapBuild (ret, orig, va);
1235     return ret;
1236 }
1237
1238 FcPattern *
1239 FcPatternBuild (FcPattern *orig, ...)
1240 {
1241     va_list     va;
1242
1243     va_start (va, orig);
1244     FcPatternVapBuild (orig, orig, va);
1245     va_end (va);
1246     return orig;
1247 }
1248
1249 /*
1250  * Add all of the elements in 's' to 'p'
1251  */
1252 FcBool
1253 FcPatternAppend (FcPattern *p, FcPattern *s)
1254 {
1255     int             i;
1256     FcPatternElt    *e;
1257     FcValueListPtr  v;
1258
1259     for (i = 0; i < s->num; i++)
1260     {
1261         e = FcPatternEltU(s->elts)+i;
1262         for (v = e->values; FcValueListPtrU(v);
1263              v = FcValueListPtrU(v)->next)
1264         {
1265             if (!FcPatternAddWithBinding (p, FcObjectPtrU(e->object),
1266                                           FcValueListPtrU(v)->value,
1267                                           FcValueListPtrU(v)->binding, FcTrue))
1268                 return FcFalse;
1269         }
1270     }
1271     return FcTrue;
1272 }
1273
1274 FcPatternElt *
1275 FcPatternEltU (FcPatternEltPtr pei)
1276 {
1277     switch (pei.storage)
1278     {
1279     case FcStorageStatic:
1280         if (pei.u.stat == 0) return 0;
1281         return &fcpatternelts[pei.u.stat];
1282     case FcStorageDynamic:
1283         return pei.u.dyn;
1284     default:
1285         return 0;
1286     }
1287 }
1288
1289 static FcPatternEltPtr
1290 FcPatternEltPtrCreateDynamic (FcPatternElt * e)
1291 {
1292     FcPatternEltPtr new;
1293     new.storage = FcStorageDynamic;
1294     new.u.dyn = e;
1295     return new;
1296 }
1297
1298 static FcPatternEltPtr
1299 FcPatternEltPtrCreateStatic (int i)
1300 {
1301     FcPatternEltPtr new;
1302     new.storage = FcStorageStatic;
1303     new.u.stat = i;
1304     return new;
1305 }
1306
1307 static FcBool
1308 FcPatternEltIsDynamic (FcPatternEltPtr pei)
1309 {
1310     return pei.storage == FcStorageDynamic;
1311 }
1312
1313
1314 void
1315 FcPatternClearStatic (void)
1316 {
1317     fcpatterns = 0;
1318     fcpattern_ptr = 0;
1319     fcpattern_count = 0;
1320
1321     fcpatternelts = 0;
1322     fcpatternelt_ptr = 0;
1323     fcpatternelt_count = 0;
1324 }
1325
1326 void
1327 FcValueListClearStatic (void)
1328 {
1329     fcvaluelists = 0;
1330     fcvaluelist_ptr = 0;
1331     fcvaluelist_count = 0;
1332 }
1333
1334 static FcObjectPtr
1335 FcObjectSerialize (FcObjectPtr si);
1336
1337 FcBool
1338 FcPatternPrepareSerialize (FcPattern * p)
1339 {
1340     int i;
1341
1342     fcpattern_count++;
1343     fcpatternelt_count += p->num;
1344
1345     for (i = 0; i < p->num; i++)
1346     {
1347         FcObjectPrepareSerialize
1348             ((FcPatternEltU(p->elts)+i)->object);
1349         if (!FcValueListPrepareSerialize
1350             (FcValueListPtrU(((FcPatternEltU(p->elts)+i)->values))))
1351             return FcFalse;
1352     }
1353
1354     return FcTrue;
1355 }
1356
1357 FcBool
1358 FcValueListPrepareSerialize (FcValueList *p)
1359 {
1360     FcValueList *vl;
1361
1362     for (vl = p;
1363          vl;
1364          vl = FcValueListPtrU(vl->next))
1365     {
1366         FcValue v = vl->value;
1367
1368         switch (v.type)
1369         {
1370         case FcTypeMatrix:
1371             FcMatrixPrepareSerialize(FcMatrixPtrU(v.u.mi));
1372             break;
1373         case FcTypeCharSet:
1374             FcCharSetPrepareSerialize(FcCharSetPtrU(v.u.ci));
1375             break;
1376         case FcTypeLangSet:
1377             FcLangSetPrepareSerialize(FcLangSetPtrU(v.u.li));
1378             break;
1379         case FcTypeString:
1380             FcObjectPrepareSerialize(v.u.si);
1381         default:
1382             break;
1383         }
1384         fcvaluelist_count++;
1385     }
1386
1387     return FcTrue;
1388 }
1389
1390 FcPattern *
1391 FcPatternSerialize (FcPattern *old)
1392 {
1393     FcPattern *p;
1394     FcPatternElt *e, *nep;
1395     FcValueList * nv;
1396     FcValueListPtr v, nv_head, nvp;
1397     int i, elts;
1398
1399     if (!fcpatterns)
1400     {
1401         p = malloc (sizeof (FcPattern) * fcpattern_count);
1402         if (!p)
1403             goto bail;
1404
1405         FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * fcpattern_count);
1406         fcpatterns = p;
1407         fcpattern_ptr = 0;
1408
1409         e = malloc (sizeof (FcPatternElt) * fcpatternelt_count);
1410         if (!e)
1411             goto bail1;
1412
1413         FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt) * fcpatternelt_count);
1414         fcpatternelts = e;
1415         fcpatternelt_ptr = 0;
1416     }
1417
1418     p = FcPatternCreate();
1419     elts = fcpatternelt_ptr;
1420     nep = &fcpatternelts[elts];
1421     if (!nep)
1422         return FcFalse;
1423     fcpatternelt_ptr += old->num;
1424
1425     for (e = FcPatternEltU(old->elts), i=0; i < old->num; i++, e++)
1426     {
1427         v = e->values;
1428         nvp = nv_head = FcValueListSerialize(FcValueListPtrU(v));
1429         if (!FcValueListPtrU(nv_head))
1430             goto bail2;
1431         nv = FcValueListPtrU(nvp);
1432
1433         for (;
1434              FcValueListPtrU(v);
1435              v = FcValueListPtrU(v)->next,
1436                  nv = FcValueListPtrU(nv->next))
1437         {
1438
1439             if (FcValueListPtrU(FcValueListPtrU(v)->next))
1440             {
1441                 nvp = FcValueListSerialize
1442                     (FcValueListPtrU(FcValueListPtrU(v)->next));
1443                 nv->next = nvp;
1444             }
1445         }
1446
1447         nep[i].values = nv_head;
1448         nep[i].object = FcObjectSerialize
1449             (FcObjectStaticName(FcObjectPtrU(e->object)));
1450     }
1451
1452     p->elts = FcPatternEltPtrCreateStatic(elts);
1453     p->size = old->num;
1454     p->ref = FC_REF_CONSTANT;
1455     return p;
1456
1457  bail2:
1458     free (fcpatternelts);
1459  bail1:
1460     free (fcpatterns);
1461  bail:
1462     return 0;
1463  }
1464
1465 FcValueListPtr
1466 FcValueListSerialize(FcValueList *pi)
1467 {
1468     FcValueListPtr new;
1469     FcValue * v;
1470     FcValueList * vl;
1471
1472     if (!fcvaluelists)
1473     {
1474         vl = malloc (sizeof (FcValueList) * fcvaluelist_count);
1475         if (!vl)
1476             return FcValueListPtrCreateDynamic(0);
1477
1478         FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList) * fcvaluelist_count);
1479         fcvaluelists = vl;
1480         fcvaluelist_ptr = 0;
1481     }
1482
1483     fcvaluelists[fcvaluelist_ptr] = *pi;
1484     new.storage = FcStorageStatic;
1485     new.u.stat = fcvaluelist_ptr++;
1486     v = &fcvaluelists[new.u.stat].value;
1487     switch (v->type)
1488     {
1489     case FcTypeString:
1490         if (FcObjectPtrU(v->u.si))
1491         {
1492             FcObjectPtr si =
1493                 FcObjectSerialize(FcObjectStaticName(FcObjectPtrU(v->u.si)));
1494             if (!FcObjectPtrU(v->u.si))
1495                 return FcValueListPtrCreateDynamic(pi);
1496             v->u.si = si;
1497         }
1498         break;
1499     case FcTypeMatrix:
1500         if (FcMatrixPtrU(v->u.mi))
1501         {
1502             FcMatrixPtr mi = FcMatrixSerialize(FcMatrixPtrU(v->u.mi));
1503
1504             if (!FcMatrixPtrU(mi))
1505                 return FcValueListPtrCreateDynamic(pi);
1506             v->u.mi = mi;
1507         }
1508         break;
1509     case FcTypeCharSet:
1510         if (FcCharSetPtrU(v->u.ci))
1511         {
1512             FcCharSetPtr ci = FcCharSetSerialize(FcCharSetPtrU(v->u.ci));
1513             if (!FcCharSetPtrU(v->u.ci))
1514                 return FcValueListPtrCreateDynamic(pi);
1515             v->u.ci = ci;
1516         }
1517         break;
1518     case FcTypeLangSet:
1519         if (FcLangSetPtrU(v->u.li))
1520         {
1521             FcLangSetPtr li = FcLangSetSerialize(FcLangSetPtrU(v->u.li));
1522             if (!FcLangSetPtrU(v->u.li))
1523                 return FcValueListPtrCreateDynamic(pi);
1524             v->u.li = li;
1525         }
1526         break;
1527     default:
1528         break;
1529     }
1530     return new;
1531 }
1532
1533 FcValueList *
1534 FcValueListPtrU (FcValueListPtr pi)
1535 {
1536     switch (pi.storage)
1537     {
1538     case FcStorageStatic:
1539         if (pi.u.stat == 0) return 0;
1540         return &fcvaluelists[pi.u.stat];
1541     case FcStorageDynamic:
1542         return pi.u.dyn;
1543     default:
1544         return 0;
1545     }
1546 }
1547
1548 FcValueListPtr
1549 FcValueListPtrCreateDynamic(FcValueList * p)
1550 {
1551     FcValueListPtr r;
1552
1553     r.storage = FcStorageDynamic;
1554     r.u.dyn = p;
1555     return r;
1556 }
1557
1558 /* Indices allow us to convert dynamic strings into static
1559  * strings without having to reassign IDs.  We do reassign IDs
1560  * when serializing, which effectively performs mark-and-sweep
1561  * garbage collection. */
1562
1563 /* objectptr_count maps FcObjectPtr to:
1564      + offsets in objectcontent_static_buf (if positive)
1565      - entries in objectcontent_dynamic (if negative)
1566 */
1567 static int objectptr_count = 1;
1568 static int objectptr_alloc = 0;
1569 static int * objectptr_indices = 0;
1570
1571 /* invariant: objectcontent_static_buf must be sorted. */
1572 /* e.g. objectptr_static_buf = "name\0style\0weight\0" */
1573 static int objectcontent_static_bytes = 0;
1574 static char * objectcontent_static_buf;
1575
1576 /* just a bunch of strings. */
1577 static int objectcontent_dynamic_count = 1;
1578 static int objectcontent_dynamic_alloc = 0;
1579 static const char ** objectcontent_dynamic = 0;
1580 static int * objectcontent_dynamic_refcount = 0;
1581
1582 #define OBJECT_HASH_SIZE    31
1583 struct objectBucket {
1584     struct objectBucket *next;
1585     FcChar32            hash;
1586 };
1587 static struct objectBucket **buckets = 0;
1588
1589 FcObjectPtr
1590 FcObjectStaticName (const char *name)
1591 {
1592     FcChar32            hash = FcStringHash ((const FcChar8 *) name);
1593     struct objectBucket **p;
1594     struct objectBucket *b;
1595     const char *        nn;
1596     int                 size;
1597     FcObjectPtr         new;
1598
1599     if (!buckets)
1600     {
1601         buckets = malloc(sizeof (struct objectBucket *)*OBJECT_HASH_SIZE);
1602         memset (buckets, 0, sizeof (struct objectBucket *)*OBJECT_HASH_SIZE);
1603     }
1604
1605     for (p = &buckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1606     {
1607         FcObjectPtr bp = *((FcObjectPtr *) (b + 1));
1608         if (b->hash == hash && FcObjectPtrU(bp) && !strcmp (name, FcObjectPtrU(bp)))
1609         {
1610             if (objectptr_indices[bp] < 0)
1611                 objectcontent_dynamic_refcount[-objectptr_indices[bp]]++;
1612             return bp;
1613         }
1614     }
1615
1616     /* didn't find it, so add a new dynamic string */
1617     if (objectcontent_dynamic_count >= objectcontent_dynamic_alloc)
1618     {
1619         int s = objectcontent_dynamic_alloc + 4;
1620
1621         const char ** d = realloc (objectcontent_dynamic,
1622                                    s*sizeof(char *));
1623         if (!d)
1624             return 0;
1625         FcMemFree(FC_MEM_STATICSTR,
1626                   objectcontent_dynamic_alloc * sizeof(char *));
1627         FcMemAlloc(FC_MEM_STATICSTR, s*sizeof(char *));
1628         objectcontent_dynamic = d;
1629         objectcontent_dynamic_alloc = s;
1630
1631         int * rc = realloc (objectcontent_dynamic_refcount, s*sizeof(int));
1632         if (!rc)
1633             return 0;
1634         FcMemFree(FC_MEM_STATICSTR,
1635                   objectcontent_dynamic_alloc * sizeof(int));
1636         FcMemAlloc(FC_MEM_STATICSTR, s * sizeof(int));
1637         objectcontent_dynamic_refcount = rc;
1638     }
1639     if (objectptr_count >= objectptr_alloc)
1640     {
1641         int s = objectptr_alloc + 4;
1642         int * d = realloc (objectptr_indices, s*sizeof(int));
1643         if (!d)
1644             return 0;
1645         FcMemFree(FC_MEM_STATICSTR, objectptr_alloc * sizeof(int));
1646         FcMemAlloc(FC_MEM_STATICSTR, s);
1647         objectptr_indices = d;
1648         objectptr_indices[0] = 0;
1649         objectptr_alloc = s;
1650     }
1651
1652     size = sizeof (struct objectBucket) + sizeof (FcObjectPtr);
1653     b = malloc (size);
1654     if (!b)
1655         return 0;
1656     FcMemAlloc (FC_MEM_STATICSTR, size);
1657     b->next = 0;
1658     b->hash = hash;
1659     nn = malloc(strlen(name)+1);
1660     if (!nn)
1661         goto bail;
1662     strcpy ((char *)nn, name);
1663     objectptr_indices[objectptr_count] = -objectcontent_dynamic_count;
1664     objectcontent_dynamic_refcount[objectcontent_dynamic_count] = 1;
1665     objectcontent_dynamic[objectcontent_dynamic_count++] = nn;
1666     new = objectptr_count++;
1667     *((FcObjectPtr *)(b+1)) = new;
1668     *p = b;
1669     return new;
1670
1671  bail:
1672     free(b);
1673     return 0;
1674 }
1675
1676 void
1677 FcObjectPtrDestroy (FcObjectPtr p)
1678 {
1679     if (objectptr_indices[p] < 0)
1680     {
1681         objectcontent_dynamic_refcount[-objectptr_indices[p]]--;
1682         if (objectcontent_dynamic_refcount[-objectptr_indices[p]] == 0)
1683         {
1684             /* this code doesn't seem to be reached terribly often. */
1685             /* (note that objectcontent_dynamic overapproximates
1686              * the use count, because not every result from
1687              * StaticName is stored. */
1688             FcStrFree((char *)objectcontent_dynamic[-objectptr_indices[p]]);
1689             objectcontent_dynamic[-objectptr_indices[p]] = 0;
1690         }
1691     }
1692 }
1693
1694 const char *
1695 FcObjectPtrU (FcObjectPtr si)
1696 {
1697     if (objectptr_indices[si] > 0)
1698         return &objectcontent_static_buf[objectptr_indices[si]];
1699     else
1700         return objectcontent_dynamic[-objectptr_indices[si]];
1701 }
1702
1703 static FcBool objectptr_first_serialization = FcFalse;
1704 static int * object_old_id_to_new = 0;
1705
1706 static void
1707 FcObjectRebuildStaticNameHashtable (void)
1708 {
1709     int i;
1710     struct objectBucket *b, *bn;
1711
1712     if (buckets)
1713     {
1714         for (i = 0; i < OBJECT_HASH_SIZE; i++)
1715         {
1716             b = buckets[i];
1717             while (b)
1718             {
1719                 bn = b->next;
1720                 free(b);
1721                 FcMemFree (FC_MEM_STATICSTR,
1722                            sizeof (struct objectBucket)+sizeof (FcObjectPtr));
1723                 b = bn;
1724             }
1725         }
1726         free (buckets);
1727     }
1728
1729     buckets = malloc(sizeof (struct objectBucket *)*OBJECT_HASH_SIZE);
1730     memset (buckets, 0, sizeof (struct objectBucket *)*OBJECT_HASH_SIZE);
1731
1732     for (i = 1; i < objectptr_count; i++)
1733     {
1734         if (FcObjectPtrU(i))
1735         {
1736             const char * name = FcObjectPtrU(i);
1737             FcChar32     hash = FcStringHash ((const FcChar8 *) name);
1738             struct objectBucket **p;
1739             int size;
1740
1741             for (p = &buckets[hash % OBJECT_HASH_SIZE]; (b = *p);
1742                  p = &(b->next))
1743                 ;
1744             size = sizeof (struct objectBucket) + sizeof (FcObjectPtr);
1745             b = malloc (size);
1746             if (!b)
1747                 return;
1748             FcMemAlloc (FC_MEM_STATICSTR, size);
1749             b->next = 0;
1750             b->hash = hash;
1751             *((FcObjectPtr *)(b+1)) = i;
1752             *p = b;
1753         }
1754     }
1755 }
1756
1757 /* Hmm.  This will have a terrible effect on the memory size,
1758  * because the mmapped strings now get reallocated on the heap.
1759  * Is it all worth it? (Of course, the Serialization codepath is
1760  * not problematic.) */
1761 static FcBool
1762 FcObjectPtrConvertToStatic(FcBool renumber)
1763 {
1764     int active_count, i, j, longest_string = 0,
1765         new_static_bytes = 1;
1766     char * fixed_length_buf, * new_static_buf, * p;
1767     int * new_indices;
1768
1769     if (renumber)
1770         objectptr_first_serialization = FcFalse;
1771
1772     /* collect statistics */
1773     for (i = 1, active_count = 1; i < objectptr_count; i++)
1774         if (!renumber || object_old_id_to_new[i] == -1)
1775         {
1776             int sl = strlen(FcObjectPtrU(i));
1777             active_count++;
1778             if (sl > longest_string)
1779                 longest_string = sl;
1780             new_static_bytes += sl + 1;
1781         }
1782
1783     /* allocate storage */
1784     fixed_length_buf = malloc
1785         ((longest_string+1) * active_count * sizeof(char));
1786     if (!fixed_length_buf)
1787         goto bail;
1788     new_static_buf = malloc (new_static_bytes * sizeof(char));
1789     if (!new_static_buf)
1790         goto bail1;
1791     new_indices = malloc (active_count * sizeof(int));
1792     if (!new_indices)
1793         goto bail2;
1794
1795     FcMemAlloc (FC_MEM_STATICSTR, new_static_bytes);
1796     FcMemFree (FC_MEM_STATICSTR, objectptr_count * sizeof (int));
1797     FcMemAlloc (FC_MEM_STATICSTR, active_count * sizeof (int));
1798
1799     /* copy strings to temporary buffers */
1800     for (j = 0, i = 1; i < objectptr_count; i++)
1801         if (!renumber || object_old_id_to_new[i] == -1)
1802         {
1803             strcpy (fixed_length_buf+(j*(longest_string+1)), FcObjectPtrU(i));
1804             j++;
1805         }
1806
1807     /* sort the new statics */
1808     qsort (fixed_length_buf, active_count-1, longest_string+1,
1809            (int (*)(const void *, const void *)) FcStrCmp);
1810
1811     /* now we create the new static buffer in sorted order. */
1812     p = new_static_buf+1;
1813     for (i = 0; i < active_count-1; i++)
1814     {
1815         strcpy(p, fixed_length_buf + i * (longest_string+1));
1816         p += strlen(p)+1;
1817     }
1818
1819     /* create translation table by iterating over sorted strings
1820      * and getting their old values */
1821     p = new_static_buf+1;
1822     for (i = 0; i < active_count-1; i++)
1823     {
1824         int n = FcObjectStaticName(fixed_length_buf+i*(longest_string+1));
1825         if (renumber)
1826         {
1827             object_old_id_to_new[n] = i;
1828             new_indices[i] = p-new_static_buf;
1829         }
1830         else
1831             new_indices[n] = p-new_static_buf;
1832         p += strlen(p)+1;
1833     }
1834
1835     free (objectptr_indices);
1836     objectptr_indices = new_indices;
1837     objectptr_count = active_count;
1838     objectptr_alloc = active_count;
1839
1840     /* free old storage */
1841     for (i = 1; i < objectcontent_dynamic_count; i++)
1842     {
1843         if (objectcontent_dynamic[i])
1844         {
1845             FcMemFree (FC_MEM_STATICSTR, strlen(objectcontent_dynamic[i])+1);
1846             free ((char *)objectcontent_dynamic[i]);
1847         }
1848     }
1849     free (objectcontent_dynamic);
1850     free (objectcontent_dynamic_refcount);
1851     FcMemFree (FC_MEM_STATICSTR, objectcontent_dynamic_count*sizeof (int));
1852     objectcontent_dynamic = 0;
1853     objectcontent_dynamic_refcount = 0;
1854     objectcontent_dynamic_count = 1;
1855     objectcontent_dynamic_alloc = 0;
1856     free (objectcontent_static_buf);
1857     FcMemFree (FC_MEM_STATICSTR, objectcontent_static_bytes);
1858     objectcontent_static_buf = new_static_buf;
1859     objectcontent_static_bytes = new_static_bytes;
1860
1861     /* fix up hash table */
1862     FcObjectRebuildStaticNameHashtable();
1863
1864     free (fixed_length_buf);
1865     return FcTrue;
1866
1867  bail2:
1868     free (new_static_buf);
1869  bail1:
1870     free (fixed_length_buf);
1871  bail:
1872     return FcFalse;
1873 }
1874
1875 #define OBJECT_PTR_CONVERSION_TRIGGER 100000
1876
1877 int
1878 FcObjectPtrCompare (const FcObjectPtr a, const FcObjectPtr b)
1879 {
1880     /* This is the dynamic count.  We could also use a static
1881      * count, i.e. the number of slow strings being created.
1882      * I think dyncount gives us a better estimate of inefficiency. -PL */
1883     static int compare_count = OBJECT_PTR_CONVERSION_TRIGGER;
1884
1885     /* count on sortedness for fast objectptrs. */
1886     if ((a == b) || (objectptr_indices[a] > 0 && objectptr_indices[b] > 0))
1887         return objectptr_indices[a] - objectptr_indices[b];
1888
1889     compare_count--;
1890     if (!compare_count)
1891     {
1892         FcObjectPtrConvertToStatic(FcFalse);
1893         compare_count = OBJECT_PTR_CONVERSION_TRIGGER;
1894     }
1895
1896     return strcmp (FcObjectPtrU(a), FcObjectPtrU(b));
1897 }
1898
1899 void
1900 FcObjectClearStatic(void)
1901 {
1902     objectptr_count = 1;
1903     objectptr_alloc = 0;
1904     objectptr_indices = 0;
1905
1906     objectcontent_static_bytes = 0;
1907     objectcontent_static_buf = 0;
1908
1909     objectcontent_dynamic_count = 1;
1910     objectcontent_dynamic_alloc = 0;
1911     objectcontent_dynamic = 0;
1912     objectcontent_dynamic_refcount = 0;
1913
1914     object_old_id_to_new = 0;
1915 }
1916
1917 static FcObjectPtr
1918 FcObjectSerialize (FcObjectPtr si)
1919 {
1920     if (objectptr_first_serialization)
1921         if (!FcObjectPtrConvertToStatic(FcTrue))
1922             return 0;
1923
1924     return object_old_id_to_new[si];
1925 }
1926
1927 /* In the pre-serialization phase, mark the used strings with
1928  * -1 in the mapping array. */
1929 /* The first call to the serialization phase assigns actual
1930  * static indices to the strings (sweep). */
1931 FcBool
1932 FcObjectPrepareSerialize (FcObjectPtr si)
1933 {
1934     if (object_old_id_to_new == 0)
1935     {
1936         object_old_id_to_new = malloc(objectptr_count * sizeof(int));
1937         if (!object_old_id_to_new)
1938             goto bail;
1939         memset (object_old_id_to_new, 0,
1940                 objectptr_count * sizeof(int));
1941     }
1942
1943     object_old_id_to_new[si] = -1;
1944     objectptr_first_serialization = FcTrue;
1945
1946     return FcTrue;
1947
1948  bail:
1949     return FcFalse;
1950 }