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 "fcint.h"
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <assert.h>
  29
  30 static FcPattern ** _fcPatterns = 0;
  31 static int fcpattern_bank_count = 0, fcpattern_ptr, fcpattern_count;
  32 FcPatternElt ** _fcPatternElts = 0;
  33 static int fcpatternelt_ptr, fcpatternelt_count;
  34 FcValueList ** _fcValueLists = 0;
  35 static int fcvaluelist_bank_count = 0, fcvaluelist_ptr, fcvaluelist_count;
  36
  37 static FcPatternEltPtr
  38 FcPatternEltPtrCreateDynamic (FcPatternElt * e);
  39 static FcBool
  40 FcStrHashed (const FcChar8 *name);
  41
  42 FcPattern *
  43 FcPatternCreate (void)
  44 {
  45     FcPattern   *p;
  46
  47     p = (FcPattern *) malloc (sizeof (FcPattern));
  48     if (!p)
  49         return 0;
  50     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern));
  51     p->num = 0;
  52     p->size = 0;
  53     p->elts = FcPatternEltPtrCreateDynamic(0);
  54     p->bank = FC_BANK_DYNAMIC;
  55     p->ref = 1;
  56     return p;
  57 }
  58
  59 void
  60 FcValueDestroy (FcValue v)
  61 {
  62     switch (v.type) {
  63     case FcTypeString:
  64         if (!FcStrHashed (v.u.s))
  65             FcStrFree ((FcChar8 *) v.u.s);
  66         break;
  67     case FcTypeMatrix:
  68         FcMatrixFree ((FcMatrix *) v.u.m);
  69         break;
  70     case FcTypeCharSet:
  71         FcCharSetDestroy ((FcCharSet *) v.u.c);
  72         break;
  73     case FcTypeLangSet:
  74         FcLangSetDestroy ((FcLangSet *) v.u.l);
  75         break;
  76     default:
  77         break;
  78     }
  79 }
  80
  81 FcValue
  82 FcValueCanonicalize (const FcValue *v)
  83 {
  84     if (v->type & FC_STORAGE_STATIC)
  85     {
  86         FcValue new = *v;
  87
  88         switch (v->type & ~FC_STORAGE_STATIC)
  89         {
  90         case FcTypeString:
  91             new.u.s = fc_value_string(v);
  92             new.type = FcTypeString;
  93             break;
  94         case FcTypeCharSet:
  95             new.u.c = fc_value_charset(v);
  96             new.type = FcTypeCharSet;
  97             break;
  98         case FcTypeLangSet:
  99             new.u.l = fc_value_langset(v);
 100             new.type = FcTypeLangSet;
 101             break;
 102         }
 103         return new;
 104     }
 105     return *v;
 106 }
 107
 108 FcValue
 109 FcValueSave (FcValue v)
 110 {
 111     switch (v.type) {
 112     case FcTypeString:
 113         v.u.s = FcStrCopy (v.u.s);
 114         if (!v.u.s)
 115             v.type = FcTypeVoid;
 116         break;
 117     case FcTypeMatrix:
 118         v.u.m = FcMatrixCopy (v.u.m);
 119         if (!v.u.m)
 120             v.type = FcTypeVoid;
 121         break;
 122     case FcTypeCharSet:
 123         v.u.c = FcCharSetCopy ((FcCharSet *) v.u.c);
 124         if (!v.u.c)
 125             v.type = FcTypeVoid;
 126         break;
 127     case FcTypeLangSet:
 128         v.u.l = FcLangSetCopy (v.u.l);
 129         if (!v.u.l)
 130             v.type = FcTypeVoid;
 131         break;
 132     default:
 133         break;
 134     }
 135     return v;
 136 }
 137
 138 void
 139 FcValueListDestroy (FcValueListPtr l)
 140 {
 141     FcValueListPtr next;
 142     for (; FcValueListPtrU(l); l = next)
 143     {
 144         switch (FcValueListPtrU(l)->value.type) {
 145         case FcTypeString:
 146             if (!FcStrHashed ((FcChar8 *)FcValueListPtrU(l)->value.u.s))
 147                 FcStrFree ((FcChar8 *)FcValueListPtrU(l)->value.u.s);
 148             break;
 149         case FcTypeMatrix:
 150             FcMatrixFree ((FcMatrix *)FcValueListPtrU(l)->value.u.m);
 151             break;
 152         case FcTypeCharSet:
 153             FcCharSetDestroy
 154                 ((FcCharSet *) (FcValueListPtrU(l)->value.u.c));
 155             break;
 156         case FcTypeLangSet:
 157             FcLangSetDestroy
 158                 ((FcLangSet *) (FcValueListPtrU(l)->value.u.l));
 159             break;
 160         default:
 161             break;
 162         }
 163         next = FcValueListPtrU(l)->next;
 164         FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 165         if (l.bank == FC_BANK_DYNAMIC)
 166             free(l.u.dyn);
 167     }
 168 }
 169
 170 FcBool
 171 FcValueEqual (FcValue va, FcValue vb)
 172 {
 173     if (va.type != vb.type)
 174     {
 175         if (va.type == FcTypeInteger)
 176         {
 177             va.type = FcTypeDouble;
 178             va.u.d = va.u.i;
 179         }
 180         if (vb.type == FcTypeInteger)
 181         {
 182             vb.type = FcTypeDouble;
 183             vb.u.d = vb.u.i;
 184         }
 185         if (va.type != vb.type)
 186             return FcFalse;
 187     }
 188     switch (va.type) {
 189     case FcTypeVoid:
 190         return FcTrue;
 191     case FcTypeInteger:
 192         return va.u.i == vb.u.i;
 193     case FcTypeDouble:
 194         return va.u.d == vb.u.d;
 195     case FcTypeString:
 196         return FcStrCmpIgnoreCase (va.u.s, vb.u.s) == 0;
 197     case FcTypeBool:
 198         return va.u.b == vb.u.b;
 199     case FcTypeMatrix:
 200         return FcMatrixEqual (va.u.m, vb.u.m);
 201     case FcTypeCharSet:
 202         return FcCharSetEqual (va.u.c, vb.u.c);
 203     case FcTypeFTFace:
 204         return va.u.f == vb.u.f;
 205     case FcTypeLangSet:
 206         return FcLangSetEqual (va.u.l, vb.u.l);
 207     }
 208     return FcFalse;
 209 }
 210
 211 static FcChar32
 212 FcDoubleHash (double d)
 213 {
 214     if (d < 0)
 215         d = -d;
 216     if (d > 0xffffffff)
 217         d = 0xffffffff;
 218     return (FcChar32) d;
 219 }
 220
 221 FcChar32
 222 FcStringHash (const FcChar8 *s)
 223 {
 224     FcChar8     c;
 225     FcChar32    h = 0;
 226
 227     if (s)
 228         while ((c = *s++))
 229             h = ((h << 1) | (h >> 31)) ^ c;
 230     return h;
 231 }
 232
 233 static FcChar32
 234 FcValueHash (const FcValue *v)
 235 {
 236     switch (fc_storage_type(v)) {
 237     case FcTypeVoid:
 238         return 0;
 239     case FcTypeInteger:
 240         return (FcChar32) v->u.i;
 241     case FcTypeDouble:
 242         return FcDoubleHash (v->u.d);
 243     case FcTypeString:
 244         return FcStringHash (fc_value_string(v));
 245     case FcTypeBool:
 246         return (FcChar32) v->u.b;
 247     case FcTypeMatrix:
 248         return (FcDoubleHash (v->u.m->xx) ^
 249                 FcDoubleHash (v->u.m->xy) ^
 250                 FcDoubleHash (v->u.m->yx) ^
 251                 FcDoubleHash (v->u.m->yy));
 252     case FcTypeCharSet:
 253         return (FcChar32) fc_value_charset(v)->num;
 254     case FcTypeFTFace:
 255         return FcStringHash ((const FcChar8 *) ((FT_Face) v->u.f)->family_name) ^
 256                FcStringHash ((const FcChar8 *) ((FT_Face) v->u.f)->style_name);
 257     case FcTypeLangSet:
 258         return FcLangSetHash (fc_value_langset(v));
 259     }
 260     return FcFalse;
 261 }
 262
 263 static FcBool
 264 FcValueListEqual (FcValueListPtr la, FcValueListPtr lb)
 265 {
 266     if (FcValueListPtrU(la) == FcValueListPtrU(lb))
 267         return FcTrue;
 268
 269     while (FcValueListPtrU(la) && FcValueListPtrU(lb))
 270     {
 271         if (!FcValueEqual (FcValueListPtrU(la)->value,
 272                            FcValueListPtrU(lb)->value))
 273             return FcFalse;
 274         la = FcValueListPtrU(la)->next;
 275         lb = FcValueListPtrU(lb)->next;
 276     }
 277     if (FcValueListPtrU(la) || FcValueListPtrU(lb))
 278         return FcFalse;
 279     return FcTrue;
 280 }
 281
 282 static FcChar32
 283 FcValueListHash (FcValueListPtr l)
 284 {
 285     FcChar32    hash = 0;
 286     FcValueList *l_ptrU;
 287
 288     for (l_ptrU = FcValueListPtrU(l); l_ptrU;
 289          l_ptrU = FcValueListPtrU(l_ptrU->next))
 290     {
 291         hash = ((hash << 1) | (hash >> 31)) ^ FcValueHash (&l_ptrU->value);
 292     }
 293     return hash;
 294 }
 295
 296 void
 297 FcPatternDestroy (FcPattern *p)
 298 {
 299     int             i;
 300
 301     if (p->ref == FC_REF_CONSTANT || --p->ref > 0)
 302         return;
 303
 304     for (i = 0; i < p->num; i++)
 305         FcValueListDestroy ((FcPatternEltU(p->elts)+i)->values);
 306
 307     p->num = 0;
 308     if (FcPatternEltU(p->elts) && p->elts.bank == FC_BANK_DYNAMIC)
 309     {
 310         FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
 311         free (FcPatternEltU(p->elts));
 312         p->elts = FcPatternEltPtrCreateDynamic(0);
 313     }
 314     p->size = 0;
 315     FcMemFree (FC_MEM_PATTERN, sizeof (FcPattern));
 316     free (p);
 317 }
 318
 319 #define FC_VALUE_LIST_HASH_SIZE     257
 320 #define FC_PATTERN_HASH_SIZE        67
 321
 322 typedef struct _FcValueListEnt FcValueListEnt;
 323
 324 struct _FcValueListEnt {
 325     FcValueListEnt  *next;
 326     FcValueListPtr  list;
 327     FcChar32        hash, pad;
 328 };
 329
 330 typedef union _FcValueListAlign {
 331     FcValueListEnt  ent;
 332     FcValueList     list;
 333 } FcValueListAlign;
 334
 335 static int          FcValueListFrozenCount[FcTypeLangSet + 1];
 336 static int          FcValueListFrozenBytes[FcTypeLangSet + 1];
 337 static const char   FcValueListFrozenName[][8] = {
 338     "Void",
 339     "Integer",
 340     "Double",
 341     "String",
 342     "Bool",
 343     "Matrix",
 344     "CharSet",
 345     "FTFace",
 346     "LangSet"
 347 };
 348
 349 void
 350 FcValueListReport (void);
 351
 352 void
 353 FcValueListReport (void)
 354 {
 355     FcType  t;
 356
 357     printf ("Fc Frozen Values:\n");
 358     printf ("\t%8s %9s %9s\n", "Type", "Count", "Bytes");
 359     for (t = FcTypeVoid; t <= FcTypeLangSet; t++)
 360         printf ("\t%8s %9d %9d\n", FcValueListFrozenName[t],
 361                 FcValueListFrozenCount[t], FcValueListFrozenBytes[t]);
 362 }
 363
 364 static FcValueListEnt *
 365 FcValueListEntCreate (FcValueListPtr h)
 366 {
 367     FcValueListAlign    *ea;
 368     FcValueListEnt  *e;
 369     FcValueListPtr  l;
 370     FcValueList     *new;
 371     int             n;
 372     int             size;
 373
 374     n = 0;
 375     for (l = h; FcValueListPtrU(l); l = FcValueListPtrU(l)->next)
 376         n++;
 377     size = sizeof (FcValueListAlign) + n * sizeof (FcValueList);
 378     FcValueListFrozenCount[FcValueListPtrU(h)->value.type]++;
 379     FcValueListFrozenBytes[FcValueListPtrU(h)->value.type] += size;
 380     /* this leaks for some reason */
 381     ea = malloc (sizeof (FcValueListAlign));
 382     if (!ea)
 383         return 0;
 384     new = malloc (n * sizeof (FcValueList));
 385     if (!new)
 386     {
 387         free (ea);
 388         return 0;
 389     }
 390     memset(new, 0, n * sizeof (FcValueList));
 391     FcMemAlloc (FC_MEM_VALLIST, size);
 392     e = &ea->ent;
 393     e->list = FcValueListPtrCreateDynamic(new);
 394     for (l = h; FcValueListPtrU(l);
 395          l = FcValueListPtrU(l)->next, new++)
 396     {
 397         if ((FcValueListPtrU(l)->value.type & ~FC_STORAGE_STATIC) == FcTypeString)
 398         {
 399             new->value.type = FcTypeString;
 400             new->value.u.s = FcStrStaticName
 401                 (fc_value_string(&FcValueListPtrU(l)->value));
 402         }
 403         else
 404         {
 405             new->value = FcValueSave (FcValueCanonicalize
 406                                       (&FcValueListPtrU(l)->value));
 407         }
 408         new->binding = FcValueListPtrU(l)->binding;
 409         if (FcValueListPtrU(FcValueListPtrU(l)->next))
 410         {
 411             new->next = FcValueListPtrCreateDynamic(new + 1);
 412         }
 413         else
 414         {
 415             new->next = FcValueListPtrCreateDynamic(0);
 416         }
 417     }
 418     return e;
 419 }
 420
 421 static void
 422 FcValueListEntDestroy (FcValueListEnt *e)
 423 {
 424     FcValueListPtr      l;
 425
 426     FcValueListFrozenCount[FcValueListPtrU(e->list)->value.type]--;
 427
 428     /* XXX: We should perform these two operations with "size" as
 429        computed in FcValueListEntCreate, but we don't have access to
 430        that value here. Without this, the FcValueListFrozenBytes
 431        values will be wrong as will the FcMemFree counts.
 432
 433        FcValueListFrozenBytes[e->list->value.type] -= size;
 434        FcMemFree (FC_MEM_VALLIST, size);
 435     */
 436
 437     for (l = e->list; FcValueListPtrU(l);
 438          l = FcValueListPtrU(l)->next)
 439     {
 440         if (FcValueListPtrU(l)->value.type != FcTypeString)
 441             FcValueDestroy (FcValueListPtrU(l)->value);
 442     }
 443     /* XXX: Are we being too chummy with the implementation here to
 444        free(e) when it was actually the enclosing FcValueListAlign
 445        that was allocated? */
 446     free (e);
 447 }
 448
 449 static int      FcValueListTotal;
 450 static int      FcValueListUsed;
 451
 452 static FcValueListEnt   *FcValueListHashTable[FC_VALUE_LIST_HASH_SIZE];
 453
 454 static FcValueListPtr
 455 FcValueListFreeze (FcValueListPtr l)
 456 {
 457     FcChar32                hash = FcValueListHash (l);
 458     FcValueListEnt          **bucket = &FcValueListHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
 459     FcValueListEnt          *ent;
 460
 461     FcValueListTotal++;
 462     for (ent = *bucket; ent; ent = ent->next)
 463     {
 464         if (ent->hash == hash && FcValueListEqual (ent->list, l))
 465             return ent->list;
 466     }
 467
 468     ent = FcValueListEntCreate (l);
 469     if (!ent)
 470         return FcValueListPtrCreateDynamic(0);
 471
 472     FcValueListUsed++;
 473     ent->hash = hash;
 474     ent->next = *bucket;
 475     *bucket = ent;
 476     return ent->list;
 477 }
 478
 479 static void
 480 FcValueListThawAll (void)
 481 {
 482     int i;
 483     FcValueListEnt      *ent, *next;
 484
 485     for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
 486     {
 487         for (ent = FcValueListHashTable[i]; ent; ent = next)
 488         {
 489             next = ent->next;
 490             FcValueListEntDestroy (ent);
 491         }
 492         FcValueListHashTable[i] = 0;
 493     }
 494
 495     FcValueListTotal = 0;
 496     FcValueListUsed = 0;
 497 }
 498
 499 static FcChar32
 500 FcPatternBaseHash (FcPattern *b)
 501 {
 502     FcChar32    hash = b->num;
 503     int         i;
 504
 505     for (i = 0; i < b->num; i++)
 506         hash = ((hash << 1) | (hash >> 31)) ^
 507             (long) (FcValueListPtrU((FcPatternEltU(b->elts)+i)->values));
 508     return hash;
 509 }
 510
 511 typedef struct _FcPatternEnt FcPatternEnt;
 512
 513 struct _FcPatternEnt {
 514     FcPatternEnt    *next;
 515     FcChar32        hash;
 516     FcPattern       *pattern;
 517 };
 518
 519 static int      FcPatternTotal;
 520 static int      FcPatternUsed;
 521
 522 static FcPatternEnt     *FcPatternHashTable[FC_VALUE_LIST_HASH_SIZE];
 523
 524 static FcPattern *
 525 FcPatternBaseFreeze (FcPattern *b)
 526 {
 527     FcPattern           *ep;
 528     FcPatternElt        *epp;
 529     FcChar32            hash = FcPatternBaseHash (b);
 530     FcPatternEnt        **bucket = &FcPatternHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
 531     FcPatternEnt        *ent;
 532     int                 i;
 533
 534     FcPatternTotal++;
 535     for (ent = *bucket; ent; ent = ent->next)
 536     {
 537         if (ent->hash == hash && b->num == ent->pattern->num)
 538         {
 539             for (i = 0; i < b->num; i++)
 540             {
 541                 if (FcObjectPtrCompare((FcPatternEltU(b->elts)+i)->object,
 542                                        (FcPatternEltU(ent->pattern->elts)+i)->object) != 0)
 543                     break;
 544                 if (FcValueListPtrU((FcPatternEltU(b->elts)+i)->values) !=
 545                     FcValueListPtrU((FcPatternEltU(ent->pattern->elts)+i)->values))
 546                     break;
 547             }
 548             if (i == b->num)
 549                 return ent->pattern;
 550         }
 551     }
 552
 553     /*
 554      * Compute size of pattern + elts
 555      */
 556     ent = malloc (sizeof (FcPatternEnt));
 557     if (!ent)
 558         return 0;
 559
 560     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPatternEnt));
 561     FcPatternUsed++;
 562
 563     ep = FcPatternCreate();
 564     if (!ep)
 565         goto bail;
 566     ent->pattern = ep;
 567     epp = malloc(b->num * sizeof (FcPatternElt));
 568     if (!epp)
 569     {
 570         FcPatternDestroy (ep);
 571         goto bail;
 572     }
 573     ep->elts = FcPatternEltPtrCreateDynamic(epp);
 574
 575     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));
 576
 577     ep->num = b->num;
 578     ep->size = b->num;
 579     ep->ref = FC_REF_CONSTANT;
 580
 581     for (i = 0; i < b->num; i++)
 582     {
 583         (FcPatternEltU(ep->elts)+i)->values =
 584             (FcPatternEltU(b->elts)+i)->values;
 585         (FcPatternEltU(ep->elts)+i)->object =
 586             (FcPatternEltU(b->elts)+i)->object;
 587     }
 588
 589     ent->hash = hash;
 590     ent->next = *bucket;
 591     *bucket = ent;
 592     return ent->pattern;
 593  bail:
 594     free(ent);
 595     FcMemFree (FC_MEM_PATTERN, sizeof (FcPatternEnt));
 596     FcPatternUsed--;
 597     return 0;
 598 }
 599
 600 static void
 601 FcPatternBaseThawAll (void)
 602 {
 603     int i;
 604     FcPatternEnt        *ent, *next;
 605
 606     for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
 607     {
 608         for (ent = FcPatternHashTable[i]; ent; ent = next)
 609         {
 610             next = ent->next;
 611             free (ent);
 612         }
 613         FcPatternHashTable[i] = 0;
 614     }
 615
 616     FcPatternTotal = 0;
 617     FcPatternUsed = 0;
 618 }
 619
 620 FcPattern *
 621 FcPatternFreeze (FcPattern *p)
 622 {
 623     FcPattern   *b, *n = 0, *freeme = 0;
 624     FcPatternElt *e;
 625     int         i;
 626
 627     if (p->ref == FC_REF_CONSTANT)
 628        return p;
 629
 630     b = FcPatternCreate();
 631     if (!b)
 632         return 0;
 633
 634     b->num = p->num;
 635     b->size = b->num;
 636     b->ref = 1;
 637
 638     e = malloc(b->num * sizeof (FcPatternElt));
 639     if (!e)
 640     {
 641         FcPatternDestroy (b);
 642         return 0;
 643     }
 644     b->elts = FcPatternEltPtrCreateDynamic(e);
 645     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));
 646
 647     /*
 648      * Freeze object lists
 649      */
 650     for (i = 0; i < p->num; i++)
 651     {
 652         (FcPatternEltU(b->elts)+i)->object =
 653             (FcPatternEltU(p->elts)+i)->object;
 654         (FcPatternEltU(b->elts)+i)->values =
 655             FcValueListFreeze((FcPatternEltU(p->elts)+i)->values);
 656         if (!FcValueListPtrU((FcPatternEltU(p->elts)+i)->values))
 657         {
 658             freeme = b;
 659             goto bail;
 660         }
 661     }
 662
 663     /*
 664      * Freeze base
 665      */
 666     n = FcPatternBaseFreeze (b);
 667 #ifdef CHATTY
 668     if (FcDebug() & FC_DBG_MEMORY)
 669     {
 670         printf ("ValueLists: total %9d used %9d\n", FcValueListTotal, FcValueListUsed);
 671         printf ("Patterns:   total %9d used %9d\n", FcPatternTotal, FcPatternUsed);
 672     }
 673 #endif
 674  bail:
 675     free(FcPatternEltU(b->elts));
 676     b->elts = FcPatternEltPtrCreateDynamic(0);
 677     FcMemFree (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));
 678     b->num = -1;
 679     if (freeme)
 680         FcPatternDestroy (freeme);
 681 #ifdef DEBUG
 682     assert (FcPatternEqual (n, p));
 683 #endif
 684     return n;
 685 }
 686
 687 static int
 688 FcPatternPosition (const FcPattern *p, const char *object)
 689 {
 690     int     low, high, mid, c;
 691     FcObjectPtr obj;
 692
 693     obj = FcObjectToPtr(object);
 694     low = 0;
 695     high = p->num - 1;
 696     c = 1;
 697     mid = 0;
 698     while (low <= high)
 699     {
 700         mid = (low + high) >> 1;
 701         c = FcObjectPtrCompare((FcPatternEltU(p->elts)+mid)->object, obj);
 702         if (c == 0)
 703             return mid;
 704         if (c < 0)
 705             low = mid + 1;
 706         else
 707             high = mid - 1;
 708     }
 709     if (c < 0)
 710         mid++;
 711     return -(mid + 1);
 712 }
 713
 714 FcPatternElt *
 715 FcPatternFindElt (const FcPattern *p, const char *object)
 716 {
 717     int     i = FcPatternPosition (p, object);
 718     if (i < 0)
 719         return 0;
 720     return FcPatternEltU(p->elts)+i;
 721 }
 722
 723 FcPatternElt *
 724 FcPatternInsertElt (FcPattern *p, const char *object)
 725 {
 726     int             i;
 727     FcPatternElt   *e;
 728
 729     i = FcPatternPosition (p, object);
 730     if (i < 0)
 731     {
 732         i = -i - 1;
 733
 734         /* reallocate array */
 735         if (p->num + 1 >= p->size)
 736         {
 737             int s = p->size + 16;
 738             if (FcPatternEltU(p->elts))
 739             {
 740                 FcPatternElt *e0 = FcPatternEltU(p->elts);
 741                 e = (FcPatternElt *) realloc (e0, s * sizeof (FcPatternElt));
 742                 if (!e) /* maybe it was mmapped */
 743                 {
 744                     e = malloc(s * sizeof (FcPatternElt));
 745                     if (e)
 746                         memcpy(e, e0, p->num * sizeof (FcPatternElt));
 747                 }
 748             }
 749             else
 750                 e = (FcPatternElt *) malloc (s * sizeof (FcPatternElt));
 751             if (!e)
 752                 return FcFalse;
 753             p->elts = FcPatternEltPtrCreateDynamic(e);
 754             if (p->size)
 755                 FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
 756             FcMemAlloc (FC_MEM_PATELT, s * sizeof (FcPatternElt));
 757             while (p->size < s)
 758             {
 759                 (FcPatternEltU(p->elts)+p->size)->object = 0;
 760                 (FcPatternEltU(p->elts)+p->size)->values =
 761                     FcValueListPtrCreateDynamic(0);
 762                 p->size++;
 763             }
 764         }
 765
 766         /* move elts up */
 767         memmove (FcPatternEltU(p->elts) + i + 1,
 768                  FcPatternEltU(p->elts) + i,
 769                  sizeof (FcPatternElt) *
 770                  (p->num - i));
 771
 772         /* bump count */
 773         p->num++;
 774
 775         (FcPatternEltU(p->elts)+i)->object = FcObjectToPtr (object);
 776         (FcPatternEltU(p->elts)+i)->values = FcValueListPtrCreateDynamic(0);
 777     }
 778
 779     return FcPatternEltU(p->elts)+i;
 780 }
 781
 782 FcBool
 783 FcPatternEqual (const FcPattern *pa, const FcPattern *pb)
 784 {
 785     int i;
 786
 787     if (pa == pb)
 788         return FcTrue;
 789
 790     if (pa->num != pb->num)
 791         return FcFalse;
 792     for (i = 0; i < pa->num; i++)
 793     {
 794         if (FcObjectPtrCompare((FcPatternEltU(pa->elts)+i)->object,
 795                                (FcPatternEltU(pb->elts)+i)->object) != 0)
 796             return FcFalse;
 797         if (!FcValueListEqual ((FcPatternEltU(pa->elts)+i)->values,
 798                                (FcPatternEltU(pb->elts)+i)->values))
 799             return FcFalse;
 800     }
 801     return FcTrue;
 802 }
 803
 804 FcChar32
 805 FcPatternHash (const FcPattern *p)
 806 {
 807     int         i;
 808     FcChar32    h = 0;
 809
 810     for (i = 0; i < p->num; i++)
 811     {
 812         h = (((h << 1) | (h >> 31)) ^
 813              FcStringHash ((FcChar8 *)FcObjectPtrU ((FcPatternEltU(p->elts)+i)->object)) ^
 814              FcValueListHash ((FcPatternEltU(p->elts)+i)->values));
 815     }
 816     return h;
 817 }
 818
 819 FcBool
 820 FcPatternEqualSubset (const FcPattern *pai, const FcPattern *pbi, const FcObjectSet *os)
 821 {
 822     FcPatternElt    *ea, *eb;
 823     int             i;
 824
 825     for (i = 0; i < os->nobject; i++)
 826     {
 827         ea = FcPatternFindElt (pai, os->objects[i]);
 828         eb = FcPatternFindElt (pbi, os->objects[i]);
 829         if (ea)
 830         {
 831             if (!eb)
 832                 return FcFalse;
 833             if (!FcValueListEqual (ea->values, eb->values))
 834                 return FcFalse;
 835         }
 836         else
 837         {
 838             if (eb)
 839                 return FcFalse;
 840         }
 841     }
 842     return FcTrue;
 843 }
 844
 845 FcBool
 846 FcPatternAddWithBinding  (FcPattern         *p,
 847                           const char        *object,
 848                           FcValue           value,
 849                           FcValueBinding    binding,
 850                           FcBool            append)
 851 {
 852     FcPatternElt   *e;
 853     FcValueListPtr new, *prev;
 854     FcValueList    *newp;
 855     FcObjectPtr    objectPtr;
 856
 857     if (p->ref == FC_REF_CONSTANT)
 858         goto bail0;
 859
 860     newp = malloc (sizeof (FcValueList));
 861     if (!newp)
 862         goto bail0;
 863
 864     memset(newp, 0, sizeof (FcValueList));
 865     new = FcValueListPtrCreateDynamic(newp);
 866     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList));
 867     /* dup string */
 868     if (value.type == FcTypeString)
 869     {
 870         value.u.s = FcStrStaticName (value.u.s);
 871         if (!value.u.s)
 872             value.type = FcTypeVoid;
 873     }
 874     else
 875         value = FcValueSave (value);
 876     if (value.type == FcTypeVoid)
 877         goto bail1;
 878
 879     /* quick and dirty hack to enable FcCompareFamily/FcCompareString
 880      * speedup: only allow strings to be added under the FC_FAMILY,
 881      * FC_FOUNDRY, FC_STYLE, FC_RASTERIZER keys.
 882      * and charsets under FC_CHARSET key.
 883      * This is slightly semantically different from the old behaviour,
 884      * but fonts shouldn't be getting non-strings here anyway.
 885      * a better hack would use FcBaseObjectTypes to check all objects. */
 886     objectPtr = FcObjectToPtr(object);
 887     if ((objectPtr == FcObjectToPtr(FC_FAMILY)
 888          || objectPtr == FcObjectToPtr(FC_FOUNDRY)
 889          || objectPtr == FcObjectToPtr(FC_STYLE)
 890          || objectPtr == FcObjectToPtr(FC_RASTERIZER))
 891         && value.type != FcTypeString)
 892         goto bail1;
 893     if (objectPtr == FcObjectToPtr(FC_CHARSET)
 894         && value.type != FcTypeCharSet)
 895         goto bail1;
 896
 897     FcValueListPtrU(new)->value = value;
 898     FcValueListPtrU(new)->binding = binding;
 899     FcValueListPtrU(new)->next = FcValueListPtrCreateDynamic(0);
 900
 901     e = FcPatternInsertElt (p, object);
 902     if (!e)
 903         goto bail2;
 904
 905     if (append)
 906     {
 907         for (prev = &e->values; FcValueListPtrU(*prev); prev = &FcValueListPtrU(*prev)->next)
 908             ;
 909         *prev = new;
 910     }
 911     else
 912     {
 913         FcValueListPtrU(new)->next = e->values;
 914         e->values = new;
 915     }
 916
 917     return FcTrue;
 918
 919 bail2:
 920     switch (value.type) {
 921     case FcTypeString:
 922         FcStrFree ((FcChar8 *) value.u.s);
 923         break;
 924     case FcTypeMatrix:
 925         FcMatrixFree ((FcMatrix *) value.u.m);
 926         break;
 927     case FcTypeCharSet:
 928         FcCharSetDestroy ((FcCharSet *) value.u.c);
 929         break;
 930     case FcTypeLangSet:
 931         FcLangSetDestroy ((FcLangSet *) value.u.l);
 932         break;
 933     default:
 934         break;
 935     }
 936 bail1:
 937     FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
 938     free (FcValueListPtrU(new));
 939 bail0:
 940     return FcFalse;
 941 }
 942
 943 FcBool
 944 FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
 945 {
 946     return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
 947 }
 948
 949 FcBool
 950 FcPatternAddWeak  (FcPattern *p, const char *object, FcValue value, FcBool append)
 951 {
 952     return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
 953 }
 954
 955 FcBool
 956 FcPatternDel (FcPattern *p, const char *object)
 957 {
 958     FcPatternElt   *e;
 959
 960     e = FcPatternFindElt (p, object);
 961     if (!e)
 962         return FcFalse;
 963
 964     /* destroy value */
 965     FcValueListDestroy (e->values);
 966
 967     /* shuffle existing ones down */
 968     memmove (e, e+1,
 969              (FcPatternEltU(p->elts) + p->num - (e + 1)) *
 970              sizeof (FcPatternElt));
 971     p->num--;
 972     (FcPatternEltU(p->elts)+p->num)->object = 0;
 973     (FcPatternEltU(p->elts)+p->num)->values = FcValueListPtrCreateDynamic(0);
 974     return FcTrue;
 975 }
 976
 977 FcBool
 978 FcPatternRemove (FcPattern *p, const char *object, int id)
 979 {
 980     FcPatternElt    *e;
 981     FcValueListPtr  *prev, l;
 982
 983     e = FcPatternFindElt (p, object);
 984     if (!e)
 985         return FcFalse;
 986     for (prev = &e->values;
 987          FcValueListPtrU(l = *prev);
 988          prev = &FcValueListPtrU(l)->next)
 989     {
 990         if (!id)
 991         {
 992             *prev = FcValueListPtrU(l)->next;
 993             FcValueListPtrU(l)->next = FcValueListPtrCreateDynamic(0);
 994             FcValueListDestroy (l);
 995             if (!FcValueListPtrU(e->values))
 996                 FcPatternDel (p, object);
 997             return FcTrue;
 998         }
 999         id--;
1000     }
1001     return FcFalse;
1002 }
1003
1004 FcBool
1005 FcPatternAddInteger (FcPattern *p, const char *object, int i)
1006 {
1007     FcValue     v;
1008
1009     v.type = FcTypeInteger;
1010     v.u.i = i;
1011     return FcPatternAdd (p, object, v, FcTrue);
1012 }
1013
1014 FcBool
1015 FcPatternAddDouble (FcPattern *p, const char *object, double d)
1016 {
1017     FcValue     v;
1018
1019     v.type = FcTypeDouble;
1020     v.u.d = d;
1021     return FcPatternAdd (p, object, v, FcTrue);
1022 }
1023
1024
1025 FcBool
1026 FcPatternAddString (FcPattern *p, const char *object, const FcChar8 *s)
1027 {
1028     FcValue     v;
1029
1030     if (!s)
1031     {
1032         v.type = FcTypeVoid;
1033         v.u.s = 0;
1034         return FcPatternAdd (p, object, v, FcTrue);
1035     }
1036
1037     v.type = FcTypeString;
1038     v.u.s = FcStrStaticName(s);
1039     return FcPatternAdd (p, object, v, FcTrue);
1040 }
1041
1042 FcBool
1043 FcPatternAddMatrix (FcPattern *p, const char *object, const FcMatrix *s)
1044 {
1045     FcValue     v;
1046
1047     v.type = FcTypeMatrix;
1048     v.u.m = s;
1049     return FcPatternAdd (p, object, v, FcTrue);
1050 }
1051
1052
1053 FcBool
1054 FcPatternAddBool (FcPattern *p, const char *object, FcBool b)
1055 {
1056     FcValue     v;
1057
1058     v.type = FcTypeBool;
1059     v.u.b = b;
1060     return FcPatternAdd (p, object, v, FcTrue);
1061 }
1062
1063 FcBool
1064 FcPatternAddCharSet (FcPattern *p, const char *object, const FcCharSet *c)
1065 {
1066     FcValue     v;
1067
1068     v.type = FcTypeCharSet;
1069     v.u.c = (FcCharSet *)c;
1070     return FcPatternAdd (p, object, v, FcTrue);
1071 }
1072
1073 FcBool
1074 FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
1075 {
1076     FcValue     v;
1077
1078     v.type = FcTypeFTFace;
1079     v.u.f = (void *) f;
1080     return FcPatternAdd (p, object, v, FcTrue);
1081 }
1082
1083 FcBool
1084 FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
1085 {
1086     FcValue     v;
1087
1088     v.type = FcTypeLangSet;
1089     v.u.l = (FcLangSet *)ls;
1090     return FcPatternAdd (p, object, v, FcTrue);
1091 }
1092
1093 FcResult
1094 FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
1095 {
1096     FcPatternElt   *e;
1097     FcValueListPtr l;
1098
1099     e = FcPatternFindElt (p, object);
1100     if (!e)
1101         return FcResultNoMatch;
1102     for (l = e->values; FcValueListPtrU(l); l = FcValueListPtrU(l)->next)
1103     {
1104         if (!id)
1105         {
1106             *v = FcValueCanonicalize(&FcValueListPtrU(l)->value);
1107             return FcResultMatch;
1108         }
1109         id--;
1110     }
1111     return FcResultNoId;
1112 }
1113
1114 FcResult
1115 FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
1116 {
1117     FcValue     v;
1118     FcResult    r;
1119
1120     r = FcPatternGet (p, object, id, &v);
1121     if (r != FcResultMatch)
1122         return r;
1123     switch (v.type) {
1124     case FcTypeDouble:
1125         *i = (int) v.u.d;
1126         break;
1127     case FcTypeInteger:
1128         *i = v.u.i;
1129         break;
1130     default:
1131         return FcResultTypeMismatch;
1132     }
1133     return FcResultMatch;
1134 }
1135
1136 FcResult
1137 FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
1138 {
1139     FcValue     v;
1140     FcResult    r;
1141
1142     r = FcPatternGet (p, object, id, &v);
1143     if (r != FcResultMatch)
1144         return r;
1145     switch (v.type) {
1146     case FcTypeDouble:
1147         *d = v.u.d;
1148         break;
1149     case FcTypeInteger:
1150         *d = (double) v.u.i;
1151         break;
1152     default:
1153         return FcResultTypeMismatch;
1154     }
1155     return FcResultMatch;
1156 }
1157
1158 FcResult
1159 FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
1160 {
1161     FcValue     v;
1162     FcResult    r;
1163
1164     r = FcPatternGet (p, object, id, &v);
1165     if (r != FcResultMatch)
1166         return r;
1167     if (v.type != FcTypeString)
1168         return FcResultTypeMismatch;
1169
1170     *s = (FcChar8 *) v.u.s;
1171     return FcResultMatch;
1172 }
1173
1174 FcResult
1175 FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
1176 {
1177     FcValue     v;
1178     FcResult    r;
1179
1180     r = FcPatternGet (p, object, id, &v);
1181     if (r != FcResultMatch)
1182         return r;
1183     if (v.type != FcTypeMatrix)
1184         return FcResultTypeMismatch;
1185     *m = (FcMatrix *)v.u.m;
1186     return FcResultMatch;
1187 }
1188
1189
1190 FcResult
1191 FcPatternGetBool(const FcPattern *p, const char *object, int id, FcBool *b)
1192 {
1193     FcValue     v;
1194     FcResult    r;
1195
1196     r = FcPatternGet (p, object, id, &v);
1197     if (r != FcResultMatch)
1198         return r;
1199     if (v.type != FcTypeBool)
1200         return FcResultTypeMismatch;
1201     *b = v.u.b;
1202     return FcResultMatch;
1203 }
1204
1205 FcResult
1206 FcPatternGetCharSet(const FcPattern *p, const char *object, int id, FcCharSet **c)
1207 {
1208     FcValue     v;
1209     FcResult    r;
1210
1211     r = FcPatternGet (p, object, id, &v);
1212     if (r != FcResultMatch)
1213         return r;
1214     if (v.type != FcTypeCharSet)
1215         return FcResultTypeMismatch;
1216     *c = (FcCharSet *)v.u.c;
1217     return FcResultMatch;
1218 }
1219
1220 FcResult
1221 FcPatternGetFTFace(const FcPattern *p, const char *object, int id, FT_Face *f)
1222 {
1223     FcValue     v;
1224     FcResult    r;
1225
1226     r = FcPatternGet (p, object, id, &v);
1227     if (r != FcResultMatch)
1228         return r;
1229     if (v.type != FcTypeFTFace)
1230         return FcResultTypeMismatch;
1231     *f = (FT_Face) v.u.f;
1232     return FcResultMatch;
1233 }
1234
1235 FcResult
1236 FcPatternGetLangSet(const FcPattern *p, const char *object, int id, FcLangSet **ls)
1237 {
1238     FcValue     v;
1239     FcResult    r;
1240
1241     r = FcPatternGet (p, object, id, &v);
1242     if (r != FcResultMatch)
1243         return r;
1244     if (v.type != FcTypeLangSet)
1245         return FcResultTypeMismatch;
1246     *ls = (FcLangSet *)v.u.l;
1247     return FcResultMatch;
1248 }
1249
1250 FcPattern *
1251 FcPatternDuplicate (const FcPattern *orig)
1252 {
1253     FcPattern       *new;
1254     FcPatternElt    *e;
1255     int             i;
1256     FcValueListPtr  l;
1257
1258     new = FcPatternCreate ();
1259     if (!new)
1260         goto bail0;
1261
1262     e = FcPatternEltU(orig->elts);
1263
1264     for (i = 0; i < orig->num; i++)
1265     {
1266         for (l = (e + i)->values;
1267              FcValueListPtrU(l);
1268              l = FcValueListPtrU(l)->next)
1269             if (!FcPatternAdd (new, FcObjectPtrU((e + i)->object),
1270                                FcValueCanonicalize(&FcValueListPtrU(l)->value),
1271                                FcTrue))
1272                 goto bail1;
1273     }
1274
1275     return new;
1276
1277 bail1:
1278     FcPatternDestroy (new);
1279 bail0:
1280     return 0;
1281 }
1282
1283 void
1284 FcPatternReference (FcPattern *p)
1285 {
1286     if (p->ref != FC_REF_CONSTANT)
1287         p->ref++;
1288 }
1289
1290 FcPattern *
1291 FcPatternVaBuild (FcPattern *orig, va_list va)
1292 {
1293     FcPattern   *ret;
1294
1295     FcPatternVapBuild (ret, orig, va);
1296     return ret;
1297 }
1298
1299 FcPattern *
1300 FcPatternBuild (FcPattern *orig, ...)
1301 {
1302     va_list     va;
1303
1304     va_start (va, orig);
1305     FcPatternVapBuild (orig, orig, va);
1306     va_end (va);
1307     return orig;
1308 }
1309
1310 /*
1311  * Add all of the elements in 's' to 'p'
1312  */
1313 FcBool
1314 FcPatternAppend (FcPattern *p, FcPattern *s)
1315 {
1316     int             i;
1317     FcPatternElt    *e;
1318     FcValueListPtr  v;
1319
1320     for (i = 0; i < s->num; i++)
1321     {
1322         e = FcPatternEltU(s->elts)+i;
1323         for (v = e->values; FcValueListPtrU(v);
1324              v = FcValueListPtrU(v)->next)
1325         {
1326             if (!FcPatternAddWithBinding (p, FcObjectPtrU(e->object),
1327                                           FcValueCanonicalize(&FcValueListPtrU(v)->value),
1328                                           FcValueListPtrU(v)->binding, FcTrue))
1329                 return FcFalse;
1330         }
1331     }
1332     return FcTrue;
1333 }
1334
1335 #define OBJECT_HASH_SIZE    31
1336 static struct objectBucket {
1337     struct objectBucket *next;
1338     FcChar32            hash;
1339 } *FcObjectBuckets[OBJECT_HASH_SIZE];
1340
1341 static FcBool
1342 FcStrHashed (const FcChar8 *name)
1343 {
1344     FcChar32            hash = FcStringHash (name);
1345     struct objectBucket **p;
1346     struct objectBucket *b;
1347
1348     for (p = &FcObjectBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1349         if (b->hash == hash && !strcmp ((char *)name, (char *) (b + 1)))
1350             return FcTrue;
1351     return FcFalse;
1352 }
1353
1354 const FcChar8 *
1355 FcStrStaticName (const FcChar8 *name)
1356 {
1357     FcChar32            hash = FcStringHash (name);
1358     struct objectBucket **p;
1359     struct objectBucket *b;
1360     int                 size;
1361
1362     for (p = &FcObjectBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1363         if (b->hash == hash && !strcmp ((char *)name, (char *) (b + 1)))
1364             return (FcChar8 *) (b + 1);
1365     size = sizeof (struct objectBucket) + strlen ((char *)name) + 1;
1366     b = malloc (size + sizeof (int));
1367     /* workaround glibc bug which reads strlen in groups of 4 */
1368     FcMemAlloc (FC_MEM_STATICSTR, size + sizeof (int));
1369     if (!b)
1370         return NULL;
1371     b->next = 0;
1372     b->hash = hash;
1373     strcpy ((char *) (b + 1), (char *)name);
1374     *p = b;
1375     return (FcChar8 *) (b + 1);
1376 }
1377
1378 static void
1379 FcStrStaticNameFini (void)
1380 {
1381     int i, size;
1382     struct objectBucket *b, *next;
1383     char *name;
1384
1385     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1386     {
1387         for (b = FcObjectBuckets[i]; b; b = next)
1388         {
1389             next = b->next;
1390             name = (char *) (b + 1);
1391             size = sizeof (struct objectBucket) + strlen (name) + 1;
1392             FcMemFree (FC_MEM_STATICSTR, size);
1393             free (b);
1394         }
1395         FcObjectBuckets[i] = 0;
1396     }
1397 }
1398
1399 void
1400 FcPatternFini (void)
1401 {
1402     FcPatternBaseThawAll ();
1403     FcValueListThawAll ();
1404     FcStrStaticNameFini ();
1405     FcObjectStaticNameFini ();
1406 }
1407
1408 static FcPatternEltPtr
1409 FcPatternEltPtrCreateDynamic (FcPatternElt * e)
1410 {
1411     FcPatternEltPtr new;
1412     new.bank = FC_BANK_DYNAMIC;
1413     new.u.dyn = e;
1414     return new;
1415 }
1416
1417 static FcPatternEltPtr
1418 FcPatternEltPtrCreateStatic (int bank, int i)
1419 {
1420     FcPatternEltPtr new;
1421     new.bank = bank;
1422     new.u.stat = i;
1423     return new;
1424 }
1425
1426 static void
1427 FcStrNewBank (void);
1428 static int
1429 FcStrNeededBytes (const FcChar8 * s);
1430 static int
1431 FcStrNeededBytesAlign (void);
1432 static void *
1433 FcStrDistributeBytes (FcCache * metadata, void * block_ptr);
1434 static const FcChar8 *
1435 FcStrSerialize (int bank, const FcChar8 * s);
1436 static void *
1437 FcStrUnserialize (FcCache * metadata, void *block_ptr);
1438
1439 static void
1440 FcValueListNewBank (void);
1441 static int
1442 FcValueListNeededBytes (FcValueList * vl);
1443 static int
1444 FcValueListNeededBytesAlign (void);
1445 static void *
1446 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr);
1447 static FcValueListPtr
1448 FcValueListSerialize(int bank, FcValueList *pi);
1449 static void *
1450 FcValueListUnserialize (FcCache * metadata, void *block_ptr);
1451
1452
1453 void
1454 FcPatternNewBank (void)
1455 {
1456     fcpattern_count = 0;
1457     fcpatternelt_count = 0;
1458
1459     FcStrNewBank();
1460     FcValueListNewBank();
1461 }
1462
1463 int
1464 FcPatternNeededBytes (FcPattern * p)
1465 {
1466     int i, cum = 0, c;
1467
1468     fcpattern_count++;
1469     fcpatternelt_count += p->num;
1470
1471     for (i = 0; i < p->num; i++)
1472     {
1473         c = FcValueListNeededBytes (FcValueListPtrU
1474                                     (((FcPatternEltU(p->elts)+i)->values)));
1475         if (c < 0)
1476             return c;
1477         cum += c;
1478     }
1479
1480     return cum + sizeof (FcPattern) + sizeof(FcPatternElt)*p->num;
1481 }
1482
1483 int
1484 FcPatternNeededBytesAlign (void)
1485 {
1486     return fc_alignof (FcPattern) + fc_alignof (FcPatternElt) +
1487         FcValueListNeededBytesAlign ();
1488 }
1489
1490 static FcBool
1491 FcPatternEnsureBank (int bi)
1492 {
1493     FcPattern **pp;
1494     FcPatternElt **ep;
1495     int i;
1496
1497     if (!_fcPatterns || fcpattern_bank_count <= bi)
1498     {
1499         int new_count = bi + 4;
1500         pp = realloc (_fcPatterns, sizeof (FcPattern *) * new_count);
1501         if (!pp)
1502             return 0;
1503
1504         FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern *) * new_count);
1505         _fcPatterns = pp;
1506
1507         ep = realloc (_fcPatternElts, sizeof (FcPatternElt *) * new_count);
1508         if (!ep)
1509             return 0;
1510
1511         FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt *) * new_count);
1512         _fcPatternElts = ep;
1513
1514         for (i = fcpattern_bank_count; i < new_count; i++)
1515         {
1516             _fcPatterns[i] = 0;
1517             _fcPatternElts[i] = 0;
1518         }
1519
1520         fcpattern_bank_count = new_count;
1521     }
1522
1523     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * fcpattern_count);
1524     return FcTrue;
1525 }
1526
1527 void *
1528 FcPatternDistributeBytes (FcCache * metadata, void * block_ptr)
1529 {
1530     int bi = FcCacheBankToIndex(metadata->bank);
1531
1532     if (!FcPatternEnsureBank(bi))
1533         return 0;
1534
1535     fcpattern_ptr = 0;
1536     block_ptr = ALIGN(block_ptr, FcPattern);
1537     _fcPatterns[bi] = (FcPattern *)block_ptr;
1538     block_ptr = (void *)((char *)block_ptr +
1539                          (sizeof (FcPattern) * fcpattern_count));
1540
1541     FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt) * fcpatternelt_count);
1542     fcpatternelt_ptr = 0;
1543     block_ptr = ALIGN(block_ptr, FcPatternElt);
1544     _fcPatternElts[bi] = (FcPatternElt *)block_ptr;
1545     block_ptr = (void *)((char *)block_ptr +
1546                          (sizeof (FcPatternElt) * fcpatternelt_count));
1547
1548     metadata->pattern_count = fcpattern_count;
1549     metadata->patternelt_count = fcpatternelt_count;
1550
1551     block_ptr = FcStrDistributeBytes (metadata, block_ptr);
1552     block_ptr = FcValueListDistributeBytes (metadata, block_ptr);
1553     return block_ptr;
1554 }
1555
1556 FcPattern *
1557 FcPatternSerialize (int bank, FcPattern *old)
1558 {
1559     FcPattern *p;
1560     FcPatternElt *e, *nep;
1561     FcValueList * nv;
1562     FcValueListPtr v, nv_head, nvp;
1563     int i, elts, bi = FcCacheBankToIndex(bank);
1564
1565     p = &_fcPatterns[bi][fcpattern_ptr++];
1566     p->bank = bank;
1567     elts = fcpatternelt_ptr;
1568     nep = &_fcPatternElts[bi][elts];
1569     if (!nep)
1570         return FcFalse;
1571
1572     fcpatternelt_ptr += old->num;
1573
1574     for (e = FcPatternEltU(old->elts), i=0; i < old->num; i++, e++)
1575     {
1576         v = e->values;
1577         nvp = nv_head = FcValueListSerialize(bank, FcValueListPtrU(v));
1578         if (!FcValueListPtrU(nv_head))
1579             return 0;
1580         nv = FcValueListPtrU(nvp);
1581
1582         for (;
1583              FcValueListPtrU(v);
1584              v = FcValueListPtrU(v)->next,
1585                  nv = FcValueListPtrU(nv->next))
1586         {
1587
1588             if (FcValueListPtrU(FcValueListPtrU(v)->next))
1589             {
1590                 nvp = FcValueListSerialize
1591                     (bank, FcValueListPtrU(FcValueListPtrU(v)->next));
1592                 nv->next = nvp;
1593             }
1594         }
1595
1596         nep[i].values = nv_head;
1597         nep[i].object = e->object;
1598     }
1599
1600     p->elts = old->elts;
1601     p->elts = FcPatternEltPtrCreateStatic(bank, elts);
1602     p->size = old->num;
1603     p->num = old->num;
1604     p->ref = FC_REF_CONSTANT;
1605     return p;
1606 }
1607
1608 void *
1609 FcPatternUnserialize (FcCache * metadata, void *block_ptr)
1610 {
1611     int bi = FcCacheBankToIndex(metadata->bank);
1612     if (!FcPatternEnsureBank(bi))
1613         return FcFalse;
1614
1615     FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern) * metadata->pattern_count);
1616     block_ptr = ALIGN(block_ptr, FcPattern);
1617     _fcPatterns[bi] = (FcPattern *)block_ptr;
1618     block_ptr = (void *)((char *)block_ptr +
1619                          (sizeof (FcPattern) * metadata->pattern_count));
1620
1621     FcMemAlloc (FC_MEM_PATELT,
1622                 sizeof (FcPatternElt) * metadata->patternelt_count);
1623     block_ptr = ALIGN(block_ptr, FcPatternElt);
1624     _fcPatternElts[bi] = (FcPatternElt *)block_ptr;
1625     block_ptr = (void *)((char *)block_ptr +
1626                          (sizeof (FcPatternElt) * metadata->patternelt_count));
1627
1628     block_ptr = FcStrUnserialize (metadata, block_ptr);
1629     block_ptr = FcValueListUnserialize (metadata, block_ptr);
1630
1631     return block_ptr;
1632 }
1633
1634 static void
1635 FcValueListNewBank (void)
1636 {
1637     fcvaluelist_count = 0;
1638
1639     FcCharSetNewBank();
1640     FcLangSetNewBank();
1641 }
1642
1643 static int
1644 FcValueListNeededBytes (FcValueList *p)
1645 {
1646     FcValueList *vl;
1647     int cum = 0;
1648
1649     for (vl = p;
1650          vl;
1651          vl = FcValueListPtrU(vl->next))
1652     {
1653         /* unserialize just in case */
1654         FcValue v = FcValueCanonicalize(&vl->value);
1655
1656         switch (v.type)
1657         {
1658         case FcTypeCharSet:
1659             cum += FcCharSetNeededBytes(v.u.c);
1660             break;
1661         case FcTypeLangSet:
1662             cum += FcLangSetNeededBytes(v.u.l);
1663             break;
1664         case FcTypeString:
1665             cum += FcStrNeededBytes(v.u.s);
1666         default:
1667             break;
1668         }
1669         fcvaluelist_count++;
1670         cum += sizeof (FcValueList);
1671     }
1672
1673     return cum;
1674 }
1675
1676 static int
1677 FcValueListNeededBytesAlign (void)
1678 {
1679     return FcCharSetNeededBytesAlign() + FcLangSetNeededBytesAlign() +
1680         FcStrNeededBytesAlign() + fc_alignof (FcValueList);
1681 }
1682
1683 static FcBool
1684 FcValueListEnsureBank (int bi)
1685 {
1686     FcValueList **pvl;
1687
1688     if (!_fcValueLists || fcvaluelist_bank_count <= bi)
1689     {
1690         int new_count = bi + 2, i;
1691
1692         pvl = realloc (_fcValueLists, sizeof (FcValueList *) * new_count);
1693         if (!pvl)
1694             return FcFalse;
1695
1696         FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList *) * new_count);
1697
1698         _fcValueLists = pvl;
1699         for (i = fcvaluelist_bank_count; i < new_count; i++)
1700             _fcValueLists[i] = 0;
1701
1702         fcvaluelist_bank_count = new_count;
1703     }
1704     return FcTrue;
1705 }
1706
1707 static void *
1708 FcValueListDistributeBytes (FcCache * metadata, void *block_ptr)
1709 {
1710     int bi = FcCacheBankToIndex(metadata->bank);
1711
1712     if (!FcValueListEnsureBank(bi))
1713         return 0;
1714
1715     FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList) * fcvaluelist_count);
1716     fcvaluelist_ptr = 0;
1717     block_ptr = ALIGN(block_ptr, FcValueList);
1718     _fcValueLists[bi] = (FcValueList *)block_ptr;
1719     block_ptr = (void *)((char *)block_ptr +
1720                          (sizeof (FcValueList) * fcvaluelist_count));
1721     metadata->valuelist_count = fcvaluelist_count;
1722
1723     block_ptr = FcCharSetDistributeBytes(metadata, block_ptr);
1724     block_ptr = FcLangSetDistributeBytes(metadata, block_ptr);
1725
1726     return block_ptr;
1727 }
1728
1729 static FcValueListPtr
1730 FcValueListSerialize(int bank, FcValueList *pi)
1731 {
1732     FcValueListPtr new;
1733     FcValue * v;
1734     int bi = FcCacheBankToIndex(bank);
1735
1736     if (!pi)
1737     {
1738         new.bank = FC_BANK_DYNAMIC;
1739         new.u.dyn = 0;
1740         return new;
1741     }
1742
1743     _fcValueLists[bi][fcvaluelist_ptr] = *pi;
1744     new.bank = bank;
1745     new.u.stat = fcvaluelist_ptr++;
1746     _fcValueLists[bi][new.u.stat].value = FcValueCanonicalize (&pi->value);
1747     v = &_fcValueLists[bi][new.u.stat].value;
1748     switch (v->type)
1749     {
1750     case FcTypeString:
1751         if (v->u.s)
1752         {
1753             const FcChar8 * s = FcStrSerialize(bank, v->u.s);
1754             if (!s)
1755                 return FcValueListPtrCreateDynamic(pi);
1756             v->u.s_off = s - (const FcChar8 *)v;
1757             v->type |= FC_STORAGE_STATIC;
1758         }
1759         break;
1760     case FcTypeMatrix:
1761         break;
1762     case FcTypeCharSet:
1763         if (v->u.c)
1764         {
1765             FcCharSet * c = FcCharSetSerialize(bank, (FcCharSet *)v->u.c);
1766             if (!c)
1767                 return FcValueListPtrCreateDynamic(pi);
1768             v->u.c_off = (char *)c - (char *)v;
1769             v->type |= FC_STORAGE_STATIC;
1770         }
1771         break;
1772     case FcTypeLangSet:
1773         if (v->u.l)
1774         {
1775             FcLangSet * l = FcLangSetSerialize(bank, (FcLangSet *)v->u.l);
1776             if (!l)
1777                 return FcValueListPtrCreateDynamic(pi);
1778             v->u.l_off = (char *)l - (char *)v;
1779             v->type |= FC_STORAGE_STATIC;
1780         }
1781         break;
1782     default:
1783         break;
1784     }
1785     return new;
1786 }
1787
1788 static void *
1789 FcValueListUnserialize (FcCache * metadata, void *block_ptr)
1790 {
1791     int bi = FcCacheBankToIndex(metadata->bank);
1792
1793     if (!FcValueListEnsureBank(bi))
1794         return 0;
1795
1796     FcMemAlloc (FC_MEM_VALLIST,
1797                 sizeof (FcValueList) * metadata->valuelist_count);
1798     block_ptr = ALIGN(block_ptr, FcValueList);
1799     _fcValueLists[bi] = (FcValueList *)block_ptr;
1800     block_ptr = (void *)((char *)block_ptr +
1801                          (sizeof (FcValueList) * metadata->valuelist_count));
1802
1803     block_ptr = FcCharSetUnserialize(metadata, block_ptr);
1804     block_ptr = FcLangSetUnserialize(metadata, block_ptr);
1805
1806     return block_ptr;
1807 }
1808
1809 FcValueListPtr
1810 FcValueListPtrCreateDynamic(FcValueList * p)
1811 {
1812     FcValueListPtr r;
1813
1814     r.bank = FC_BANK_DYNAMIC;
1815     r.u.dyn = p;
1816     return r;
1817 }
1818
1819 static FcChar8 ** static_strs;
1820 static int static_str_bank_count = 0, fcstr_ptr, fcstr_count;
1821
1822 static struct objectBucket *FcStrBuckets[OBJECT_HASH_SIZE];
1823
1824 static void
1825 FcStrNewBank (void)
1826 {
1827     int i, size;
1828     struct objectBucket *b, *next;
1829     char *name;
1830
1831     for (i = 0; i < OBJECT_HASH_SIZE; i++)
1832     {
1833         for (b = FcStrBuckets[i]; b; b = next)
1834         {
1835             next = b->next;
1836             name = (char *) (b + 1);
1837             size = sizeof (struct objectBucket) + strlen (name) + 1;
1838             FcMemFree (FC_MEM_STATICSTR, size);
1839             free (b);
1840         }
1841         FcStrBuckets[i] = 0;
1842     }
1843
1844     fcstr_count = 0;
1845 }
1846
1847 static int
1848 FcStrNeededBytes (const FcChar8 * s)
1849 {
1850     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1851     struct objectBucket **p;
1852     struct objectBucket *b;
1853     int                 size;
1854     FcChar8 *const null = 0;
1855
1856     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1857         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1858             return 0;
1859     size = sizeof (struct objectBucket) + strlen ((char *)s) + 1 + sizeof(char *);
1860     b = malloc (size);
1861     FcMemAlloc (FC_MEM_STATICSTR, size);
1862     if (!b)
1863         return -1;
1864     b->next = 0;
1865     b->hash = hash;
1866     strcpy ((char *) (b + 1), (char *)s);
1867
1868     /* Yes, the following line is convoluted.  However, it is
1869      * incorrect to replace the with a memset, because the C
1870      * specification doesn't guarantee that the null pointer is
1871      * the same as the zero bit pattern. */
1872     /* Misaligned pointers are not guaranteed to work, either! */
1873     memcpy (((char *) (b + 1) + strlen((char *)s) + 1), &null, sizeof (null));
1874     *p = b;
1875
1876     fcstr_count += strlen((char *)s) + 1;
1877     return strlen((char *)s) + 1;
1878 }
1879
1880 static int
1881 FcStrNeededBytesAlign (void)
1882 {
1883     return fc_alignof (char);
1884 }
1885
1886 static FcBool
1887 FcStrEnsureBank (int bi)
1888 {
1889     FcChar8 ** ss;
1890
1891     if (!static_strs || static_str_bank_count <= bi)
1892     {
1893         int new_count = bi + 4, i;
1894         ss = realloc (static_strs, sizeof (const char *) * new_count);
1895         if (!ss)
1896             return FcFalse;
1897
1898         FcMemAlloc (FC_MEM_STRING, sizeof (const char *) * (new_count-static_str_bank_count));
1899         static_strs = ss;
1900
1901         for (i = static_str_bank_count; i < new_count; i++)
1902             static_strs[i] = 0;
1903         static_str_bank_count = new_count;
1904     }
1905     return FcTrue;
1906 }
1907
1908 static void *
1909 FcStrDistributeBytes (FcCache * metadata, void * block_ptr)
1910 {
1911     int bi = FcCacheBankToIndex(metadata->bank);
1912     if (!FcStrEnsureBank(bi))
1913         return 0;
1914
1915     FcMemAlloc (FC_MEM_STRING, sizeof (char) * fcstr_count);
1916     block_ptr = ALIGN (block_ptr, FcChar8);
1917     static_strs[bi] = (FcChar8 *)block_ptr;
1918     block_ptr = (void *)((char *)block_ptr + (sizeof (char) * fcstr_count));
1919     metadata->str_count = fcstr_count;
1920     fcstr_ptr = 0;
1921
1922     return block_ptr;
1923 }
1924
1925 static const FcChar8 *
1926 FcStrSerialize (int bank, const FcChar8 * s)
1927 {
1928     FcChar32            hash = FcStringHash ((const FcChar8 *) s);
1929     struct objectBucket **p;
1930     struct objectBucket *b;
1931     int bi = FcCacheBankToIndex(bank);
1932
1933     for (p = &FcStrBuckets[hash % OBJECT_HASH_SIZE]; (b = *p); p = &(b->next))
1934         if (b->hash == hash && !strcmp ((char *)s, (char *) (b + 1)))
1935         {
1936             FcChar8 * t;
1937             memcpy (&t, ((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1, sizeof (FcChar8 *));
1938             if (!t)
1939             {
1940                 strcpy((char *)(static_strs[bi] + fcstr_ptr), (char *)s);
1941                 t = static_strs[bi] + fcstr_ptr;
1942                 memcpy ((FcChar8 *) (b + 1) + strlen((char *)s) + 1, &t, sizeof (FcChar8 *));
1943                 fcstr_ptr += strlen((char *)s) + 1;
1944                 memcpy (&t, ((FcChar8 *)(b + 1)) + strlen ((char *)s) + 1, sizeof (FcChar8 *));
1945             }
1946             return t;
1947         }
1948     return 0;
1949 }
1950
1951 static void *
1952 FcStrUnserialize (FcCache * metadata, void *block_ptr)
1953 {
1954     int bi = FcCacheBankToIndex(metadata->bank);
1955     if (!FcStrEnsureBank(bi))
1956         return 0;
1957
1958     FcMemAlloc (FC_MEM_STRING, sizeof (char) * metadata->str_count);
1959     block_ptr = ALIGN (block_ptr, FcChar8);
1960     static_strs[bi] = (FcChar8 *)block_ptr;
1961     block_ptr = (void *)((char *)block_ptr +
1962                          (sizeof (char) * metadata->str_count));
1963
1964     return block_ptr;
1965 }