src/fcstr.c

   1 /*
   2  * $RCSId: xc/lib/fontconfig/src/fcstr.c,v 1.10 2002/08/31 22:17:32 keithp Exp $
   3  *
   4  * Copyright © 2000 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 <ctype.h>
  27 #include <string.h>
  28 #include <sys/mman.h>
  29 #include "fcint.h"
  30
  31 FcChar8 *
  32 FcStrCopy (const FcChar8 *s)
  33 {
  34     FcChar8     *r;
  35
  36     if (!s)
  37         return 0;
  38     r = (FcChar8 *) malloc (strlen ((char *) s) + 1);
  39     if (!r)
  40         return 0;
  41     FcMemAlloc (FC_MEM_STRING, strlen ((char *) s) + 1);
  42     strcpy ((char *) r, (char *) s);
  43     return r;
  44 }
  45
  46 FcChar8 *
  47 FcStrPlus (const FcChar8 *s1, const FcChar8 *s2)
  48 {
  49     int     l = strlen ((char *)s1) + strlen ((char *) s2) + 1;
  50     FcChar8 *s = malloc (l);
  51
  52     if (!s)
  53         return 0;
  54     FcMemAlloc (FC_MEM_STRING, l);
  55     strcpy ((char *) s, (char *) s1);
  56     strcat ((char *) s, (char *) s2);
  57     return s;
  58 }
  59
  60 void
  61 FcStrFree (FcChar8 *s)
  62 {
  63     FcMemFree (FC_MEM_STRING, strlen ((char *) s) + 1);
  64     free (s);
  65 }
  66
  67
  68 #include "../fc-case/fccase.h"
  69
  70 #define FcCaseFoldUpperCount(cf) \
  71     ((cf)->method == FC_CASE_FOLD_FULL ? 1 : (cf)->count)
  72
  73 #define FC_STR_CANON_BUF_LEN    1024
  74
  75 typedef struct _FcCaseWalker {
  76     const FcChar8   *read;
  77     const FcChar8   *src;
  78     int             len;
  79     FcChar8         utf8[FC_MAX_CASE_FOLD_CHARS + 1];
  80 } FcCaseWalker;
  81
  82 static void
  83 FcStrCaseWalkerInit (const FcChar8 *src, FcCaseWalker *w)
  84 {
  85     w->src = src;
  86     w->read = 0;
  87     w->len = strlen (src);
  88 }
  89
  90 static FcChar8
  91 FcStrCaseWalkerLong (FcCaseWalker *w, FcChar8 r)
  92 {
  93     FcChar32    ucs4;
  94     int         slen;
  95
  96     slen = FcUtf8ToUcs4 (w->src - 1, &ucs4, w->len + 1);
  97     if (slen <= 0)
  98         return r;
  99     if (FC_MIN_FOLD_CHAR <= ucs4 && ucs4 <= FC_MAX_FOLD_CHAR)
 100     {
 101         int min = 0;
 102         int max = FC_NUM_CASE_FOLD;
 103
 104         while (min <= max)
 105         {
 106             int         mid = (min + max) >> 1;
 107             FcChar32    low = fcCaseFold[mid].upper;
 108             FcChar32    high = low + FcCaseFoldUpperCount (&fcCaseFold[mid]);
 109
 110             if (high <= ucs4)
 111                 min = mid + 1;
 112             else if (ucs4 < low)
 113                 max = mid - 1;
 114             else
 115             {
 116                 const FcCaseFold    *fold = &fcCaseFold[mid];
 117                 int                 dlen;
 118
 119                 switch (fold->method) {
 120                 case  FC_CASE_FOLD_EVEN_ODD:
 121                     if ((ucs4 & 1) != (fold->upper & 1))
 122                         return r;
 123                     /* fall through ... */
 124                 default:
 125                     dlen = FcUcs4ToUtf8 (ucs4 + fold->offset, w->utf8);
 126                     break;
 127                 case FC_CASE_FOLD_FULL:
 128                     dlen = fold->count;
 129                     memcpy (w->utf8, fcCaseFoldChars + fold->offset, dlen);
 130                     break;
 131                 }
 132
 133                 /* consume rest of src utf-8 bytes */
 134                 w->src += slen - 1;
 135                 w->len -= slen - 1;
 136
 137                 /* read from temp buffer */
 138                 w->utf8[dlen] = '\0';
 139                 w->read = w->utf8;
 140                 return *w->read++;
 141             }
 142         }
 143     }
 144     return r;
 145 }
 146
 147 static FcChar8
 148 FcStrCaseWalkerNext (FcCaseWalker *w)
 149 {
 150     FcChar8     r;
 151
 152     if (w->read)
 153     {
 154         if ((r = *w->read++))
 155             return r;
 156         w->read = 0;
 157     }
 158     r = *w->src++;
 159     --w->len;
 160
 161     if ((r & 0xc0) == 0xc0)
 162         return FcStrCaseWalkerLong (w, r);
 163     if ('A' <= r && r <= 'Z')
 164         r = r - 'A' + 'a';
 165     return r;
 166 }
 167
 168 static FcChar8
 169 FcStrCaseWalkerNextIgnoreBlanks (FcCaseWalker *w)
 170 {
 171     FcChar8     r;
 172
 173     if (w->read)
 174     {
 175         if ((r = *w->read++))
 176             return r;
 177         w->read = 0;
 178     }
 179     do
 180     {
 181         r = *w->src++;
 182         --w->len;
 183     } while (r == ' ');
 184
 185     if ((r & 0xc0) == 0xc0)
 186         return FcStrCaseWalkerLong (w, r);
 187     if ('A' <= r && r <= 'Z')
 188         r = r - 'A' + 'a';
 189     return r;
 190 }
 191
 192 FcChar8 *
 193 FcStrDowncase (const FcChar8 *s)
 194 {
 195     FcCaseWalker    w;
 196     int             len = 0;
 197     FcChar8         *dst, *d;
 198
 199     FcStrCaseWalkerInit (s, &w);
 200     while (FcStrCaseWalkerNext (&w))
 201         len++;
 202     d = dst = malloc (len + 1);
 203     if (!d)
 204         return 0;
 205     FcMemAlloc (FC_MEM_STRING, len + 1);
 206     FcStrCaseWalkerInit (s, &w);
 207     while ((*d++ = FcStrCaseWalkerNext (&w)));
 208     return dst;
 209 }
 210
 211 int
 212 FcStrCmpIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
 213 {
 214     FcCaseWalker    w1, w2;
 215     FcChar8         c1, c2;
 216
 217     if (s1 == s2) return 0;
 218
 219     FcStrCaseWalkerInit (s1, &w1);
 220     FcStrCaseWalkerInit (s2, &w2);
 221
 222     for (;;)
 223     {
 224         c1 = FcStrCaseWalkerNext (&w1);
 225         c2 = FcStrCaseWalkerNext (&w2);
 226         if (!c1 || (c1 != c2))
 227             break;
 228     }
 229     return (int) c1 - (int) c2;
 230 }
 231
 232 int
 233 FcStrCmpIgnoreBlanksAndCase (const FcChar8 *s1, const FcChar8 *s2)
 234 {
 235     FcCaseWalker    w1, w2;
 236     FcChar8         c1, c2;
 237
 238     if (s1 == s2) return 0;
 239
 240     FcStrCaseWalkerInit (s1, &w1);
 241     FcStrCaseWalkerInit (s2, &w2);
 242
 243     for (;;)
 244     {
 245         c1 = FcStrCaseWalkerNextIgnoreBlanks (&w1);
 246         c2 = FcStrCaseWalkerNextIgnoreBlanks (&w2);
 247         if (!c1 || (c1 != c2))
 248             break;
 249     }
 250     return (int) c1 - (int) c2;
 251 }
 252
 253 int
 254 FcStrCmp (const FcChar8 *s1, const FcChar8 *s2)
 255 {
 256     FcChar8 c1, c2;
 257
 258     if (s1 == s2)
 259         return 0;
 260     for (;;)
 261     {
 262         c1 = *s1++;
 263         c2 = *s2++;
 264         if (!c1 || c1 != c2)
 265             break;
 266     }
 267     return (int) c1 - (int) c2;
 268 }
 269
 270 /*
 271  * Return a hash value for a string
 272  */
 273
 274 FcChar32
 275 FcStrHashIgnoreCase (const FcChar8 *s)
 276 {
 277     FcChar32        h = 0;
 278     FcCaseWalker    w;
 279     FcChar8         c;
 280
 281     FcStrCaseWalkerInit (s, &w);
 282     while ((c = FcStrCaseWalkerNext (&w)))
 283         h = ((h << 3) ^ (h >> 3)) ^ c;
 284     return h;
 285 }
 286
 287 /*
 288  * Is the head of s1 equal to s2?
 289  */
 290
 291 static FcBool
 292 FcStrIsAtIgnoreBlanksAndCase (const FcChar8 *s1, const FcChar8 *s2)
 293 {
 294     FcCaseWalker    w1, w2;
 295     FcChar8         c1, c2;
 296
 297     FcStrCaseWalkerInit (s1, &w1);
 298     FcStrCaseWalkerInit (s2, &w2);
 299
 300     for (;;)
 301     {
 302         c1 = FcStrCaseWalkerNextIgnoreBlanks (&w1);
 303         c2 = FcStrCaseWalkerNextIgnoreBlanks (&w2);
 304         if (!c1 || (c1 != c2))
 305             break;
 306     }
 307     return c1 == c2 || !c2;
 308 }
 309
 310 /*
 311  * Does s1 contain an instance of s2 (ignoring blanks and case)?
 312  */
 313
 314 const FcChar8 *
 315 FcStrContainsIgnoreBlanksAndCase (const FcChar8 *s1, const FcChar8 *s2)
 316 {
 317     while (*s1)
 318     {
 319         if (FcStrIsAtIgnoreBlanksAndCase (s1, s2))
 320             return s1;
 321         s1++;
 322     }
 323     return 0;
 324 }
 325
 326 /*
 327  * Is the head of s1 equal to s2?
 328  */
 329
 330 static FcBool
 331 FcStrIsAtIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
 332 {
 333     FcCaseWalker    w1, w2;
 334     FcChar8         c1, c2;
 335
 336     FcStrCaseWalkerInit (s1, &w1);
 337     FcStrCaseWalkerInit (s2, &w2);
 338
 339     for (;;)
 340     {
 341         c1 = FcStrCaseWalkerNext (&w1);
 342         c2 = FcStrCaseWalkerNext (&w2);
 343         if (!c1 || (c1 != c2))
 344             break;
 345     }
 346     return c1 == c2 || !c2;
 347 }
 348
 349 /*
 350  * Does s1 contain an instance of s2 (ignoring blanks and case)?
 351  */
 352
 353 const FcChar8 *
 354 FcStrContainsIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
 355 {
 356     while (*s1)
 357     {
 358         if (FcStrIsAtIgnoreCase (s1, s2))
 359             return s1;
 360         s1++;
 361     }
 362     return 0;
 363 }
 364
 365 const FcChar8 *
 366 FcStrStrIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
 367 {
 368     FcCaseWalker    w1, w2;
 369     FcChar8         c1, c2;
 370     const FcChar8   *cur;
 371
 372     if (!s1 || !s2)
 373         return 0;
 374
 375     if (s1 == s2)
 376         return s1;
 377
 378     FcStrCaseWalkerInit (s1, &w1);
 379     FcStrCaseWalkerInit (s2, &w2);
 380
 381     c2 = FcStrCaseWalkerNext (&w2);
 382
 383     for (;;)
 384     {
 385         cur = w1.src;
 386         c1 = FcStrCaseWalkerNext (&w1);
 387         if (!c1)
 388             break;
 389         if (c1 == c2)
 390         {
 391             FcCaseWalker    w1t = w1;
 392             FcCaseWalker    w2t = w2;
 393             FcChar8         c1t, c2t;
 394
 395             for (;;)
 396             {
 397                 c1t = FcStrCaseWalkerNext (&w1t);
 398                 c2t = FcStrCaseWalkerNext (&w2t);
 399
 400                 if (!c2t)
 401                     return cur;
 402                 if (c2t != c1t)
 403                     break;
 404             }
 405         }
 406     }
 407     return 0;
 408 }
 409
 410 const FcChar8 *
 411 FcStrStr (const FcChar8 *s1, const FcChar8 *s2)
 412 {
 413     FcChar8 c1, c2;
 414     const FcChar8 * p = s1;
 415     const FcChar8 * b = s2;
 416
 417     if (!s1 || !s2)
 418         return 0;
 419
 420     if (s1 == s2)
 421         return s1;
 422
 423 again:
 424     c2 = *s2++;
 425
 426     if (!c2)
 427         return 0;
 428
 429     for (;;)
 430     {
 431         p = s1;
 432         c1 = *s1++;
 433         if (!c1 || c1 == c2)
 434             break;
 435     }
 436
 437     if (c1 != c2)
 438         return 0;
 439
 440     for (;;)
 441     {
 442         c1 = *s1;
 443         c2 = *s2;
 444         if (c1 && c2 && c1 != c2)
 445         {
 446             s1 = p + 1;
 447             s2 = b;
 448             goto again;
 449         }
 450         if (!c2)
 451             return p;
 452         if (!c1)
 453             return 0;
 454         ++ s1;
 455         ++ s2;
 456     }
 457
 458     return 0;
 459 }
 460
 461 int
 462 FcUtf8ToUcs4 (const FcChar8 *src_orig,
 463               FcChar32      *dst,
 464               int           len)
 465 {
 466     const FcChar8   *src = src_orig;
 467     FcChar8         s;
 468     int             extra;
 469     FcChar32        result;
 470
 471     if (len == 0)
 472         return 0;
 473
 474     s = *src++;
 475     len--;
 476
 477     if (!(s & 0x80))
 478     {
 479         result = s;
 480         extra = 0;
 481     }
 482     else if (!(s & 0x40))
 483     {
 484         return -1;
 485     }
 486     else if (!(s & 0x20))
 487     {
 488         result = s & 0x1f;
 489         extra = 1;
 490     }
 491     else if (!(s & 0x10))
 492     {
 493         result = s & 0xf;
 494         extra = 2;
 495     }
 496     else if (!(s & 0x08))
 497     {
 498         result = s & 0x07;
 499         extra = 3;
 500     }
 501     else if (!(s & 0x04))
 502     {
 503         result = s & 0x03;
 504         extra = 4;
 505     }
 506     else if ( ! (s & 0x02))
 507     {
 508         result = s & 0x01;
 509         extra = 5;
 510     }
 511     else
 512     {
 513         return -1;
 514     }
 515     if (extra > len)
 516         return -1;
 517
 518     while (extra--)
 519     {
 520         result <<= 6;
 521         s = *src++;
 522
 523         if ((s & 0xc0) != 0x80)
 524             return -1;
 525
 526         result |= s & 0x3f;
 527     }
 528     *dst = result;
 529     return src - src_orig;
 530 }
 531
 532 FcBool
 533 FcUtf8Len (const FcChar8    *string,
 534            int              len,
 535            int              *nchar,
 536            int              *wchar)
 537 {
 538     int         n;
 539     int         clen;
 540     FcChar32    c;
 541     FcChar32    max;
 542
 543     n = 0;
 544     max = 0;
 545     while (len)
 546     {
 547         clen = FcUtf8ToUcs4 (string, &c, len);
 548         if (clen <= 0)  /* malformed UTF8 string */
 549             return FcFalse;
 550         if (c > max)
 551             max = c;
 552         string += clen;
 553         len -= clen;
 554         n++;
 555     }
 556     *nchar = n;
 557     if (max >= 0x10000)
 558         *wchar = 4;
 559     else if (max > 0x100)
 560         *wchar = 2;
 561     else
 562         *wchar = 1;
 563     return FcTrue;
 564 }
 565
 566 int
 567 FcUcs4ToUtf8 (FcChar32  ucs4,
 568               FcChar8   dest[FC_UTF8_MAX_LEN])
 569 {
 570     int bits;
 571     FcChar8 *d = dest;
 572
 573     if      (ucs4 <       0x80) {  *d++=  ucs4;                         bits= -6; }
 574     else if (ucs4 <      0x800) {  *d++= ((ucs4 >>  6) & 0x1F) | 0xC0;  bits=  0; }
 575     else if (ucs4 <    0x10000) {  *d++= ((ucs4 >> 12) & 0x0F) | 0xE0;  bits=  6; }
 576     else if (ucs4 <   0x200000) {  *d++= ((ucs4 >> 18) & 0x07) | 0xF0;  bits= 12; }
 577     else if (ucs4 <  0x4000000) {  *d++= ((ucs4 >> 24) & 0x03) | 0xF8;  bits= 18; }
 578     else if (ucs4 < 0x80000000) {  *d++= ((ucs4 >> 30) & 0x01) | 0xFC;  bits= 24; }
 579     else return 0;
 580
 581     for ( ; bits >= 0; bits-= 6) {
 582         *d++= ((ucs4 >> bits) & 0x3F) | 0x80;
 583     }
 584     return d - dest;
 585 }
 586
 587 #define GetUtf16(src,endian) \
 588     ((FcChar16) ((src)[endian == FcEndianBig ? 0 : 1] << 8) | \
 589      (FcChar16) ((src)[endian == FcEndianBig ? 1 : 0]))
 590
 591 int
 592 FcUtf16ToUcs4 (const FcChar8    *src_orig,
 593                FcEndian         endian,
 594                FcChar32         *dst,
 595                int              len)    /* in bytes */
 596 {
 597     const FcChar8   *src = src_orig;
 598     FcChar16        a, b;
 599     FcChar32        result;
 600
 601     if (len < 2)
 602         return 0;
 603
 604     a = GetUtf16 (src, endian); src += 2; len -= 2;
 605
 606     /*
 607      * Check for surrogate
 608      */
 609     if ((a & 0xfc00) == 0xd800)
 610     {
 611         if (len < 2)
 612             return 0;
 613         b = GetUtf16 (src, endian); src += 2; len -= 2;
 614         /*
 615          * Check for invalid surrogate sequence
 616          */
 617         if ((b & 0xfc00) != 0xdc00)
 618             return 0;
 619         result = ((((FcChar32) a & 0x3ff) << 10) |
 620                   ((FcChar32) b & 0x3ff)) + 0x10000;
 621     }
 622     else
 623         result = a;
 624     *dst = result;
 625     return src - src_orig;
 626 }
 627
 628 FcBool
 629 FcUtf16Len (const FcChar8   *string,
 630             FcEndian        endian,
 631             int             len,        /* in bytes */
 632             int             *nchar,
 633             int             *wchar)
 634 {
 635     int         n;
 636     int         clen;
 637     FcChar32    c;
 638     FcChar32    max;
 639
 640     n = 0;
 641     max = 0;
 642     while (len)
 643     {
 644         clen = FcUtf16ToUcs4 (string, endian, &c, len);
 645         if (clen <= 0)  /* malformed UTF8 string */
 646             return FcFalse;
 647         if (c > max)
 648             max = c;
 649         string += clen;
 650         len -= clen;
 651         n++;
 652     }
 653     *nchar = n;
 654     if (max >= 0x10000)
 655         *wchar = 4;
 656     else if (max > 0x100)
 657         *wchar = 2;
 658     else
 659         *wchar = 1;
 660     return FcTrue;
 661 }
 662
 663 void
 664 FcStrBufInit (FcStrBuf *buf, FcChar8 *init, int size)
 665 {
 666     buf->buf = init;
 667     buf->allocated = FcFalse;
 668     buf->failed = FcFalse;
 669     buf->len = 0;
 670     buf->size = size;
 671 }
 672
 673 void
 674 FcStrBufDestroy (FcStrBuf *buf)
 675 {
 676     if (buf->allocated)
 677     {
 678         FcMemFree (FC_MEM_STRBUF, buf->size);
 679         free (buf->buf);
 680         FcStrBufInit (buf, 0, 0);
 681     }
 682 }
 683
 684 FcChar8 *
 685 FcStrBufDone (FcStrBuf *buf)
 686 {
 687     FcChar8 *ret;
 688
 689     ret = malloc (buf->len + 1);
 690     if (ret)
 691     {
 692         FcMemAlloc (FC_MEM_STRING, buf->len + 1);
 693         memcpy (ret, buf->buf, buf->len);
 694         ret[buf->len] = '\0';
 695     }
 696     FcStrBufDestroy (buf);
 697     return ret;
 698 }
 699
 700 FcBool
 701 FcStrBufChar (FcStrBuf *buf, FcChar8 c)
 702 {
 703     if (buf->len == buf->size)
 704     {
 705         FcChar8     *new;
 706         int         size;
 707
 708         if (buf->allocated)
 709         {
 710             size = buf->size * 2;
 711             new = realloc (buf->buf, size);
 712         }
 713         else
 714         {
 715             size = buf->size + 1024;
 716             new = malloc (size);
 717             if (new)
 718             {
 719                 buf->allocated = FcTrue;
 720                 memcpy (new, buf->buf, buf->len);
 721             }
 722         }
 723         if (!new)
 724         {
 725             buf->failed = FcTrue;
 726             return FcFalse;
 727         }
 728         if (buf->size)
 729             FcMemFree (FC_MEM_STRBUF, buf->size);
 730         FcMemAlloc (FC_MEM_STRBUF, size);
 731         buf->size = size;
 732         buf->buf = new;
 733     }
 734     buf->buf[buf->len++] = c;
 735     return FcTrue;
 736 }
 737
 738 FcBool
 739 FcStrBufString (FcStrBuf *buf, const FcChar8 *s)
 740 {
 741     FcChar8 c;
 742     while ((c = *s++))
 743         if (!FcStrBufChar (buf, c))
 744             return FcFalse;
 745     return FcTrue;
 746 }
 747
 748 FcBool
 749 FcStrBufData (FcStrBuf *buf, const FcChar8 *s, int len)
 750 {
 751     while (len-- > 0)
 752         if (!FcStrBufChar (buf, *s++))
 753             return FcFalse;
 754     return FcTrue;
 755 }
 756
 757 FcBool
 758 FcStrUsesHome (const FcChar8 *s)
 759 {
 760     return *s == '~';
 761 }
 762
 763 FcChar8 *
 764 FcStrCopyFilename (const FcChar8 *s)
 765 {
 766     FcChar8 *new;
 767
 768     if (*s == '~')
 769     {
 770         FcChar8 *home = FcConfigHome ();
 771         int     size;
 772         if (!home)
 773             return 0;
 774         size = strlen ((char *) home) + strlen ((char *) s);
 775         new = (FcChar8 *) malloc (size);
 776         if (!new)
 777             return 0;
 778         FcMemAlloc (FC_MEM_STRING, size);
 779         strcpy ((char *) new, (char *) home);
 780         strcat ((char *) new, (char *) s + 1);
 781     }
 782     else
 783     {
 784         int     size = strlen ((char *) s) + 1;
 785         new = (FcChar8 *) malloc (size);
 786         if (!new)
 787             return 0;
 788         FcMemAlloc (FC_MEM_STRING, size);
 789         strcpy ((char *) new, (const char *) s);
 790     }
 791     return new;
 792 }
 793
 794 FcChar8 *
 795 FcStrLastSlash (const FcChar8  *path)
 796 {
 797     FcChar8         *slash;
 798
 799     slash = (FcChar8 *) strrchr ((const char *) path, '/');
 800 #ifdef _WIN32
 801     {
 802         FcChar8     *backslash;
 803
 804         backslash = (FcChar8 *) strrchr ((const char *) path, '\\');
 805         if (!slash || (backslash && backslash > slash))
 806             slash = backslash;
 807     }
 808 #endif
 809
 810     return slash;
 811 }
 812
 813 FcChar8 *
 814 FcStrDirname (const FcChar8 *file)
 815 {
 816     FcChar8 *slash;
 817     FcChar8 *dir;
 818
 819     slash = FcStrLastSlash (file);
 820     if (!slash)
 821         return FcStrCopy ((FcChar8 *) ".");
 822     dir = malloc ((slash - file) + 1);
 823     if (!dir)
 824         return 0;
 825     FcMemAlloc (FC_MEM_STRING, (slash - file) + 1);
 826     strncpy ((char *) dir, (const char *) file, slash - file);
 827     dir[slash - file] = '\0';
 828     return dir;
 829 }
 830
 831 FcChar8 *
 832 FcStrBasename (const FcChar8 *file)
 833 {
 834     FcChar8 *slash;
 835
 836     slash = FcStrLastSlash (file);
 837     if (!slash)
 838         return FcStrCopy (file);
 839     return FcStrCopy (slash + 1);
 840 }
 841
 842 FcStrSet *
 843 FcStrSetCreate (void)
 844 {
 845     FcStrSet    *set = malloc (sizeof (FcStrSet));
 846     if (!set)
 847         return 0;
 848     FcMemAlloc (FC_MEM_STRSET, sizeof (FcStrSet));
 849     set->ref = 1;
 850     set->num = 0;
 851     set->size = 0;
 852     set->storage = FcStorageDynamic;
 853     set->u.strs = 0;
 854     return set;
 855 }
 856
 857 static FcChar8 * strset_buf = 0;
 858 static int strset_buf_ptr = 0, strset_buf_count = 0;
 859 static int * strset_idx = 0;
 860 static int strset_idx_ptr = 0, strset_idx_count = 0;
 861 static FcStrSet * strsets = 0;
 862 static int strset_ptr = 0, strset_count = 0;
 863
 864 void FcStrSetClearStatic()
 865 {
 866     strset_buf = 0; strset_buf_ptr = 0; strset_buf_count = 0;
 867     strset_idx = 0; strset_idx_ptr = 0; strset_idx_count = 0;
 868     strsets = 0; strset_ptr = 0; strset_count = 0;
 869 }
 870
 871 FcChar8 *
 872 FcStrSetGet (const FcStrSet *set, int i)
 873 {
 874     int index;
 875     switch (set->storage)
 876     {
 877     case FcStorageStatic:
 878         index = strset_idx[set->u.stridx_offset];
 879         if (index == -1)
 880             return 0;
 881         return &strset_buf[index];
 882     case FcStorageDynamic:
 883         return set->u.strs[i];
 884     default:
 885         return 0;
 886     }
 887 }
 888
 889 FcStrSet *
 890 FcStrSetPtrU (const FcStrSetPtr set)
 891 {
 892     switch (set.storage)
 893     {
 894     case FcStorageStatic:
 895         return &strsets[set.u.stat];
 896     case FcStorageDynamic:
 897         return (FcStrSet *)set.u.dyn;
 898     default:
 899         return 0;
 900     }
 901 }
 902
 903 FcStrSetPtr
 904 FcStrSetPtrCreateDynamic (const FcStrSet * set)
 905 {
 906     FcStrSetPtr new;
 907
 908     new.storage = FcStorageDynamic;
 909     new.u.dyn = (FcStrSet *)set;
 910     return new;
 911 }
 912
 913 static FcBool
 914 _FcStrSetAppend (FcStrSet *set, FcChar8 *s)
 915 {
 916     if (FcStrSetMember (set, s))
 917     {
 918         FcStrFree (s);
 919         return FcTrue;
 920     }
 921     if (set->num == set->size || set->storage == FcStorageStatic)
 922     {
 923         FcChar8 **strs = malloc ((set->size + 2) * sizeof (FcChar8 *));
 924
 925         if (!strs)
 926             return FcFalse;
 927         FcMemAlloc (FC_MEM_STRSET, (set->size + 2) * sizeof (FcChar8 *));
 928         set->size = set->size + 1;
 929         if (set->storage == FcStorageDynamic)
 930         {
 931             if (set->num)
 932                 memcpy (strs, set->u.strs, set->num * sizeof (FcChar8 *));
 933             if (set->u.strs)
 934                 free (set->u.strs);
 935         }
 936         else
 937         {
 938             if (set->num)
 939                 memcpy (strs, strset_idx+set->u.stridx_offset,
 940                         set->num * sizeof (FcChar8 *));
 941             set->storage = FcStorageDynamic;
 942         }
 943         set->u.strs = strs;
 944     }
 945     set->u.strs[set->num++] = s;
 946     set->u.strs[set->num] = 0;
 947     return FcTrue;
 948 }
 949
 950 FcBool
 951 FcStrSetMember (FcStrSet *set, const FcChar8 *s)
 952 {
 953     int i;
 954
 955     for (i = 0; i < set->num; i++)
 956         if (!FcStrCmp (FcStrSetGet(set, i), s))
 957             return FcTrue;
 958     return FcFalse;
 959 }
 960
 961 FcBool
 962 FcStrSetEqual (FcStrSet *sa, FcStrSet *sb)
 963 {
 964     int i;
 965     if (sa->num != sb->num)
 966         return FcFalse;
 967     for (i = 0; i < sa->num; i++)
 968         if (!FcStrSetMember (sb, FcStrSetGet(sa, i)))
 969             return FcFalse;
 970     return FcTrue;
 971 }
 972
 973 FcBool
 974 FcStrSetAdd (FcStrSet *set, const FcChar8 *s)
 975 {
 976     FcChar8 *new = FcStrCopy (s);
 977     if (!new)
 978         return FcFalse;
 979     if (!_FcStrSetAppend (set, new))
 980     {
 981         FcStrFree (new);
 982         return FcFalse;
 983     }
 984     return FcTrue;
 985 }
 986
 987 FcBool
 988 FcStrSetAddFilename (FcStrSet *set, const FcChar8 *s)
 989 {
 990     FcChar8 *new = FcStrCopyFilename (s);
 991     if (!new)
 992         return FcFalse;
 993     if (!_FcStrSetAppend (set, new))
 994     {
 995         FcStrFree (new);
 996         return FcFalse;
 997     }
 998     return FcTrue;
 999 }
1000
1001 FcBool
1002 FcStrSetDel (FcStrSet *set, const FcChar8 *s)
1003 {
1004     int i;
1005
1006     for (i = 0; i < set->num; i++)
1007         if (!FcStrCmp (FcStrSetGet(set, i), s))
1008         {
1009             if (set->storage == FcStorageDynamic)
1010                 FcStrFree (set->u.strs[i]);
1011             /*
1012              * copy remaining string pointers and trailing
1013              * NULL
1014              */
1015             memmove (FcStrSetGet(set, i), FcStrSetGet(set, i+1),
1016                      (set->num - i) * sizeof (FcChar8 *));
1017             set->num--;
1018             return FcTrue;
1019         }
1020     return FcFalse;
1021 }
1022
1023 void
1024 FcStrSetDestroy (FcStrSet *set)
1025 {
1026     if (--set->ref == 0)
1027     {
1028         int     i;
1029
1030         if (set->storage == FcStorageDynamic)
1031         {
1032             for (i = 0; i < set->num; i++)
1033                 FcStrFree (set->u.strs[i]);
1034             FcMemFree (FC_MEM_STRSET, (set->size) * sizeof (FcChar8 *));
1035             if (set->u.strs)
1036                 free (set->u.strs);
1037             FcMemFree (FC_MEM_STRSET, sizeof (FcStrSet));
1038         }
1039         free (set);
1040     }
1041 }
1042
1043 static int _FcStrSetSort_helper (const void * a, const void * b)
1044 {
1045     return FcStrCmp (&strset_buf[(int)a],
1046                      &strset_buf[(int)b]);
1047 }
1048
1049 void
1050 FcStrSetSort (FcStrSet * set)
1051 {
1052     switch (set->storage)
1053     {
1054     case FcStorageDynamic:
1055         qsort (set->u.strs, set->num, sizeof (FcChar8 *),
1056                (int (*)(const void *, const void *)) FcStrCmp);
1057         break;
1058     case FcStorageStatic:
1059         qsort (strset_idx+set->u.stridx_offset, set->num, sizeof (int),
1060                _FcStrSetSort_helper);
1061         break;
1062     default:
1063         break;
1064     }
1065 }
1066
1067 FcBool
1068 FcStrSetPrepareSerialize (const FcStrSet *set)
1069 {
1070     int i;
1071
1072     if (!set)
1073         return FcTrue;
1074
1075     strset_count ++;
1076     strset_idx_count += set->num;
1077     for (i = 0; i < set->num; i++)
1078     {
1079         if (FcStrSetGet(set, i))
1080             strset_buf_count += strlen(FcStrSetGet(set, i));
1081     }
1082
1083     return FcTrue;
1084 }
1085
1086 FcStrSetPtr
1087 FcStrSetSerialize (FcStrSet *set)
1088 {
1089     FcStrSet * new;
1090     FcStrSetPtr newp;
1091     int i;
1092
1093     if (!strsets)
1094     {
1095         strsets = malloc (strset_count * sizeof(FcStrSet));
1096         if (!strsets) goto bail1;
1097         strset_idx = malloc (strset_idx_count * sizeof(int));
1098         if (!strset_idx) goto bail2;
1099         strset_buf = malloc (strset_buf_count * sizeof (FcChar8));
1100         if (!strset_buf) goto bail3;
1101     }
1102
1103     if (!set)
1104         return FcStrSetPtrCreateDynamic(0);
1105
1106     newp.storage = FcStorageStatic;
1107     newp.u.stat = strset_ptr;
1108
1109     new = &strsets[strset_ptr++];
1110     new->ref = set->ref;
1111     new->num = set->num;
1112     new->size = set->num;
1113     new->storage = FcStorageStatic;
1114     new->u.stridx_offset = strset_idx_ptr;
1115     for (i = 0; i < set->num; i++)
1116     {
1117         FcChar8 * s = FcStrSetGet(set, i);
1118
1119         if (s)
1120         {
1121             memcpy(strset_buf+strset_buf_ptr, s,
1122                    strlen((char *)s));
1123             strset_idx[strset_idx_ptr++] = strset_buf_ptr;
1124             strset_buf_ptr += strlen((char *)s)+1;
1125         }
1126         else
1127             strset_idx[strset_idx_ptr++] = -1;
1128     }
1129
1130     if (strset_ptr > strset_count || strset_idx_ptr > strset_idx_count)
1131         return FcStrSetPtrCreateDynamic(0);
1132
1133     // problem with multiple ptrs to the same StrSet.
1134     // should hash StrSets or something.
1135     // FcStrSetDestroy (set);
1136
1137     return newp;
1138
1139  bail3:
1140     free (strset_idx);
1141  bail2:
1142     free (strsets);
1143  bail1:
1144     return FcStrSetPtrCreateDynamic(0);
1145 }
1146
1147 FcBool
1148 FcStrSetRead (int fd, FcCache metadata)
1149 {
1150     strsets = mmap(NULL,
1151                    metadata.strsets_length * sizeof (FcStrSet),
1152                    PROT_READ,
1153                    MAP_SHARED, fd, metadata.strsets_offset);
1154     if (strsets == MAP_FAILED)
1155         goto bail;
1156     strset_count = strset_ptr = metadata.strsets_length;
1157
1158     strset_idx = mmap(NULL,
1159                       metadata.strsets_idx_length * sizeof (int),
1160                       PROT_READ,
1161                       MAP_SHARED, fd, metadata.strsets_idx_offset);
1162     if (strset_idx == MAP_FAILED)
1163         goto bail1;
1164     strset_idx_count = strset_idx_ptr = metadata.strsets_length;
1165
1166     strset_buf = mmap(NULL,
1167                       metadata.strset_buf_length * sizeof (char),
1168                       PROT_READ,
1169                       MAP_SHARED, fd, metadata.strset_buf_offset);
1170     if (strset_buf == MAP_FAILED)
1171         goto bail2;
1172     strset_buf_count = strset_buf_ptr = metadata.strset_buf_length;
1173
1174     return FcTrue;
1175
1176  bail2:
1177     munmap (strset_idx, metadata.strsets_idx_length * sizeof (int));
1178  bail1:
1179     munmap (strsets, metadata.strsets_length * sizeof (FcStrSet));
1180  bail:
1181     return FcFalse;
1182 }
1183
1184 FcBool
1185 FcStrSetWrite (int fd, FcCache *metadata)
1186 {
1187     metadata->strsets_length = strset_ptr;
1188     metadata->strsets_offset = FcCacheNextOffset(fd);
1189     if (strset_ptr > 0)
1190     {
1191         lseek (fd, metadata->strsets_offset, SEEK_SET);
1192         if (write (fd, strsets, strset_ptr * sizeof(FcStrSet)) == -1)
1193             return FcFalse;
1194     }
1195
1196     metadata->strsets_idx_length = strset_idx_ptr;
1197     metadata->strsets_idx_offset = FcCacheNextOffset(fd);
1198     if (strset_idx_ptr > 0)
1199     {
1200         lseek (fd, metadata->strsets_idx_offset, SEEK_SET);
1201         if (write (fd, strset_idx, strset_idx_ptr * sizeof (int)) == -1)
1202             return FcFalse;
1203     }
1204
1205     metadata->strset_buf_offset = FcCacheNextOffset(fd);
1206     metadata->strset_buf_length = strset_buf_ptr;
1207     if (strset_buf_ptr > 0)
1208     {
1209         lseek (fd, metadata->strset_buf_offset, SEEK_SET);
1210         if (write (fd, strset_buf,
1211                    metadata->strset_buf_length * sizeof (char)) == -1)
1212             return FcFalse;
1213     }
1214
1215     return FcTrue;
1216 }
1217
1218 FcStrList *
1219 FcStrListCreate (FcStrSet *set)
1220 {
1221     FcStrList   *list;
1222
1223     list = malloc (sizeof (FcStrList));
1224     if (!list)
1225         return 0;
1226     FcMemAlloc (FC_MEM_STRLIST, sizeof (FcStrList));
1227     list->set = set;
1228     set->ref++;
1229     list->n = 0;
1230     return list;
1231 }
1232
1233 FcChar8 *
1234 FcStrListNext (FcStrList *list)
1235 {
1236     if (list->n >= list->set->num)
1237         return 0;
1238     return FcStrSetGet(list->set, list->n++);
1239 }
1240
1241 void
1242 FcStrListDone (FcStrList *list)
1243 {
1244     FcStrSetDestroy (list->set);
1245     FcMemFree (FC_MEM_STRLIST, sizeof (FcStrList));
1246     free (list);
1247 }