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             string_size = 0;
 325     FcChar8         *strs;
 326     int             size;
 327
 328     n = 0;
 329     for (l = h; l; l = l->next)
 330     {
 331         if (l->value.type == FcTypeString)
 332             string_size += strlen ((char *) l->value.u.s) + 1;
 333         n++;
 334     }
 335     size = sizeof (FcValueListAlign) + n * sizeof (FcValueList) + string_size;
 336     FcValueListFrozenCount[h->value.type]++;
 337     FcValueListFrozenBytes[h->value.type] += size;
 338     ea = malloc (size);
 339     if (!ea)
 340         return 0;
 341     FcMemAlloc (FC_MEM_VALLIST, size);
 342     e = &ea->ent;
 343     e->list = (FcValueList *) (ea + 1);
 344     strs = (FcChar8 *) (e->list + n);
 345     new = e->list;
 346     for (l = h; l; l = l->next, new++)
 347     {
 348         if (l->value.type == FcTypeString)
 349         {
 350             new->value.type = FcTypeString;
 351             new->value.u.s = strs;
 352             strcpy ((char *) strs, (char *) l->value.u.s);
 353             strs += strlen ((char *) strs) + 1;
 354         }
 355         else
 356         {
 357             new->value = l->value;
 358             new->value = FcValueSave (new->value);
 359         }
 360         new->binding = l->binding;
 361         if (l->next)
 362             new->next = new + 1;
 363         else
 364             new->next = 0;
 365     }
 366     return e;
 367 }
 368
 369 static void
 370 FcValueListEntDestroy (FcValueListEnt *e)
 371 {
 372     FcValueList *l;
 373
 374     FcValueListFrozenCount[e->list->value.type]--;
 375
 376     /* XXX: We should perform these two operations with "size" as
 377        computed in FcValueListEntCreate, but we don't have access to
 378        that value here. Without this, the FcValueListFrozenBytes
 379        values will be wrong as will the FcMemFree counts.
 380
 381        FcValueListFrozenBytes[e->list->value.type] -= size;
 382        FcMemFree (FC_MEM_VALLIST, size);
 383     */
 384
 385     for (l = e->list; l; l = l->next)
 386     {
 387         if (l->value.type != FcTypeString)
 388             FcValueDestroy (l->value);
 389     }
 390     /* XXX: Are we being too chummy with the implementation here to
 391        free(e) when it was actually the enclosing FcValueListAlign
 392        that was allocated? */
 393     free (e);
 394 }
 395
 396 static int      FcValueListTotal;
 397 static int      FcValueListUsed;
 398
 399 static FcValueListEnt   *FcValueListHashTable[FC_VALUE_LIST_HASH_SIZE];
 400
 401 static FcValueList *
 402 FcValueListFreeze (FcValueList *l)
 403 {
 404     FcChar32                hash = FcValueListHash (l);
 405     FcValueListEnt          **bucket = &FcValueListHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
 406     FcValueListEnt          *ent;
 407
 408     FcValueListTotal++;
 409     for (ent = *bucket; ent; ent = ent->next)
 410     {
 411         if (ent->hash == hash && FcValueListEqual (ent->list, l))
 412             return ent->list;
 413     }
 414
 415     ent = FcValueListEntCreate (l);
 416     if (!ent)
 417         return 0;
 418
 419     FcValueListUsed++;
 420     ent->hash = hash;
 421     ent->next = *bucket;
 422     *bucket = ent;
 423     return ent->list;
 424 }
 425
 426 static void
 427 FcValueListThawAll (void)
 428 {
 429     int i;
 430     FcValueListEnt      *ent, *next;
 431
 432     for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
 433     {
 434         for (ent = FcValueListHashTable[i]; ent; ent = next)
 435         {
 436             next = ent->next;
 437             FcValueListEntDestroy (ent);
 438         }
 439         FcValueListHashTable[i] = 0;
 440     }
 441
 442     FcValueListTotal = 0;
 443     FcValueListUsed = 0;
 444 }
 445
 446 static FcChar32
 447 FcPatternBaseHash (FcPattern *b)
 448 {
 449     FcChar32    hash = b->num;
 450     int         i;
 451
 452     for (i = 0; i < b->num; i++)
 453         hash = ((hash << 1) | (hash >> 31)) ^ ((long) b->elts[i].values);
 454     return hash;
 455 }
 456
 457 typedef struct _FcPatternEnt FcPatternEnt;
 458
 459 struct _FcPatternEnt {
 460     FcPatternEnt    *next;
 461     FcChar32        hash;
 462     FcPattern       pattern;
 463 };
 464
 465 static int      FcPatternTotal;
 466 static int      FcPatternUsed;
 467
 468 static FcPatternEnt     *FcPatternHashTable[FC_VALUE_LIST_HASH_SIZE];
 469
 470 static FcPattern *
 471 FcPatternBaseFreeze (FcPattern *b)
 472 {
 473     FcChar32            hash = FcPatternBaseHash (b);
 474     FcPatternEnt        **bucket = &FcPatternHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
 475     FcPatternEnt        *ent;
 476     int                 i;
 477     char                *objects;
 478     int                 size_objects;
 479     int                 size;
 480
 481     FcPatternTotal++;
 482     for (ent = *bucket; ent; ent = ent->next)
 483     {
 484         if (ent->hash == hash && b->num == ent->pattern.num)
 485         {
 486             for (i = 0; i < b->num; i++)
 487             {
 488                 if (strcmp (b->elts[i].object, ent->pattern.elts[i].object))
 489                     break;
 490                 if (b->elts[i].values != ent->pattern.elts[i].values)
 491                     break;
 492             }
 493             if (i == b->num)
 494                 return &ent->pattern;
 495         }
 496     }
 497
 498     /*
 499      * Compute size of pattern + elts + object names
 500      */
 501     size_objects = 0;
 502     for (i = 0; i < b->num; i++)
 503         size_objects += strlen (b->elts[i].object) + 1;
 504
 505     size = sizeof (FcPatternEnt) + b->num*sizeof (FcPatternElt) + size_objects;
 506     ent = malloc (size);
 507     if (!ent)
 508         return 0;
 509
 510     FcMemAlloc (FC_MEM_PATTERN, size);
 511     FcPatternUsed++;
 512
 513     ent->pattern.elts = (FcPatternElt *) (ent + 1);
 514     ent->pattern.num = b->num;
 515     ent->pattern.size = b->num;
 516     ent->pattern.ref = FC_REF_CONSTANT;
 517
 518     objects = (char *) (ent->pattern.elts + b->num);
 519     for (i = 0; i < b->num; i++)
 520     {
 521         ent->pattern.elts[i].values = b->elts[i].values;
 522         strcpy (objects, b->elts[i].object);
 523         ent->pattern.elts[i].object = objects;
 524         objects += strlen (objects) + 1;
 525     }
 526
 527     ent->hash = hash;
 528     ent->next = *bucket;
 529     *bucket = ent;
 530     return &ent->pattern;
 531 }
 532
 533 static void
 534 FcPatternBaseThawAll (void)
 535 {
 536     int i;
 537     FcPatternEnt        *ent, *next;
 538
 539     for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
 540     {
 541         for (ent = FcPatternHashTable[i]; ent; ent = next)
 542         {
 543             next = ent->next;
 544             free (ent);
 545         }
 546         FcPatternHashTable[i] = 0;
 547     }
 548
 549     FcPatternTotal = 0;
 550     FcPatternUsed = 0;
 551 }
 552
 553 FcPattern *
 554 FcPatternFreeze (FcPattern *p)
 555 {
 556     FcPattern   *b, *n = 0;
 557     int         size;
 558     int         i;
 559
 560     size = sizeof (FcPattern) + p->num * sizeof (FcPatternElt);
 561     b = (FcPattern *) malloc (size);
 562     if (!b)
 563         return 0;
 564     FcMemAlloc (FC_MEM_PATTERN, size);
 565     b->num = p->num;
 566     b->size = b->num;
 567     b->ref = 1;
 568     b->elts = (FcPatternElt *) (b + 1);
 569     /*
 570      * Freeze object lists
 571      */
 572     for (i = 0; i < p->num; i++)
 573     {
 574         b->elts[i].object = p->elts[i].object;
 575         b->elts[i].values = FcValueListFreeze (p->elts[i].values);
 576         if (!b->elts[i].values)
 577             goto bail;
 578     }
 579     /*
 580      * Freeze base
 581      */
 582     n = FcPatternBaseFreeze (b);
 583 #ifdef CHATTY
 584     if (FcDebug() & FC_DBG_MEMORY)
 585     {
 586         printf ("ValueLists: total %9d used %9d\n", FcValueListTotal, FcValueListUsed);
 587         printf ("Patterns:   total %9d used %9d\n", FcPatternTotal, FcPatternUsed);
 588     }
 589 #endif
 590 bail:
 591     free (b);
 592 #ifdef DEBUG
 593     assert (FcPatternEqual (n, p));
 594 #endif
 595     return n;
 596 }
 597
 598 void
 599 FcPatternThawAll (void)
 600 {
 601     FcPatternBaseThawAll ();
 602     FcValueListThawAll ();
 603 }
 604
 605 static int
 606 FcPatternPosition (const FcPattern *p, const char *object)
 607 {
 608     int     low, high, mid, c;
 609
 610     low = 0;
 611     high = p->num - 1;
 612     c = 1;
 613     mid = 0;
 614     while (low <= high)
 615     {
 616         mid = (low + high) >> 1;
 617         c = strcmp (p->elts[mid].object, object);
 618         if (c == 0)
 619             return mid;
 620         if (c < 0)
 621             low = mid + 1;
 622         else
 623             high = mid - 1;
 624     }
 625     if (c < 0)
 626         mid++;
 627     return -(mid + 1);
 628 }
 629
 630 FcPatternElt *
 631 FcPatternFindElt (const FcPattern *p, const char *object)
 632 {
 633     int     i = FcPatternPosition (p, object);
 634     if (i < 0)
 635         return 0;
 636     return &p->elts[i];
 637 }
 638
 639 FcPatternElt *
 640 FcPatternInsertElt (FcPattern *p, const char *object)
 641 {
 642     int             i;
 643     FcPatternElt   *e;
 644
 645     i = FcPatternPosition (p, object);
 646     if (i < 0)
 647     {
 648         i = -i - 1;
 649
 650         /* grow array */
 651         if (p->num + 1 >= p->size)
 652         {
 653             int s = p->size + 16;
 654             if (p->elts)
 655                 e = (FcPatternElt *) realloc (p->elts, s * sizeof (FcPatternElt));
 656             else
 657                 e = (FcPatternElt *) malloc (s * sizeof (FcPatternElt));
 658             if (!e)
 659                 return FcFalse;
 660             p->elts = e;
 661             if (p->size)
 662                 FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
 663             FcMemAlloc (FC_MEM_PATELT, s * sizeof (FcPatternElt));
 664             while (p->size < s)
 665             {
 666                 p->elts[p->size].object = 0;
 667                 p->elts[p->size].values = 0;
 668                 p->size++;
 669             }
 670         }
 671
 672         /* move elts up */
 673         memmove (p->elts + i + 1,
 674                  p->elts + i,
 675                  sizeof (FcPatternElt) *
 676                  (p->num - i));
 677
 678         /* bump count */
 679         p->num++;
 680
 681         p->elts[i].object = object;
 682         p->elts[i].values = 0;
 683     }
 684
 685     return &p->elts[i];
 686 }
 687
 688 FcBool
 689 FcPatternEqual (const FcPattern *pa, const FcPattern *pb)
 690 {
 691     int i;
 692
 693     if (pa == pb)
 694         return FcTrue;
 695
 696     if (pa->num != pb->num)
 697         return FcFalse;
 698     for (i = 0; i < pa->num; i++)
 699     {
 700         if (strcmp (pa->elts[i].object, pb->elts[i].object) != 0)
 701             return FcFalse;
 702         if (!FcValueListEqual (pa->elts[i].values, pb->elts[i].values))
 703             return FcFalse;
 704     }
 705     return FcTrue;
 706 }
 707
 708 FcChar32
 709 FcPatternHash (const FcPattern *p)
 710 {
 711     int         i;
 712     FcChar32    h = 0;
 713
 714     for (i = 0; i < p->num; i++)
 715     {
 716         h = (((h << 1) | (h >> 31)) ^
 717              FcStringHash ((const FcChar8 *) p->elts[i].object) ^
 718              FcValueListHash (p->elts[i].values));
 719     }
 720     return h;
 721 }
 722
 723 FcBool
 724 FcPatternEqualSubset (const FcPattern *pa, const FcPattern *pb, const FcObjectSet *os)
 725 {
 726     FcPatternElt    *ea, *eb;
 727     int             i;
 728
 729     for (i = 0; i < os->nobject; i++)
 730     {
 731         ea = FcPatternFindElt (pa, os->objects[i]);
 732         eb = FcPatternFindElt (pb, os->objects[i]);
 733         if (ea)
 734         {
 735             if (!eb)
 736                 return FcFalse;
 737             if (!FcValueListEqual (ea->values, eb->values))
 738                 return FcFalse;
 739         }
 740         else
 741         {
 742             if (eb)
 743                 return FcFalse;
 744         }
 745     }
 746     return FcTrue;
 747 }
 748
 749 FcBool
 750 FcPatternAddWithBinding  (FcPattern         *p,
 751                           const char        *object,
 752                           FcValue           value,
 753                           FcValueBinding    binding,
 754                           FcBool            append)
 755 {
 756     FcPatternElt   *e;
 757     FcValueList    *new, **prev;
 758
 759     if (p->ref == FC_REF_CONSTANT)
 760         goto bail0;
 761
 762     new = (FcValueList *) malloc (sizeof (FcValueList));
 763     if (!new)
 764         goto bail0;
 765
 766     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList));
 767     /* dup string */
 768     value = FcValueSave (value);
 769     if (value.type == FcTypeVoid)
 770         goto bail1;
 771
 772     new->value = value;
 773     new->binding = binding;
 774     new->next = 0;
 775
 776     e = FcPatternInsertElt (p, object);
 777     if (!e)
 778         goto bail2;
 779
 780     if (append)
 781     {
 782         for (prev = &e->values; *prev; prev = &(*prev)->next);
 783         *prev = new;
 784     }
 785     else
 786     {
 787         new->next = e->values;
 788         e->values = new;
 789     }
 790
 791     return FcTrue;
 792
 793 bail2:
 794     switch (value.type) {
 795     case FcTypeString:
 796         FcStrFree ((FcChar8 *) value.u.s);
 797         break;
 798     case FcTypeMatrix:
 799         FcMatrixFree ((FcMatrix *) value.u.m);
 800         break;
 801     case FcTypeCharSet:
 802         FcCharSetDestroy ((FcCharSet *) value.u.c);
 803         break;
 804     case FcTypeLangSet:
 805         FcLangSetDestroy ((FcLangSet *) value.u.l);
 806         break;
 807     default:
 808         break;
 809     }
 810 bail1:
 811     FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 812     free (new);
 813 bail0:
 814     return FcFalse;
 815 }
 816
 817 FcBool
 818 FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
 819 {
 820     return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
 821 }
 822
 823 FcBool
 824 FcPatternAddWeak  (FcPattern *p, const char *object, FcValue value, FcBool append)
 825 {
 826     return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
 827 }
 828
 829 FcBool
 830 FcPatternDel (FcPattern *p, const char *object)
 831 {
 832     FcPatternElt   *e;
 833     int             i;
 834
 835     e = FcPatternFindElt (p, object);
 836     if (!e)
 837         return FcFalse;
 838
 839     i = e - p->elts;
 840
 841     /* destroy value */
 842     FcValueListDestroy (e->values);
 843
 844     /* shuffle existing ones down */
 845     memmove (e, e+1, (p->elts + p->num - (e + 1)) * sizeof (FcPatternElt));
 846     p->num--;
 847     p->elts[p->num].object = 0;
 848     p->elts[p->num].values = 0;
 849     return FcTrue;
 850 }
 851
 852 FcBool
 853 FcPatternRemove (FcPattern *p, const char *object, int id)
 854 {
 855     FcPatternElt   *e;
 856     FcValueList    **prev, *l;
 857
 858     e = FcPatternFindElt (p, object);
 859     if (!e)
 860         return FcFalse;
 861     for (prev = &e->values; (l = *prev); prev = &l->next)
 862     {
 863         if (!id)
 864         {
 865             *prev = l->next;
 866             l->next = 0;
 867             FcValueListDestroy (l);
 868             if (!e->values)
 869                 FcPatternDel (p, object);
 870             return FcTrue;
 871         }
 872         id--;
 873     }
 874     return FcFalse;
 875 }
 876
 877 FcBool
 878 FcPatternAddInteger (FcPattern *p, const char *object, int i)
 879 {
 880     FcValue     v;
 881
 882     v.type = FcTypeInteger;
 883     v.u.i = i;
 884     return FcPatternAdd (p, object, v, FcTrue);
 885 }
 886
 887 FcBool
 888 FcPatternAddDouble (FcPattern *p, const char *object, double d)
 889 {
 890     FcValue     v;
 891
 892     v.type = FcTypeDouble;
 893     v.u.d = d;
 894     return FcPatternAdd (p, object, v, FcTrue);
 895 }
 896
 897
 898 FcBool
 899 FcPatternAddString (FcPattern *p, const char *object, const FcChar8 *s)
 900 {
 901     FcValue     v;
 902
 903     v.type = FcTypeString;
 904     v.u.s = s;
 905     return FcPatternAdd (p, object, v, FcTrue);
 906 }
 907
 908 FcBool
 909 FcPatternAddMatrix (FcPattern *p, const char *object, const FcMatrix *s)
 910 {
 911     FcValue     v;
 912
 913     v.type = FcTypeMatrix;
 914     v.u.m = (FcMatrix *) s;
 915     return FcPatternAdd (p, object, v, FcTrue);
 916 }
 917
 918
 919 FcBool
 920 FcPatternAddBool (FcPattern *p, const char *object, FcBool b)
 921 {
 922     FcValue     v;
 923
 924     v.type = FcTypeBool;
 925     v.u.b = b;
 926     return FcPatternAdd (p, object, v, FcTrue);
 927 }
 928
 929 FcBool
 930 FcPatternAddCharSet (FcPattern *p, const char *object, const FcCharSet *c)
 931 {
 932     FcValue     v;
 933
 934     v.type = FcTypeCharSet;
 935     v.u.c = (FcCharSet *) c;
 936     return FcPatternAdd (p, object, v, FcTrue);
 937 }
 938
 939 FcBool
 940 FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
 941 {
 942     FcValue     v;
 943
 944     v.type = FcTypeFTFace;
 945     v.u.f = (void *) f;
 946     return FcPatternAdd (p, object, v, FcTrue);
 947 }
 948
 949 FcBool
 950 FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
 951 {
 952     FcValue     v;
 953
 954     v.type = FcTypeLangSet;
 955     v.u.l = (FcLangSet *) ls;
 956     return FcPatternAdd (p, object, v, FcTrue);
 957 }
 958
 959 FcResult
 960 FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
 961 {
 962     FcPatternElt   *e;
 963     FcValueList    *l;
 964
 965     e = FcPatternFindElt (p, object);
 966     if (!e)
 967         return FcResultNoMatch;
 968     for (l = e->values; l; l = l->next)
 969     {
 970         if (!id)
 971         {
 972             *v = l->value;
 973             return FcResultMatch;
 974         }
 975         id--;
 976     }
 977     return FcResultNoId;
 978 }
 979
 980 FcResult
 981 FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
 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         *i = (int) v.u.d;
 992         break;
 993     case FcTypeInteger:
 994         *i = v.u.i;
 995         break;
 996     default:
 997         return FcResultTypeMismatch;
 998     }
 999     return FcResultMatch;
1000 }
1001
1002 FcResult
1003 FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
1004 {
1005     FcValue     v;
1006     FcResult    r;
1007
1008     r = FcPatternGet (p, object, id, &v);
1009     if (r != FcResultMatch)
1010         return r;
1011     switch (v.type) {
1012     case FcTypeDouble:
1013         *d = v.u.d;
1014         break;
1015     case FcTypeInteger:
1016         *d = (double) v.u.i;
1017         break;
1018     default:
1019         return FcResultTypeMismatch;
1020     }
1021     return FcResultMatch;
1022 }
1023
1024 FcResult
1025 FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
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 != FcTypeString)
1034         return FcResultTypeMismatch;
1035     *s = (FcChar8 *) v.u.s;
1036     return FcResultMatch;
1037 }
1038
1039 FcResult
1040 FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
1041 {
1042     FcValue     v;
1043     FcResult    r;
1044
1045     r = FcPatternGet (p, object, id, &v);
1046     if (r != FcResultMatch)
1047         return r;
1048     if (v.type != FcTypeMatrix)
1049         return FcResultTypeMismatch;
1050     *m = (FcMatrix *) v.u.m;
1051     return FcResultMatch;
1052 }
1053
1054
1055 FcResult
1056 FcPatternGetBool(const FcPattern *p, const char *object, int id, FcBool *b)
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 != FcTypeBool)
1065         return FcResultTypeMismatch;
1066     *b = v.u.b;
1067     return FcResultMatch;
1068 }
1069
1070 FcResult
1071 FcPatternGetCharSet(const FcPattern *p, const char *object, int id, FcCharSet **c)
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 != FcTypeCharSet)
1080         return FcResultTypeMismatch;
1081     *c = (FcCharSet *) v.u.c;
1082     return FcResultMatch;
1083 }
1084
1085 FcResult
1086 FcPatternGetFTFace(const FcPattern *p, const char *object, int id, FT_Face *f)
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 != FcTypeFTFace)
1095         return FcResultTypeMismatch;
1096     *f = (FT_Face) v.u.f;
1097     return FcResultMatch;
1098 }
1099
1100 FcResult
1101 FcPatternGetLangSet(const FcPattern *p, const char *object, int id, FcLangSet **ls)
1102 {
1103     FcValue     v;
1104     FcResult    r;
1105
1106     r = FcPatternGet (p, object, id, &v);
1107     if (r != FcResultMatch)
1108         return r;
1109     if (v.type != FcTypeLangSet)
1110         return FcResultTypeMismatch;
1111     *ls = (FcLangSet *) v.u.l;
1112     return FcResultMatch;
1113 }
1114
1115 FcPattern *
1116 FcPatternDuplicate (const FcPattern *orig)
1117 {
1118     FcPattern       *new;
1119     int             i;
1120     FcValueList    *l;
1121
1122     new = FcPatternCreate ();
1123     if (!new)
1124         goto bail0;
1125
1126     for (i = 0; i < orig->num; i++)
1127     {
1128         for (l = orig->elts[i].values; l; l = l->next)
1129             if (!FcPatternAdd (new, orig->elts[i].object, l->value, FcTrue))
1130                 goto bail1;
1131     }
1132
1133     return new;
1134
1135 bail1:
1136     FcPatternDestroy (new);
1137 bail0:
1138     return 0;
1139 }
1140
1141 void
1142 FcPatternReference (FcPattern *p)
1143 {
1144     if (p->ref != FC_REF_CONSTANT)
1145         p->ref++;
1146 }
1147
1148 FcPattern *
1149 FcPatternVaBuild (FcPattern *orig, va_list va)
1150 {
1151     FcPattern   *ret;
1152
1153     FcPatternVapBuild (ret, orig, va);
1154     return ret;
1155 }
1156
1157 FcPattern *
1158 FcPatternBuild (FcPattern *orig, ...)
1159 {
1160     va_list     va;
1161
1162     va_start (va, orig);
1163     FcPatternVapBuild (orig, orig, va);
1164     va_end (va);
1165     return orig;
1166 }
1167
1168 /*
1169  * Add all of the elements in 's' to 'p'
1170  */
1171 FcBool
1172 FcPatternAppend (FcPattern *p, FcPattern *s)
1173 {
1174     int             i;
1175     FcPatternElt    *e;
1176     FcValueList     *v;
1177
1178     for (i = 0; i < s->num; i++)
1179     {
1180         e = &s->elts[i];
1181         for (v = e->values; v; v = v->next)
1182         {
1183             if (!FcPatternAddWithBinding (p, e->object,
1184                                           v->value, v->binding, FcTrue))
1185                 return FcFalse;
1186         }
1187     }
1188     return FcTrue;
1189 }
1190
1191 const char *
1192 FcObjectStaticName (const char *name)
1193 {
1194 #define OBJECT_HASH_SIZE    31
1195     static struct objectBucket {
1196         struct objectBucket     *next;
1197         FcChar32                hash;
1198     } *buckets[OBJECT_HASH_SIZE];
1199     FcChar32            hash = FcStringHash ((const FcChar8 *) name);
1200     struct objectBucket **p;
1201     struct objectBucket *b;
1202
1203     for (p = &buckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1204         if (b->hash == hash && !strcmp (name, (char *) (b + 1)))
1205             return (char *) (b + 1);
1206     b = malloc (sizeof (struct objectBucket) + strlen (name) + 1);
1207     if (!b)
1208         return NULL;
1209     b->next = 0;
1210     b->hash = hash;
1211     strcpy ((char *) (b + 1), name);
1212     *p = b;
1213     return (char *) (b + 1);
1214 }