src/fccharset.c

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