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 "fcint.h"
  29
  30 FcChar8 *
  31 FcStrCopy (const FcChar8 *s)
  32 {
  33     FcChar8     *r;
  34
  35     if (!s)
  36         return 0;
  37     r = (FcChar8 *) malloc (strlen ((char *) s) + 1);
  38     if (!r)
  39         return 0;
  40     FcMemAlloc (FC_MEM_STRING, strlen ((char *) s) + 1);
  41     strcpy ((char *) r, (char *) s);
  42     return r;
  43 }
  44
  45 FcChar8 *
  46 FcStrPlus (const FcChar8 *s1, const FcChar8 *s2)
  47 {
  48     int     l = strlen ((char *)s1) + strlen ((char *) s2) + 1;
  49     FcChar8 *s = malloc (l);
  50
  51     if (!s)
  52         return 0;
  53     FcMemAlloc (FC_MEM_STRING, l);
  54     strcpy ((char *) s, (char *) s1);
  55     strcat ((char *) s, (char *) s2);
  56     return s;
  57 }
  58
  59 void
  60 FcStrFree (FcChar8 *s)
  61 {
  62     FcMemFree (FC_MEM_STRING, strlen ((char *) s) + 1);
  63     free (s);
  64 }
  65
  66
  67 #include "../fc-case/fccase.h"
  68
  69 #define FcCaseFoldUpperCount(cf) \
  70     ((cf)->method == FC_CASE_FOLD_FULL ? 1 : (cf)->count)
  71
  72 #define FC_STR_CANON_BUF_LEN    1024
  73
  74 typedef struct _FcCaseWalker {
  75     const FcChar8   *read;
  76     const FcChar8   *src;
  77     int             len;
  78     FcChar8         utf8[FC_MAX_CASE_FOLD_CHARS + 1];
  79 } FcCaseWalker;
  80
  81 static void
  82 FcStrCaseWalkerInit (const FcChar8 *src, FcCaseWalker *w)
  83 {
  84     w->src = src;
  85     w->read = 0;
  86     w->len = strlen (src);
  87 }
  88
  89 static FcChar8
  90 FcStrCaseWalkerLong (FcCaseWalker *w, FcChar8 r)
  91 {
  92     FcChar32    ucs4;
  93     int         slen;
  94
  95     slen = FcUtf8ToUcs4 (w->src - 1, &ucs4, w->len + 1);
  96     if (slen <= 0)
  97         return r;
  98     if (FC_MIN_FOLD_CHAR <= ucs4 && ucs4 <= FC_MAX_FOLD_CHAR)
  99     {
 100         int min = 0;
 101         int max = FC_NUM_CASE_FOLD;
 102
 103         while (min <= max)
 104         {
 105             int         mid = (min + max) >> 1;
 106             FcChar32    low = fcCaseFold[mid].upper;
 107             FcChar32    high = low + FcCaseFoldUpperCount (&fcCaseFold[mid]);
 108
 109             if (high <= ucs4)
 110                 min = mid + 1;
 111             else if (ucs4 < low)
 112                 max = mid - 1;
 113             else
 114             {
 115                 const FcCaseFold    *fold = &fcCaseFold[mid];
 116                 int                 dlen;
 117
 118                 switch (fold->method) {
 119                 case  FC_CASE_FOLD_EVEN_ODD:
 120                     if ((ucs4 & 1) != (fold->upper & 1))
 121                         return r;
 122                     /* fall through ... */
 123                 default:
 124                     dlen = FcUcs4ToUtf8 (ucs4 + fold->offset, w->utf8);
 125                     break;
 126                 case FC_CASE_FOLD_FULL:
 127                     dlen = fold->count;
 128                     memcpy (w->utf8, fcCaseFoldChars + fold->offset, dlen);
 129                     break;
 130                 }
 131
 132                 /* consume rest of src utf-8 bytes */
 133                 w->src += slen - 1;
 134                 w->len -= slen - 1;
 135
 136                 /* read from temp buffer */
 137                 w->utf8[dlen] = '\0';
 138                 w->read = w->utf8;
 139                 return *w->read++;
 140             }
 141         }
 142     }
 143     return r;
 144 }
 145
 146 static FcChar8
 147 FcStrCaseWalkerNext (FcCaseWalker *w)
 148 {
 149     FcChar8     r;
 150
 151     if (w->read)
 152     {
 153         if ((r = *w->read++))
 154             return r;
 155         w->read = 0;
 156     }
 157     r = *w->src++;
 158     --w->len;
 159
 160     if ((r & 0xc0) == 0xc0)
 161         return FcStrCaseWalkerLong (w, r);
 162     if ('A' <= r && r <= 'Z')
 163         r = r - 'A' + 'a';
 164     return r;
 165 }
 166
 167 static FcChar8
 168 FcStrCaseWalkerNextIgnoreBlanks (FcCaseWalker *w)
 169 {
 170     FcChar8     r;
 171
 172     if (w->read)
 173     {
 174         if ((r = *w->read++))
 175             return r;
 176         w->read = 0;
 177     }
 178     do
 179     {
 180         r = *w->src++;
 181         --w->len;
 182     } while (r == ' ');
 183
 184     if ((r & 0xc0) == 0xc0)
 185         return FcStrCaseWalkerLong (w, r);
 186     if ('A' <= r && r <= 'Z')
 187         r = r - 'A' + 'a';
 188     return r;
 189 }
 190
 191 FcChar8 *
 192 FcStrDowncase (const FcChar8 *s)
 193 {
 194     FcCaseWalker    w;
 195     int             len = 0;
 196     FcChar8         *dst, *d;
 197
 198     FcStrCaseWalkerInit (s, &w);
 199     while (FcStrCaseWalkerNext (&w))
 200         len++;
 201     d = dst = malloc (len + 1);
 202     if (!d)
 203         return 0;
 204     FcMemAlloc (FC_MEM_STRING, len + 1);
 205     FcStrCaseWalkerInit (s, &w);
 206     while ((*d++ = FcStrCaseWalkerNext (&w)));
 207     return dst;
 208 }
 209
 210 int
 211 FcStrCmpIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
 212 {
 213     FcCaseWalker    w1, w2;
 214     FcChar8         c1, c2;
 215
 216     if (s1 == s2) return 0;
 217
 218     FcStrCaseWalkerInit (s1, &w1);
 219     FcStrCaseWalkerInit (s2, &w2);
 220
 221     for (;;)
 222     {
 223         c1 = FcStrCaseWalkerNext (&w1);
 224         c2 = FcStrCaseWalkerNext (&w2);
 225         if (!c1 || (c1 != c2))
 226             break;
 227     }
 228     return (int) c1 - (int) c2;
 229 }
 230
 231 int
 232 FcStrCmpIgnoreBlanksAndCase (const FcChar8 *s1, const FcChar8 *s2)
 233 {
 234     FcCaseWalker    w1, w2;
 235     FcChar8         c1, c2;
 236
 237     if (s1 == s2) return 0;
 238
 239     FcStrCaseWalkerInit (s1, &w1);
 240     FcStrCaseWalkerInit (s2, &w2);
 241
 242     for (;;)
 243     {
 244         c1 = FcStrCaseWalkerNextIgnoreBlanks (&w1);
 245         c2 = FcStrCaseWalkerNextIgnoreBlanks (&w2);
 246         if (!c1 || (c1 != c2))
 247             break;
 248     }
 249     return (int) c1 - (int) c2;
 250 }
 251
 252 int
 253 FcStrCmp (const FcChar8 *s1, const FcChar8 *s2)
 254 {
 255     FcChar8 c1, c2;
 256
 257     if (s1 == s2)
 258         return 0;
 259     for (;;)
 260     {
 261         c1 = *s1++;
 262         c2 = *s2++;
 263         if (!c1 || c1 != c2)
 264             break;
 265     }
 266     return (int) c1 - (int) c2;
 267 }
 268
 269 /*
 270  * Return a hash value for a string
 271  */
 272
 273 FcChar32
 274 FcStrHashIgnoreCase (const FcChar8 *s)
 275 {
 276     FcChar32        h = 0;
 277     FcCaseWalker    w;
 278     FcChar8         c;
 279
 280     FcStrCaseWalkerInit (s, &w);
 281     while ((c = FcStrCaseWalkerNext (&w)))
 282         h = ((h << 3) ^ (h >> 3)) ^ c;
 283     return h;
 284 }
 285
 286 /*
 287  * Is the head of s1 equal to s2?
 288  */
 289
 290 static FcBool
 291 FcStrIsAtIgnoreBlanksAndCase (const FcChar8 *s1, const FcChar8 *s2)
 292 {
 293     FcCaseWalker    w1, w2;
 294     FcChar8         c1, c2;
 295
 296     FcStrCaseWalkerInit (s1, &w1);
 297     FcStrCaseWalkerInit (s2, &w2);
 298
 299     for (;;)
 300     {
 301         c1 = FcStrCaseWalkerNextIgnoreBlanks (&w1);
 302         c2 = FcStrCaseWalkerNextIgnoreBlanks (&w2);
 303         if (!c1 || (c1 != c2))
 304             break;
 305     }
 306     return c1 == c2 || !c2;
 307 }
 308
 309 /*
 310  * Does s1 contain an instance of s2 (ignoring blanks and case)?
 311  */
 312
 313 const FcChar8 *
 314 FcStrContainsIgnoreBlanksAndCase (const FcChar8 *s1, const FcChar8 *s2)
 315 {
 316     while (*s1)
 317     {
 318         if (FcStrIsAtIgnoreBlanksAndCase (s1, s2))
 319             return s1;
 320         s1++;
 321     }
 322     return 0;
 323 }
 324
 325 /*
 326  * Is the head of s1 equal to s2?
 327  */
 328
 329 static FcBool
 330 FcStrIsAtIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
 331 {
 332     FcCaseWalker    w1, w2;
 333     FcChar8         c1, c2;
 334
 335     FcStrCaseWalkerInit (s1, &w1);
 336     FcStrCaseWalkerInit (s2, &w2);
 337
 338     for (;;)
 339     {
 340         c1 = FcStrCaseWalkerNext (&w1);
 341         c2 = FcStrCaseWalkerNext (&w2);
 342         if (!c1 || (c1 != c2))
 343             break;
 344     }
 345     return c1 == c2 || !c2;
 346 }
 347
 348 /*
 349  * Does s1 contain an instance of s2 (ignoring blanks and case)?
 350  */
 351
 352 const FcChar8 *
 353 FcStrContainsIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
 354 {
 355     while (*s1)
 356     {
 357         if (FcStrIsAtIgnoreCase (s1, s2))
 358             return s1;
 359         s1++;
 360     }
 361     return 0;
 362 }
 363
 364 const FcChar8 *
 365 FcStrStrIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
 366 {
 367     FcCaseWalker    w1, w2;
 368     FcChar8         c1, c2;
 369     const FcChar8   *cur;
 370
 371     if (!s1 || !s2)
 372         return 0;
 373
 374     if (s1 == s2)
 375         return s1;
 376
 377     FcStrCaseWalkerInit (s1, &w1);
 378     FcStrCaseWalkerInit (s2, &w2);
 379
 380     c2 = FcStrCaseWalkerNext (&w2);
 381
 382     for (;;)
 383     {
 384         cur = w1.src;
 385         c1 = FcStrCaseWalkerNext (&w1);
 386         if (!c1)
 387             break;
 388         if (c1 == c2)
 389         {
 390             FcCaseWalker    w1t = w1;
 391             FcCaseWalker    w2t = w2;
 392             FcChar8         c1t, c2t;
 393
 394             for (;;)
 395             {
 396                 c1t = FcStrCaseWalkerNext (&w1t);
 397                 c2t = FcStrCaseWalkerNext (&w2t);
 398
 399                 if (!c2t)
 400                     return cur;
 401                 if (c2t != c1t)
 402                     break;
 403             }
 404         }
 405     }
 406     return 0;
 407 }
 408
 409 const FcChar8 *
 410 FcStrStr (const FcChar8 *s1, const FcChar8 *s2)
 411 {
 412     FcChar8 c1, c2;
 413     const FcChar8 * p = s1;
 414     const FcChar8 * b = s2;
 415
 416     if (!s1 || !s2)
 417         return 0;
 418
 419     if (s1 == s2)
 420         return s1;
 421
 422 again:
 423     c2 = *s2++;
 424
 425     if (!c2)
 426         return 0;
 427
 428     for (;;)
 429     {
 430         p = s1;
 431         c1 = *s1++;
 432         if (!c1 || c1 == c2)
 433             break;
 434     }
 435
 436     if (c1 != c2)
 437         return 0;
 438
 439     for (;;)
 440     {
 441         c1 = *s1;
 442         c2 = *s2;
 443         if (c1 && c2 && c1 != c2)
 444         {
 445             s1 = p + 1;
 446             s2 = b;
 447             goto again;
 448         }
 449         if (!c2)
 450             return p;
 451         if (!c1)
 452             return 0;
 453         ++ s1;
 454         ++ s2;
 455     }
 456
 457     return 0;
 458 }
 459
 460 int
 461 FcUtf8ToUcs4 (const FcChar8 *src_orig,
 462               FcChar32      *dst,
 463               int           len)
 464 {
 465     const FcChar8   *src = src_orig;
 466     FcChar8         s;
 467     int             extra;
 468     FcChar32        result;
 469
 470     if (len == 0)
 471         return 0;
 472
 473     s = *src++;
 474     len--;
 475
 476     if (!(s & 0x80))
 477     {
 478         result = s;
 479         extra = 0;
 480     }
 481     else if (!(s & 0x40))
 482     {
 483         return -1;
 484     }
 485     else if (!(s & 0x20))
 486     {
 487         result = s & 0x1f;
 488         extra = 1;
 489     }
 490     else if (!(s & 0x10))
 491     {
 492         result = s & 0xf;
 493         extra = 2;
 494     }
 495     else if (!(s & 0x08))
 496     {
 497         result = s & 0x07;
 498         extra = 3;
 499     }
 500     else if (!(s & 0x04))
 501     {
 502         result = s & 0x03;
 503         extra = 4;
 504     }
 505     else if ( ! (s & 0x02))
 506     {
 507         result = s & 0x01;
 508         extra = 5;
 509     }
 510     else
 511     {
 512         return -1;
 513     }
 514     if (extra > len)
 515         return -1;
 516
 517     while (extra--)
 518     {
 519         result <<= 6;
 520         s = *src++;
 521
 522         if ((s & 0xc0) != 0x80)
 523             return -1;
 524
 525         result |= s & 0x3f;
 526     }
 527     *dst = result;
 528     return src - src_orig;
 529 }
 530
 531 FcBool
 532 FcUtf8Len (const FcChar8    *string,
 533            int              len,
 534            int              *nchar,
 535            int              *wchar)
 536 {
 537     int         n;
 538     int         clen;
 539     FcChar32    c;
 540     FcChar32    max;
 541
 542     n = 0;
 543     max = 0;
 544     while (len)
 545     {
 546         clen = FcUtf8ToUcs4 (string, &c, len);
 547         if (clen <= 0)  /* malformed UTF8 string */
 548             return FcFalse;
 549         if (c > max)
 550             max = c;
 551         string += clen;
 552         len -= clen;
 553         n++;
 554     }
 555     *nchar = n;
 556     if (max >= 0x10000)
 557         *wchar = 4;
 558     else if (max > 0x100)
 559         *wchar = 2;
 560     else
 561         *wchar = 1;
 562     return FcTrue;
 563 }
 564
 565 int
 566 FcUcs4ToUtf8 (FcChar32  ucs4,
 567               FcChar8   dest[FC_UTF8_MAX_LEN])
 568 {
 569     int bits;
 570     FcChar8 *d = dest;
 571
 572     if      (ucs4 <       0x80) {  *d++=  ucs4;                         bits= -6; }
 573     else if (ucs4 <      0x800) {  *d++= ((ucs4 >>  6) & 0x1F) | 0xC0;  bits=  0; }
 574     else if (ucs4 <    0x10000) {  *d++= ((ucs4 >> 12) & 0x0F) | 0xE0;  bits=  6; }
 575     else if (ucs4 <   0x200000) {  *d++= ((ucs4 >> 18) & 0x07) | 0xF0;  bits= 12; }
 576     else if (ucs4 <  0x4000000) {  *d++= ((ucs4 >> 24) & 0x03) | 0xF8;  bits= 18; }
 577     else if (ucs4 < 0x80000000) {  *d++= ((ucs4 >> 30) & 0x01) | 0xFC;  bits= 24; }
 578     else return 0;
 579
 580     for ( ; bits >= 0; bits-= 6) {
 581         *d++= ((ucs4 >> bits) & 0x3F) | 0x80;
 582     }
 583     return d - dest;
 584 }
 585
 586 #define GetUtf16(src,endian) \
 587     ((FcChar16) ((src)[endian == FcEndianBig ? 0 : 1] << 8) | \
 588      (FcChar16) ((src)[endian == FcEndianBig ? 1 : 0]))
 589
 590 int
 591 FcUtf16ToUcs4 (const FcChar8    *src_orig,
 592                FcEndian         endian,
 593                FcChar32         *dst,
 594                int              len)    /* in bytes */
 595 {
 596     const FcChar8   *src = src_orig;
 597     FcChar16        a, b;
 598     FcChar32        result;
 599
 600     if (len < 2)
 601         return 0;
 602
 603     a = GetUtf16 (src, endian); src += 2; len -= 2;
 604
 605     /*
 606      * Check for surrogate
 607      */
 608     if ((a & 0xfc00) == 0xd800)
 609     {
 610         if (len < 2)
 611             return 0;
 612         b = GetUtf16 (src, endian); src += 2; len -= 2;
 613         /*
 614          * Check for invalid surrogate sequence
 615          */
 616         if ((b & 0xfc00) != 0xdc00)
 617             return 0;
 618         result = ((((FcChar32) a & 0x3ff) << 10) |
 619                   ((FcChar32) b & 0x3ff)) + 0x10000;
 620     }
 621     else
 622         result = a;
 623     *dst = result;
 624     return src - src_orig;
 625 }
 626
 627 FcBool
 628 FcUtf16Len (const FcChar8   *string,
 629             FcEndian        endian,
 630             int             len,        /* in bytes */
 631             int             *nchar,
 632             int             *wchar)
 633 {
 634     int         n;
 635     int         clen;
 636     FcChar32    c;
 637     FcChar32    max;
 638
 639     n = 0;
 640     max = 0;
 641     while (len)
 642     {
 643         clen = FcUtf16ToUcs4 (string, endian, &c, len);
 644         if (clen <= 0)  /* malformed UTF8 string */
 645             return FcFalse;
 646         if (c > max)
 647             max = c;
 648         string += clen;
 649         len -= clen;
 650         n++;
 651     }
 652     *nchar = n;
 653     if (max >= 0x10000)
 654         *wchar = 4;
 655     else if (max > 0x100)
 656         *wchar = 2;
 657     else
 658         *wchar = 1;
 659     return FcTrue;
 660 }
 661
 662 void
 663 FcStrBufInit (FcStrBuf *buf, FcChar8 *init, int size)
 664 {
 665     buf->buf = init;
 666     buf->allocated = FcFalse;
 667     buf->failed = FcFalse;
 668     buf->len = 0;
 669     buf->size = size;
 670 }
 671
 672 void
 673 FcStrBufDestroy (FcStrBuf *buf)
 674 {
 675     if (buf->allocated)
 676     {
 677         FcMemFree (FC_MEM_STRBUF, buf->size);
 678         free (buf->buf);
 679         FcStrBufInit (buf, 0, 0);
 680     }
 681 }
 682
 683 FcChar8 *
 684 FcStrBufDone (FcStrBuf *buf)
 685 {
 686     FcChar8 *ret;
 687
 688     ret = malloc (buf->len + 1);
 689     if (ret)
 690     {
 691         FcMemAlloc (FC_MEM_STRING, buf->len + 1);
 692         memcpy (ret, buf->buf, buf->len);
 693         ret[buf->len] = '\0';
 694     }
 695     FcStrBufDestroy (buf);
 696     return ret;
 697 }
 698
 699 FcBool
 700 FcStrBufChar (FcStrBuf *buf, FcChar8 c)
 701 {
 702     if (buf->len == buf->size)
 703     {
 704         FcChar8     *new;
 705         int         size;
 706
 707         if (buf->allocated)
 708         {
 709             size = buf->size * 2;
 710             new = realloc (buf->buf, size);
 711         }
 712         else
 713         {
 714             size = buf->size + 1024;
 715             new = malloc (size);
 716             if (new)
 717             {
 718                 buf->allocated = FcTrue;
 719                 memcpy (new, buf->buf, buf->len);
 720             }
 721         }
 722         if (!new)
 723         {
 724             buf->failed = FcTrue;
 725             return FcFalse;
 726         }
 727         if (buf->size)
 728             FcMemFree (FC_MEM_STRBUF, buf->size);
 729         FcMemAlloc (FC_MEM_STRBUF, size);
 730         buf->size = size;
 731         buf->buf = new;
 732     }
 733     buf->buf[buf->len++] = c;
 734     return FcTrue;
 735 }
 736
 737 FcBool
 738 FcStrBufString (FcStrBuf *buf, const FcChar8 *s)
 739 {
 740     FcChar8 c;
 741     while ((c = *s++))
 742         if (!FcStrBufChar (buf, c))
 743             return FcFalse;
 744     return FcTrue;
 745 }
 746
 747 FcBool
 748 FcStrBufData (FcStrBuf *buf, const FcChar8 *s, int len)
 749 {
 750     while (len-- > 0)
 751         if (!FcStrBufChar (buf, *s++))
 752             return FcFalse;
 753     return FcTrue;
 754 }
 755
 756 FcBool
 757 FcStrUsesHome (const FcChar8 *s)
 758 {
 759     return *s == '~';
 760 }
 761
 762 FcChar8 *
 763 FcStrCopyFilename (const FcChar8 *s)
 764 {
 765     FcChar8 *new;
 766
 767     if (*s == '~')
 768     {
 769         FcChar8 *home = FcConfigHome ();
 770         int     size;
 771         if (!home)
 772             return 0;
 773         size = strlen ((char *) home) + strlen ((char *) s);
 774         new = (FcChar8 *) malloc (size);
 775         if (!new)
 776             return 0;
 777         FcMemAlloc (FC_MEM_STRING, size);
 778         strcpy ((char *) new, (char *) home);
 779         strcat ((char *) new, (char *) s + 1);
 780     }
 781     else
 782     {
 783         int     size = strlen ((char *) s) + 1;
 784         new = (FcChar8 *) malloc (size);
 785         if (!new)
 786             return 0;
 787         FcMemAlloc (FC_MEM_STRING, size);
 788         strcpy ((char *) new, (const char *) s);
 789     }
 790     return new;
 791 }
 792
 793 FcChar8 *
 794 FcStrLastSlash (const FcChar8  *path)
 795 {
 796     FcChar8         *slash;
 797
 798     slash = (FcChar8 *) strrchr ((const char *) path, '/');
 799 #ifdef _WIN32
 800     {
 801         FcChar8     *backslash;
 802
 803         backslash = (FcChar8 *) strrchr ((const char *) path, '\\');
 804         if (!slash || (backslash && backslash > slash))
 805             slash = backslash;
 806     }
 807 #endif
 808
 809     return slash;
 810 }
 811
 812 FcChar8 *
 813 FcStrDirname (const FcChar8 *file)
 814 {
 815     FcChar8 *slash;
 816     FcChar8 *dir;
 817
 818     slash = FcStrLastSlash (file);
 819     if (!slash)
 820         return FcStrCopy ((FcChar8 *) ".");
 821     dir = malloc ((slash - file) + 1);
 822     if (!dir)
 823         return 0;
 824     FcMemAlloc (FC_MEM_STRING, (slash - file) + 1);
 825     strncpy ((char *) dir, (const char *) file, slash - file);
 826     dir[slash - file] = '\0';
 827     return dir;
 828 }
 829
 830 FcChar8 *
 831 FcStrBasename (const FcChar8 *file)
 832 {
 833     FcChar8 *slash;
 834
 835     slash = FcStrLastSlash (file);
 836     if (!slash)
 837         return FcStrCopy (file);
 838     return FcStrCopy (slash + 1);
 839 }
 840
 841 FcStrSet *
 842 FcStrSetCreate (void)
 843 {
 844     FcStrSet    *set = malloc (sizeof (FcStrSet));
 845     if (!set)
 846         return 0;
 847     FcMemAlloc (FC_MEM_STRSET, sizeof (FcStrSet));
 848     set->ref = 1;
 849     set->num = 0;
 850     set->size = 0;
 851     set->strs = 0;
 852     return set;
 853 }
 854
 855 static FcBool
 856 _FcStrSetAppend (FcStrSet *set, FcChar8 *s)
 857 {
 858     if (FcStrSetMember (set, s))
 859     {
 860         FcStrFree (s);
 861         return FcTrue;
 862     }
 863     if (set->num == set->size)
 864     {
 865         FcChar8 **strs = malloc ((set->size + 2) * sizeof (FcChar8 *));
 866
 867         if (!strs)
 868             return FcFalse;
 869         FcMemAlloc (FC_MEM_STRSET, (set->size + 2) * sizeof (FcChar8 *));
 870         set->size = set->size + 1;
 871         if (set->num)
 872             memcpy (strs, set->strs, set->num * sizeof (FcChar8 *));
 873         if (set->strs)
 874             free (set->strs);
 875         set->strs = strs;
 876     }
 877     set->strs[set->num++] = s;
 878     set->strs[set->num] = 0;
 879     return FcTrue;
 880 }
 881
 882 FcBool
 883 FcStrSetMember (FcStrSet *set, const FcChar8 *s)
 884 {
 885     int i;
 886
 887     for (i = 0; i < set->num; i++)
 888         if (!FcStrCmp (set->strs[i], s))
 889             return FcTrue;
 890     return FcFalse;
 891 }
 892
 893 FcBool
 894 FcStrSetEqual (FcStrSet *sa, FcStrSet *sb)
 895 {
 896     int i;
 897     if (sa->num != sb->num)
 898         return FcFalse;
 899     for (i = 0; i < sa->num; i++)
 900         if (!FcStrSetMember (sb, sa->strs[i]))
 901             return FcFalse;
 902     return FcTrue;
 903 }
 904
 905 FcBool
 906 FcStrSetAdd (FcStrSet *set, const FcChar8 *s)
 907 {
 908     FcChar8 *new = FcStrCopy (s);
 909     if (!new)
 910         return FcFalse;
 911     if (!_FcStrSetAppend (set, new))
 912     {
 913         FcStrFree (new);
 914         return FcFalse;
 915     }
 916     return FcTrue;
 917 }
 918
 919 FcBool
 920 FcStrSetAddFilename (FcStrSet *set, const FcChar8 *s)
 921 {
 922     FcChar8 *new = FcStrCopyFilename (s);
 923     if (!new)
 924         return FcFalse;
 925     if (!_FcStrSetAppend (set, new))
 926     {
 927         FcStrFree (new);
 928         return FcFalse;
 929     }
 930     return FcTrue;
 931 }
 932
 933 FcBool
 934 FcStrSetDel (FcStrSet *set, const FcChar8 *s)
 935 {
 936     int i;
 937
 938     for (i = 0; i < set->num; i++)
 939         if (!FcStrCmp (set->strs[i], s))
 940         {
 941             FcStrFree (set->strs[i]);
 942             /*
 943              * copy remaining string pointers and trailing
 944              * NULL
 945              */
 946             memmove (&set->strs[i], &set->strs[i+1],
 947                      (set->num - i) * sizeof (FcChar8 *));
 948             set->num--;
 949             return FcTrue;
 950         }
 951     return FcFalse;
 952 }
 953
 954 void
 955 FcStrSetDestroy (FcStrSet *set)
 956 {
 957     if (--set->ref == 0)
 958     {
 959         int     i;
 960
 961         for (i = 0; i < set->num; i++)
 962             FcStrFree (set->strs[i]);
 963         FcMemFree (FC_MEM_STRSET, (set->size) * sizeof (FcChar8 *));
 964         if (set->strs)
 965             free (set->strs);
 966         FcMemFree (FC_MEM_STRSET, sizeof (FcStrSet));
 967         free (set);
 968     }
 969 }
 970
 971 FcStrList *
 972 FcStrListCreate (FcStrSet *set)
 973 {
 974     FcStrList   *list;
 975
 976     list = malloc (sizeof (FcStrList));
 977     if (!list)
 978         return 0;
 979     FcMemAlloc (FC_MEM_STRLIST, sizeof (FcStrList));
 980     list->set = set;
 981     set->ref++;
 982     list->n = 0;
 983     return list;
 984 }
 985
 986 FcChar8 *
 987 FcStrListNext (FcStrList *list)
 988 {
 989     if (list->n >= list->set->num)
 990         return 0;
 991     return list->set->strs[list->n++];
 992 }
 993
 994 void
 995 FcStrListDone (FcStrList *list)
 996 {
 997     FcStrSetDestroy (list->set);
 998     FcMemFree (FC_MEM_STRLIST, sizeof (FcStrList));
 999     free (list);
1000 }