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