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