fcstr.c revision 2c393a42 
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
33FcChar8 *
34FcStrCopy (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
50FcChar8 *
51FcStrPlus (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
64void
65FcStrFree (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
79typedef struct _FcCaseWalker {
80    const FcChar8   *read;
81    const FcChar8   *src;
82    FcChar8	    utf8[FC_MAX_CASE_FOLD_CHARS + 1];
83} FcCaseWalker;
84
85static void
86FcStrCaseWalkerInit (const FcChar8 *src, FcCaseWalker *w)
87{
88    w->src = src;
89    w->read = 0;
90}
91
92static FcChar8
93FcStrCaseWalkerLong (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
149static FcChar8
150FcStrCaseWalkerNext (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
169static FcChar8
170FcStrCaseWalkerNextIgnoreBlanks (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
192FcChar8 *
193FcStrDowncase (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
211int
212FcStrCmpIgnoreCase (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
232int
233FcStrCmpIgnoreBlanksAndCase (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
253int
254FcStrCmp (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
274FcChar32
275FcStrHashIgnoreCase (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
291static FcBool
292FcStrIsAtIgnoreBlanksAndCase (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
314const FcChar8 *
315FcStrContainsIgnoreBlanksAndCase (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
326static FcBool
327FcCharIsPunct (const FcChar8 c)
328{
329    if (c < '0')
330	return FcTrue;
331    if (c <= '9')
332	return FcFalse;
333    if (c < 'A')
334	return FcTrue;
335    if (c <= 'Z')
336	return FcFalse;
337    if (c < 'a')
338	return FcTrue;
339    if (c <= 'z')
340	return FcFalse;
341    if (c <= '~')
342	return FcTrue;
343    return FcFalse;
344}
345
346/*
347 * Is the head of s1 equal to s2?
348 */
349
350static FcBool
351FcStrIsAtIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
352{
353    FcCaseWalker    w1, w2;
354    FcChar8	    c1, c2;
355
356    FcStrCaseWalkerInit (s1, &w1);
357    FcStrCaseWalkerInit (s2, &w2);
358
359    for (;;)
360    {
361	c1 = FcStrCaseWalkerNext (&w1);
362	c2 = FcStrCaseWalkerNext (&w2);
363	if (!c1 || (c1 != c2))
364	    break;
365    }
366    return c1 == c2 || !c2;
367}
368
369/*
370 * Does s1 contain an instance of s2 (ignoring blanks and case)?
371 */
372
373const FcChar8 *
374FcStrContainsIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
375{
376    while (*s1)
377    {
378	if (FcStrIsAtIgnoreCase (s1, s2))
379	    return s1;
380	s1++;
381    }
382    return 0;
383}
384
385/*
386 * Does s1 contain an instance of s2 on a word boundary (ignoring case)?
387 */
388
389const FcChar8 *
390FcStrContainsWord (const FcChar8 *s1, const FcChar8 *s2)
391{
392    FcBool  wordStart = FcTrue;
393    int	    s1len = strlen ((char *) s1);
394    int	    s2len = strlen ((char *) s2);
395
396    while (s1len >= s2len)
397    {
398	if (wordStart &&
399	    FcStrIsAtIgnoreCase (s1, s2) &&
400	    (s1len == s2len || FcCharIsPunct (s1[s2len])))
401	{
402	    return s1;
403	}
404	wordStart = FcFalse;
405	if (FcCharIsPunct (*s1))
406	    wordStart = FcTrue;
407	s1++;
408	s1len--;
409    }
410    return 0;
411}
412
413const FcChar8 *
414FcStrStrIgnoreCase (const FcChar8 *s1, const FcChar8 *s2)
415{
416    FcCaseWalker    w1, w2;
417    FcChar8	    c1, c2;
418    const FcChar8   *cur;
419
420    if (!s1 || !s2)
421	return 0;
422
423    if (s1 == s2)
424	return s1;
425
426    FcStrCaseWalkerInit (s1, &w1);
427    FcStrCaseWalkerInit (s2, &w2);
428
429    c2 = FcStrCaseWalkerNext (&w2);
430
431    for (;;)
432    {
433	cur = w1.src;
434	c1 = FcStrCaseWalkerNext (&w1);
435	if (!c1)
436	    break;
437	if (c1 == c2)
438	{
439	    FcCaseWalker    w1t = w1;
440	    FcCaseWalker    w2t = w2;
441	    FcChar8	    c1t, c2t;
442
443	    for (;;)
444	    {
445		c1t = FcStrCaseWalkerNext (&w1t);
446		c2t = FcStrCaseWalkerNext (&w2t);
447
448		if (!c2t)
449		    return cur;
450		if (c2t != c1t)
451		    break;
452	    }
453	}
454    }
455    return 0;
456}
457
458const FcChar8 *
459FcStrStr (const FcChar8 *s1, const FcChar8 *s2)
460{
461    FcChar8 c1, c2;
462    const FcChar8 * p = s1;
463    const FcChar8 * b = s2;
464
465    if (!s1 || !s2)
466	return 0;
467
468    if (s1 == s2)
469	return s1;
470
471again:
472    c2 = *s2++;
473
474    if (!c2)
475	return 0;
476
477    for (;;)
478    {
479	p = s1;
480	c1 = *s1++;
481	if (!c1 || c1 == c2)
482	    break;
483    }
484
485    if (c1 != c2)
486	return 0;
487
488    for (;;)
489    {
490	c1 = *s1;
491	c2 = *s2;
492	if (c1 && c2 && c1 != c2)
493	{
494	    s1 = p + 1;
495	    s2 = b;
496	    goto again;
497	}
498	if (!c2)
499	    return p;
500	if (!c1)
501	    return 0;
502	++ s1;
503	++ s2;
504    }
505    /* never reached. */
506}
507
508int
509FcUtf8ToUcs4 (const FcChar8 *src_orig,
510	      FcChar32	    *dst,
511	      int	    len)
512{
513    const FcChar8   *src = src_orig;
514    FcChar8	    s;
515    int		    extra;
516    FcChar32	    result;
517
518    if (len == 0)
519	return 0;
520
521    s = *src++;
522    len--;
523
524    if (!(s & 0x80))
525    {
526	result = s;
527	extra = 0;
528    }
529    else if (!(s & 0x40))
530    {
531	return -1;
532    }
533    else if (!(s & 0x20))
534    {
535	result = s & 0x1f;
536	extra = 1;
537    }
538    else if (!(s & 0x10))
539    {
540	result = s & 0xf;
541	extra = 2;
542    }
543    else if (!(s & 0x08))
544    {
545	result = s & 0x07;
546	extra = 3;
547    }
548    else if (!(s & 0x04))
549    {
550	result = s & 0x03;
551	extra = 4;
552    }
553    else if ( ! (s & 0x02))
554    {
555	result = s & 0x01;
556	extra = 5;
557    }
558    else
559    {
560	return -1;
561    }
562    if (extra > len)
563	return -1;
564
565    while (extra--)
566    {
567	result <<= 6;
568	s = *src++;
569
570	if ((s & 0xc0) != 0x80)
571	    return -1;
572
573	result |= s & 0x3f;
574    }
575    *dst = result;
576    return src - src_orig;
577}
578
579FcBool
580FcUtf8Len (const FcChar8    *string,
581	   int		    len,
582	   int		    *nchar,
583	   int		    *wchar)
584{
585    int		n;
586    int		clen;
587    FcChar32	c;
588    FcChar32	max;
589
590    n = 0;
591    max = 0;
592    while (len)
593    {
594	clen = FcUtf8ToUcs4 (string, &c, len);
595	if (clen <= 0)	/* malformed UTF8 string */
596	    return FcFalse;
597	if (c > max)
598	    max = c;
599	string += clen;
600	len -= clen;
601	n++;
602    }
603    *nchar = n;
604    if (max >= 0x10000)
605	*wchar = 4;
606    else if (max > 0x100)
607	*wchar = 2;
608    else
609	*wchar = 1;
610    return FcTrue;
611}
612
613int
614FcUcs4ToUtf8 (FcChar32	ucs4,
615	      FcChar8	dest[FC_UTF8_MAX_LEN])
616{
617    int	bits;
618    FcChar8 *d = dest;
619
620    if      (ucs4 <       0x80) {  *d++=  ucs4;                         bits= -6; }
621    else if (ucs4 <      0x800) {  *d++= ((ucs4 >>  6) & 0x1F) | 0xC0;  bits=  0; }
622    else if (ucs4 <    0x10000) {  *d++= ((ucs4 >> 12) & 0x0F) | 0xE0;  bits=  6; }
623    else if (ucs4 <   0x200000) {  *d++= ((ucs4 >> 18) & 0x07) | 0xF0;  bits= 12; }
624    else if (ucs4 <  0x4000000) {  *d++= ((ucs4 >> 24) & 0x03) | 0xF8;  bits= 18; }
625    else if (ucs4 < 0x80000000) {  *d++= ((ucs4 >> 30) & 0x01) | 0xFC;  bits= 24; }
626    else return 0;
627
628    for ( ; bits >= 0; bits-= 6) {
629	*d++= ((ucs4 >> bits) & 0x3F) | 0x80;
630    }
631    return d - dest;
632}
633
634#define GetUtf16(src,endian) \
635    ((FcChar16) ((src)[endian == FcEndianBig ? 0 : 1] << 8) | \
636     (FcChar16) ((src)[endian == FcEndianBig ? 1 : 0]))
637
638int
639FcUtf16ToUcs4 (const FcChar8	*src_orig,
640	       FcEndian		endian,
641	       FcChar32		*dst,
642	       int		len)	/* in bytes */
643{
644    const FcChar8   *src = src_orig;
645    FcChar16	    a, b;
646    FcChar32	    result;
647
648    if (len < 2)
649	return 0;
650
651    a = GetUtf16 (src, endian); src += 2; len -= 2;
652
653    /*
654     * Check for surrogate
655     */
656    if ((a & 0xfc00) == 0xd800)
657    {
658	if (len < 2)
659	    return 0;
660	b = GetUtf16 (src, endian); src += 2; len -= 2;
661	/*
662	 * Check for invalid surrogate sequence
663	 */
664	if ((b & 0xfc00) != 0xdc00)
665	    return 0;
666	result = ((((FcChar32) a & 0x3ff) << 10) |
667		  ((FcChar32) b & 0x3ff)) + 0x10000;
668    }
669    else
670	result = a;
671    *dst = result;
672    return src - src_orig;
673}
674
675FcBool
676FcUtf16Len (const FcChar8   *string,
677	    FcEndian	    endian,
678	    int		    len,	/* in bytes */
679	    int		    *nchar,
680	    int		    *wchar)
681{
682    int		n;
683    int		clen;
684    FcChar32	c;
685    FcChar32	max;
686
687    n = 0;
688    max = 0;
689    while (len)
690    {
691	clen = FcUtf16ToUcs4 (string, endian, &c, len);
692	if (clen <= 0)	/* malformed UTF8 string */
693	    return FcFalse;
694	if (c > max)
695	    max = c;
696	string += clen;
697	len -= clen;
698	n++;
699    }
700    *nchar = n;
701    if (max >= 0x10000)
702	*wchar = 4;
703    else if (max > 0x100)
704	*wchar = 2;
705    else
706	*wchar = 1;
707    return FcTrue;
708}
709
710void
711FcStrBufInit (FcStrBuf *buf, FcChar8 *init, int size)
712{
713    buf->buf = init;
714    buf->allocated = FcFalse;
715    buf->failed = FcFalse;
716    buf->len = 0;
717    buf->size = size;
718}
719
720void
721FcStrBufDestroy (FcStrBuf *buf)
722{
723    if (buf->allocated)
724    {
725	FcMemFree (FC_MEM_STRBUF, buf->size);
726	free (buf->buf);
727	FcStrBufInit (buf, 0, 0);
728    }
729}
730
731FcChar8 *
732FcStrBufDone (FcStrBuf *buf)
733{
734    FcChar8 *ret;
735
736    ret = malloc (buf->len + 1);
737    if (ret)
738    {
739	FcMemAlloc (FC_MEM_STRING, buf->len + 1);
740	memcpy (ret, buf->buf, buf->len);
741	ret[buf->len] = '\0';
742    }
743    FcStrBufDestroy (buf);
744    return ret;
745}
746
747FcBool
748FcStrBufChar (FcStrBuf *buf, FcChar8 c)
749{
750    if (buf->len == buf->size)
751    {
752	FcChar8	    *new;
753	int	    size;
754
755	if (buf->allocated)
756	{
757	    size = buf->size * 2;
758	    new = realloc (buf->buf, size);
759	}
760	else
761	{
762	    size = buf->size + 64;
763	    new = malloc (size);
764	    if (new)
765	    {
766		buf->allocated = FcTrue;
767		memcpy (new, buf->buf, buf->len);
768	    }
769	}
770	if (!new)
771	{
772	    buf->failed = FcTrue;
773	    return FcFalse;
774	}
775	if (buf->size)
776	    FcMemFree (FC_MEM_STRBUF, buf->size);
777	FcMemAlloc (FC_MEM_STRBUF, size);
778	buf->size = size;
779	buf->buf = new;
780    }
781    buf->buf[buf->len++] = c;
782    return FcTrue;
783}
784
785FcBool
786FcStrBufString (FcStrBuf *buf, const FcChar8 *s)
787{
788    FcChar8 c;
789    while ((c = *s++))
790	if (!FcStrBufChar (buf, c))
791	    return FcFalse;
792    return FcTrue;
793}
794
795FcBool
796FcStrBufData (FcStrBuf *buf, const FcChar8 *s, int len)
797{
798    while (len-- > 0)
799	if (!FcStrBufChar (buf, *s++))
800	    return FcFalse;
801    return FcTrue;
802}
803
804FcBool
805FcStrUsesHome (const FcChar8 *s)
806{
807    return *s == '~';
808}
809
810FcChar8 *
811FcStrCopyFilename (const FcChar8 *s)
812{
813    FcChar8 *new;
814
815    if (*s == '~')
816    {
817	FcChar8	*home = FcConfigHome ();
818	FcChar8	*full;
819	int	size;
820	if (!home)
821	    return 0;
822	size = strlen ((char *) home) + strlen ((char *) s);
823	full = (FcChar8 *) malloc (size);
824	if (!full)
825	    return 0;
826	strcpy ((char *) full, (char *) home);
827	strcat ((char *) full, (char *) s + 1);
828	new = FcStrCanonFilename (full);
829	free (full);
830    }
831    else
832	new = FcStrCanonFilename (s);
833    return new;
834}
835
836FcChar8 *
837FcStrLastSlash (const FcChar8  *path)
838{
839    FcChar8	    *slash;
840
841    slash = (FcChar8 *) strrchr ((const char *) path, '/');
842#ifdef _WIN32
843    {
844        FcChar8     *backslash;
845
846	backslash = (FcChar8 *) strrchr ((const char *) path, '\\');
847	if (!slash || (backslash && backslash > slash))
848	    slash = backslash;
849    }
850#endif
851
852    return slash;
853}
854
855FcChar8 *
856FcStrDirname (const FcChar8 *file)
857{
858    FcChar8 *slash;
859    FcChar8 *dir;
860
861    slash = FcStrLastSlash (file);
862    if (!slash)
863	return FcStrCopy ((FcChar8 *) ".");
864    dir = malloc ((slash - file) + 1);
865    if (!dir)
866	return 0;
867    FcMemAlloc (FC_MEM_STRING, (slash - file) + 1);
868    strncpy ((char *) dir, (const char *) file, slash - file);
869    dir[slash - file] = '\0';
870    return dir;
871}
872
873FcChar8 *
874FcStrBasename (const FcChar8 *file)
875{
876    FcChar8 *slash;
877
878    slash = FcStrLastSlash (file);
879    if (!slash)
880	return FcStrCopy (file);
881    return FcStrCopy (slash + 1);
882}
883
884static FcChar8 *
885FcStrCanonAbsoluteFilename (const FcChar8 *s)
886{
887    FcChar8 *file;
888    FcChar8 *f;
889    const FcChar8 *slash;
890    int size;
891
892    size = strlen ((char *) s) + 1;
893    file = malloc (size);
894    if (!file)
895	return NULL;
896    FcMemAlloc (FC_MEM_STRING, size);
897    slash = NULL;
898    f = file;
899    for (;;) {
900	if (*s == '/' || *s == '\0')
901	{
902	    if (slash)
903	    {
904		switch (s - slash) {
905		case 2:
906		    if (!strncmp ((char *) slash, "/.", 2))
907		    {
908			f -= 2;	/* trim /. from file */
909		    }
910		    break;
911		case 3:
912		    if (!strncmp ((char *) slash, "/..", 3))
913		    {
914			f -= 3;	/* trim /.. from file */
915			while (f > file) {
916			    if (*--f == '/')
917				break;
918			}
919		    }
920		    break;
921		}
922	    }
923	    slash = s;
924	}
925	if (!(*f++ = *s++))
926	    break;
927    }
928    return file;
929}
930
931#ifdef _WIN32
932/*
933 * Convert '\\' to '/' , remove double '/'
934 */
935static void
936FcConvertDosPath (char *str)
937{
938  size_t len = strlen (str);
939  char *p = str;
940  char *dest = str;
941  char *end = str + len;
942  char last = 0;
943
944  while (p < end)
945    {
946      if (*p == '\\')
947	*p = '/';
948
949      if (*p != '/'
950	  || last != '/')
951	{
952	  *dest++ = *p;
953	}
954
955      last = *p;
956      p++;
957    }
958
959  *dest = 0;
960}
961#endif
962
963FcChar8 *
964FcStrCanonFilename (const FcChar8 *s)
965{
966#ifdef _WIN32
967    FcChar8 full[FC_MAX_FILE_LEN + 2];
968    FcChar8 basename[FC_MAX_FILE_LEN + 2];
969    int size = GetFullPathName (s, sizeof (full) -1,
970				full,
971				basename);
972
973    if (size == 0)
974	perror ("GetFullPathName");
975
976    FcConvertDosPath (full);
977    return FcStrCanonAbsoluteFilename (full);
978#else
979    if (s[0] == '/')
980	return FcStrCanonAbsoluteFilename (s);
981    else
982    {
983	FcChar8	*full;
984	FcChar8 *file;
985
986	FcChar8	cwd[FC_MAX_FILE_LEN + 2];
987	if (getcwd ((char *) cwd, FC_MAX_FILE_LEN) == NULL)
988	    return NULL;
989	strcat ((char *) cwd, "/");
990	full = FcStrPlus (cwd, s);
991	file = FcStrCanonAbsoluteFilename (full);
992	FcStrFree (full);
993	return file;
994    }
995#endif
996}
997
998
999FcStrSet *
1000FcStrSetCreate (void)
1001{
1002    FcStrSet	*set = malloc (sizeof (FcStrSet));
1003    if (!set)
1004	return 0;
1005    FcMemAlloc (FC_MEM_STRSET, sizeof (FcStrSet));
1006    set->ref = 1;
1007    set->num = 0;
1008    set->size = 0;
1009    set->strs = 0;
1010    return set;
1011}
1012
1013static FcBool
1014_FcStrSetAppend (FcStrSet *set, FcChar8 *s)
1015{
1016    if (FcStrSetMember (set, s))
1017    {
1018	FcStrFree (s);
1019	return FcTrue;
1020    }
1021    if (set->num == set->size)
1022    {
1023	FcChar8	**strs = malloc ((set->size + 2) * sizeof (FcChar8 *));
1024
1025	if (!strs)
1026	    return FcFalse;
1027	FcMemAlloc (FC_MEM_STRSET, (set->size + 2) * sizeof (FcChar8 *));
1028	if (set->num)
1029	    memcpy (strs, set->strs, set->num * sizeof (FcChar8 *));
1030	if (set->strs)
1031	{
1032	    FcMemFree (FC_MEM_STRSET, (set->size + 1) * sizeof (FcChar8 *));
1033	    free (set->strs);
1034	}
1035	set->size = set->size + 1;
1036	set->strs = strs;
1037    }
1038    set->strs[set->num++] = s;
1039    set->strs[set->num] = 0;
1040    return FcTrue;
1041}
1042
1043FcBool
1044FcStrSetMember (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	    return FcTrue;
1051    return FcFalse;
1052}
1053
1054FcBool
1055FcStrSetEqual (FcStrSet *sa, FcStrSet *sb)
1056{
1057    int	i;
1058    if (sa->num != sb->num)
1059	return FcFalse;
1060    for (i = 0; i < sa->num; i++)
1061	if (!FcStrSetMember (sb, sa->strs[i]))
1062	    return FcFalse;
1063    return FcTrue;
1064}
1065
1066FcBool
1067FcStrSetAdd (FcStrSet *set, const FcChar8 *s)
1068{
1069    FcChar8 *new = FcStrCopy (s);
1070    if (!new)
1071	return FcFalse;
1072    if (!_FcStrSetAppend (set, new))
1073    {
1074	FcStrFree (new);
1075	return FcFalse;
1076    }
1077    return FcTrue;
1078}
1079
1080FcBool
1081FcStrSetAddFilename (FcStrSet *set, const FcChar8 *s)
1082{
1083    FcChar8 *new = FcStrCopyFilename (s);
1084    if (!new)
1085	return FcFalse;
1086    if (!_FcStrSetAppend (set, new))
1087    {
1088	FcStrFree (new);
1089	return FcFalse;
1090    }
1091    return FcTrue;
1092}
1093
1094FcBool
1095FcStrSetDel (FcStrSet *set, const FcChar8 *s)
1096{
1097    int	i;
1098
1099    for (i = 0; i < set->num; i++)
1100	if (!FcStrCmp (set->strs[i], s))
1101	{
1102	    FcStrFree (set->strs[i]);
1103	    /*
1104	     * copy remaining string pointers and trailing
1105	     * NULL
1106	     */
1107	    memmove (&set->strs[i], &set->strs[i+1],
1108		     (set->num - i) * sizeof (FcChar8 *));
1109	    set->num--;
1110	    return FcTrue;
1111	}
1112    return FcFalse;
1113}
1114
1115void
1116FcStrSetDestroy (FcStrSet *set)
1117{
1118    if (--set->ref == 0)
1119    {
1120	int	i;
1121
1122	for (i = 0; i < set->num; i++)
1123	    FcStrFree (set->strs[i]);
1124	if (set->strs)
1125	{
1126	    FcMemFree (FC_MEM_STRSET, (set->size + 1) * sizeof (FcChar8 *));
1127	    free (set->strs);
1128	}
1129	FcMemFree (FC_MEM_STRSET, sizeof (FcStrSet));
1130	free (set);
1131    }
1132}
1133
1134FcStrList *
1135FcStrListCreate (FcStrSet *set)
1136{
1137    FcStrList	*list;
1138
1139    list = malloc (sizeof (FcStrList));
1140    if (!list)
1141	return 0;
1142    FcMemAlloc (FC_MEM_STRLIST, sizeof (FcStrList));
1143    list->set = set;
1144    set->ref++;
1145    list->n = 0;
1146    return list;
1147}
1148
1149FcChar8 *
1150FcStrListNext (FcStrList *list)
1151{
1152    if (list->n >= list->set->num)
1153	return 0;
1154    return list->set->strs[list->n++];
1155}
1156
1157void
1158FcStrListDone (FcStrList *list)
1159{
1160    FcStrSetDestroy (list->set);
1161    FcMemFree (FC_MEM_STRLIST, sizeof (FcStrList));
1162    free (list);
1163}
1164
1165#define __fcstr__
1166#include "fcaliastail.h"
1167#undef __fcstr__
1168