src/fcpat.c

   1 /*
   2  * $RCSId: xc/lib/fontconfig/src/fcpat.c,v 1.18 2002/09/18 17:11:46 tsi Exp $
   3  *
   4  * Copyright © 2000 Keith Packard
   5  *
   6  * Permission to use, copy, modify, distribute, and sell this software and its
   7  * documentation for any purpose is hereby granted without fee, provided that
   8  * the above copyright notice appear in all copies and that both that
   9  * copyright notice and this permission notice appear in supporting
  10  * documentation, and that the name of Keith Packard not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  Keith Packard makes no
  13  * representations about the suitability of this software for any purpose.  It
  14  * is provided "as is" without express or implied warranty.
  15  *
  16  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  18  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  19  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  20  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  21  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  22  * PERFORMANCE OF THIS SOFTWARE.
  23  */
  24
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <assert.h>
  28 #include "fcint.h"
  29
  30 FcPattern *
  31 FcPatternCreate (void)
  32 {
  33     FcPattern   *p;
  34
  35     p = (FcPattern *) malloc (sizeof (FcPattern));
  36     if (!p)
  37         return 0;
  38     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern));
  39     p->num = 0;
  40     p->size = 0;
  41     p->elts = 0;
  42     p->ref = 1;
  43     return p;
  44 }
  45
  46 void
  47 FcValueDestroy (FcValue v)
  48 {
  49     switch (v.type) {
  50     case FcTypeString:
  51         FcStrFree ((FcChar8 *) v.u.s);
  52         break;
  53     case FcTypeMatrix:
  54         FcMatrixFree ((FcMatrix *) v.u.m);
  55         break;
  56     case FcTypeCharSet:
  57         FcCharSetDestroy ((FcCharSet *) v.u.c);
  58         break;
  59     case FcTypeLangSet:
  60         FcLangSetDestroy ((FcLangSet *) v.u.l);
  61         break;
  62     default:
  63         break;
  64     }
  65 }
  66
  67 FcValue
  68 FcValueSave (FcValue v)
  69 {
  70     switch (v.type) {
  71     case FcTypeString:
  72         v.u.s = FcStrCopy (v.u.s);
  73         if (!v.u.s)
  74             v.type = FcTypeVoid;
  75         break;
  76     case FcTypeMatrix:
  77         v.u.m = FcMatrixCopy (v.u.m);
  78         if (!v.u.m)
  79             v.type = FcTypeVoid;
  80         break;
  81     case FcTypeCharSet:
  82         v.u.c = FcCharSetCopy ((FcCharSet *) v.u.c);
  83         if (!v.u.c)
  84             v.type = FcTypeVoid;
  85         break;
  86     case FcTypeLangSet:
  87         v.u.l = FcLangSetCopy (v.u.l);
  88         if (!v.u.l)
  89             v.type = FcTypeVoid;
  90         break;
  91     default:
  92         break;
  93     }
  94     return v;
  95 }
  96
  97 void
  98 FcValueListDestroy (FcValueList *l)
  99 {
 100     FcValueList    *next;
 101     for (; l; l = next)
 102     {
 103         switch (l->value.type) {
 104         case FcTypeString:
 105             FcStrFree ((FcChar8 *) l->value.u.s);
 106             break;
 107         case FcTypeMatrix:
 108             FcMatrixFree ((FcMatrix *) l->value.u.m);
 109             break;
 110         case FcTypeCharSet:
 111             FcCharSetDestroy ((FcCharSet *) l->value.u.c);
 112             break;
 113         case FcTypeLangSet:
 114             FcLangSetDestroy ((FcLangSet *) l->value.u.l);
 115             break;
 116         default:
 117             break;
 118         }
 119         next = l->next;
 120         FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 121         free (l);
 122     }
 123 }
 124
 125 FcBool
 126 FcValueEqual (FcValue va, FcValue vb)
 127 {
 128     if (va.type != vb.type)
 129     {
 130         if (va.type == FcTypeInteger)
 131         {
 132             va.type = FcTypeDouble;
 133             va.u.d = va.u.i;
 134         }
 135         if (vb.type == FcTypeInteger)
 136         {
 137             vb.type = FcTypeDouble;
 138             vb.u.d = vb.u.i;
 139         }
 140         if (va.type != vb.type)
 141             return FcFalse;
 142     }
 143     switch (va.type) {
 144     case FcTypeVoid:
 145         return FcTrue;
 146     case FcTypeInteger:
 147         return va.u.i == vb.u.i;
 148     case FcTypeDouble:
 149         return va.u.d == vb.u.d;
 150     case FcTypeString:
 151         return FcStrCmpIgnoreCase (va.u.s, vb.u.s) == 0;
 152     case FcTypeBool:
 153         return va.u.b == vb.u.b;
 154     case FcTypeMatrix:
 155         return FcMatrixEqual (va.u.m, vb.u.m);
 156     case FcTypeCharSet:
 157         return FcCharSetEqual (va.u.c, vb.u.c);
 158     case FcTypeFTFace:
 159         return va.u.f == vb.u.f;
 160     case FcTypeLangSet:
 161         return FcLangSetEqual (va.u.l, vb.u.l);
 162     }
 163     return FcFalse;
 164 }
 165
 166 static FcChar32
 167 FcDoubleHash (double d)
 168 {
 169     if (d < 0)
 170         d = -d;
 171     if (d > 0xffffffff)
 172         d = 0xffffffff;
 173     return (FcChar32) d;
 174 }
 175
 176 static FcChar32
 177 FcStringHash (const FcChar8 *s)
 178 {
 179     FcChar8     c;
 180     FcChar32    h = 0;
 181
 182     if (s)
 183         while ((c = *s++))
 184             h = ((h << 1) | (h >> 31)) ^ c;
 185     return h;
 186 }
 187
 188 static FcChar32
 189 FcValueHash (FcValue v)
 190 {
 191     switch (v.type) {
 192     case FcTypeVoid:
 193         return 0;
 194     case FcTypeInteger:
 195         return (FcChar32) v.u.i;
 196     case FcTypeDouble:
 197         return FcDoubleHash (v.u.d);
 198     case FcTypeString:
 199         return FcStringHash (v.u.s);
 200     case FcTypeBool:
 201         return (FcChar32) v.u.b;
 202     case FcTypeMatrix:
 203         return (FcDoubleHash (v.u.m->xx) ^
 204                 FcDoubleHash (v.u.m->xy) ^
 205                 FcDoubleHash (v.u.m->yx) ^
 206                 FcDoubleHash (v.u.m->yy));
 207     case FcTypeCharSet:
 208         return (FcChar32) v.u.c->num;
 209     case FcTypeFTFace:
 210         return FcStringHash ((const FcChar8 *) ((FT_Face) v.u.f)->family_name) ^
 211                FcStringHash ((const FcChar8 *) ((FT_Face) v.u.f)->style_name);
 212     case FcTypeLangSet:
 213         return FcLangSetHash (v.u.l);
 214     }
 215     return FcFalse;
 216 }
 217
 218 static FcBool
 219 FcValueListEqual (FcValueList *la, FcValueList *lb)
 220 {
 221     if (la == lb)
 222         return FcTrue;
 223
 224     while (la && lb)
 225     {
 226         if (!FcValueEqual (la->value, lb->value))
 227             return FcFalse;
 228         la = la->next;
 229         lb = lb->next;
 230     }
 231     if (la || lb)
 232         return FcFalse;
 233     return FcTrue;
 234 }
 235
 236 static FcChar32
 237 FcValueListHash (FcValueList *l)
 238 {
 239     FcChar32    hash = 0;
 240
 241     while (l)
 242     {
 243         hash = ((hash << 1) | (hash >> 31)) ^ FcValueHash (l->value);
 244         l = l->next;
 245     }
 246     return hash;
 247 }
 248
 249 void
 250 FcPatternDestroy (FcPattern *p)
 251 {
 252     int             i;
 253
 254     if (p->ref == FC_REF_CONSTANT || --p->ref > 0)
 255         return;
 256
 257     for (i = 0; i < p->num; i++)
 258         FcValueListDestroy (p->elts[i].values);
 259
 260     p->num = 0;
 261     if (p->elts)
 262     {
 263         FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
 264         free (p->elts);
 265         p->elts = 0;
 266     }
 267     p->size = 0;
 268     FcMemFree (FC_MEM_PATTERN, sizeof (FcPattern));
 269     free (p);
 270 }
 271
 272 #define FC_VALUE_LIST_HASH_SIZE     257
 273 #define FC_PATTERN_HASH_SIZE        67
 274
 275 typedef struct _FcValueListEnt FcValueListEnt;
 276
 277 struct _FcValueListEnt {
 278     FcValueListEnt  *next;
 279     FcValueList     *list;
 280     FcChar32        hash, pad;
 281 };
 282
 283 typedef union _FcValueListAlign {
 284     FcValueListEnt  ent;
 285     FcValueList     list;
 286 } FcValueListAlign;
 287
 288 static int          FcValueListFrozenCount[FcTypeLangSet + 1];
 289 static int          FcValueListFrozenBytes[FcTypeLangSet + 1];
 290 static char         *FcValueListFrozenName[] = {
 291     "Void",
 292     "Integer",
 293     "Double",
 294     "String",
 295     "Bool",
 296     "Matrix",
 297     "CharSet",
 298     "FTFace",
 299     "LangSet"
 300 };
 301
 302 void
 303 FcValueListReport (void);
 304
 305 void
 306 FcValueListReport (void)
 307 {
 308     FcType  t;
 309
 310     printf ("Fc Frozen Values:\n");
 311     printf ("\t%8s %9s %9s\n", "Type", "Count", "Bytes");
 312     for (t = FcTypeVoid; t <= FcTypeLangSet; t++)
 313         printf ("\t%8s %9d %9d\n", FcValueListFrozenName[t],
 314                 FcValueListFrozenCount[t], FcValueListFrozenBytes[t]);
 315 }
 316
 317 static FcValueListEnt *
 318 FcValueListEntCreate (FcValueList *h)
 319 {
 320     FcValueListAlign    *ea;
 321     FcValueListEnt  *e;
 322     FcValueList     *l, *new;
 323     int             n;
 324     int             size;
 325
 326     n = 0;
 327     for (l = h; l; l = l->next)
 328         n++;
 329     size = sizeof (FcValueListAlign) + n * sizeof (FcValueList);
 330     FcValueListFrozenCount[h->value.type]++;
 331     FcValueListFrozenBytes[h->value.type] += size;
 332     ea = malloc (size);
 333     if (!ea)
 334         return 0;
 335     FcMemAlloc (FC_MEM_VALLIST, size);
 336     e = &ea->ent;
 337     e->list = (FcValueList *) (ea + 1);
 338     new = e->list;
 339     for (l = h; l; l = l->next, new++)
 340     {
 341         if (l->value.type == FcTypeString)
 342         {
 343             new->value.type = FcTypeString;
 344             new->value.u.s = FcObjectStaticName (l->value.u.s);
 345         }
 346         else
 347         {
 348             new->value = FcValueSave (l->value);
 349         }
 350         new->binding = l->binding;
 351         if (l->next)
 352             new->next = new + 1;
 353         else
 354             new->next = 0;
 355     }
 356     return e;
 357 }
 358
 359 static void
 360 FcValueListEntDestroy (FcValueListEnt *e)
 361 {
 362     FcValueList *l;
 363
 364     FcValueListFrozenCount[e->list->value.type]--;
 365
 366     /* XXX: We should perform these two operations with "size" as
 367        computed in FcValueListEntCreate, but we don't have access to
 368        that value here. Without this, the FcValueListFrozenBytes
 369        values will be wrong as will the FcMemFree counts.
 370
 371        FcValueListFrozenBytes[e->list->value.type] -= size;
 372        FcMemFree (FC_MEM_VALLIST, size);
 373     */
 374
 375     for (l = e->list; l; l = l->next)
 376     {
 377         if (l->value.type != FcTypeString)
 378             FcValueDestroy (l->value);
 379     }
 380     /* XXX: Are we being too chummy with the implementation here to
 381        free(e) when it was actually the enclosing FcValueListAlign
 382        that was allocated? */
 383     free (e);
 384 }
 385
 386 static int      FcValueListTotal;
 387 static int      FcValueListUsed;
 388
 389 static FcValueListEnt   *FcValueListHashTable[FC_VALUE_LIST_HASH_SIZE];
 390
 391 static FcValueList *
 392 FcValueListFreeze (FcValueList *l)
 393 {
 394     FcChar32                hash = FcValueListHash (l);
 395     FcValueListEnt          **bucket = &FcValueListHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
 396     FcValueListEnt          *ent;
 397
 398     FcValueListTotal++;
 399     for (ent = *bucket; ent; ent = ent->next)
 400     {
 401         if (ent->hash == hash && FcValueListEqual (ent->list, l))
 402             return ent->list;
 403     }
 404
 405     ent = FcValueListEntCreate (l);
 406     if (!ent)
 407         return 0;
 408
 409     FcValueListUsed++;
 410     ent->hash = hash;
 411     ent->next = *bucket;
 412     *bucket = ent;
 413     return ent->list;
 414 }
 415
 416 static void
 417 FcValueListThawAll (void)
 418 {
 419     int i;
 420     FcValueListEnt      *ent, *next;
 421
 422     for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
 423     {
 424         for (ent = FcValueListHashTable[i]; ent; ent = next)
 425         {
 426             next = ent->next;
 427             FcValueListEntDestroy (ent);
 428         }
 429         FcValueListHashTable[i] = 0;
 430     }
 431
 432     FcValueListTotal = 0;
 433     FcValueListUsed = 0;
 434 }
 435
 436 static FcChar32
 437 FcPatternBaseHash (FcPattern *b)
 438 {
 439     FcChar32    hash = b->num;
 440     int         i;
 441
 442     for (i = 0; i < b->num; i++)
 443         hash = ((hash << 1) | (hash >> 31)) ^ ((long) b->elts[i].values);
 444     return hash;
 445 }
 446
 447 typedef struct _FcPatternEnt FcPatternEnt;
 448
 449 struct _FcPatternEnt {
 450     FcPatternEnt    *next;
 451     FcChar32        hash;
 452     FcPattern       pattern;
 453 };
 454
 455 static int      FcPatternTotal;
 456 static int      FcPatternUsed;
 457
 458 static FcPatternEnt     *FcPatternHashTable[FC_VALUE_LIST_HASH_SIZE];
 459
 460 static FcPattern *
 461 FcPatternBaseFreeze (FcPattern *b)
 462 {
 463     FcChar32            hash = FcPatternBaseHash (b);
 464     FcPatternEnt        **bucket = &FcPatternHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
 465     FcPatternEnt        *ent;
 466     int                 i;
 467     int                 size;
 468
 469     FcPatternTotal++;
 470     for (ent = *bucket; ent; ent = ent->next)
 471     {
 472         if (ent->hash == hash && b->num == ent->pattern.num)
 473         {
 474             for (i = 0; i < b->num; i++)
 475             {
 476                 if (b->elts[i].object != ent->pattern.elts[i].object)
 477                     break;
 478                 if (b->elts[i].values != ent->pattern.elts[i].values)
 479                     break;
 480             }
 481             if (i == b->num)
 482                 return &ent->pattern;
 483         }
 484     }
 485
 486     /*
 487      * Compute size of pattern + elts
 488      */
 489     size = sizeof (FcPatternEnt) + b->num*sizeof (FcPatternElt);
 490     ent = malloc (size);
 491     if (!ent)
 492         return 0;
 493
 494     FcMemAlloc (FC_MEM_PATTERN, size);
 495     FcPatternUsed++;
 496
 497     ent->pattern.elts = (FcPatternElt *) (ent + 1);
 498     ent->pattern.num = b->num;
 499     ent->pattern.size = b->num;
 500     ent->pattern.ref = FC_REF_CONSTANT;
 501
 502     for (i = 0; i < b->num; i++)
 503     {
 504         ent->pattern.elts[i].values = b->elts[i].values;
 505         ent->pattern.elts[i].object = b->elts[i].object;
 506     }
 507
 508     ent->hash = hash;
 509     ent->next = *bucket;
 510     *bucket = ent;
 511     return &ent->pattern;
 512 }
 513
 514 static void
 515 FcPatternBaseThawAll (void)
 516 {
 517     int i;
 518     FcPatternEnt        *ent, *next;
 519
 520     for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
 521     {
 522         for (ent = FcPatternHashTable[i]; ent; ent = next)
 523         {
 524             next = ent->next;
 525             free (ent);
 526         }
 527         FcPatternHashTable[i] = 0;
 528     }
 529
 530     FcPatternTotal = 0;
 531     FcPatternUsed = 0;
 532 }
 533
 534 FcPattern *
 535 FcPatternFreeze (FcPattern *p)
 536 {
 537     FcPattern   *b, *n = 0;
 538     int         size;
 539     int         i;
 540
 541     size = sizeof (FcPattern) + p->num * sizeof (FcPatternElt);
 542     b = (FcPattern *) malloc (size);
 543     if (!b)
 544         return 0;
 545     FcMemAlloc (FC_MEM_PATTERN, size);
 546     b->num = p->num;
 547     b->size = b->num;
 548     b->ref = 1;
 549     b->elts = (FcPatternElt *) (b + 1);
 550     /*
 551      * Freeze object lists
 552      */
 553     for (i = 0; i < p->num; i++)
 554     {
 555         b->elts[i].object = p->elts[i].object;
 556         b->elts[i].values = FcValueListFreeze (p->elts[i].values);
 557         if (!b->elts[i].values)
 558             goto bail;
 559     }
 560     /*
 561      * Freeze base
 562      */
 563     n = FcPatternBaseFreeze (b);
 564 #ifdef CHATTY
 565     if (FcDebug() & FC_DBG_MEMORY)
 566     {
 567         printf ("ValueLists: total %9d used %9d\n", FcValueListTotal, FcValueListUsed);
 568         printf ("Patterns:   total %9d used %9d\n", FcPatternTotal, FcPatternUsed);
 569     }
 570 #endif
 571 bail:
 572     free (b);
 573 #ifdef DEBUG
 574     assert (FcPatternEqual (n, p));
 575 #endif
 576     return n;
 577 }
 578
 579 void
 580 FcPatternThawAll (void)
 581 {
 582     FcPatternBaseThawAll ();
 583     FcValueListThawAll ();
 584 }
 585
 586 static int
 587 FcPatternPosition (const FcPattern *p, const char *object)
 588 {
 589     int     low, high, mid, c;
 590
 591     low = 0;
 592     high = p->num - 1;
 593     c = 1;
 594     mid = 0;
 595     while (low <= high)
 596     {
 597         mid = (low + high) >> 1;
 598         c = strcmp (p->elts[mid].object, object);
 599         if (c == 0)
 600             return mid;
 601         if (c < 0)
 602             low = mid + 1;
 603         else
 604             high = mid - 1;
 605     }
 606     if (c < 0)
 607         mid++;
 608     return -(mid + 1);
 609 }
 610
 611 FcPatternElt *
 612 FcPatternFindElt (const FcPattern *p, const char *object)
 613 {
 614     int     i = FcPatternPosition (p, object);
 615     if (i < 0)
 616         return 0;
 617     return &p->elts[i];
 618 }
 619
 620 FcPatternElt *
 621 FcPatternInsertElt (FcPattern *p, const char *object)
 622 {
 623     int             i;
 624     FcPatternElt   *e;
 625
 626     i = FcPatternPosition (p, object);
 627     if (i < 0)
 628     {
 629         i = -i - 1;
 630
 631         /* grow array */
 632         if (p->num + 1 >= p->size)
 633         {
 634             int s = p->size + 16;
 635             if (p->elts)
 636                 e = (FcPatternElt *) realloc (p->elts, s * sizeof (FcPatternElt));
 637             else
 638                 e = (FcPatternElt *) malloc (s * sizeof (FcPatternElt));
 639             if (!e)
 640                 return FcFalse;
 641             p->elts = e;
 642             if (p->size)
 643                 FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
 644             FcMemAlloc (FC_MEM_PATELT, s * sizeof (FcPatternElt));
 645             while (p->size < s)
 646             {
 647                 p->elts[p->size].object = 0;
 648                 p->elts[p->size].values = 0;
 649                 p->size++;
 650             }
 651         }
 652
 653         /* move elts up */
 654         memmove (p->elts + i + 1,
 655                  p->elts + i,
 656                  sizeof (FcPatternElt) *
 657                  (p->num - i));
 658
 659         /* bump count */
 660         p->num++;
 661
 662         p->elts[i].object = FcObjectStaticName (object);
 663         p->elts[i].values = 0;
 664     }
 665
 666     return &p->elts[i];
 667 }
 668
 669 FcBool
 670 FcPatternEqual (const FcPattern *pa, const FcPattern *pb)
 671 {
 672     int i;
 673
 674     if (pa == pb)
 675         return FcTrue;
 676
 677     if (pa->num != pb->num)
 678         return FcFalse;
 679     for (i = 0; i < pa->num; i++)
 680     {
 681         if (pa->elts[i].object != pb->elts[i].object)
 682             return FcFalse;
 683         if (!FcValueListEqual (pa->elts[i].values, pb->elts[i].values))
 684             return FcFalse;
 685     }
 686     return FcTrue;
 687 }
 688
 689 FcChar32
 690 FcPatternHash (const FcPattern *p)
 691 {
 692     int         i;
 693     FcChar32    h = 0;
 694
 695     for (i = 0; i < p->num; i++)
 696     {
 697         h = (((h << 1) | (h >> 31)) ^
 698              FcStringHash ((const FcChar8 *) p->elts[i].object) ^
 699              FcValueListHash (p->elts[i].values));
 700     }
 701     return h;
 702 }
 703
 704 FcBool
 705 FcPatternEqualSubset (const FcPattern *pa, const FcPattern *pb, const FcObjectSet *os)
 706 {
 707     FcPatternElt    *ea, *eb;
 708     int             i;
 709
 710     for (i = 0; i < os->nobject; i++)
 711     {
 712         ea = FcPatternFindElt (pa, os->objects[i]);
 713         eb = FcPatternFindElt (pb, os->objects[i]);
 714         if (ea)
 715         {
 716             if (!eb)
 717                 return FcFalse;
 718             if (!FcValueListEqual (ea->values, eb->values))
 719                 return FcFalse;
 720         }
 721         else
 722         {
 723             if (eb)
 724                 return FcFalse;
 725         }
 726     }
 727     return FcTrue;
 728 }
 729
 730 FcBool
 731 FcPatternAddWithBinding  (FcPattern         *p,
 732                           const char        *object,
 733                           FcValue           value,
 734                           FcValueBinding    binding,
 735                           FcBool            append)
 736 {
 737     FcPatternElt   *e;
 738     FcValueList    *new, **prev;
 739
 740     if (p->ref == FC_REF_CONSTANT)
 741         goto bail0;
 742
 743     new = (FcValueList *) malloc (sizeof (FcValueList));
 744     if (!new)
 745         goto bail0;
 746
 747     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList));
 748     /* dup string */
 749     value = FcValueSave (value);
 750     if (value.type == FcTypeVoid)
 751         goto bail1;
 752
 753     new->value = value;
 754     new->binding = binding;
 755     new->next = 0;
 756
 757     e = FcPatternInsertElt (p, object);
 758     if (!e)
 759         goto bail2;
 760
 761     if (append)
 762     {
 763         for (prev = &e->values; *prev; prev = &(*prev)->next);
 764         *prev = new;
 765     }
 766     else
 767     {
 768         new->next = e->values;
 769         e->values = new;
 770     }
 771
 772     return FcTrue;
 773
 774 bail2:
 775     switch (value.type) {
 776     case FcTypeString:
 777         FcStrFree ((FcChar8 *) value.u.s);
 778         break;
 779     case FcTypeMatrix:
 780         FcMatrixFree ((FcMatrix *) value.u.m);
 781         break;
 782     case FcTypeCharSet:
 783         FcCharSetDestroy ((FcCharSet *) value.u.c);
 784         break;
 785     case FcTypeLangSet:
 786         FcLangSetDestroy ((FcLangSet *) value.u.l);
 787         break;
 788     default:
 789         break;
 790     }
 791 bail1:
 792     FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 793     free (new);
 794 bail0:
 795     return FcFalse;
 796 }
 797
 798 FcBool
 799 FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
 800 {
 801     return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
 802 }
 803
 804 FcBool
 805 FcPatternAddWeak  (FcPattern *p, const char *object, FcValue value, FcBool append)
 806 {
 807     return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
 808 }
 809
 810 FcBool
 811 FcPatternDel (FcPattern *p, const char *object)
 812 {
 813     FcPatternElt   *e;
 814     int             i;
 815
 816     e = FcPatternFindElt (p, object);
 817     if (!e)
 818         return FcFalse;
 819
 820     i = e - p->elts;
 821
 822     /* destroy value */
 823     FcValueListDestroy (e->values);
 824
 825     /* shuffle existing ones down */
 826     memmove (e, e+1, (p->elts + p->num - (e + 1)) * sizeof (FcPatternElt));
 827     p->num--;
 828     p->elts[p->num].object = 0;
 829     p->elts[p->num].values = 0;
 830     return FcTrue;
 831 }
 832
 833 FcBool
 834 FcPatternRemove (FcPattern *p, const char *object, int id)
 835 {
 836     FcPatternElt   *e;
 837     FcValueList    **prev, *l;
 838
 839     e = FcPatternFindElt (p, object);
 840     if (!e)
 841         return FcFalse;
 842     for (prev = &e->values; (l = *prev); prev = &l->next)
 843     {
 844         if (!id)
 845         {
 846             *prev = l->next;
 847             l->next = 0;
 848             FcValueListDestroy (l);
 849             if (!e->values)
 850                 FcPatternDel (p, object);
 851             return FcTrue;
 852         }
 853         id--;
 854     }
 855     return FcFalse;
 856 }
 857
 858 FcBool
 859 FcPatternAddInteger (FcPattern *p, const char *object, int i)
 860 {
 861     FcValue     v;
 862
 863     v.type = FcTypeInteger;
 864     v.u.i = i;
 865     return FcPatternAdd (p, object, v, FcTrue);
 866 }
 867
 868 FcBool
 869 FcPatternAddDouble (FcPattern *p, const char *object, double d)
 870 {
 871     FcValue     v;
 872
 873     v.type = FcTypeDouble;
 874     v.u.d = d;
 875     return FcPatternAdd (p, object, v, FcTrue);
 876 }
 877
 878
 879 FcBool
 880 FcPatternAddString (FcPattern *p, const char *object, const FcChar8 *s)
 881 {
 882     FcValue     v;
 883
 884     v.type = FcTypeString;
 885     v.u.s = s;
 886     return FcPatternAdd (p, object, v, FcTrue);
 887 }
 888
 889 FcBool
 890 FcPatternAddMatrix (FcPattern *p, const char *object, const FcMatrix *s)
 891 {
 892     FcValue     v;
 893
 894     v.type = FcTypeMatrix;
 895     v.u.m = (FcMatrix *) s;
 896     return FcPatternAdd (p, object, v, FcTrue);
 897 }
 898
 899
 900 FcBool
 901 FcPatternAddBool (FcPattern *p, const char *object, FcBool b)
 902 {
 903     FcValue     v;
 904
 905     v.type = FcTypeBool;
 906     v.u.b = b;
 907     return FcPatternAdd (p, object, v, FcTrue);
 908 }
 909
 910 FcBool
 911 FcPatternAddCharSet (FcPattern *p, const char *object, const FcCharSet *c)
 912 {
 913     FcValue     v;
 914
 915     v.type = FcTypeCharSet;
 916     v.u.c = (FcCharSet *) c;
 917     return FcPatternAdd (p, object, v, FcTrue);
 918 }
 919
 920 FcBool
 921 FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
 922 {
 923     FcValue     v;
 924
 925     v.type = FcTypeFTFace;
 926     v.u.f = (void *) f;
 927     return FcPatternAdd (p, object, v, FcTrue);
 928 }
 929
 930 FcBool
 931 FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
 932 {
 933     FcValue     v;
 934
 935     v.type = FcTypeLangSet;
 936     v.u.l = (FcLangSet *) ls;
 937     return FcPatternAdd (p, object, v, FcTrue);
 938 }
 939
 940 FcResult
 941 FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
 942 {
 943     FcPatternElt   *e;
 944     FcValueList    *l;
 945
 946     e = FcPatternFindElt (p, object);
 947     if (!e)
 948         return FcResultNoMatch;
 949     for (l = e->values; l; l = l->next)
 950     {
 951         if (!id)
 952         {
 953             *v = l->value;
 954             return FcResultMatch;
 955         }
 956         id--;
 957     }
 958     return FcResultNoId;
 959 }
 960
 961 FcResult
 962 FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
 963 {
 964     FcValue     v;
 965     FcResult    r;
 966
 967     r = FcPatternGet (p, object, id, &v);
 968     if (r != FcResultMatch)
 969         return r;
 970     switch (v.type) {
 971     case FcTypeDouble:
 972         *i = (int) v.u.d;
 973         break;
 974     case FcTypeInteger:
 975         *i = v.u.i;
 976         break;
 977     default:
 978         return FcResultTypeMismatch;
 979     }
 980     return FcResultMatch;
 981 }
 982
 983 FcResult
 984 FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
 985 {
 986     FcValue     v;
 987     FcResult    r;
 988
 989     r = FcPatternGet (p, object, id, &v);
 990     if (r != FcResultMatch)
 991         return r;
 992     switch (v.type) {
 993     case FcTypeDouble:
 994         *d = v.u.d;
 995         break;
 996     case FcTypeInteger:
 997         *d = (double) v.u.i;
 998         break;
 999     default:
1000         return FcResultTypeMismatch;
1001     }
1002     return FcResultMatch;
1003 }
1004
1005 FcResult
1006 FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
1007 {
1008     FcValue     v;
1009     FcResult    r;
1010
1011     r = FcPatternGet (p, object, id, &v);
1012     if (r != FcResultMatch)
1013         return r;
1014     if (v.type != FcTypeString)
1015         return FcResultTypeMismatch;
1016     *s = (FcChar8 *) v.u.s;
1017     return FcResultMatch;
1018 }
1019
1020 FcResult
1021 FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
1022 {
1023     FcValue     v;
1024     FcResult    r;
1025
1026     r = FcPatternGet (p, object, id, &v);
1027     if (r != FcResultMatch)
1028         return r;
1029     if (v.type != FcTypeMatrix)
1030         return FcResultTypeMismatch;
1031     *m = (FcMatrix *) v.u.m;
1032     return FcResultMatch;
1033 }
1034
1035
1036 FcResult
1037 FcPatternGetBool(const FcPattern *p, const char *object, int id, FcBool *b)
1038 {
1039     FcValue     v;
1040     FcResult    r;
1041
1042     r = FcPatternGet (p, object, id, &v);
1043     if (r != FcResultMatch)
1044         return r;
1045     if (v.type != FcTypeBool)
1046         return FcResultTypeMismatch;
1047     *b = v.u.b;
1048     return FcResultMatch;
1049 }
1050
1051 FcResult
1052 FcPatternGetCharSet(const FcPattern *p, const char *object, int id, FcCharSet **c)
1053 {
1054     FcValue     v;
1055     FcResult    r;
1056
1057     r = FcPatternGet (p, object, id, &v);
1058     if (r != FcResultMatch)
1059         return r;
1060     if (v.type != FcTypeCharSet)
1061         return FcResultTypeMismatch;
1062     *c = (FcCharSet *) v.u.c;
1063     return FcResultMatch;
1064 }
1065
1066 FcResult
1067 FcPatternGetFTFace(const FcPattern *p, const char *object, int id, FT_Face *f)
1068 {
1069     FcValue     v;
1070     FcResult    r;
1071
1072     r = FcPatternGet (p, object, id, &v);
1073     if (r != FcResultMatch)
1074         return r;
1075     if (v.type != FcTypeFTFace)
1076         return FcResultTypeMismatch;
1077     *f = (FT_Face) v.u.f;
1078     return FcResultMatch;
1079 }
1080
1081 FcResult
1082 FcPatternGetLangSet(const FcPattern *p, const char *object, int id, FcLangSet **ls)
1083 {
1084     FcValue     v;
1085     FcResult    r;
1086
1087     r = FcPatternGet (p, object, id, &v);
1088     if (r != FcResultMatch)
1089         return r;
1090     if (v.type != FcTypeLangSet)
1091         return FcResultTypeMismatch;
1092     *ls = (FcLangSet *) v.u.l;
1093     return FcResultMatch;
1094 }
1095
1096 FcPattern *
1097 FcPatternDuplicate (const FcPattern *orig)
1098 {
1099     FcPattern       *new;
1100     int             i;
1101     FcValueList    *l;
1102
1103     new = FcPatternCreate ();
1104     if (!new)
1105         goto bail0;
1106
1107     for (i = 0; i < orig->num; i++)
1108     {
1109         for (l = orig->elts[i].values; l; l = l->next)
1110             if (!FcPatternAdd (new, orig->elts[i].object, l->value, FcTrue))
1111                 goto bail1;
1112     }
1113
1114     return new;
1115
1116 bail1:
1117     FcPatternDestroy (new);
1118 bail0:
1119     return 0;
1120 }
1121
1122 void
1123 FcPatternReference (FcPattern *p)
1124 {
1125     if (p->ref != FC_REF_CONSTANT)
1126         p->ref++;
1127 }
1128
1129 FcPattern *
1130 FcPatternVaBuild (FcPattern *orig, va_list va)
1131 {
1132     FcPattern   *ret;
1133
1134     FcPatternVapBuild (ret, orig, va);
1135     return ret;
1136 }
1137
1138 FcPattern *
1139 FcPatternBuild (FcPattern *orig, ...)
1140 {
1141     va_list     va;
1142
1143     va_start (va, orig);
1144     FcPatternVapBuild (orig, orig, va);
1145     va_end (va);
1146     return orig;
1147 }
1148
1149 /*
1150  * Add all of the elements in 's' to 'p'
1151  */
1152 FcBool
1153 FcPatternAppend (FcPattern *p, FcPattern *s)
1154 {
1155     int             i;
1156     FcPatternElt    *e;
1157     FcValueList     *v;
1158
1159     for (i = 0; i < s->num; i++)
1160     {
1161         e = &s->elts[i];
1162         for (v = e->values; v; v = v->next)
1163         {
1164             if (!FcPatternAddWithBinding (p, e->object,
1165                                           v->value, v->binding, FcTrue))
1166                 return FcFalse;
1167         }
1168     }
1169     return FcTrue;
1170 }
1171
1172 const char *
1173 FcObjectStaticName (const char *name)
1174 {
1175 #define OBJECT_HASH_SIZE    31
1176     static struct objectBucket {
1177         struct objectBucket     *next;
1178         FcChar32                hash;
1179     } *buckets[OBJECT_HASH_SIZE];
1180     FcChar32            hash = FcStringHash ((const FcChar8 *) name);
1181     struct objectBucket **p;
1182     struct objectBucket *b;
1183     int                 size;
1184
1185     for (p = &buckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1186         if (b->hash == hash && !strcmp (name, (char *) (b + 1)))
1187             return (char *) (b + 1);
1188     size = sizeof (struct objectBucket) + strlen (name) + 1;
1189     b = malloc (size);
1190     FcMemAlloc (FC_MEM_STATICSTR, size);
1191     if (!b)
1192         return NULL;
1193     b->next = 0;
1194     b->hash = hash;
1195     strcpy ((char *) (b + 1), name);
1196     *p = b;
1197     return (char *) (b + 1);
1198 }