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 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  * 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         FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (intptr_t));
  72         free (FcCharSetLeaves (fcs));
  73     }
  74     if (fcs->num)
  75     {
  76         FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
  77         free (FcCharSetNumbers (fcs));
  78     }
  79     FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
  80     free (fcs);
  81 }
  82
  83 /*
  84  * Search for the leaf containing with the specified num.
  85  * Return its index if it exists, otherwise return negative of
  86  * the (position + 1) where it should be inserted
  87  */
  88
  89
  90 static int
  91 FcCharSetFindLeafForward (const FcCharSet *fcs, int start, FcChar16 num)
  92 {
  93     FcChar16            *numbers = FcCharSetNumbers(fcs);
  94     FcChar16            page;
  95     int                 low = start;
  96     int                 high = fcs->num - 1;
  97
  98     if (!numbers)
  99         return -1;
 100     while (low <= high)
 101     {
 102         int mid = (low + high) >> 1;
 103         page = numbers[mid];
 104         if (page == num)
 105             return mid;
 106         if (page < num)
 107             low = mid + 1;
 108         else
 109             high = mid - 1;
 110     }
 111     if (high < 0 || (high < fcs->num && numbers[high] < num))
 112         high++;
 113     return -(high + 1);
 114 }
 115
 116 /*
 117  * Locate the leaf containing the specified char, return
 118  * its index if it exists, otherwise return negative of
 119  * the (position + 1) where it should be inserted
 120  */
 121
 122 static int
 123 FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
 124 {
 125     return FcCharSetFindLeafForward (fcs, 0, ucs4 >> 8);
 126 }
 127
 128 static FcCharLeaf *
 129 FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
 130 {
 131     int pos = FcCharSetFindLeafPos (fcs, ucs4);
 132     if (pos >= 0)
 133         return FcCharSetLeaf(fcs, pos);
 134     return 0;
 135 }
 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     /* XXX We can't handle Unicode values in Plane 16 */
 147     ucs4 >>= 8;
 148     if (ucs4 >= 0x10000)
 149         return FcFalse;
 150
 151     if (fcs->num == fcs->alloced)
 152     {
 153         intptr_t    *new_leaves = realloc (leaves, (fcs->num + 1) *
 154                                            sizeof (*leaves));
 155         intptr_t    distance = (intptr_t) new_leaves - (intptr_t) leaves;
 156
 157         if (new_leaves && distance)
 158         {
 159             int i;
 160
 161             for (i = 0; i < fcs->num; i++)
 162                 new_leaves[i] -= distance;
 163         }
 164         leaves = new_leaves;
 165     }
 166     if (!leaves)
 167         return FcFalse;
 168
 169     if (fcs->num)
 170         FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (intptr_t));
 171     FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (intptr_t));
 172     fcs->leaves_offset = FcPtrToOffset (fcs, leaves);
 173
 174     if (!fcs->num)
 175         numbers = malloc (sizeof (FcChar16));
 176     else
 177         numbers = realloc (numbers, (fcs->num + 1) * sizeof (FcChar16));
 178     if (!numbers)
 179         return FcFalse;
 180
 181     if (fcs->num)
 182         FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
 183     FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcChar16));
 184     fcs->numbers_offset = FcPtrToOffset (fcs, numbers);
 185
 186     memmove (leaves + pos + 1, leaves + pos,
 187              (fcs->num - pos) * sizeof (*leaves));
 188     memmove (numbers + pos + 1, numbers + pos,
 189              (fcs->num - pos) * sizeof (*numbers));
 190     numbers[pos] = (FcChar16) ucs4;
 191     leaves[pos] = FcPtrToOffset (leaves, leaf);
 192     fcs->num++;
 193     return FcTrue;
 194 }
 195
 196 /*
 197  * Locate the leaf containing the specified char, creating it
 198  * if desired
 199  */
 200
 201 FcCharLeaf *
 202 FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
 203 {
 204     int                 pos;
 205     FcCharLeaf          *leaf;
 206
 207     pos = FcCharSetFindLeafPos (fcs, ucs4);
 208     if (pos >= 0)
 209         return FcCharSetLeaf(fcs, pos);
 210
 211     leaf = calloc (1, sizeof (FcCharLeaf));
 212     if (!leaf)
 213         return 0;
 214
 215     pos = -pos - 1;
 216     if (!FcCharSetPutLeaf (fcs, ucs4, leaf, pos))
 217     {
 218         free (leaf);
 219         return 0;
 220     }
 221     FcMemAlloc (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
 222     return leaf;
 223 }
 224
 225 static FcBool
 226 FcCharSetInsertLeaf (FcCharSet *fcs, FcChar32 ucs4, FcCharLeaf *leaf)
 227 {
 228     int             pos;
 229
 230     pos = FcCharSetFindLeafPos (fcs, ucs4);
 231     if (pos >= 0)
 232     {
 233         FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
 234         free (FcCharSetLeaf (fcs, pos));
 235         FcCharSetLeaves(fcs)[pos] = FcPtrToOffset (FcCharSetLeaves(fcs),
 236                                                    leaf);
 237         return FcTrue;
 238     }
 239     pos = -pos - 1;
 240     return FcCharSetPutLeaf (fcs, ucs4, leaf, pos);
 241 }
 242
 243 FcBool
 244 FcCharSetAddChar (FcCharSet *fcs, FcChar32 ucs4)
 245 {
 246     FcCharLeaf  *leaf;
 247     FcChar32    *b;
 248
 249     if (fcs->ref == FC_REF_CONSTANT)
 250         return FcFalse;
 251     leaf = FcCharSetFindLeafCreate (fcs, ucs4);
 252     if (!leaf)
 253         return FcFalse;
 254     b = &leaf->map[(ucs4 & 0xff) >> 5];
 255     *b |= (1 << (ucs4 & 0x1f));
 256     return FcTrue;
 257 }
 258
 259 /*
 260  * An iterator for the leaves of a charset
 261  */
 262
 263 typedef struct _fcCharSetIter {
 264     FcCharLeaf      *leaf;
 265     FcChar32        ucs4;
 266     int             pos;
 267 } FcCharSetIter;
 268
 269 /*
 270  * Set iter->leaf to the leaf containing iter->ucs4 or higher
 271  */
 272
 273 static void
 274 FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
 275 {
 276     int             pos = FcCharSetFindLeafPos (fcs, iter->ucs4);
 277
 278     if (pos < 0)
 279     {
 280         pos = -pos - 1;
 281         if (pos == fcs->num)
 282         {
 283             iter->ucs4 = ~0;
 284             iter->leaf = 0;
 285             return;
 286         }
 287         iter->ucs4 = (FcChar32) FcCharSetNumbers(fcs)[pos] << 8;
 288     }
 289     iter->leaf = FcCharSetLeaf(fcs, pos);
 290     iter->pos = pos;
 291 }
 292
 293 static void
 294 FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
 295 {
 296     int pos = iter->pos + 1;
 297     if (pos >= fcs->num)
 298     {
 299         iter->ucs4 = ~0;
 300         iter->leaf = 0;
 301     }
 302     else
 303     {
 304         iter->ucs4 = (FcChar32) FcCharSetNumbers(fcs)[pos] << 8;
 305         iter->leaf = FcCharSetLeaf(fcs, pos);
 306         iter->pos = pos;
 307     }
 308 }
 309
 310
 311 static void
 312 FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
 313 {
 314     iter->ucs4 = 0;
 315     iter->pos = 0;
 316     FcCharSetIterSet (fcs, iter);
 317 }
 318
 319 FcCharSet *
 320 FcCharSetCopy (FcCharSet *src)
 321 {
 322     if (src->ref != FC_REF_CONSTANT)
 323         src->ref++;
 324     else
 325         FcCacheObjectReference (src);
 326     return src;
 327 }
 328
 329 FcBool
 330 FcCharSetEqual (const FcCharSet *a, const FcCharSet *b)
 331 {
 332     FcCharSetIter   ai, bi;
 333     int             i;
 334
 335     if (a == b)
 336         return FcTrue;
 337     for (FcCharSetIterStart (a, &ai), FcCharSetIterStart (b, &bi);
 338          ai.leaf && bi.leaf;
 339          FcCharSetIterNext (a, &ai), FcCharSetIterNext (b, &bi))
 340     {
 341         if (ai.ucs4 != bi.ucs4)
 342             return FcFalse;
 343         for (i = 0; i < 256/32; i++)
 344             if (ai.leaf->map[i] != bi.leaf->map[i])
 345                 return FcFalse;
 346     }
 347     return ai.leaf == bi.leaf;
 348 }
 349
 350 static FcBool
 351 FcCharSetAddLeaf (FcCharSet     *fcs,
 352                   FcChar32      ucs4,
 353                   FcCharLeaf    *leaf)
 354 {
 355     FcCharLeaf   *new = FcCharSetFindLeafCreate (fcs, ucs4);
 356     if (!new)
 357         return FcFalse;
 358     *new = *leaf;
 359     return FcTrue;
 360 }
 361
 362 static FcCharSet *
 363 FcCharSetOperate (const FcCharSet   *a,
 364                   const FcCharSet   *b,
 365                   FcBool            (*overlap) (FcCharLeaf          *result,
 366                                                 const FcCharLeaf    *al,
 367                                                 const FcCharLeaf    *bl),
 368                   FcBool        aonly,
 369                   FcBool        bonly)
 370 {
 371     FcCharSet       *fcs;
 372     FcCharSetIter   ai, bi;
 373
 374     fcs = FcCharSetCreate ();
 375     if (!fcs)
 376         goto bail0;
 377     FcCharSetIterStart (a, &ai);
 378     FcCharSetIterStart (b, &bi);
 379     while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
 380     {
 381         if (ai.ucs4 < bi.ucs4)
 382         {
 383             if (aonly)
 384             {
 385                 if (!FcCharSetAddLeaf (fcs, ai.ucs4, ai.leaf))
 386                     goto bail1;
 387                 FcCharSetIterNext (a, &ai);
 388             }
 389             else
 390             {
 391                 ai.ucs4 = bi.ucs4;
 392                 FcCharSetIterSet (a, &ai);
 393             }
 394         }
 395         else if (bi.ucs4 < ai.ucs4 )
 396         {
 397             if (bonly)
 398             {
 399                 if (!FcCharSetAddLeaf (fcs, bi.ucs4, bi.leaf))
 400                     goto bail1;
 401                 FcCharSetIterNext (b, &bi);
 402             }
 403             else
 404             {
 405                 bi.ucs4 = ai.ucs4;
 406                 FcCharSetIterSet (b, &bi);
 407             }
 408         }
 409         else
 410         {
 411             FcCharLeaf  leaf;
 412
 413             if ((*overlap) (&leaf, ai.leaf, bi.leaf))
 414             {
 415                 if (!FcCharSetAddLeaf (fcs, ai.ucs4, &leaf))
 416                     goto bail1;
 417             }
 418             FcCharSetIterNext (a, &ai);
 419             FcCharSetIterNext (b, &bi);
 420         }
 421     }
 422     return fcs;
 423 bail1:
 424     FcCharSetDestroy (fcs);
 425 bail0:
 426     return 0;
 427 }
 428
 429 static FcBool
 430 FcCharSetIntersectLeaf (FcCharLeaf *result,
 431                         const FcCharLeaf *al,
 432                         const FcCharLeaf *bl)
 433 {
 434     int     i;
 435     FcBool  nonempty = FcFalse;
 436
 437     for (i = 0; i < 256/32; i++)
 438         if ((result->map[i] = al->map[i] & bl->map[i]))
 439             nonempty = FcTrue;
 440     return nonempty;
 441 }
 442
 443 FcCharSet *
 444 FcCharSetIntersect (const FcCharSet *a, const FcCharSet *b)
 445 {
 446     return FcCharSetOperate (a, b, FcCharSetIntersectLeaf, FcFalse, FcFalse);
 447 }
 448
 449 static FcBool
 450 FcCharSetUnionLeaf (FcCharLeaf *result,
 451                     const FcCharLeaf *al,
 452                     const FcCharLeaf *bl)
 453 {
 454     int i;
 455
 456     for (i = 0; i < 256/32; i++)
 457         result->map[i] = al->map[i] | bl->map[i];
 458     return FcTrue;
 459 }
 460
 461 FcCharSet *
 462 FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
 463 {
 464     return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
 465 }
 466
 467 FcBool
 468 FcCharSetMerge (FcCharSet *a, const FcCharSet *b, FcBool *changed)
 469 {
 470     int         ai = 0, bi = 0;
 471     FcChar16    an, bn;
 472
 473     if (a->ref == FC_REF_CONSTANT) {
 474         if (changed)
 475             *changed = FcFalse;
 476         return FcFalse;
 477     }
 478
 479     if (changed) {
 480         *changed = !FcCharSetIsSubset(b, a);
 481         if (!*changed)
 482             return FcTrue;
 483     }
 484
 485     while (bi < b->num)
 486     {
 487         an = ai < a->num ? FcCharSetNumbers(a)[ai] : ~0;
 488         bn = FcCharSetNumbers(b)[bi];
 489
 490         if (an < bn)
 491         {
 492             ai = FcCharSetFindLeafForward (a, ai + 1, bn);
 493             if (ai < 0)
 494                 ai = -ai - 1;
 495         }
 496         else
 497         {
 498             FcCharLeaf *bl = FcCharSetLeaf(b, bi);
 499             if (bn < an)
 500             {
 501                 if (!FcCharSetAddLeaf (a, bn << 8, bl))
 502                     return FcFalse;
 503             }
 504             else
 505             {
 506                 FcCharLeaf *al = FcCharSetLeaf(a, ai);
 507                 FcCharSetUnionLeaf (al, al, bl);
 508             }
 509
 510             ai++;
 511             bi++;
 512         }
 513     }
 514
 515     return FcTrue;
 516 }
 517
 518 static FcBool
 519 FcCharSetSubtractLeaf (FcCharLeaf *result,
 520                        const FcCharLeaf *al,
 521                        const FcCharLeaf *bl)
 522 {
 523     int     i;
 524     FcBool  nonempty = FcFalse;
 525
 526     for (i = 0; i < 256/32; i++)
 527         if ((result->map[i] = al->map[i] & ~bl->map[i]))
 528             nonempty = FcTrue;
 529     return nonempty;
 530 }
 531
 532 FcCharSet *
 533 FcCharSetSubtract (const FcCharSet *a, const FcCharSet *b)
 534 {
 535     return FcCharSetOperate (a, b, FcCharSetSubtractLeaf, FcTrue, FcFalse);
 536 }
 537
 538 FcBool
 539 FcCharSetHasChar (const FcCharSet *fcs, FcChar32 ucs4)
 540 {
 541     FcCharLeaf  *leaf = FcCharSetFindLeaf (fcs, ucs4);
 542     if (!leaf)
 543         return FcFalse;
 544     return (leaf->map[(ucs4 & 0xff) >> 5] & (1 << (ucs4 & 0x1f))) != 0;
 545 }
 546
 547 static FcChar32
 548 FcCharSetPopCount (FcChar32 c1)
 549 {
 550 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 551     return __builtin_popcount (c1);
 552 #else
 553     /* hackmem 169 */
 554     FcChar32    c2 = (c1 >> 1) & 033333333333;
 555     c2 = c1 - c2 - ((c2 >> 1) & 033333333333);
 556     return (((c2 + (c2 >> 3)) & 030707070707) % 077);
 557 #endif
 558 }
 559
 560 FcChar32
 561 FcCharSetIntersectCount (const FcCharSet *a, const FcCharSet *b)
 562 {
 563     FcCharSetIter   ai, bi;
 564     FcChar32        count = 0;
 565
 566     FcCharSetIterStart (a, &ai);
 567     FcCharSetIterStart (b, &bi);
 568     while (ai.leaf && bi.leaf)
 569     {
 570         if (ai.ucs4 == bi.ucs4)
 571         {
 572             FcChar32    *am = ai.leaf->map;
 573             FcChar32    *bm = bi.leaf->map;
 574             int         i = 256/32;
 575             while (i--)
 576                 count += FcCharSetPopCount (*am++ & *bm++);
 577             FcCharSetIterNext (a, &ai);
 578         }
 579         else if (ai.ucs4 < bi.ucs4)
 580         {
 581             ai.ucs4 = bi.ucs4;
 582             FcCharSetIterSet (a, &ai);
 583         }
 584         if (bi.ucs4 < ai.ucs4)
 585         {
 586             bi.ucs4 = ai.ucs4;
 587             FcCharSetIterSet (b, &bi);
 588         }
 589     }
 590     return count;
 591 }
 592
 593 FcChar32
 594 FcCharSetCount (const FcCharSet *a)
 595 {
 596     FcCharSetIter   ai;
 597     FcChar32        count = 0;
 598
 599     for (FcCharSetIterStart (a, &ai); ai.leaf; FcCharSetIterNext (a, &ai))
 600     {
 601         int                 i = 256/32;
 602         FcChar32            *am = ai.leaf->map;
 603
 604         while (i--)
 605             count += FcCharSetPopCount (*am++);
 606     }
 607     return count;
 608 }
 609
 610 FcChar32
 611 FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b)
 612 {
 613     FcCharSetIter   ai, bi;
 614     FcChar32        count = 0;
 615
 616     FcCharSetIterStart (a, &ai);
 617     FcCharSetIterStart (b, &bi);
 618     while (ai.leaf)
 619     {
 620         if (ai.ucs4 <= bi.ucs4)
 621         {
 622             FcChar32    *am = ai.leaf->map;
 623             int         i = 256/32;
 624             if (ai.ucs4 == bi.ucs4)
 625             {
 626                 FcChar32        *bm = bi.leaf->map;
 627                 while (i--)
 628                     count += FcCharSetPopCount (*am++ & ~*bm++);
 629             }
 630             else
 631             {
 632                 while (i--)
 633                     count += FcCharSetPopCount (*am++);
 634             }
 635             FcCharSetIterNext (a, &ai);
 636         }
 637         else if (bi.leaf)
 638         {
 639             bi.ucs4 = ai.ucs4;
 640             FcCharSetIterSet (b, &bi);
 641         }
 642     }
 643     return count;
 644 }
 645
 646 /*
 647  * return FcTrue iff a is a subset of b
 648  */
 649 FcBool
 650 FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
 651 {
 652     int         ai, bi;
 653     FcChar16    an, bn;
 654
 655     if (a == b) return FcTrue;
 656     bi = 0;
 657     ai = 0;
 658     while (ai < a->num && bi < b->num)
 659     {
 660         an = FcCharSetNumbers(a)[ai];
 661         bn = FcCharSetNumbers(b)[bi];
 662         /*
 663          * Check matching pages
 664          */
 665         if (an == bn)
 666         {
 667             FcChar32    *am = FcCharSetLeaf(a, ai)->map;
 668             FcChar32    *bm = FcCharSetLeaf(b, bi)->map;
 669
 670             if (am != bm)
 671             {
 672                 int     i = 256/32;
 673                 /*
 674                  * Does am have any bits not in bm?
 675                  */
 676                 while (i--)
 677                     if (*am++ & ~*bm++)
 678                         return FcFalse;
 679             }
 680             ai++;
 681             bi++;
 682         }
 683         /*
 684          * Does a have any pages not in b?
 685          */
 686         else if (an < bn)
 687             return FcFalse;
 688         else
 689         {
 690             bi = FcCharSetFindLeafForward (b, bi + 1, an);
 691             if (bi < 0)
 692                 bi = -bi - 1;
 693         }
 694     }
 695     /*
 696      * did we look at every page?
 697      */
 698     return ai >= a->num;
 699 }
 700
 701 /*
 702  * These two functions efficiently walk the entire charmap for
 703  * other software (like pango) that want their own copy
 704  */
 705
 706 FcChar32
 707 FcCharSetNextPage (const FcCharSet  *a,
 708                    FcChar32         map[FC_CHARSET_MAP_SIZE],
 709                    FcChar32         *next)
 710 {
 711     FcCharSetIter   ai;
 712     FcChar32        page;
 713
 714     ai.ucs4 = *next;
 715     FcCharSetIterSet (a, &ai);
 716     if (!ai.leaf)
 717         return FC_CHARSET_DONE;
 718
 719     /*
 720      * Save current information
 721      */
 722     page = ai.ucs4;
 723     memcpy (map, ai.leaf->map, sizeof (ai.leaf->map));
 724     /*
 725      * Step to next page
 726      */
 727     FcCharSetIterNext (a, &ai);
 728     *next = ai.ucs4;
 729
 730     return page;
 731 }
 732
 733 FcChar32
 734 FcCharSetFirstPage (const FcCharSet *a,
 735                     FcChar32        map[FC_CHARSET_MAP_SIZE],
 736                     FcChar32        *next)
 737 {
 738     *next = 0;
 739     return FcCharSetNextPage (a, map, next);
 740 }
 741
 742 /*
 743  * old coverage API, rather hard to use correctly
 744  */
 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 FcCharSet *
 881 FcNameParseCharSet (FcChar8 *string)
 882 {
 883     FcCharSet   *c;
 884     FcChar32    ucs4;
 885     FcCharLeaf  *leaf;
 886     FcCharLeaf  temp;
 887     FcChar32    bits;
 888     int         i;
 889
 890     c = FcCharSetCreate ();
 891     if (!c)
 892         goto bail0;
 893     while (*string)
 894     {
 895         string = FcCharSetParseValue (string, &ucs4);
 896         if (!string)
 897             goto bail1;
 898         bits = 0;
 899         for (i = 0; i < 256/32; i++)
 900         {
 901             string = FcCharSetParseValue (string, &temp.map[i]);
 902             if (!string)
 903                 goto bail1;
 904             bits |= temp.map[i];
 905         }
 906         if (bits)
 907         {
 908             leaf = malloc (sizeof (FcCharLeaf));
 909             if (!leaf)
 910                 goto bail1;
 911             *leaf = temp;
 912             if (!FcCharSetInsertLeaf (c, ucs4, leaf))
 913                 goto bail1;
 914         }
 915     }
 916     return c;
 917 bail1:
 918     if (c->num)
 919     {
 920         FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcCharLeaf *));
 921         free (FcCharSetLeaves (c));
 922     }
 923     if (c->num)
 924     {
 925         FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcChar16));
 926         free (FcCharSetNumbers (c));
 927     }
 928     FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
 929     free (c);
 930 bail0:
 931     return NULL;
 932 }
 933
 934 FcBool
 935 FcNameUnparseCharSet (FcStrBuf *buf, const FcCharSet *c)
 936 {
 937     FcCharSetIter   ci;
 938     int             i;
 939 #ifdef CHECK
 940     int             len = buf->len;
 941 #endif
 942
 943     for (FcCharSetIterStart (c, &ci);
 944          ci.leaf;
 945          FcCharSetIterNext (c, &ci))
 946     {
 947         if (!FcCharSetUnparseValue (buf, ci.ucs4))
 948             return FcFalse;
 949         for (i = 0; i < 256/32; i++)
 950             if (!FcCharSetUnparseValue (buf, ci.leaf->map[i]))
 951                 return FcFalse;
 952     }
 953 #ifdef CHECK
 954     {
 955         FcCharSet       *check;
 956         FcChar32        missing;
 957         FcCharSetIter   ci, checki;
 958
 959         /* null terminate for parser */
 960         FcStrBufChar (buf, '\0');
 961         /* step back over null for life after test */
 962         buf->len--;
 963         check = FcNameParseCharSet (buf->buf + len);
 964         FcCharSetIterStart (c, &ci);
 965         FcCharSetIterStart (check, &checki);
 966         while (ci.leaf || checki.leaf)
 967         {
 968             if (ci.ucs4 < checki.ucs4)
 969             {
 970                 printf ("Missing leaf node at 0x%x\n", ci.ucs4);
 971                 FcCharSetIterNext (c, &ci);
 972             }
 973             else if (checki.ucs4 < ci.ucs4)
 974             {
 975                 printf ("Extra leaf node at 0x%x\n", checki.ucs4);
 976                 FcCharSetIterNext (check, &checki);
 977             }
 978             else
 979             {
 980                 int         i = 256/32;
 981                 FcChar32    *cm = ci.leaf->map;
 982                 FcChar32    *checkm = checki.leaf->map;
 983
 984                 for (i = 0; i < 256; i += 32)
 985                 {
 986                     if (*cm != *checkm)
 987                         printf ("Mismatching sets at 0x%08x: 0x%08x != 0x%08x\n",
 988                                 ci.ucs4 + i, *cm, *checkm);
 989                     cm++;
 990                     checkm++;
 991                 }
 992                 FcCharSetIterNext (c, &ci);
 993                 FcCharSetIterNext (check, &checki);
 994             }
 995         }
 996         if ((missing = FcCharSetSubtractCount (c, check)))
 997             printf ("%d missing in reparsed result\n", missing);
 998         if ((missing = FcCharSetSubtractCount (check, c)))
 999             printf ("%d extra in reparsed result\n", missing);
1000         FcCharSetDestroy (check);
1001     }
1002 #endif
1003
1004     return FcTrue;
1005 }
1006
1007 typedef struct _FcCharLeafEnt FcCharLeafEnt;
1008
1009 struct _FcCharLeafEnt {
1010     FcCharLeafEnt   *next;
1011     FcChar32        hash;
1012     FcCharLeaf      leaf;
1013 };
1014
1015 #define FC_CHAR_LEAF_BLOCK      (4096 / sizeof (FcCharLeafEnt))
1016 #define FC_CHAR_LEAF_HASH_SIZE  257
1017
1018 typedef struct _FcCharSetEnt FcCharSetEnt;
1019
1020 struct _FcCharSetEnt {
1021     FcCharSetEnt        *next;
1022     FcChar32            hash;
1023     FcCharSet           set;
1024 };
1025
1026 typedef struct _FcCharSetOrigEnt FcCharSetOrigEnt;
1027
1028 struct _FcCharSetOrigEnt {
1029     FcCharSetOrigEnt    *next;
1030     const FcCharSet     *orig;
1031     const FcCharSet     *frozen;
1032 };
1033
1034 #define FC_CHAR_SET_HASH_SIZE    67
1035
1036 struct _FcCharSetFreezer {
1037     FcCharLeafEnt   *leaf_hash_table[FC_CHAR_LEAF_HASH_SIZE];
1038     FcCharLeafEnt   **leaf_blocks;
1039     int             leaf_block_count;
1040     FcCharSetEnt    *set_hash_table[FC_CHAR_SET_HASH_SIZE];
1041     FcCharSetOrigEnt    *orig_hash_table[FC_CHAR_SET_HASH_SIZE];
1042     FcCharLeafEnt   *current_block;
1043     int             leaf_remain;
1044     int             leaves_seen;
1045     int             charsets_seen;
1046     int             leaves_allocated;
1047     int             charsets_allocated;
1048 };
1049
1050 static FcCharLeafEnt *
1051 FcCharLeafEntCreate (FcCharSetFreezer *freezer)
1052 {
1053     if (!freezer->leaf_remain)
1054     {
1055         FcCharLeafEnt **newBlocks;
1056
1057         freezer->leaf_block_count++;
1058         newBlocks = realloc (freezer->leaf_blocks, freezer->leaf_block_count * sizeof (FcCharLeafEnt *));
1059         if (!newBlocks)
1060             return 0;
1061         freezer->leaf_blocks = newBlocks;
1062         freezer->current_block = freezer->leaf_blocks[freezer->leaf_block_count-1] = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
1063         if (!freezer->current_block)
1064             return 0;
1065         FcMemAlloc (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
1066         freezer->leaf_remain = FC_CHAR_LEAF_BLOCK;
1067     }
1068     freezer->leaf_remain--;
1069     freezer->leaves_allocated++;
1070     return freezer->current_block++;
1071 }
1072
1073 static FcChar32
1074 FcCharLeafHash (FcCharLeaf *leaf)
1075 {
1076     FcChar32    hash = 0;
1077     int         i;
1078
1079     for (i = 0; i < 256/32; i++)
1080         hash = ((hash << 1) | (hash >> 31)) ^ leaf->map[i];
1081     return hash;
1082 }
1083
1084 static FcCharLeaf *
1085 FcCharSetFreezeLeaf (FcCharSetFreezer *freezer, FcCharLeaf *leaf)
1086 {
1087     FcChar32                    hash = FcCharLeafHash (leaf);
1088     FcCharLeafEnt               **bucket = &freezer->leaf_hash_table[hash % FC_CHAR_LEAF_HASH_SIZE];
1089     FcCharLeafEnt               *ent;
1090
1091     for (ent = *bucket; ent; ent = ent->next)
1092     {
1093         if (ent->hash == hash && !memcmp (&ent->leaf, leaf, sizeof (FcCharLeaf)))
1094             return &ent->leaf;
1095     }
1096
1097     ent = FcCharLeafEntCreate(freezer);
1098     if (!ent)
1099         return 0;
1100     ent->leaf = *leaf;
1101     ent->hash = hash;
1102     ent->next = *bucket;
1103     *bucket = ent;
1104     return &ent->leaf;
1105 }
1106
1107 static FcChar32
1108 FcCharSetHash (FcCharSet *fcs)
1109 {
1110     FcChar32    hash = 0;
1111     int         i;
1112
1113     /* hash in leaves */
1114     for (i = 0; i < fcs->num; i++)
1115         hash = ((hash << 1) | (hash >> 31)) ^ FcCharLeafHash (FcCharSetLeaf(fcs,i));
1116     /* hash in numbers */
1117     for (i = 0; i < fcs->num; i++)
1118         hash = ((hash << 1) | (hash >> 31)) ^ *FcCharSetNumbers(fcs);
1119     return hash;
1120 }
1121
1122 static FcBool
1123 FcCharSetFreezeOrig (FcCharSetFreezer *freezer, const FcCharSet *orig, const FcCharSet *frozen)
1124 {
1125     FcCharSetOrigEnt    **bucket = &freezer->orig_hash_table[((uintptr_t) orig) & FC_CHAR_SET_HASH_SIZE];
1126     FcCharSetOrigEnt    *ent;
1127
1128     ent = malloc (sizeof (FcCharSetOrigEnt));
1129     if (!ent)
1130         return FcFalse;
1131     ent->orig = orig;
1132     ent->frozen = frozen;
1133     ent->next = *bucket;
1134     *bucket = ent;
1135     return FcTrue;
1136 }
1137
1138 static FcCharSet *
1139 FcCharSetFreezeBase (FcCharSetFreezer *freezer, FcCharSet *fcs, const FcCharSet *orig)
1140 {
1141     FcChar32            hash = FcCharSetHash (fcs);
1142     FcCharSetEnt        **bucket = &freezer->set_hash_table[hash % FC_CHAR_SET_HASH_SIZE];
1143     FcCharSetEnt        *ent;
1144     int                 size;
1145     int                 i;
1146
1147     for (ent = *bucket; ent; ent = ent->next)
1148     {
1149         if (ent->hash == hash &&
1150             ent->set.num == fcs->num &&
1151             !memcmp (FcCharSetNumbers(&ent->set),
1152                      FcCharSetNumbers(fcs),
1153                      fcs->num * sizeof (FcChar16)))
1154         {
1155             FcBool ok = FcTrue;
1156             int i;
1157
1158             for (i = 0; i < fcs->num; i++)
1159                 if (FcCharSetLeaf(&ent->set, i) != FcCharSetLeaf(fcs, i))
1160                     ok = FcFalse;
1161             if (ok)
1162                 return &ent->set;
1163         }
1164     }
1165
1166     size = (sizeof (FcCharSetEnt) +
1167             fcs->num * sizeof (FcCharLeaf *) +
1168             fcs->num * sizeof (FcChar16));
1169     ent = malloc (size);
1170     if (!ent)
1171         return 0;
1172     FcMemAlloc (FC_MEM_CHARSET, size);
1173
1174     freezer->charsets_allocated++;
1175
1176     ent->set.ref = FC_REF_CONSTANT;
1177     ent->set.num = fcs->num;
1178     if (fcs->num)
1179     {
1180         intptr_t    *ent_leaves;
1181
1182         ent->set.leaves_offset = sizeof (ent->set);
1183         ent->set.numbers_offset = (ent->set.leaves_offset +
1184                                    fcs->num * sizeof (intptr_t));
1185
1186         ent_leaves = FcCharSetLeaves (&ent->set);
1187         for (i = 0; i < fcs->num; i++)
1188             ent_leaves[i] = FcPtrToOffset (ent_leaves,
1189                                            FcCharSetLeaf (fcs, i));
1190         memcpy (FcCharSetNumbers (&ent->set),
1191                 FcCharSetNumbers (fcs),
1192                 fcs->num * sizeof (FcChar16));
1193     }
1194     else
1195     {
1196         ent->set.leaves_offset = 0;
1197         ent->set.numbers_offset = 0;
1198     }
1199
1200     ent->hash = hash;
1201     ent->next = *bucket;
1202     *bucket = ent;
1203
1204     return &ent->set;
1205 }
1206
1207 static const FcCharSet *
1208 FcCharSetFindFrozen (FcCharSetFreezer *freezer, const FcCharSet *orig)
1209 {
1210     FcCharSetOrigEnt    **bucket = &freezer->orig_hash_table[((uintptr_t) orig) & FC_CHAR_SET_HASH_SIZE];
1211     FcCharSetOrigEnt    *ent;
1212
1213     for (ent = *bucket; ent; ent = ent->next)
1214         if (ent->orig == orig)
1215             return ent->frozen;
1216     return NULL;
1217 }
1218
1219 const FcCharSet *
1220 FcCharSetFreeze (FcCharSetFreezer *freezer, const FcCharSet *fcs)
1221 {
1222     FcCharSet       *b;
1223     const FcCharSet *n = 0;
1224     FcCharLeaf      *l;
1225     int             i;
1226
1227     b = FcCharSetCreate ();
1228     if (!b)
1229         goto bail0;
1230     for (i = 0; i < fcs->num; i++)
1231     {
1232         l = FcCharSetFreezeLeaf (freezer, FcCharSetLeaf(fcs, i));
1233         if (!l)
1234             goto bail1;
1235         if (!FcCharSetInsertLeaf (b, FcCharSetNumbers(fcs)[i] << 8, l))
1236             goto bail1;
1237     }
1238     n = FcCharSetFreezeBase (freezer, b, fcs);
1239     if (!FcCharSetFreezeOrig (freezer, fcs, n))
1240     {
1241         n = NULL;
1242         goto bail1;
1243     }
1244     freezer->charsets_seen++;
1245     freezer->leaves_seen += fcs->num;
1246 bail1:
1247     if (b->num)
1248     {
1249         FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcCharLeaf *));
1250         free (FcCharSetLeaves (b));
1251     }
1252     if (b->num)
1253     {
1254         FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcChar16));
1255         free (FcCharSetNumbers (b));
1256     }
1257     FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
1258     free (b);
1259 bail0:
1260     return n;
1261 }
1262
1263 FcCharSetFreezer *
1264 FcCharSetFreezerCreate (void)
1265 {
1266     FcCharSetFreezer    *freezer;
1267
1268     freezer = calloc (1, sizeof (FcCharSetFreezer));
1269     return freezer;
1270 }
1271
1272 void
1273 FcCharSetFreezerDestroy (FcCharSetFreezer *freezer)
1274 {
1275     int i;
1276
1277     if (FcDebug() & FC_DBG_CACHE)
1278     {
1279         printf ("\ncharsets %d -> %d leaves %d -> %d\n",
1280                 freezer->charsets_seen, freezer->charsets_allocated,
1281                 freezer->leaves_seen, freezer->leaves_allocated);
1282     }
1283     for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1284     {
1285         FcCharSetEnt    *ent, *next;
1286         for (ent = freezer->set_hash_table[i]; ent; ent = next)
1287         {
1288             next = ent->next;
1289             FcMemFree (FC_MEM_CHARSET, (sizeof (FcCharSetEnt) +
1290                                         ent->set.num * sizeof (FcCharLeaf *) +
1291                                         ent->set.num * sizeof (FcChar16)));
1292             free (ent);
1293         }
1294     }
1295
1296     for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1297     {
1298         FcCharSetOrigEnt        *ent, *next;
1299         for (ent = freezer->orig_hash_table[i]; ent; ent = next)
1300         {
1301             next = ent->next;
1302             free (ent);
1303         }
1304     }
1305
1306     for (i = 0; i < freezer->leaf_block_count; i++)
1307     {
1308         free (freezer->leaf_blocks[i]);
1309         FcMemFree (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
1310     }
1311
1312     free (freezer->leaf_blocks);
1313     free (freezer);
1314 }
1315
1316 FcBool
1317 FcCharSetSerializeAlloc (FcSerialize *serialize, const FcCharSet *cs)
1318 {
1319     intptr_t        *leaves;
1320     FcChar16        *numbers;
1321     int             i;
1322
1323     if (cs->ref != FC_REF_CONSTANT)
1324     {
1325         if (!serialize->cs_freezer)
1326         {
1327             serialize->cs_freezer = FcCharSetFreezerCreate ();
1328             if (!serialize->cs_freezer)
1329                 return FcFalse;
1330         }
1331         if (FcCharSetFindFrozen (serialize->cs_freezer, cs))
1332             return FcTrue;
1333
1334         cs = FcCharSetFreeze (serialize->cs_freezer, cs);
1335     }
1336
1337     leaves = FcCharSetLeaves (cs);
1338     numbers = FcCharSetNumbers (cs);
1339
1340     if (!FcSerializeAlloc (serialize, cs, sizeof (FcCharSet)))
1341         return FcFalse;
1342     if (!FcSerializeAlloc (serialize, leaves, cs->num * sizeof (intptr_t)))
1343         return FcFalse;
1344     if (!FcSerializeAlloc (serialize, numbers, cs->num * sizeof (FcChar16)))
1345         return FcFalse;
1346     for (i = 0; i < cs->num; i++)
1347         if (!FcSerializeAlloc (serialize, FcCharSetLeaf(cs, i),
1348                                sizeof (FcCharLeaf)))
1349             return FcFalse;
1350     return FcTrue;
1351 }
1352
1353 FcCharSet *
1354 FcCharSetSerialize(FcSerialize *serialize, const FcCharSet *cs)
1355 {
1356     FcCharSet   *cs_serialized;
1357     intptr_t    *leaves, *leaves_serialized;
1358     FcChar16    *numbers, *numbers_serialized;
1359     FcCharLeaf  *leaf, *leaf_serialized;
1360     int         i;
1361
1362     if (cs->ref != FC_REF_CONSTANT && serialize->cs_freezer)
1363     {
1364         cs = FcCharSetFindFrozen (serialize->cs_freezer, cs);
1365         if (!cs)
1366             return NULL;
1367     }
1368
1369     cs_serialized = FcSerializePtr (serialize, cs);
1370     if (!cs_serialized)
1371         return NULL;
1372
1373     cs_serialized->ref = FC_REF_CONSTANT;
1374     cs_serialized->num = cs->num;
1375
1376     if (cs->num)
1377     {
1378         leaves = FcCharSetLeaves (cs);
1379         leaves_serialized = FcSerializePtr (serialize, leaves);
1380         if (!leaves_serialized)
1381             return NULL;
1382
1383         cs_serialized->leaves_offset = FcPtrToOffset (cs_serialized,
1384                                                       leaves_serialized);
1385
1386         numbers = FcCharSetNumbers (cs);
1387         numbers_serialized = FcSerializePtr (serialize, numbers);
1388         if (!numbers)
1389             return NULL;
1390
1391         cs_serialized->numbers_offset = FcPtrToOffset (cs_serialized,
1392                                                        numbers_serialized);
1393
1394         for (i = 0; i < cs->num; i++)
1395         {
1396             leaf = FcCharSetLeaf (cs, i);
1397             leaf_serialized = FcSerializePtr (serialize, leaf);
1398             if (!leaf_serialized)
1399                 return NULL;
1400             *leaf_serialized = *leaf;
1401             leaves_serialized[i] = FcPtrToOffset (leaves_serialized,
1402                                                   leaf_serialized);
1403             numbers_serialized[i] = numbers[i];
1404         }
1405     }
1406     else
1407     {
1408         cs_serialized->leaves_offset = 0;
1409         cs_serialized->numbers_offset = 0;
1410     }
1411
1412     return cs_serialized;
1413 }
1414 #define __fccharset__
1415 #include "fcaliastail.h"
1416 #undef __fccharset__