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