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