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