src/fccharset.c

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