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