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