src/fcstr.c

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