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