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