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 "fcint.h"
  26 #include <stdlib.h>
  27 #include <ctype.h>
  28 #include <string.h>
  29 #ifdef _WIN32
  30 #include <windows.h>
  31 #endif
  32
  33 FcChar8 *
  34 FcStrCopy (const FcChar8 *s)
  35 {
  36     int     len;
  37     FcChar8 *r;
  38
  39     if (!s)
  40         return 0;
  41     len = strlen ((char *) s) + 1;
  42     r = (FcChar8 *) malloc (len);
  43     if (!r)
  44         return 0;
  45     FcMemAlloc (FC_MEM_STRING, len);
  46     memcpy (r, s, len);
  47     return r;
  48 }
  49
  50 FcChar8 *
  51 FcStrPlus (const FcChar8 *s1, const FcChar8 *s2)
  52 {
  53     int     l = strlen ((char *)s1) + strlen ((char *) s2) + 1;
  54     FcChar8 *s = malloc (l);
  55
  56     if (!s)
  57         return 0;
  58     FcMemAlloc (FC_MEM_STRING, l);
  59     strcpy ((char *) s, (char *) s1);
  60     strcat ((char *) s, (char *) s2);
  61     return s;
  62 }
  63
  64 void
  65 FcStrFree (FcChar8 *s)
  66 {
  67     FcMemFree (FC_MEM_STRING, strlen ((char *) s) + 1);
  68     free (s);
  69 }
  70
  71
  72 #include "../fc-case/fccase.h"
  73
  74 #define FcCaseFoldUpperCount(cf) \
  75     ((cf)->method == FC_CASE_FOLD_FULL ? 1 : (cf)->count)
  76
  77 #define FC_STR_CANON_BUF_LEN    1024
  78
  79 typedef struct _FcCaseWalker {
  80     const FcChar8   *read;
  81     const FcChar8   *src;
  82     FcChar8         utf8[FC_MAX_CASE_FOLD_CHARS + 1];
  83 } FcCaseWalker;
  84
  85 static void
  86 FcStrCaseWalkerInit (const FcChar8 *src, FcCaseWalker *w)
  87 {
  88     w->src = src;
  89     w->read = 0;
  90 }
  91
  92 static FcChar8
  93 FcStrCaseWalkerLong (FcCaseWalker *w, FcChar8 r)
  94 {
  95     FcChar32    ucs4;
  96     int         slen;
  97     int         len = strlen((char*)w->src);
  98
  99     slen = FcUtf8ToUcs4 (w->src - 1, &ucs4, len + 1);
 100     if (slen <= 0)
 101         return r;
 102     if (FC_MIN_FOLD_CHAR <= ucs4 && ucs4 <= FC_MAX_FOLD_CHAR)
 103     {
 104         int min = 0;
 105         int max = FC_NUM_CASE_FOLD;
 106
 107         while (min <= max)
 108         {
 109             int         mid = (min + max) >> 1;
 110             FcChar32    low = fcCaseFold[mid].upper;
 111             FcChar32    high = low + FcCaseFoldUpperCount (&fcCaseFold[mid]);
 112
 113             if (high <= ucs4)
 114                 min = mid + 1;
 115             else if (ucs4 < low)
 116                 max = mid - 1;
 117             else
 118             {
 119                 const FcCaseFold    *fold = &fcCaseFold[mid];
 120                 int                 dlen;
 121
 122                 switch (fold->method) {
 123                 case  FC_CASE_FOLD_EVEN_ODD:
 124                     if ((ucs4 & 1) != (fold->upper & 1))
 125                         return r;
 126                     /* fall through ... */
 127                 default:
 128                     dlen = FcUcs4ToUtf8 (ucs4 + fold->offset, w->utf8);
 129                     break;
 130                 case FC_CASE_FOLD_FULL:
 131                     dlen = fold->count;
 132                     memcpy (w->utf8, fcCaseFoldChars + fold->offset, dlen);
 133                     break;
 134                 }
 135
 136                 /* consume rest of src utf-8 bytes */
 137                 w->src += slen - 1;
 138
 139                 /* read from temp buffer */
 140                 w->utf8[dlen] = '\0';
 141                 w->read = w->utf8;
 142                 return *w->read++;
 143             }
 144         }
 145     }
 146     return r;
 147 }
 148
 149 static FcChar8
 150 FcStrCaseWalkerNext (FcCaseWalker *w)
 151 {
 152     FcChar8     r;
 153
 154     if (w->read)
 155     {
 156         if ((r = *w->read++))
 157             return r;
 158         w->read = 0;
 159     }
 160     r = *w->src++;
 161
 162     if ((r & 0xc0) == 0xc0)
 163         return FcStrCaseWalkerLong (w, r);
 164     if ('A' <= r && r <= 'Z')
 165         r = r - 'A' + 'a';
 166     return r;
 167 }
 168
 169 static FcChar8
 170 FcStrCaseWalkerNextIgnoreBlanks (FcCaseWalker *w)
 171 {
 172     FcChar8     r;
 173
 174     if (w->read)
 175     {
 176         if ((r = *w->read++))
 177             return r;
 178         w->read = 0;
 179     }
 180     do
 181     {
 182         r = *w->src++;
 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     /* never reached. */
 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 + 64;
 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         FcChar8 *full;
 771         int     size;
 772         if (!home)
 773             return 0;
 774         size = strlen ((char *) home) + strlen ((char *) s);
 775         full = (FcChar8 *) malloc (size);
 776         if (!full)
 777             return 0;
 778         strcpy ((char *) full, (char *) home);
 779         strcat ((char *) full, (char *) s + 1);
 780         new = FcStrCanonFilename (full);
 781         free (full);
 782     }
 783     else
 784         new = FcStrCanonFilename (s);
 785     return new;
 786 }
 787
 788 FcChar8 *
 789 FcStrLastSlash (const FcChar8  *path)
 790 {
 791     FcChar8         *slash;
 792
 793     slash = (FcChar8 *) strrchr ((const char *) path, '/');
 794 #ifdef _WIN32
 795     {
 796         FcChar8     *backslash;
 797
 798         backslash = (FcChar8 *) strrchr ((const char *) path, '\\');
 799         if (!slash || (backslash && backslash > slash))
 800             slash = backslash;
 801     }
 802 #endif
 803
 804     return slash;
 805 }
 806
 807 FcChar8 *
 808 FcStrDirname (const FcChar8 *file)
 809 {
 810     FcChar8 *slash;
 811     FcChar8 *dir;
 812
 813     slash = FcStrLastSlash (file);
 814     if (!slash)
 815         return FcStrCopy ((FcChar8 *) ".");
 816     dir = malloc ((slash - file) + 1);
 817     if (!dir)
 818         return 0;
 819     FcMemAlloc (FC_MEM_STRING, (slash - file) + 1);
 820     strncpy ((char *) dir, (const char *) file, slash - file);
 821     dir[slash - file] = '\0';
 822     return dir;
 823 }
 824
 825 FcChar8 *
 826 FcStrBasename (const FcChar8 *file)
 827 {
 828     FcChar8 *slash;
 829
 830     slash = FcStrLastSlash (file);
 831     if (!slash)
 832         return FcStrCopy (file);
 833     return FcStrCopy (slash + 1);
 834 }
 835
 836 static FcChar8 *
 837 FcStrCanonAbsoluteFilename (const FcChar8 *s)
 838 {
 839     FcChar8 *file;
 840     FcChar8 *f;
 841     const FcChar8 *slash;
 842     int size;
 843
 844     size = strlen ((char *) s) + 1;
 845     file = malloc (size);
 846     if (!file)
 847         return NULL;
 848     FcMemAlloc (FC_MEM_STRING, size);
 849     slash = NULL;
 850     f = file;
 851     for (;;) {
 852         if (*s == '/' || *s == '\0')
 853         {
 854             if (slash)
 855             {
 856                 switch (s - slash) {
 857                 case 2:
 858                     if (!strncmp ((char *) slash, "/.", 2))
 859                     {
 860                         f -= 2; /* trim /. from file */
 861                     }
 862                     break;
 863                 case 3:
 864                     if (!strncmp ((char *) slash, "/..", 3))
 865                     {
 866                         f -= 3; /* trim /.. from file */
 867                         while (f > file) {
 868                             if (*--f == '/')
 869                                 break;
 870                         }
 871                     }
 872                     break;
 873                 }
 874             }
 875             slash = s;
 876         }
 877         if (!(*f++ = *s++))
 878             break;
 879     }
 880     return file;
 881 }
 882
 883 #ifdef _WIN32
 884 /*
 885  * Convert '\\' to '/' , remove double '/'
 886  */
 887 static void
 888 FcConvertDosPath (char *str)
 889 {
 890   size_t len = strlen (str);
 891   char *p = str;
 892   char *dest = str;
 893   char *end = str + len;
 894   char last = 0;
 895
 896   while (p < end)
 897     {
 898       if (*p == '\\')
 899         *p = '/';
 900
 901       if (*p != '/'
 902           || last != '/')
 903         {
 904           *dest++ = *p;
 905         }
 906
 907       last = *p;
 908       p++;
 909     }
 910
 911   *dest = 0;
 912 }
 913 #endif
 914
 915 FcChar8 *
 916 FcStrCanonFilename (const FcChar8 *s)
 917 {
 918 #ifdef _WIN32
 919     FcChar8 full[FC_MAX_FILE_LEN + 2];
 920     FcChar8 basename[FC_MAX_FILE_LEN + 2];
 921     int size = GetFullPathName (s, sizeof (full) -1,
 922                                 full,
 923                                 basename);
 924
 925     if (size == 0)
 926         perror ("GetFullPathName");
 927
 928     FcConvertDosPath (full);
 929     return FcStrCanonAbsoluteFilename (full);
 930 #else
 931     if (s[0] == '/')
 932         return FcStrCanonAbsoluteFilename (s);
 933     else
 934     {
 935         FcChar8 *full;
 936         FcChar8 *file;
 937
 938         FcChar8 cwd[FC_MAX_FILE_LEN + 2];
 939         if (getcwd ((char *) cwd, FC_MAX_FILE_LEN) == NULL)
 940             return NULL;
 941         strcat ((char *) cwd, "/");
 942         full = FcStrPlus (cwd, s);
 943         file = FcStrCanonAbsoluteFilename (full);
 944         FcStrFree (full);
 945         return file;
 946     }
 947 #endif
 948 }
 949
 950
 951 FcStrSet *
 952 FcStrSetCreate (void)
 953 {
 954     FcStrSet    *set = malloc (sizeof (FcStrSet));
 955     if (!set)
 956         return 0;
 957     FcMemAlloc (FC_MEM_STRSET, sizeof (FcStrSet));
 958     set->ref = 1;
 959     set->num = 0;
 960     set->size = 0;
 961     set->strs = 0;
 962     return set;
 963 }
 964
 965 static FcBool
 966 _FcStrSetAppend (FcStrSet *set, FcChar8 *s)
 967 {
 968     if (FcStrSetMember (set, s))
 969     {
 970         FcStrFree (s);
 971         return FcTrue;
 972     }
 973     if (set->num == set->size)
 974     {
 975         FcChar8 **strs = malloc ((set->size + 2) * sizeof (FcChar8 *));
 976
 977         if (!strs)
 978             return FcFalse;
 979         FcMemAlloc (FC_MEM_STRSET, (set->size + 2) * sizeof (FcChar8 *));
 980         set->size = set->size + 1;
 981         if (set->num)
 982             memcpy (strs, set->strs, set->num * sizeof (FcChar8 *));
 983         if (set->strs)
 984             free (set->strs);
 985         set->strs = strs;
 986     }
 987     set->strs[set->num++] = s;
 988     set->strs[set->num] = 0;
 989     return FcTrue;
 990 }
 991
 992 FcBool
 993 FcStrSetMember (FcStrSet *set, const FcChar8 *s)
 994 {
 995     int i;
 996
 997     for (i = 0; i < set->num; i++)
 998         if (!FcStrCmp (set->strs[i], s))
 999             return FcTrue;
1000     return FcFalse;
1001 }
1002
1003 FcBool
1004 FcStrSetEqual (FcStrSet *sa, FcStrSet *sb)
1005 {
1006     int i;
1007     if (sa->num != sb->num)
1008         return FcFalse;
1009     for (i = 0; i < sa->num; i++)
1010         if (!FcStrSetMember (sb, sa->strs[i]))
1011             return FcFalse;
1012     return FcTrue;
1013 }
1014
1015 FcBool
1016 FcStrSetAdd (FcStrSet *set, const FcChar8 *s)
1017 {
1018     FcChar8 *new = FcStrCopy (s);
1019     if (!new)
1020         return FcFalse;
1021     if (!_FcStrSetAppend (set, new))
1022     {
1023         FcStrFree (new);
1024         return FcFalse;
1025     }
1026     return FcTrue;
1027 }
1028
1029 FcBool
1030 FcStrSetAddFilename (FcStrSet *set, const FcChar8 *s)
1031 {
1032     FcChar8 *new = FcStrCopyFilename (s);
1033     if (!new)
1034         return FcFalse;
1035     if (!_FcStrSetAppend (set, new))
1036     {
1037         FcStrFree (new);
1038         return FcFalse;
1039     }
1040     return FcTrue;
1041 }
1042
1043 FcBool
1044 FcStrSetDel (FcStrSet *set, const FcChar8 *s)
1045 {
1046     int i;
1047
1048     for (i = 0; i < set->num; i++)
1049         if (!FcStrCmp (set->strs[i], s))
1050         {
1051             FcStrFree (set->strs[i]);
1052             /*
1053              * copy remaining string pointers and trailing
1054              * NULL
1055              */
1056             memmove (&set->strs[i], &set->strs[i+1],
1057                      (set->num - i) * sizeof (FcChar8 *));
1058             set->num--;
1059             return FcTrue;
1060         }
1061     return FcFalse;
1062 }
1063
1064 void
1065 FcStrSetDestroy (FcStrSet *set)
1066 {
1067     if (--set->ref == 0)
1068     {
1069         int     i;
1070
1071         for (i = 0; i < set->num; i++)
1072             FcStrFree (set->strs[i]);
1073         FcMemFree (FC_MEM_STRSET, (set->size) * sizeof (FcChar8 *));
1074         if (set->strs)
1075             free (set->strs);
1076         FcMemFree (FC_MEM_STRSET, sizeof (FcStrSet));
1077         free (set);
1078     }
1079 }
1080
1081 FcStrList *
1082 FcStrListCreate (FcStrSet *set)
1083 {
1084     FcStrList   *list;
1085
1086     list = malloc (sizeof (FcStrList));
1087     if (!list)
1088         return 0;
1089     FcMemAlloc (FC_MEM_STRLIST, sizeof (FcStrList));
1090     list->set = set;
1091     set->ref++;
1092     list->n = 0;
1093     return list;
1094 }
1095
1096 FcChar8 *
1097 FcStrListNext (FcStrList *list)
1098 {
1099     if (list->n >= list->set->num)
1100         return 0;
1101     return list->set->strs[list->n++];
1102 }
1103
1104 void
1105 FcStrListDone (FcStrList *list)
1106 {
1107     FcStrSetDestroy (list->set);
1108     FcMemFree (FC_MEM_STRLIST, sizeof (FcStrList));
1109     free (list);
1110 }
1111
1112 #define __fcstr__
1113 #include "fcaliastail.h"
1114 #undef __fcstr__