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     if (p->ref == FC_REF_CONSTANT)
 542        return p;
 543
 544     size = sizeof (FcPattern) + p->num * sizeof (FcPatternElt);
 545     b = (FcPattern *) malloc (size);
 546     if (!b)
 547         return 0;
 548     FcMemAlloc (FC_MEM_PATTERN, size);
 549     b->num = p->num;
 550     b->size = b->num;
 551     b->ref = 1;
 552     b->elts = (FcPatternElt *) (b + 1);
 553     /*
 554      * Freeze object lists
 555      */
 556     for (i = 0; i < p->num; i++)
 557     {
 558         b->elts[i].object = p->elts[i].object;
 559         b->elts[i].values = FcValueListFreeze (p->elts[i].values);
 560         if (!b->elts[i].values)
 561             goto bail;
 562     }
 563     /*
 564      * Freeze base
 565      */
 566     n = FcPatternBaseFreeze (b);
 567 #ifdef CHATTY
 568     if (FcDebug() & FC_DBG_MEMORY)
 569     {
 570         printf ("ValueLists: total %9d used %9d\n", FcValueListTotal, FcValueListUsed);
 571         printf ("Patterns:   total %9d used %9d\n", FcPatternTotal, FcPatternUsed);
 572     }
 573 #endif
 574 bail:
 575     free (b);
 576 #ifdef DEBUG
 577     assert (FcPatternEqual (n, p));
 578 #endif
 579     return n;
 580 }
 581
 582 void
 583 FcPatternThawAll (void)
 584 {
 585     FcPatternBaseThawAll ();
 586     FcValueListThawAll ();
 587 }
 588
 589 static int
 590 FcPatternPosition (const FcPattern *p, const char *object)
 591 {
 592     int     low, high, mid, c;
 593
 594     object = FcObjectStaticName(object);
 595     low = 0;
 596     high = p->num - 1;
 597     c = 1;
 598     mid = 0;
 599     while (low <= high)
 600     {
 601         mid = (low + high) >> 1;
 602         c = p->elts[mid].object - object;
 603         if (c == 0)
 604             return mid;
 605         if (c < 0)
 606             low = mid + 1;
 607         else
 608             high = mid - 1;
 609     }
 610     if (c < 0)
 611         mid++;
 612     return -(mid + 1);
 613 }
 614
 615 FcPatternElt *
 616 FcPatternFindElt (const FcPattern *p, const char *object)
 617 {
 618     int     i = FcPatternPosition (p, object);
 619     if (i < 0)
 620         return 0;
 621     return &p->elts[i];
 622 }
 623
 624 FcPatternElt *
 625 FcPatternInsertElt (FcPattern *p, const char *object)
 626 {
 627     int             i;
 628     FcPatternElt   *e;
 629
 630     i = FcPatternPosition (p, object);
 631     if (i < 0)
 632     {
 633         i = -i - 1;
 634
 635         /* grow array */
 636         if (p->num + 1 >= p->size)
 637         {
 638             int s = p->size + 16;
 639             if (p->elts)
 640                 e = (FcPatternElt *) realloc (p->elts, s * sizeof (FcPatternElt));
 641             else
 642                 e = (FcPatternElt *) malloc (s * sizeof (FcPatternElt));
 643             if (!e)
 644                 return FcFalse;
 645             p->elts = e;
 646             if (p->size)
 647                 FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
 648             FcMemAlloc (FC_MEM_PATELT, s * sizeof (FcPatternElt));
 649             while (p->size < s)
 650             {
 651                 p->elts[p->size].object = 0;
 652                 p->elts[p->size].values = 0;
 653                 p->size++;
 654             }
 655         }
 656
 657         /* move elts up */
 658         memmove (p->elts + i + 1,
 659                  p->elts + i,
 660                  sizeof (FcPatternElt) *
 661                  (p->num - i));
 662
 663         /* bump count */
 664         p->num++;
 665
 666         p->elts[i].object = FcObjectStaticName (object);
 667         p->elts[i].values = 0;
 668     }
 669
 670     return &p->elts[i];
 671 }
 672
 673 FcBool
 674 FcPatternEqual (const FcPattern *pa, const FcPattern *pb)
 675 {
 676     int i;
 677
 678     if (pa == pb)
 679         return FcTrue;
 680
 681     if (pa->num != pb->num)
 682         return FcFalse;
 683     for (i = 0; i < pa->num; i++)
 684     {
 685         if (pa->elts[i].object != pb->elts[i].object)
 686             return FcFalse;
 687         if (!FcValueListEqual (pa->elts[i].values, pb->elts[i].values))
 688             return FcFalse;
 689     }
 690     return FcTrue;
 691 }
 692
 693 FcChar32
 694 FcPatternHash (const FcPattern *p)
 695 {
 696     int         i;
 697     FcChar32    h = 0;
 698
 699     for (i = 0; i < p->num; i++)
 700     {
 701         h = (((h << 1) | (h >> 31)) ^
 702              FcStringHash ((const FcChar8 *) p->elts[i].object) ^
 703              FcValueListHash (p->elts[i].values));
 704     }
 705     return h;
 706 }
 707
 708 FcBool
 709 FcPatternEqualSubset (const FcPattern *pa, const FcPattern *pb, const FcObjectSet *os)
 710 {
 711     FcPatternElt    *ea, *eb;
 712     int             i;
 713
 714     for (i = 0; i < os->nobject; i++)
 715     {
 716         ea = FcPatternFindElt (pa, os->objects[i]);
 717         eb = FcPatternFindElt (pb, os->objects[i]);
 718         if (ea)
 719         {
 720             if (!eb)
 721                 return FcFalse;
 722             if (!FcValueListEqual (ea->values, eb->values))
 723                 return FcFalse;
 724         }
 725         else
 726         {
 727             if (eb)
 728                 return FcFalse;
 729         }
 730     }
 731     return FcTrue;
 732 }
 733
 734 FcBool
 735 FcPatternAddWithBinding  (FcPattern         *p,
 736                           const char        *object,
 737                           FcValue           value,
 738                           FcValueBinding    binding,
 739                           FcBool            append)
 740 {
 741     FcPatternElt   *e;
 742     FcValueList    *new, **prev;
 743
 744     if (p->ref == FC_REF_CONSTANT)
 745         goto bail0;
 746
 747     new = (FcValueList *) malloc (sizeof (FcValueList));
 748     if (!new)
 749         goto bail0;
 750
 751     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList));
 752     /* dup string */
 753     value = FcValueSave (value);
 754     if (value.type == FcTypeVoid)
 755         goto bail1;
 756
 757     new->value = value;
 758     new->binding = binding;
 759     new->next = 0;
 760
 761     e = FcPatternInsertElt (p, object);
 762     if (!e)
 763         goto bail2;
 764
 765     if (append)
 766     {
 767         for (prev = &e->values; *prev; prev = &(*prev)->next);
 768         *prev = new;
 769     }
 770     else
 771     {
 772         new->next = e->values;
 773         e->values = new;
 774     }
 775
 776     return FcTrue;
 777
 778 bail2:
 779     switch (value.type) {
 780     case FcTypeString:
 781         FcStrFree ((FcChar8 *) value.u.s);
 782         break;
 783     case FcTypeMatrix:
 784         FcMatrixFree ((FcMatrix *) value.u.m);
 785         break;
 786     case FcTypeCharSet:
 787         FcCharSetDestroy ((FcCharSet *) value.u.c);
 788         break;
 789     case FcTypeLangSet:
 790         FcLangSetDestroy ((FcLangSet *) value.u.l);
 791         break;
 792     default:
 793         break;
 794     }
 795 bail1:
 796     FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 797     free (new);
 798 bail0:
 799     return FcFalse;
 800 }
 801
 802 FcBool
 803 FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
 804 {
 805     return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
 806 }
 807
 808 FcBool
 809 FcPatternAddWeak  (FcPattern *p, const char *object, FcValue value, FcBool append)
 810 {
 811     return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
 812 }
 813
 814 FcBool
 815 FcPatternDel (FcPattern *p, const char *object)
 816 {
 817     FcPatternElt   *e;
 818     int             i;
 819
 820     e = FcPatternFindElt (p, object);
 821     if (!e)
 822         return FcFalse;
 823
 824     i = e - p->elts;
 825
 826     /* destroy value */
 827     FcValueListDestroy (e->values);
 828
 829     /* shuffle existing ones down */
 830     memmove (e, e+1, (p->elts + p->num - (e + 1)) * sizeof (FcPatternElt));
 831     p->num--;
 832     p->elts[p->num].object = 0;
 833     p->elts[p->num].values = 0;
 834     return FcTrue;
 835 }
 836
 837 FcBool
 838 FcPatternRemove (FcPattern *p, const char *object, int id)
 839 {
 840     FcPatternElt   *e;
 841     FcValueList    **prev, *l;
 842
 843     e = FcPatternFindElt (p, object);
 844     if (!e)
 845         return FcFalse;
 846     for (prev = &e->values; (l = *prev); prev = &l->next)
 847     {
 848         if (!id)
 849         {
 850             *prev = l->next;
 851             l->next = 0;
 852             FcValueListDestroy (l);
 853             if (!e->values)
 854                 FcPatternDel (p, object);
 855             return FcTrue;
 856         }
 857         id--;
 858     }
 859     return FcFalse;
 860 }
 861
 862 FcBool
 863 FcPatternAddInteger (FcPattern *p, const char *object, int i)
 864 {
 865     FcValue     v;
 866
 867     v.type = FcTypeInteger;
 868     v.u.i = i;
 869     return FcPatternAdd (p, object, v, FcTrue);
 870 }
 871
 872 FcBool
 873 FcPatternAddDouble (FcPattern *p, const char *object, double d)
 874 {
 875     FcValue     v;
 876
 877     v.type = FcTypeDouble;
 878     v.u.d = d;
 879     return FcPatternAdd (p, object, v, FcTrue);
 880 }
 881
 882
 883 FcBool
 884 FcPatternAddString (FcPattern *p, const char *object, const FcChar8 *s)
 885 {
 886     FcValue     v;
 887
 888     v.type = FcTypeString;
 889     v.u.s = s;
 890     return FcPatternAdd (p, object, v, FcTrue);
 891 }
 892
 893 FcBool
 894 FcPatternAddMatrix (FcPattern *p, const char *object, const FcMatrix *s)
 895 {
 896     FcValue     v;
 897
 898     v.type = FcTypeMatrix;
 899     v.u.m = (FcMatrix *) s;
 900     return FcPatternAdd (p, object, v, FcTrue);
 901 }
 902
 903
 904 FcBool
 905 FcPatternAddBool (FcPattern *p, const char *object, FcBool b)
 906 {
 907     FcValue     v;
 908
 909     v.type = FcTypeBool;
 910     v.u.b = b;
 911     return FcPatternAdd (p, object, v, FcTrue);
 912 }
 913
 914 FcBool
 915 FcPatternAddCharSet (FcPattern *p, const char *object, const FcCharSet *c)
 916 {
 917     FcValue     v;
 918
 919     v.type = FcTypeCharSet;
 920     v.u.c = (FcCharSet *) c;
 921     return FcPatternAdd (p, object, v, FcTrue);
 922 }
 923
 924 FcBool
 925 FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
 926 {
 927     FcValue     v;
 928
 929     v.type = FcTypeFTFace;
 930     v.u.f = (void *) f;
 931     return FcPatternAdd (p, object, v, FcTrue);
 932 }
 933
 934 FcBool
 935 FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
 936 {
 937     FcValue     v;
 938
 939     v.type = FcTypeLangSet;
 940     v.u.l = (FcLangSet *) ls;
 941     return FcPatternAdd (p, object, v, FcTrue);
 942 }
 943
 944 FcResult
 945 FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
 946 {
 947     FcPatternElt   *e;
 948     FcValueList    *l;
 949
 950     e = FcPatternFindElt (p, object);
 951     if (!e)
 952         return FcResultNoMatch;
 953     for (l = e->values; l; l = l->next)
 954     {
 955         if (!id)
 956         {
 957             *v = l->value;
 958             return FcResultMatch;
 959         }
 960         id--;
 961     }
 962     return FcResultNoId;
 963 }
 964
 965 FcResult
 966 FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
 967 {
 968     FcValue     v;
 969     FcResult    r;
 970
 971     r = FcPatternGet (p, object, id, &v);
 972     if (r != FcResultMatch)
 973         return r;
 974     switch (v.type) {
 975     case FcTypeDouble:
 976         *i = (int) v.u.d;
 977         break;
 978     case FcTypeInteger:
 979         *i = v.u.i;
 980         break;
 981     default:
 982         return FcResultTypeMismatch;
 983     }
 984     return FcResultMatch;
 985 }
 986
 987 FcResult
 988 FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
 989 {
 990     FcValue     v;
 991     FcResult    r;
 992
 993     r = FcPatternGet (p, object, id, &v);
 994     if (r != FcResultMatch)
 995         return r;
 996     switch (v.type) {
 997     case FcTypeDouble:
 998         *d = v.u.d;
 999         break;
1000     case FcTypeInteger:
1001         *d = (double) v.u.i;
1002         break;
1003     default:
1004         return FcResultTypeMismatch;
1005     }
1006     return FcResultMatch;
1007 }
1008
1009 FcResult
1010 FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
1011 {
1012     FcValue     v;
1013     FcResult    r;
1014
1015     r = FcPatternGet (p, object, id, &v);
1016     if (r != FcResultMatch)
1017         return r;
1018     if (v.type != FcTypeString)
1019         return FcResultTypeMismatch;
1020     *s = (FcChar8 *) v.u.s;
1021     return FcResultMatch;
1022 }
1023
1024 FcResult
1025 FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
1026 {
1027     FcValue     v;
1028     FcResult    r;
1029
1030     r = FcPatternGet (p, object, id, &v);
1031     if (r != FcResultMatch)
1032         return r;
1033     if (v.type != FcTypeMatrix)
1034         return FcResultTypeMismatch;
1035     *m = (FcMatrix *) v.u.m;
1036     return FcResultMatch;
1037 }
1038
1039
1040 FcResult
1041 FcPatternGetBool(const FcPattern *p, const char *object, int id, FcBool *b)
1042 {
1043     FcValue     v;
1044     FcResult    r;
1045
1046     r = FcPatternGet (p, object, id, &v);
1047     if (r != FcResultMatch)
1048         return r;
1049     if (v.type != FcTypeBool)
1050         return FcResultTypeMismatch;
1051     *b = v.u.b;
1052     return FcResultMatch;
1053 }
1054
1055 FcResult
1056 FcPatternGetCharSet(const FcPattern *p, const char *object, int id, FcCharSet **c)
1057 {
1058     FcValue     v;
1059     FcResult    r;
1060
1061     r = FcPatternGet (p, object, id, &v);
1062     if (r != FcResultMatch)
1063         return r;
1064     if (v.type != FcTypeCharSet)
1065         return FcResultTypeMismatch;
1066     *c = (FcCharSet *) v.u.c;
1067     return FcResultMatch;
1068 }
1069
1070 FcResult
1071 FcPatternGetFTFace(const FcPattern *p, const char *object, int id, FT_Face *f)
1072 {
1073     FcValue     v;
1074     FcResult    r;
1075
1076     r = FcPatternGet (p, object, id, &v);
1077     if (r != FcResultMatch)
1078         return r;
1079     if (v.type != FcTypeFTFace)
1080         return FcResultTypeMismatch;
1081     *f = (FT_Face) v.u.f;
1082     return FcResultMatch;
1083 }
1084
1085 FcResult
1086 FcPatternGetLangSet(const FcPattern *p, const char *object, int id, FcLangSet **ls)
1087 {
1088     FcValue     v;
1089     FcResult    r;
1090
1091     r = FcPatternGet (p, object, id, &v);
1092     if (r != FcResultMatch)
1093         return r;
1094     if (v.type != FcTypeLangSet)
1095         return FcResultTypeMismatch;
1096     *ls = (FcLangSet *) v.u.l;
1097     return FcResultMatch;
1098 }
1099
1100 FcPattern *
1101 FcPatternDuplicate (const FcPattern *orig)
1102 {
1103     FcPattern       *new;
1104     int             i;
1105     FcValueList    *l;
1106
1107     new = FcPatternCreate ();
1108     if (!new)
1109         goto bail0;
1110
1111     for (i = 0; i < orig->num; i++)
1112     {
1113         for (l = orig->elts[i].values; l; l = l->next)
1114             if (!FcPatternAdd (new, orig->elts[i].object, l->value, FcTrue))
1115                 goto bail1;
1116     }
1117
1118     return new;
1119
1120 bail1:
1121     FcPatternDestroy (new);
1122 bail0:
1123     return 0;
1124 }
1125
1126 void
1127 FcPatternReference (FcPattern *p)
1128 {
1129     if (p->ref != FC_REF_CONSTANT)
1130         p->ref++;
1131 }
1132
1133 FcPattern *
1134 FcPatternVaBuild (FcPattern *orig, va_list va)
1135 {
1136     FcPattern   *ret;
1137
1138     FcPatternVapBuild (ret, orig, va);
1139     return ret;
1140 }
1141
1142 FcPattern *
1143 FcPatternBuild (FcPattern *orig, ...)
1144 {
1145     va_list     va;
1146
1147     va_start (va, orig);
1148     FcPatternVapBuild (orig, orig, va);
1149     va_end (va);
1150     return orig;
1151 }
1152
1153 /*
1154  * Add all of the elements in 's' to 'p'
1155  */
1156 FcBool
1157 FcPatternAppend (FcPattern *p, FcPattern *s)
1158 {
1159     int             i;
1160     FcPatternElt    *e;
1161     FcValueList     *v;
1162
1163     for (i = 0; i < s->num; i++)
1164     {
1165         e = &s->elts[i];
1166         for (v = e->values; v; v = v->next)
1167         {
1168             if (!FcPatternAddWithBinding (p, e->object,
1169                                           v->value, v->binding, FcTrue))
1170                 return FcFalse;
1171         }
1172     }
1173     return FcTrue;
1174 }
1175
1176 const char *
1177 FcObjectStaticName (const char *name)
1178 {
1179 #define OBJECT_HASH_SIZE    31
1180     static struct objectBucket {
1181         struct objectBucket     *next;
1182         FcChar32                hash;
1183     } *buckets[OBJECT_HASH_SIZE];
1184     FcChar32            hash = FcStringHash ((const FcChar8 *) name);
1185     struct objectBucket **p;
1186     struct objectBucket *b;
1187     int                 size;
1188
1189     for (p = &buckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1190         if (b->hash == hash && !strcmp (name, (char *) (b + 1)))
1191             return (char *) (b + 1);
1192     size = sizeof (struct objectBucket) + strlen (name) + 1;
1193     b = malloc (size);
1194     FcMemAlloc (FC_MEM_STATICSTR, size);
1195     if (!b)
1196         return NULL;
1197     b->next = 0;
1198     b->hash = hash;
1199     strcpy ((char *) (b + 1), name);
1200     *p = b;
1201     return (char *) (b + 1);
1202 }