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