src/fccharset.c

   1 /*
   2  * $RCSId: xc/lib/fontconfig/src/fccharset.c,v 1.18 2002/08/22 07:36:44 keithp Exp $
   3  *
   4  * Copyright © 2001 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 "fcint.h"
  27
  28 /* #define CHECK */
  29
  30 /* #define CHATTY */
  31
  32 static FcCharSet * charsets = 0;
  33 static FcChar16 * numbers = 0;
  34 static int charset_ptr, charset_count;
  35 static int charset_numbers_ptr, charset_numbers_count;
  36 static FcCharLeaf * leaves = 0;
  37 static int charset_leaf_ptr, charset_leaf_count;
  38 static int * leaf_idx = 0;
  39 static int charset_leaf_idx_ptr, charset_leaf_idx_count;
  40
  41 void
  42 FcCharSetClearStatic()
  43 {
  44     charsets = 0;
  45     numbers = 0;
  46     charset_ptr = 0; charset_count = 0;
  47     leaves = 0;
  48     charset_leaf_ptr = 0; charset_leaf_count = 0;
  49     leaf_idx = 0;
  50     charset_leaf_idx_ptr = 0; charset_leaf_idx_count = 0;
  51 }
  52
  53 FcCharSet *
  54 FcCharSetCreate (void)
  55 {
  56     FcCharSet   *fcs;
  57
  58     fcs = (FcCharSet *) malloc (sizeof (FcCharSet));
  59     if (!fcs)
  60         return 0;
  61     FcMemAlloc (FC_MEM_CHARSET, sizeof (FcCharSet));
  62     fcs->ref = 1;
  63     fcs->num = 0;
  64     fcs->storage = FcStorageDynamic;
  65     fcs->u.dyn.leaves = 0;
  66     fcs->u.dyn.numbers = 0;
  67     return fcs;
  68 }
  69
  70 FcCharSet *
  71 FcCharSetNew (void);
  72
  73 FcCharSet *
  74 FcCharSetNew (void)
  75 {
  76     return FcCharSetCreate ();
  77 }
  78
  79 void
  80 FcCharSetPtrDestroy (FcCharSetPtr fcs)
  81 {
  82     FcCharSetDestroy (FcCharSetPtrU(fcs));
  83     if (fcs.storage == FcStorageDynamic &&
  84         FcCharSetPtrU(fcs)->ref != FC_REF_CONSTANT)
  85     {
  86         free (fcs.u.dyn);
  87         FcMemFree (FC_MEM_CHARSET, sizeof(FcCharSet));
  88     }
  89 }
  90
  91 void
  92 FcCharSetDestroy (FcCharSet *fcs)
  93 {
  94     int i;
  95     if (fcs->ref == FC_REF_CONSTANT)
  96         return;
  97     if (--fcs->ref > 0)
  98         return;
  99     if (fcs->storage == FcStorageDynamic)
 100     {
 101         for (i = 0; i < fcs->num; i++)
 102         {
 103             FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
 104             free (fcs->u.dyn.leaves[i]);
 105         }
 106         if (fcs->u.dyn.leaves)
 107         {
 108             FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *));
 109             free (fcs->u.dyn.leaves);
 110         }
 111         if (fcs->u.dyn.numbers)
 112         {
 113             FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
 114             free (fcs->u.dyn.numbers);
 115         }
 116     }
 117     FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
 118     free (fcs);
 119 }
 120
 121 /*
 122  * Locate the leaf containing the specified char, return
 123  * its index if it exists, otherwise return negative of
 124  * the (position + 1) where it should be inserted
 125  */
 126
 127 static int
 128 FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
 129 {
 130     FcChar16            *numbers = FcCharSetGetNumbers(fcs);
 131     FcChar16            page;
 132     int                 low = 0;
 133     int                 high = fcs->num - 1;
 134
 135     if (!numbers)
 136         return -1;
 137     ucs4 >>= 8;
 138     while (low <= high)
 139     {
 140         int mid = (low + high) >> 1;
 141         page = numbers[mid];
 142         if (page == ucs4)
 143             return mid;
 144         if (page < ucs4)
 145             low = mid + 1;
 146         else
 147             high = mid - 1;
 148     }
 149     if (high < 0 || (high < fcs->num && numbers[high] < ucs4))
 150         high++;
 151     return -(high + 1);
 152 }
 153
 154 static FcCharLeaf *
 155 FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
 156 {
 157     int pos = FcCharSetFindLeafPos (fcs, ucs4);
 158     if (pos >= 0)
 159         return FcCharSetGetLeaf(fcs, pos);
 160     return 0;
 161 }
 162
 163 static FcBool
 164 FcCharSetPutLeaf (FcCharSet     *fcs,
 165                   FcChar32      ucs4,
 166                   FcCharLeaf    *leaf,
 167                   int           pos)
 168 {
 169     FcCharLeaf  **leaves;
 170     FcChar16    *numbers;
 171
 172     ucs4 >>= 8;
 173     if (ucs4 >= 0x10000)
 174         return FcFalse;
 175     if (fcs->storage == FcStorageStatic)
 176     {
 177         int i;
 178
 179         leaves = malloc ((fcs->num + 1) * sizeof (FcCharLeaf *));
 180         if (!leaves)
 181             return FcFalse;
 182         FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcCharLeaf *));
 183         numbers = malloc ((fcs->num + 1) * sizeof (FcChar16));
 184         if (!numbers)
 185             return FcFalse;
 186         FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcChar16));
 187
 188         for (i = 0; i < fcs->num; i++)
 189             leaves[i] = FcCharSetGetLeaf(fcs, i);
 190         memcpy (numbers, FcCharSetGetNumbers(fcs),
 191                 fcs->num * sizeof (FcChar16));
 192         fcs->storage = FcStorageDynamic;
 193     }
 194     else
 195     {
 196         if (!fcs->u.dyn.leaves)
 197             leaves = malloc (sizeof (FcCharLeaf *));
 198         else
 199             leaves = realloc (fcs->u.dyn.leaves, (fcs->num + 1) * sizeof (FcCharLeaf *));
 200         if (!leaves)
 201             return FcFalse;
 202         if (fcs->num)
 203             FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *));
 204         FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcCharLeaf *));
 205         fcs->u.dyn.leaves = leaves;
 206         if (!fcs->u.dyn.numbers)
 207             numbers = malloc (sizeof (FcChar16));
 208         else
 209             numbers = realloc (fcs->u.dyn.numbers, (fcs->num + 1) * sizeof (FcChar16));
 210         if (!numbers)
 211             return FcFalse;
 212         if (fcs->num)
 213             FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
 214         FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcChar16));
 215         fcs->u.dyn.numbers = numbers;
 216     }
 217
 218     memmove (fcs->u.dyn.leaves + pos + 1, fcs->u.dyn.leaves + pos,
 219              (fcs->num - pos) * sizeof (FcCharLeaf *));
 220     memmove (fcs->u.dyn.numbers + pos + 1, fcs->u.dyn.numbers + pos,
 221              (fcs->num - pos) * sizeof (FcChar16));
 222     fcs->u.dyn.numbers[pos] = (FcChar16) ucs4;
 223     fcs->u.dyn.leaves[pos] = leaf;
 224     fcs->num++;
 225     return FcTrue;
 226 }
 227
 228 /*
 229  * Locate the leaf containing the specified char, creating it
 230  * if desired
 231  */
 232
 233 FcCharLeaf *
 234 FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
 235 {
 236     int                 pos;
 237     FcCharLeaf          *leaf;
 238
 239     pos = FcCharSetFindLeafPos (fcs, ucs4);
 240     if (pos >= 0)
 241         return FcCharSetGetLeaf(fcs, pos);
 242
 243     leaf = calloc (1, sizeof (FcCharLeaf));
 244     if (!leaf)
 245         return 0;
 246
 247     pos = -pos - 1;
 248     if (!FcCharSetPutLeaf (fcs, ucs4, leaf, pos))
 249     {
 250         free (leaf);
 251         return 0;
 252     }
 253     FcMemAlloc (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
 254     return leaf;
 255 }
 256
 257 static FcBool
 258 FcCharSetInsertLeaf (FcCharSet *fcs, FcChar32 ucs4, FcCharLeaf *leaf)
 259 {
 260     int             pos;
 261
 262     pos = FcCharSetFindLeafPos (fcs, ucs4);
 263     if (pos >= 0)
 264     {
 265         FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
 266         if (fcs->storage == FcStorageDynamic)
 267         {
 268             free (fcs->u.dyn.leaves[pos]);
 269             fcs->u.dyn.leaves[pos] = leaf;
 270         }
 271         else
 272         {
 273             leaves[leaf_idx[fcs->u.stat.leafidx_offset]+pos] = *leaf;
 274         }
 275         return FcTrue;
 276     }
 277     pos = -pos - 1;
 278     return FcCharSetPutLeaf (fcs, ucs4, leaf, pos);
 279 }
 280
 281 FcBool
 282 FcCharSetAddChar (FcCharSet *fcs, FcChar32 ucs4)
 283 {
 284     FcCharLeaf  *leaf;
 285     FcChar32    *b;
 286
 287     if (fcs->ref == FC_REF_CONSTANT)
 288         return FcFalse;
 289     leaf = FcCharSetFindLeafCreate (fcs, ucs4);
 290     if (!leaf)
 291         return FcFalse;
 292     b = &leaf->map[(ucs4 & 0xff) >> 5];
 293     *b |= (1 << (ucs4 & 0x1f));
 294     return FcTrue;
 295 }
 296
 297 /*
 298  * An iterator for the leaves of a charset
 299  */
 300
 301 typedef struct _fcCharSetIter {
 302     FcCharLeaf      *leaf;
 303     FcChar32        ucs4;
 304     int             pos;
 305 } FcCharSetIter;
 306
 307 /*
 308  * Set iter->leaf to the leaf containing iter->ucs4 or higher
 309  */
 310
 311 static void
 312 FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
 313 {
 314     int             pos = FcCharSetFindLeafPos (fcs, iter->ucs4);
 315
 316     if (pos < 0)
 317     {
 318         pos = -pos - 1;
 319         if (pos == fcs->num)
 320         {
 321             iter->ucs4 = ~0;
 322             iter->leaf = 0;
 323             return;
 324         }
 325         iter->ucs4 = (FcChar32) FcCharSetGetNumbers(fcs)[pos] << 8;
 326     }
 327     iter->leaf = FcCharSetGetLeaf(fcs, pos);
 328     iter->pos = pos;
 329 #ifdef CHATTY
 330     printf ("set %08x: %08x\n", iter->ucs4, (FcChar32) iter->leaf);
 331 #endif
 332 }
 333
 334 static void
 335 FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
 336 {
 337     int pos = iter->pos + 1;
 338     if (pos >= fcs->num)
 339     {
 340         iter->ucs4 = ~0;
 341         iter->leaf = 0;
 342     }
 343     else
 344     {
 345         iter->ucs4 = (FcChar32) FcCharSetGetNumbers(fcs)[pos] << 8;
 346         iter->leaf = FcCharSetGetLeaf(fcs, pos);
 347         iter->pos = pos;
 348     }
 349 }
 350
 351 #ifdef CHATTY
 352 static void
 353 FcCharSetDump (const FcCharSet *fcs)
 354 {
 355     int         pos;
 356
 357     printf ("fcs %08x:\n", (FcChar32) fcs);
 358     for (pos = 0; pos < fcs->num; pos++)
 359     {
 360         FcCharLeaf      *leaf = fcs->leaves[pos];
 361         FcChar32        ucs4 = (FcChar32) fcs->numbers[pos] << 8;
 362
 363         printf ("    %08x: %08x\n", ucs4, (FcChar32) leaf);
 364     }
 365 }
 366 #endif
 367
 368 static void
 369 FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
 370 {
 371 #ifdef CHATTY
 372     FcCharSetDump (fcs);
 373 #endif
 374     iter->ucs4 = 0;
 375     FcCharSetIterSet (fcs, iter);
 376 }
 377
 378 FcCharSet *
 379 FcCharSetCopy (FcCharSet *src)
 380 {
 381     if (src->ref != FC_REF_CONSTANT)
 382         src->ref++;
 383     return src;
 384 }
 385
 386 FcBool
 387 FcCharSetEqual (const FcCharSet *a, const FcCharSet *b)
 388 {
 389     FcCharSetIter   ai, bi;
 390     int             i;
 391
 392     if (a == b)
 393         return FcTrue;
 394     for (FcCharSetIterStart (a, &ai), FcCharSetIterStart (b, &bi);
 395          ai.leaf && bi.leaf;
 396          FcCharSetIterNext (a, &ai), FcCharSetIterNext (b, &bi))
 397     {
 398         if (ai.ucs4 != bi.ucs4)
 399             return FcFalse;
 400         for (i = 0; i < 256/32; i++)
 401             if (ai.leaf->map[i] != bi.leaf->map[i])
 402                 return FcFalse;
 403     }
 404     return ai.leaf == bi.leaf;
 405 }
 406
 407 static FcBool
 408 FcCharSetAddLeaf (FcCharSet     *fcs,
 409                   FcChar32      ucs4,
 410                   FcCharLeaf    *leaf)
 411 {
 412     FcCharLeaf   *new = FcCharSetFindLeafCreate (fcs, ucs4);
 413     if (!new)
 414         return FcFalse;
 415     *new = *leaf;
 416     return FcTrue;
 417 }
 418
 419 static FcCharSet *
 420 FcCharSetOperate (const FcCharSet   *a,
 421                   const FcCharSet   *b,
 422                   FcBool            (*overlap) (FcCharLeaf          *result,
 423                                                 const FcCharLeaf    *al,
 424                                                 const FcCharLeaf    *bl),
 425                   FcBool        aonly,
 426                   FcBool        bonly)
 427 {
 428     FcCharSet       *fcs;
 429     FcCharSetIter   ai, bi;
 430
 431     fcs = FcCharSetCreate ();
 432     if (!fcs)
 433         goto bail0;
 434     FcCharSetIterStart (a, &ai);
 435     FcCharSetIterStart (b, &bi);
 436     while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
 437     {
 438         if (ai.ucs4 < bi.ucs4)
 439         {
 440             if (aonly)
 441             {
 442                 if (!FcCharSetAddLeaf (fcs, ai.ucs4, ai.leaf))
 443                     goto bail1;
 444                 FcCharSetIterNext (a, &ai);
 445             }
 446             else
 447             {
 448                 ai.ucs4 = bi.ucs4;
 449                 FcCharSetIterSet (a, &ai);
 450             }
 451         }
 452         else if (bi.ucs4 < ai.ucs4 )
 453         {
 454             if (bonly)
 455             {
 456                 if (!FcCharSetAddLeaf (fcs, bi.ucs4, bi.leaf))
 457                     goto bail1;
 458                 FcCharSetIterNext (b, &bi);
 459             }
 460             else
 461             {
 462                 bi.ucs4 = ai.ucs4;
 463                 FcCharSetIterSet (b, &bi);
 464             }
 465         }
 466         else
 467         {
 468             FcCharLeaf  leaf;
 469
 470             if ((*overlap) (&leaf, ai.leaf, bi.leaf))
 471             {
 472                 if (!FcCharSetAddLeaf (fcs, ai.ucs4, &leaf))
 473                     goto bail1;
 474             }
 475             FcCharSetIterNext (a, &ai);
 476             FcCharSetIterNext (b, &bi);
 477         }
 478     }
 479     return fcs;
 480 bail1:
 481     FcCharSetDestroy (fcs);
 482 bail0:
 483     return 0;
 484 }
 485
 486 static FcBool
 487 FcCharSetIntersectLeaf (FcCharLeaf *result,
 488                         const FcCharLeaf *al,
 489                         const FcCharLeaf *bl)
 490 {
 491     int     i;
 492     FcBool  nonempty = FcFalse;
 493
 494     for (i = 0; i < 256/32; i++)
 495         if ((result->map[i] = al->map[i] & bl->map[i]))
 496             nonempty = FcTrue;
 497     return nonempty;
 498 }
 499
 500 FcCharSet *
 501 FcCharSetIntersect (const FcCharSet *a, const FcCharSet *b)
 502 {
 503     return FcCharSetOperate (a, b, FcCharSetIntersectLeaf, FcFalse, FcFalse);
 504 }
 505
 506 static FcBool
 507 FcCharSetUnionLeaf (FcCharLeaf *result,
 508                     const FcCharLeaf *al,
 509                     const FcCharLeaf *bl)
 510 {
 511     int i;
 512
 513     for (i = 0; i < 256/32; i++)
 514         result->map[i] = al->map[i] | bl->map[i];
 515     return FcTrue;
 516 }
 517
 518 FcCharSet *
 519 FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
 520 {
 521     return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
 522 }
 523
 524 static FcBool
 525 FcCharSetSubtractLeaf (FcCharLeaf *result,
 526                        const FcCharLeaf *al,
 527                        const FcCharLeaf *bl)
 528 {
 529     int     i;
 530     FcBool  nonempty = FcFalse;
 531
 532     for (i = 0; i < 256/32; i++)
 533         if ((result->map[i] = al->map[i] & ~bl->map[i]))
 534             nonempty = FcTrue;
 535     return nonempty;
 536 }
 537
 538 FcCharSet *
 539 FcCharSetSubtract (const FcCharSet *a, const FcCharSet *b)
 540 {
 541     return FcCharSetOperate (a, b, FcCharSetSubtractLeaf, FcTrue, FcFalse);
 542 }
 543
 544 FcBool
 545 FcCharSetHasChar (const FcCharSet *fcs, FcChar32 ucs4)
 546 {
 547     FcCharLeaf  *leaf = FcCharSetFindLeaf (fcs, ucs4);
 548     if (!leaf)
 549         return FcFalse;
 550     return (leaf->map[(ucs4 & 0xff) >> 5] & (1 << (ucs4 & 0x1f))) != 0;
 551 }
 552
 553 static FcChar32
 554 FcCharSetPopCount (FcChar32 c1)
 555 {
 556     /* hackmem 169 */
 557     FcChar32    c2 = (c1 >> 1) & 033333333333;
 558     c2 = c1 - c2 - ((c2 >> 1) & 033333333333);
 559     return (((c2 + (c2 >> 3)) & 030707070707) % 077);
 560 }
 561
 562 FcChar32
 563 FcCharSetIntersectCount (const FcCharSet *a, const FcCharSet *b)
 564 {
 565     FcCharSetIter   ai, bi;
 566     FcChar32        count = 0;
 567
 568     FcCharSetIterStart (a, &ai);
 569     FcCharSetIterStart (b, &bi);
 570     while (ai.leaf && bi.leaf)
 571     {
 572         if (ai.ucs4 == bi.ucs4)
 573         {
 574             FcChar32    *am = ai.leaf->map;
 575             FcChar32    *bm = bi.leaf->map;
 576             int         i = 256/32;
 577             while (i--)
 578                 count += FcCharSetPopCount (*am++ & *bm++);
 579             FcCharSetIterNext (a, &ai);
 580         }
 581         else if (ai.ucs4 < bi.ucs4)
 582         {
 583             ai.ucs4 = bi.ucs4;
 584             FcCharSetIterSet (a, &ai);
 585         }
 586         if (bi.ucs4 < ai.ucs4)
 587         {
 588             bi.ucs4 = ai.ucs4;
 589             FcCharSetIterSet (b, &bi);
 590         }
 591     }
 592     return count;
 593 }
 594
 595 FcChar32
 596 FcCharSetCount (const FcCharSet *a)
 597 {
 598     FcCharSetIter   ai;
 599     FcChar32        count = 0;
 600
 601     for (FcCharSetIterStart (a, &ai); ai.leaf; FcCharSetIterNext (a, &ai))
 602     {
 603         int                 i = 256/32;
 604         FcChar32            *am = ai.leaf->map;
 605
 606         while (i--)
 607             count += FcCharSetPopCount (*am++);
 608     }
 609     return count;
 610 }
 611
 612 FcChar32
 613 FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b)
 614 {
 615     FcCharSetIter   ai, bi;
 616     FcChar32        count = 0;
 617
 618     FcCharSetIterStart (a, &ai);
 619     FcCharSetIterStart (b, &bi);
 620     while (ai.leaf)
 621     {
 622         if (ai.ucs4 <= bi.ucs4)
 623         {
 624             FcChar32    *am = ai.leaf->map;
 625             int         i = 256/32;
 626             if (ai.ucs4 == bi.ucs4)
 627             {
 628                 FcChar32        *bm = bi.leaf->map;;
 629                 while (i--)
 630                     count += FcCharSetPopCount (*am++ & ~*bm++);
 631             }
 632             else
 633             {
 634                 while (i--)
 635                     count += FcCharSetPopCount (*am++);
 636             }
 637             FcCharSetIterNext (a, &ai);
 638         }
 639         else if (bi.leaf)
 640         {
 641             bi.ucs4 = ai.ucs4;
 642             FcCharSetIterSet (b, &bi);
 643         }
 644     }
 645     return count;
 646 }
 647
 648 /*
 649  * return FcTrue iff a is a subset of b
 650  */
 651 FcBool
 652 FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
 653 {
 654     int         ai, bi;
 655     FcChar16    an, bn;
 656
 657     if (a == b) return FcTrue;
 658     bi = 0;
 659     ai = 0;
 660     while (ai < a->num && bi < b->num)
 661     {
 662         an = FcCharSetGetNumbers(a)[ai];
 663         bn = FcCharSetGetNumbers(b)[bi];
 664         /*
 665          * Check matching pages
 666          */
 667         if (an == bn)
 668         {
 669             FcChar32    *am = FcCharSetGetLeaf(a, ai)->map;
 670             FcChar32    *bm = FcCharSetGetLeaf(b, bi)->map;
 671
 672             if (am != bm)
 673             {
 674                 int     i = 256/32;
 675                 /*
 676                  * Does am have any bits not in bm?
 677                  */
 678                 while (i--)
 679                     if (*am++ & ~*bm++)
 680                         return FcFalse;
 681             }
 682             ai++;
 683             bi++;
 684         }
 685         /*
 686          * Does a have any pages not in b?
 687          */
 688         else if (an < bn)
 689             return FcFalse;
 690         else
 691         {
 692             int     low = bi + 1;
 693             int     high = b->num - 1;
 694
 695             /*
 696              * Search for page 'an' in 'b'
 697              */
 698             while (low <= high)
 699             {
 700                 int mid = (low + high) >> 1;
 701                 bn = FcCharSetGetNumbers(b)[mid];
 702                 if (bn == an)
 703                 {
 704                     high = mid;
 705                     break;
 706                 }
 707                 if (bn < an)
 708                     low = mid + 1;
 709                 else
 710                     high = mid - 1;
 711             }
 712             bi = high;
 713             while (bi < b->num && FcCharSetGetNumbers(b)[bi] < an)
 714                 bi++;
 715         }
 716     }
 717     /*
 718      * did we look at every page?
 719      */
 720     return ai >= a->num;
 721 }
 722
 723 /*
 724  * These two functions efficiently walk the entire charmap for
 725  * other software (like pango) that want their own copy
 726  */
 727
 728 FcChar32
 729 FcCharSetNextPage (const FcCharSet  *a,
 730                    FcChar32         map[FC_CHARSET_MAP_SIZE],
 731                    FcChar32         *next)
 732 {
 733     FcCharSetIter   ai;
 734     FcChar32        page;
 735
 736     ai.ucs4 = *next;
 737     FcCharSetIterSet (a, &ai);
 738     if (!ai.leaf)
 739         return FC_CHARSET_DONE;
 740
 741     /*
 742      * Save current information
 743      */
 744     page = ai.ucs4;
 745     memcpy (map, ai.leaf->map, sizeof (ai.leaf->map));
 746     /*
 747      * Step to next page
 748      */
 749     FcCharSetIterNext (a, &ai);
 750     *next = ai.ucs4;
 751
 752     return page;
 753 }
 754
 755 FcChar32
 756 FcCharSetFirstPage (const FcCharSet *a,
 757                     FcChar32        map[FC_CHARSET_MAP_SIZE],
 758                     FcChar32        *next)
 759 {
 760     *next = 0;
 761     return FcCharSetNextPage (a, map, next);
 762 }
 763
 764 /*
 765  * old coverage API, rather hard to use correctly
 766  */
 767 FcChar32
 768 FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result);
 769
 770 FcChar32
 771 FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result)
 772 {
 773     FcCharSetIter   ai;
 774
 775     ai.ucs4 = page;
 776     FcCharSetIterSet (a, &ai);
 777     if (!ai.leaf)
 778     {
 779         memset (result, '\0', 256 / 8);
 780         page = 0;
 781     }
 782     else
 783     {
 784         memcpy (result, ai.leaf->map, sizeof (ai.leaf->map));
 785         FcCharSetIterNext (a, &ai);
 786         page = ai.ucs4;
 787     }
 788     return page;
 789 }
 790
 791 /*
 792  * ASCII representation of charsets.
 793  *
 794  * Each leaf is represented as 9 32-bit values, the code of the first character followed
 795  * by 8 32 bit values for the leaf itself.  Each value is encoded as 5 ASCII characters,
 796  * only 85 different values are used to avoid control characters as well as the other
 797  * characters used to encode font names.  85**5 > 2^32 so things work out, but
 798  * it's not exactly human readable output.  As a special case, 0 is encoded as a space
 799  */
 800
 801 static const unsigned char      charToValue[256] = {
 802     /*     "" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 803     /*   "\b" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 804     /* "\020" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 805     /* "\030" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 806     /*    " " */ 0xff,  0x00,  0xff,  0x01,  0x02,  0x03,  0x04,  0xff,
 807     /*    "(" */ 0x05,  0x06,  0x07,  0x08,  0xff,  0xff,  0x09,  0x0a,
 808     /*    "0" */ 0x0b,  0x0c,  0x0d,  0x0e,  0x0f,  0x10,  0x11,  0x12,
 809     /*    "8" */ 0x13,  0x14,  0xff,  0x15,  0x16,  0xff,  0x17,  0x18,
 810     /*    "@" */ 0x19,  0x1a,  0x1b,  0x1c,  0x1d,  0x1e,  0x1f,  0x20,
 811     /*    "H" */ 0x21,  0x22,  0x23,  0x24,  0x25,  0x26,  0x27,  0x28,
 812     /*    "P" */ 0x29,  0x2a,  0x2b,  0x2c,  0x2d,  0x2e,  0x2f,  0x30,
 813     /*    "X" */ 0x31,  0x32,  0x33,  0x34,  0xff,  0x35,  0x36,  0xff,
 814     /*    "`" */ 0xff,  0x37,  0x38,  0x39,  0x3a,  0x3b,  0x3c,  0x3d,
 815     /*    "h" */ 0x3e,  0x3f,  0x40,  0x41,  0x42,  0x43,  0x44,  0x45,
 816     /*    "p" */ 0x46,  0x47,  0x48,  0x49,  0x4a,  0x4b,  0x4c,  0x4d,
 817     /*    "x" */ 0x4e,  0x4f,  0x50,  0x51,  0x52,  0x53,  0x54,  0xff,
 818     /* "\200" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 819     /* "\210" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 820     /* "\220" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 821     /* "\230" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 822     /* "\240" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 823     /* "\250" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 824     /* "\260" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 825     /* "\270" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 826     /* "\300" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 827     /* "\310" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 828     /* "\320" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 829     /* "\330" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 830     /* "\340" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 831     /* "\350" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 832     /* "\360" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 833     /* "\370" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 834 };
 835
 836 static const FcChar8 valueToChar[0x55] = {
 837     /* 0x00 */ '!', '#', '$', '%', '&', '(', ')', '*',
 838     /* 0x08 */ '+', '.', '/', '0', '1', '2', '3', '4',
 839     /* 0x10 */ '5', '6', '7', '8', '9', ';', '<', '>',
 840     /* 0x18 */ '?', '@', 'A', 'B', 'C', 'D', 'E', 'F',
 841     /* 0x20 */ 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
 842     /* 0x28 */ 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
 843     /* 0x30 */ 'W', 'X', 'Y', 'Z', '[', ']', '^', 'a',
 844     /* 0x38 */ 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
 845     /* 0x40 */ 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q',
 846     /* 0x48 */ 'r', 's', 't', 'u', 'v', 'w', 'x', 'y',
 847     /* 0x50 */ 'z', '{', '|', '}', '~',
 848 };
 849
 850 static FcChar8 *
 851 FcCharSetParseValue (FcChar8 *string, FcChar32 *value)
 852 {
 853     int         i;
 854     FcChar32    v;
 855     FcChar32    c;
 856
 857     if (*string == ' ')
 858     {
 859         v = 0;
 860         string++;
 861     }
 862     else
 863     {
 864         v = 0;
 865         for (i = 0; i < 5; i++)
 866         {
 867             if (!(c = (FcChar32) (unsigned char) *string++))
 868                 return 0;
 869             c = charToValue[c];
 870             if (c == 0xff)
 871                 return 0;
 872             v = v * 85 + c;
 873         }
 874     }
 875     *value = v;
 876     return string;
 877 }
 878
 879 static FcBool
 880 FcCharSetUnparseValue (FcStrBuf *buf, FcChar32 value)
 881 {
 882     int     i;
 883     if (value == 0)
 884     {
 885         return FcStrBufChar (buf, ' ');
 886     }
 887     else
 888     {
 889         FcChar8 string[6];
 890         FcChar8 *s = string + 5;
 891         string[5] = '\0';
 892         for (i = 0; i < 5; i++)
 893         {
 894             *--s = valueToChar[value % 85];
 895             value /= 85;
 896         }
 897         for (i = 0; i < 5; i++)
 898             if (!FcStrBufChar (buf, *s++))
 899                 return FcFalse;
 900     }
 901     return FcTrue;
 902 }
 903
 904 typedef struct _FcCharLeafEnt FcCharLeafEnt;
 905
 906 struct _FcCharLeafEnt {
 907     FcCharLeafEnt   *next;
 908     FcChar32        hash;
 909     FcCharLeaf      leaf;
 910 };
 911
 912 #define FC_CHAR_LEAF_BLOCK      (4096 / sizeof (FcCharLeafEnt))
 913 static FcCharLeafEnt **FcCharLeafBlocks;
 914 static int FcCharLeafBlockCount;
 915
 916 static FcCharLeafEnt *
 917 FcCharLeafEntCreate (void)
 918 {
 919     static FcCharLeafEnt    *block;
 920     static int              remain;
 921
 922     if (!remain)
 923     {
 924         FcCharLeafEnt **newBlocks;
 925
 926         FcCharLeafBlockCount++;
 927         newBlocks = realloc (FcCharLeafBlocks, FcCharLeafBlockCount * sizeof (FcCharLeafEnt *));
 928         if (!newBlocks)
 929             return 0;
 930         FcCharLeafBlocks = newBlocks;
 931         block = FcCharLeafBlocks[FcCharLeafBlockCount-1] = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
 932         if (!block)
 933             return 0;
 934         FcMemAlloc (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
 935         remain = FC_CHAR_LEAF_BLOCK;
 936     }
 937     remain--;
 938     return block++;
 939 }
 940
 941 #define FC_CHAR_LEAF_HASH_SIZE  257
 942
 943 static FcChar32
 944 FcCharLeafHash (FcCharLeaf *leaf)
 945 {
 946     FcChar32    hash = 0;
 947     int         i;
 948
 949     for (i = 0; i < 256/32; i++)
 950         hash = ((hash << 1) | (hash >> 31)) ^ leaf->map[i];
 951     return hash;
 952 }
 953
 954 static int      FcCharLeafTotal;
 955 static int      FcCharLeafUsed;
 956
 957 static FcCharLeafEnt    *FcCharLeafHashTable[FC_CHAR_LEAF_HASH_SIZE];
 958
 959 static FcCharLeaf *
 960 FcCharSetFreezeLeaf (FcCharLeaf *leaf)
 961 {
 962     FcChar32                    hash = FcCharLeafHash (leaf);
 963     FcCharLeafEnt               **bucket = &FcCharLeafHashTable[hash % FC_CHAR_LEAF_HASH_SIZE];
 964     FcCharLeafEnt               *ent;
 965
 966     FcCharLeafTotal++;
 967     for (ent = *bucket; ent; ent = ent->next)
 968     {
 969         if (ent->hash == hash && !memcmp (&ent->leaf, leaf, sizeof (FcCharLeaf)))
 970             return &ent->leaf;
 971     }
 972
 973     ent = FcCharLeafEntCreate();
 974     if (!ent)
 975         return 0;
 976     FcCharLeafUsed++;
 977     ent->leaf = *leaf;
 978     ent->hash = hash;
 979     ent->next = *bucket;
 980     *bucket = ent;
 981     return &ent->leaf;
 982 }
 983
 984 static void
 985 FcCharSetThawAllLeaf (void)
 986 {
 987     int i;
 988
 989     for (i = 0; i < FC_CHAR_LEAF_HASH_SIZE; i++)
 990         FcCharLeafHashTable[i] = 0;
 991
 992     FcCharLeafTotal = 0;
 993     FcCharLeafUsed = 0;
 994
 995     for (i = 0; i < FcCharLeafBlockCount; i++)
 996         free (FcCharLeafBlocks[i]);
 997
 998     free (FcCharLeafBlocks);
 999     FcCharLeafBlocks = 0;
1000     FcCharLeafBlockCount = 0;
1001 }
1002
1003 typedef struct _FcCharSetEnt FcCharSetEnt;
1004
1005 struct _FcCharSetEnt {
1006     FcCharSetEnt        *next;
1007     FcChar32            hash;
1008     FcCharSet           set;
1009 };
1010
1011 #define FC_CHAR_SET_HASH_SIZE    67
1012
1013 static FcChar32
1014 FcCharSetHash (FcCharSet *fcs)
1015 {
1016     FcChar32    hash = 0;
1017     int         i;
1018
1019     /* hash in leaves */
1020     for (i = 0; i < fcs->num * sizeof (FcCharLeaf *) / sizeof (FcChar32); i++)
1021         hash = ((hash << 1) | (hash >> 31)) ^ (FcChar32)(FcCharSetGetLeaf(fcs, i)->map);
1022     /* hash in numbers */
1023     for (i = 0; i < fcs->num; i++)
1024         hash = ((hash << 1) | (hash >> 31)) ^ *FcCharSetGetNumbers(fcs);
1025     return hash;
1026 }
1027
1028 static int      FcCharSetTotal;
1029 static int      FcCharSetUsed;
1030 static int      FcCharSetTotalEnts, FcCharSetUsedEnts;
1031
1032 static FcCharSetEnt     *FcCharSetHashTable[FC_CHAR_SET_HASH_SIZE];
1033
1034 static FcCharSet *
1035 FcCharSetFreezeBase (FcCharSet *fcs)
1036 {
1037     FcChar32            hash = FcCharSetHash (fcs);
1038     FcCharSetEnt        **bucket = &FcCharSetHashTable[hash % FC_CHAR_SET_HASH_SIZE];
1039     FcCharSetEnt        *ent;
1040     int                 size;
1041
1042     FcCharSetTotal++;
1043     FcCharSetTotalEnts += fcs->num;
1044     for (ent = *bucket; ent; ent = ent->next)
1045     {
1046         if (ent->hash == hash &&
1047             ent->set.num == fcs->num &&
1048             !memcmp (FcCharSetGetNumbers(&ent->set),
1049                      FcCharSetGetNumbers(fcs),
1050                      fcs->num * sizeof (FcChar16)))
1051         {
1052             FcBool ok = FcTrue;
1053             int i;
1054
1055             for (i = 0; i < fcs->num; i++)
1056                 if (FcCharSetGetLeaf(&ent->set, i) != FcCharSetGetLeaf(fcs, i))
1057                     ok = FcFalse;
1058             if (ok)
1059                 return &ent->set;
1060         }
1061     }
1062
1063     size = (sizeof (FcCharSetEnt) +
1064             fcs->num * sizeof (FcCharLeaf *) +
1065             fcs->num * sizeof (FcChar16));
1066     ent = malloc (size);
1067     if (!ent)
1068         return 0;
1069     FcMemAlloc (FC_MEM_CHARSET, size);
1070     FcCharSetUsed++;
1071     FcCharSetUsedEnts += fcs->num;
1072
1073     ent->set.ref = FC_REF_CONSTANT;
1074     ent->set.num = fcs->num;
1075     ent->set.storage = fcs->storage;
1076     if (fcs->storage == FcStorageDynamic)
1077     {
1078         if (fcs->num)
1079         {
1080             ent->set.u.dyn.leaves = (FcCharLeaf **) (ent + 1);
1081             ent->set.u.dyn.numbers = (FcChar16 *) (ent->set.u.dyn.leaves + fcs->num);
1082             memcpy (ent->set.u.dyn.leaves, fcs->u.dyn.leaves, fcs->num * sizeof (FcCharLeaf *));
1083             memcpy (ent->set.u.dyn.numbers, fcs->u.dyn.numbers, fcs->num * sizeof (FcChar16));
1084         }
1085         else
1086         {
1087             ent->set.u.dyn.leaves = 0;
1088             ent->set.u.dyn.numbers = 0;
1089         }
1090     }
1091     else
1092     {
1093         ent->set.u.stat.leafidx_offset = fcs->u.stat.leafidx_offset;
1094         ent->set.u.stat.numbers_offset = fcs->u.stat.numbers_offset;
1095     }
1096
1097     ent->hash = hash;
1098     ent->next = *bucket;
1099     *bucket = ent;
1100     return &ent->set;
1101 }
1102
1103 void
1104 FcCharSetThawAll (void)
1105 {
1106     int i;
1107     FcCharSetEnt        *ent, *next;
1108
1109     for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1110     {
1111         for (ent = FcCharSetHashTable[i]; ent; ent = next)
1112         {
1113             next = ent->next;
1114             free (ent);
1115         }
1116         FcCharSetHashTable[i] = 0;
1117     }
1118
1119     FcCharSetTotal = 0;
1120     FcCharSetTotalEnts = 0;
1121     FcCharSetUsed = 0;
1122     FcCharSetUsedEnts = 0;
1123
1124     FcCharSetThawAllLeaf ();
1125 }
1126
1127 FcCharSet *
1128 FcCharSetFreeze (FcCharSet *fcs)
1129 {
1130     FcCharSet   *b;
1131     FcCharSet   *n = 0;
1132     FcCharLeaf  *l;
1133     int         i;
1134
1135     b = FcCharSetCreate ();
1136     if (!b)
1137         goto bail0;
1138     for (i = 0; i < fcs->num; i++)
1139     {
1140         l = FcCharSetFreezeLeaf (FcCharSetGetLeaf(fcs, i));
1141         if (!l)
1142             goto bail1;
1143         if (!FcCharSetInsertLeaf (b, FcCharSetGetNumbers(fcs)[i] << 8, l))
1144             goto bail1;
1145     }
1146     n = FcCharSetFreezeBase (b);
1147 bail1:
1148     if (b->storage == FcStorageDynamic)
1149     {
1150         if (b->u.dyn.leaves)
1151         {
1152             FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcCharLeaf *));
1153             free (b->u.dyn.leaves);
1154         }
1155         if (b->u.dyn.numbers)
1156         {
1157             FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcChar16));
1158             free (b->u.dyn.numbers);
1159         }
1160     }
1161     FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
1162     free (b);
1163 bail0:
1164     return n;
1165 }
1166
1167 FcCharSet *
1168 FcNameParseCharSet (FcChar8 *string)
1169 {
1170     FcCharSet   *c, *n = 0;
1171     FcChar32    ucs4;
1172     FcCharLeaf  *leaf;
1173     FcCharLeaf  temp;
1174     FcChar32    bits;
1175     int         i;
1176
1177     c = FcCharSetCreate ();
1178     if (!c)
1179         goto bail0;
1180     while (*string)
1181     {
1182         string = FcCharSetParseValue (string, &ucs4);
1183         if (!string)
1184             goto bail1;
1185         bits = 0;
1186         for (i = 0; i < 256/32; i++)
1187         {
1188             string = FcCharSetParseValue (string, &temp.map[i]);
1189             if (!string)
1190                 goto bail1;
1191             bits |= temp.map[i];
1192         }
1193         if (bits)
1194         {
1195             leaf = FcCharSetFreezeLeaf (&temp);
1196             if (!leaf)
1197                 goto bail1;
1198             if (!FcCharSetInsertLeaf (c, ucs4, leaf))
1199                 goto bail1;
1200         }
1201     }
1202 #ifdef CHATTY
1203     printf ("          %8s %8s %8s %8s\n", "total", "totalmem", "new", "newmem");
1204     printf ("Leaves:   %8d %8d %8d %8d\n",
1205             FcCharLeafTotal, sizeof (FcCharLeaf) * FcCharLeafTotal,
1206             FcCharLeafUsed, sizeof (FcCharLeaf) * FcCharLeafUsed);
1207     printf ("Charsets: %8d %8d %8d %8d\n",
1208             FcCharSetTotal, sizeof (FcCharSet) * FcCharSetTotal,
1209             FcCharSetUsed, sizeof (FcCharSet) * FcCharSetUsed);
1210     printf ("Tables:   %8d %8d %8d %8d\n",
1211             FcCharSetTotalEnts, FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
1212             FcCharSetUsedEnts, FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
1213     printf ("Total:    %8s %8d %8s %8d\n",
1214             "",
1215             sizeof (FcCharLeaf) * FcCharLeafTotal +
1216             sizeof (FcCharSet) * FcCharSetTotal +
1217             FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
1218             "",
1219             sizeof (FcCharLeaf) * FcCharLeafUsed +
1220             sizeof (FcCharSet) * FcCharSetUsed +
1221             FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
1222 #endif
1223     n = FcCharSetFreezeBase (c);
1224 bail1:
1225     if (c->storage == FcStorageDynamic)
1226     {
1227         if (c->u.dyn.leaves)
1228         {
1229             FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcCharLeaf *));
1230             free (c->u.dyn.leaves);
1231         }
1232         if (c->u.dyn.numbers)
1233         {
1234             FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcChar16));
1235             free (c->u.dyn.numbers);
1236         }
1237         FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
1238     }
1239     free (c);
1240 bail0:
1241     return n;
1242 }
1243
1244 FcBool
1245 FcNameUnparseCharSet (FcStrBuf *buf, const FcCharSet *c)
1246 {
1247     FcCharSetIter   ci;
1248     int             i;
1249 #ifdef CHECK
1250     int             len = buf->len;
1251 #endif
1252
1253     for (FcCharSetIterStart (c, &ci);
1254          ci.leaf;
1255          FcCharSetIterNext (c, &ci))
1256     {
1257         if (!FcCharSetUnparseValue (buf, ci.ucs4))
1258             return FcFalse;
1259         for (i = 0; i < 256/32; i++)
1260             if (!FcCharSetUnparseValue (buf, ci.leaf->map[i]))
1261                 return FcFalse;
1262     }
1263 #ifdef CHECK
1264     {
1265         FcCharSet       *check;
1266         FcChar32        missing;
1267         FcCharSetIter   ci, checki;
1268
1269         /* null terminate for parser */
1270         FcStrBufChar (buf, '\0');
1271         /* step back over null for life after test */
1272         buf->len--;
1273         check = FcNameParseCharSet (buf->buf + len);
1274         FcCharSetIterStart (c, &ci);
1275         FcCharSetIterStart (check, &checki);
1276         while (ci.leaf || checki.leaf)
1277         {
1278             if (ci.ucs4 < checki.ucs4)
1279             {
1280                 printf ("Missing leaf node at 0x%x\n", ci.ucs4);
1281                 FcCharSetIterNext (c, &ci);
1282             }
1283             else if (checki.ucs4 < ci.ucs4)
1284             {
1285                 printf ("Extra leaf node at 0x%x\n", checki.ucs4);
1286                 FcCharSetIterNext (check, &checki);
1287             }
1288             else
1289             {
1290                 int         i = 256/32;
1291                 FcChar32    *cm = ci.leaf->map;
1292                 FcChar32    *checkm = checki.leaf->map;
1293
1294                 for (i = 0; i < 256; i += 32)
1295                 {
1296                     if (*cm != *checkm)
1297                         printf ("Mismatching sets at 0x%08x: 0x%08x != 0x%08x\n",
1298                                 ci.ucs4 + i, *cm, *checkm);
1299                     cm++;
1300                     checkm++;
1301                 }
1302                 FcCharSetIterNext (c, &ci);
1303                 FcCharSetIterNext (check, &checki);
1304             }
1305         }
1306         if ((missing = FcCharSetSubtractCount (c, check)))
1307             printf ("%d missing in reparsed result\n", missing);
1308         if ((missing = FcCharSetSubtractCount (check, c)))
1309             printf ("%d extra in reparsed result\n", missing);
1310         FcCharSetDestroy (check);
1311     }
1312 #endif
1313
1314     return FcTrue;
1315 }
1316
1317
1318 FcCharSet *
1319 FcCharSetPtrU (FcCharSetPtr ci)
1320 {
1321     switch (ci.storage)
1322     {
1323     case FcStorageDynamic:
1324         return ci.u.dyn;
1325     case FcStorageStatic:
1326         return &charsets[ci.u.stat];
1327     default:
1328         return 0;
1329     }
1330 }
1331
1332 FcCharSetPtr
1333 FcCharSetPtrCreateDynamic(FcCharSet *c)
1334 {
1335     FcCharSetPtr new;
1336
1337     new.storage = FcStorageDynamic;
1338     new.u.dyn = c;
1339     return new;
1340 }
1341
1342 FcBool
1343 FcCharSetPrepareSerialize(FcCharSet *c)
1344 {
1345     /* note the redundancy */
1346     charset_count++;
1347     charset_leaf_idx_count++;
1348     charset_leaf_count += c->num;
1349     charset_numbers_count += c->num;
1350     return FcTrue;
1351 }
1352
1353 FcCharSetPtr
1354 FcCharSetSerialize(FcCharSet *c)
1355 {
1356     int i;
1357     FcCharSetPtr newp;
1358     FcCharSet new;
1359
1360     if (!charsets)
1361     {
1362         charsets = malloc(sizeof(FcCharSet) * charset_count);
1363         if (!charsets) goto bail;
1364         numbers = malloc(sizeof(FcChar16) * charset_numbers_count);
1365         if (!numbers) goto bail1;
1366         leaves = malloc(sizeof(FcCharLeaf) * charset_leaf_count);
1367         if (!leaves) goto bail2;
1368         leaf_idx = malloc(sizeof(int)*charset_leaf_idx_count);
1369         if (!leaf_idx) goto bail3;
1370     }
1371
1372     new.ref = c->ref;
1373     new.storage = FcStorageStatic;
1374     new.u.stat.leafidx_offset = charset_leaf_ptr;
1375     new.u.stat.numbers_offset = charset_numbers_ptr;
1376
1377     newp.storage = FcStorageStatic;
1378     newp.u.stat = charset_ptr;
1379     charsets[charset_ptr++] = new;
1380
1381     leaf_idx[charset_leaf_idx_ptr++] = charset_leaf_ptr;
1382     for (i = 0; i < c->num; i++)
1383     {
1384         memcpy (&leaves[charset_leaf_ptr++],
1385                 c->u.dyn.leaves[i], sizeof(FcCharLeaf));
1386         numbers[charset_numbers_ptr++] = c->u.dyn.numbers[i];
1387     }
1388
1389     return newp;
1390
1391  bail3:
1392     free (leaves);
1393  bail2:
1394     free (numbers);
1395  bail1:
1396     free (charsets);
1397  bail:
1398     return FcCharSetPtrCreateDynamic(0);
1399 }
1400
1401 FcCharLeaf *
1402 FcCharSetGetLeaf(const FcCharSet *c, int i)
1403 {
1404     switch (c->storage)
1405     {
1406     case FcStorageDynamic:
1407         return c->u.dyn.leaves[i];
1408     case FcStorageStatic:
1409         return &leaves[leaf_idx[c->u.stat.leafidx_offset]+i];
1410     default:
1411         return 0;
1412     }
1413 }
1414
1415 FcChar16 *
1416 FcCharSetGetNumbers(const FcCharSet *c)
1417 {
1418     switch (c->storage)
1419     {
1420     case FcStorageDynamic:
1421         return c->u.dyn.numbers;
1422     case FcStorageStatic:
1423         return &numbers[c->u.stat.numbers_offset];
1424     default:
1425         return 0;
1426     }
1427 }
1428