src/fccharset.c

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