fccharset.c revision ca08ab68 
1/*
2 * fontconfig/src/fccharset.c
3 *
4 * Copyright © 2001 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
28/* #define CHECK */
29
30FcCharSet *
31FcCharSetCreate (void)
32{
33    FcCharSet	*fcs;
34
35    fcs = (FcCharSet *) malloc (sizeof (FcCharSet));
36    if (!fcs)
37	return 0;
38    FcMemAlloc (FC_MEM_CHARSET, sizeof (FcCharSet));
39    fcs->ref = 1;
40    fcs->num = 0;
41    fcs->leaves_offset = 0;
42    fcs->numbers_offset = 0;
43    return fcs;
44}
45
46FcCharSet *
47FcCharSetNew (void)
48{
49    return FcCharSetCreate ();
50}
51
52void
53FcCharSetDestroy (FcCharSet *fcs)
54{
55    int i;
56
57    if (fcs)
58    {
59	if (fcs->ref == FC_REF_CONSTANT)
60	{
61	    FcCacheObjectDereference (fcs);
62	    return;
63	}
64	if (--fcs->ref > 0)
65	    return;
66	for (i = 0; i < fcs->num; i++)
67	{
68	    FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
69	    free (FcCharSetLeaf (fcs, i));
70	}
71	if (fcs->num)
72	{
73	    /* the numbers here are estimates */
74	    FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (intptr_t));
75	    free (FcCharSetLeaves (fcs));
76	    FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
77	    free (FcCharSetNumbers (fcs));
78	}
79	FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
80	free (fcs);
81    }
82}
83
84/*
85 * Search for the leaf containing with the specified num.
86 * Return its index if it exists, otherwise return negative of
87 * the (position + 1) where it should be inserted
88 */
89
90
91static int
92FcCharSetFindLeafForward (const FcCharSet *fcs, int start, FcChar16 num)
93{
94    FcChar16		*numbers = FcCharSetNumbers(fcs);
95    FcChar16		page;
96    int			low = start;
97    int			high = fcs->num - 1;
98
99    if (!numbers)
100	return -1;
101    while (low <= high)
102    {
103	int mid = (low + high) >> 1;
104	page = numbers[mid];
105	if (page == num)
106	    return mid;
107	if (page < num)
108	    low = mid + 1;
109	else
110	    high = mid - 1;
111    }
112    if (high < 0 || (high < fcs->num && numbers[high] < num))
113	high++;
114    return -(high + 1);
115}
116
117/*
118 * Locate the leaf containing the specified char, return
119 * its index if it exists, otherwise return negative of
120 * the (position + 1) where it should be inserted
121 */
122
123static int
124FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
125{
126    return FcCharSetFindLeafForward (fcs, 0, ucs4 >> 8);
127}
128
129static FcCharLeaf *
130FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
131{
132    int	pos = FcCharSetFindLeafPos (fcs, ucs4);
133    if (pos >= 0)
134	return FcCharSetLeaf(fcs, pos);
135    return 0;
136}
137
138#define FC_IS_ZERO_OR_POWER_OF_TWO(x) (!((x) & ((x)-1)))
139
140static FcBool
141FcCharSetPutLeaf (FcCharSet	*fcs,
142		  FcChar32	ucs4,
143		  FcCharLeaf	*leaf,
144		  int		pos)
145{
146    intptr_t	*leaves = FcCharSetLeaves (fcs);
147    FcChar16	*numbers = FcCharSetNumbers (fcs);
148
149    ucs4 >>= 8;
150    if (ucs4 >= 0x10000)
151	return FcFalse;
152
153    if (FC_IS_ZERO_OR_POWER_OF_TWO (fcs->num))
154    {
155      if (!fcs->num)
156      {
157        unsigned int alloced = 8;
158	leaves = malloc (alloced * sizeof (*leaves));
159	numbers = malloc (alloced * sizeof (*numbers));
160	FcMemAlloc (FC_MEM_CHARSET, alloced * sizeof (*leaves));
161	FcMemAlloc (FC_MEM_CHARSET, alloced * sizeof (*numbers));
162      }
163      else
164      {
165        unsigned int alloced = fcs->num;
166	intptr_t *new_leaves, distance;
167
168	FcMemFree (FC_MEM_CHARSET, alloced * sizeof (*leaves));
169	FcMemFree (FC_MEM_CHARSET, alloced * sizeof (*numbers));
170
171	alloced *= 2;
172	new_leaves = realloc (leaves, alloced * sizeof (*leaves));
173	numbers = realloc (numbers, alloced * sizeof (*numbers));
174
175	FcMemAlloc (FC_MEM_CHARSET, alloced * sizeof (*leaves));
176	FcMemAlloc (FC_MEM_CHARSET, alloced * sizeof (*numbers));
177
178	distance = (intptr_t) new_leaves - (intptr_t) leaves;
179	if (new_leaves && distance)
180	{
181	    int i;
182	    for (i = 0; i < fcs->num; i++)
183		new_leaves[i] -= distance;
184	}
185	leaves = new_leaves;
186      }
187
188      if (!leaves || !numbers)
189	  return FcFalse;
190
191      fcs->leaves_offset = FcPtrToOffset (fcs, leaves);
192      fcs->numbers_offset = FcPtrToOffset (fcs, numbers);
193    }
194
195    memmove (leaves + pos + 1, leaves + pos,
196	     (fcs->num - pos) * sizeof (*leaves));
197    memmove (numbers + pos + 1, numbers + pos,
198	     (fcs->num - pos) * sizeof (*numbers));
199    numbers[pos] = (FcChar16) ucs4;
200    leaves[pos] = FcPtrToOffset (leaves, leaf);
201    fcs->num++;
202    return FcTrue;
203}
204
205/*
206 * Locate the leaf containing the specified char, creating it
207 * if desired
208 */
209
210FcCharLeaf *
211FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
212{
213    int			pos;
214    FcCharLeaf		*leaf;
215
216    pos = FcCharSetFindLeafPos (fcs, ucs4);
217    if (pos >= 0)
218	return FcCharSetLeaf(fcs, pos);
219
220    leaf = calloc (1, sizeof (FcCharLeaf));
221    if (!leaf)
222	return 0;
223
224    pos = -pos - 1;
225    if (!FcCharSetPutLeaf (fcs, ucs4, leaf, pos))
226    {
227	free (leaf);
228	return 0;
229    }
230    FcMemAlloc (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
231    return leaf;
232}
233
234static FcBool
235FcCharSetInsertLeaf (FcCharSet *fcs, FcChar32 ucs4, FcCharLeaf *leaf)
236{
237    int		    pos;
238
239    pos = FcCharSetFindLeafPos (fcs, ucs4);
240    if (pos >= 0)
241    {
242	FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
243	free (FcCharSetLeaf (fcs, pos));
244	FcCharSetLeaves(fcs)[pos] = FcPtrToOffset (FcCharSetLeaves(fcs),
245						   leaf);
246	return FcTrue;
247    }
248    pos = -pos - 1;
249    return FcCharSetPutLeaf (fcs, ucs4, leaf, pos);
250}
251
252FcBool
253FcCharSetAddChar (FcCharSet *fcs, FcChar32 ucs4)
254{
255    FcCharLeaf	*leaf;
256    FcChar32	*b;
257
258    if (fcs == NULL || fcs->ref == FC_REF_CONSTANT)
259	return FcFalse;
260    leaf = FcCharSetFindLeafCreate (fcs, ucs4);
261    if (!leaf)
262	return FcFalse;
263    b = &leaf->map[(ucs4 & 0xff) >> 5];
264    *b |= (1 << (ucs4 & 0x1f));
265    return FcTrue;
266}
267
268FcBool
269FcCharSetDelChar (FcCharSet *fcs, FcChar32 ucs4)
270{
271    FcCharLeaf	*leaf;
272    FcChar32	*b;
273
274    if (fcs == NULL || fcs->ref == FC_REF_CONSTANT)
275	return FcFalse;
276    leaf = FcCharSetFindLeaf (fcs, ucs4);
277    if (!leaf)
278	return FcTrue;
279    b = &leaf->map[(ucs4 & 0xff) >> 5];
280    *b &= ~(1 << (ucs4 & 0x1f));
281    /* We don't bother removing the leaf if it's empty */
282    return FcTrue;
283}
284
285/*
286 * An iterator for the leaves of a charset
287 */
288
289typedef struct _fcCharSetIter {
290    FcCharLeaf	    *leaf;
291    FcChar32	    ucs4;
292    int		    pos;
293} FcCharSetIter;
294
295/*
296 * Set iter->leaf to the leaf containing iter->ucs4 or higher
297 */
298
299static void
300FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
301{
302    int		    pos = FcCharSetFindLeafPos (fcs, iter->ucs4);
303
304    if (pos < 0)
305    {
306	pos = -pos - 1;
307	if (pos == fcs->num)
308	{
309	    iter->ucs4 = ~0;
310	    iter->leaf = 0;
311	    return;
312	}
313        iter->ucs4 = (FcChar32) FcCharSetNumbers(fcs)[pos] << 8;
314    }
315    iter->leaf = FcCharSetLeaf(fcs, pos);
316    iter->pos = pos;
317}
318
319static void
320FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
321{
322    int	pos = iter->pos + 1;
323    if (pos >= fcs->num)
324    {
325	iter->ucs4 = ~0;
326	iter->leaf = 0;
327    }
328    else
329    {
330	iter->ucs4 = (FcChar32) FcCharSetNumbers(fcs)[pos] << 8;
331	iter->leaf = FcCharSetLeaf(fcs, pos);
332	iter->pos = pos;
333    }
334}
335
336
337static void
338FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
339{
340    iter->ucs4 = 0;
341    iter->pos = 0;
342    FcCharSetIterSet (fcs, iter);
343}
344
345FcCharSet *
346FcCharSetCopy (FcCharSet *src)
347{
348    if (src)
349    {
350	if (src->ref != FC_REF_CONSTANT)
351	    src->ref++;
352	else
353	    FcCacheObjectReference (src);
354    }
355    return src;
356}
357
358FcBool
359FcCharSetEqual (const FcCharSet *a, const FcCharSet *b)
360{
361    FcCharSetIter   ai, bi;
362    int		    i;
363
364    if (a == b)
365	return FcTrue;
366    if (!a || !b)
367	return FcFalse;
368    for (FcCharSetIterStart (a, &ai), FcCharSetIterStart (b, &bi);
369	 ai.leaf && bi.leaf;
370	 FcCharSetIterNext (a, &ai), FcCharSetIterNext (b, &bi))
371    {
372	if (ai.ucs4 != bi.ucs4)
373	    return FcFalse;
374	for (i = 0; i < 256/32; i++)
375	    if (ai.leaf->map[i] != bi.leaf->map[i])
376		return FcFalse;
377    }
378    return ai.leaf == bi.leaf;
379}
380
381static FcBool
382FcCharSetAddLeaf (FcCharSet	*fcs,
383		  FcChar32	ucs4,
384		  FcCharLeaf	*leaf)
385{
386    FcCharLeaf   *new = FcCharSetFindLeafCreate (fcs, ucs4);
387    if (!new)
388	return FcFalse;
389    *new = *leaf;
390    return FcTrue;
391}
392
393static FcCharSet *
394FcCharSetOperate (const FcCharSet   *a,
395		  const FcCharSet   *b,
396		  FcBool	    (*overlap) (FcCharLeaf	    *result,
397						const FcCharLeaf    *al,
398						const FcCharLeaf    *bl),
399		  FcBool	aonly,
400		  FcBool	bonly)
401{
402    FcCharSet	    *fcs;
403    FcCharSetIter   ai, bi;
404
405    if (!a || !b)
406	goto bail0;
407    fcs = FcCharSetCreate ();
408    if (!fcs)
409	goto bail0;
410    FcCharSetIterStart (a, &ai);
411    FcCharSetIterStart (b, &bi);
412    while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
413    {
414	if (ai.ucs4 < bi.ucs4)
415	{
416	    if (aonly)
417	    {
418		if (!FcCharSetAddLeaf (fcs, ai.ucs4, ai.leaf))
419		    goto bail1;
420		FcCharSetIterNext (a, &ai);
421	    }
422	    else
423	    {
424		ai.ucs4 = bi.ucs4;
425		FcCharSetIterSet (a, &ai);
426	    }
427	}
428	else if (bi.ucs4 < ai.ucs4 )
429	{
430	    if (bonly)
431	    {
432		if (!FcCharSetAddLeaf (fcs, bi.ucs4, bi.leaf))
433		    goto bail1;
434		FcCharSetIterNext (b, &bi);
435	    }
436	    else
437	    {
438		bi.ucs4 = ai.ucs4;
439		FcCharSetIterSet (b, &bi);
440	    }
441	}
442	else
443	{
444	    FcCharLeaf  leaf;
445
446	    if ((*overlap) (&leaf, ai.leaf, bi.leaf))
447	    {
448		if (!FcCharSetAddLeaf (fcs, ai.ucs4, &leaf))
449		    goto bail1;
450	    }
451	    FcCharSetIterNext (a, &ai);
452	    FcCharSetIterNext (b, &bi);
453	}
454    }
455    return fcs;
456bail1:
457    FcCharSetDestroy (fcs);
458bail0:
459    return 0;
460}
461
462static FcBool
463FcCharSetIntersectLeaf (FcCharLeaf *result,
464			const FcCharLeaf *al,
465			const FcCharLeaf *bl)
466{
467    int	    i;
468    FcBool  nonempty = FcFalse;
469
470    for (i = 0; i < 256/32; i++)
471	if ((result->map[i] = al->map[i] & bl->map[i]))
472	    nonempty = FcTrue;
473    return nonempty;
474}
475
476FcCharSet *
477FcCharSetIntersect (const FcCharSet *a, const FcCharSet *b)
478{
479    return FcCharSetOperate (a, b, FcCharSetIntersectLeaf, FcFalse, FcFalse);
480}
481
482static FcBool
483FcCharSetUnionLeaf (FcCharLeaf *result,
484		    const FcCharLeaf *al,
485		    const FcCharLeaf *bl)
486{
487    int	i;
488
489    for (i = 0; i < 256/32; i++)
490	result->map[i] = al->map[i] | bl->map[i];
491    return FcTrue;
492}
493
494FcCharSet *
495FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
496{
497    return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
498}
499
500FcBool
501FcCharSetMerge (FcCharSet *a, const FcCharSet *b, FcBool *changed)
502{
503    int		ai = 0, bi = 0;
504    FcChar16	an, bn;
505
506    if (!a || !b)
507	return FcFalse;
508
509    if (a->ref == FC_REF_CONSTANT) {
510	if (changed)
511	    *changed = FcFalse;
512	return FcFalse;
513    }
514
515    if (changed) {
516	*changed = !FcCharSetIsSubset(b, a);
517	if (!*changed)
518	    return FcTrue;
519    }
520
521    while (bi < b->num)
522    {
523	an = ai < a->num ? FcCharSetNumbers(a)[ai] : ~0;
524	bn = FcCharSetNumbers(b)[bi];
525
526	if (an < bn)
527	{
528	    ai = FcCharSetFindLeafForward (a, ai + 1, bn);
529	    if (ai < 0)
530		ai = -ai - 1;
531	}
532	else
533	{
534	    FcCharLeaf *bl = FcCharSetLeaf(b, bi);
535	    if (bn < an)
536	    {
537		if (!FcCharSetAddLeaf (a, bn << 8, bl))
538		    return FcFalse;
539	    }
540	    else
541	    {
542		FcCharLeaf *al = FcCharSetLeaf(a, ai);
543		FcCharSetUnionLeaf (al, al, bl);
544	    }
545
546	    ai++;
547	    bi++;
548	}
549    }
550
551    return FcTrue;
552}
553
554static FcBool
555FcCharSetSubtractLeaf (FcCharLeaf *result,
556		       const FcCharLeaf *al,
557		       const FcCharLeaf *bl)
558{
559    int	    i;
560    FcBool  nonempty = FcFalse;
561
562    for (i = 0; i < 256/32; i++)
563	if ((result->map[i] = al->map[i] & ~bl->map[i]))
564	    nonempty = FcTrue;
565    return nonempty;
566}
567
568FcCharSet *
569FcCharSetSubtract (const FcCharSet *a, const FcCharSet *b)
570{
571    return FcCharSetOperate (a, b, FcCharSetSubtractLeaf, FcTrue, FcFalse);
572}
573
574FcBool
575FcCharSetHasChar (const FcCharSet *fcs, FcChar32 ucs4)
576{
577    FcCharLeaf	*leaf;
578
579    if (!fcs)
580	return FcFalse;
581    leaf = FcCharSetFindLeaf (fcs, ucs4);
582    if (!leaf)
583	return FcFalse;
584    return (leaf->map[(ucs4 & 0xff) >> 5] & (1 << (ucs4 & 0x1f))) != 0;
585}
586
587static FcChar32
588FcCharSetPopCount (FcChar32 c1)
589{
590#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
591    return __builtin_popcount (c1);
592#else
593    /* hackmem 169 */
594    FcChar32	c2 = (c1 >> 1) & 033333333333;
595    c2 = c1 - c2 - ((c2 >> 1) & 033333333333);
596    return (((c2 + (c2 >> 3)) & 030707070707) % 077);
597#endif
598}
599
600FcChar32
601FcCharSetIntersectCount (const FcCharSet *a, const FcCharSet *b)
602{
603    FcCharSetIter   ai, bi;
604    FcChar32	    count = 0;
605
606    if (a && b)
607    {
608	FcCharSetIterStart (a, &ai);
609	FcCharSetIterStart (b, &bi);
610	while (ai.leaf && bi.leaf)
611	{
612	    if (ai.ucs4 == bi.ucs4)
613	    {
614		FcChar32	*am = ai.leaf->map;
615		FcChar32	*bm = bi.leaf->map;
616		int		i = 256/32;
617		while (i--)
618		    count += FcCharSetPopCount (*am++ & *bm++);
619		FcCharSetIterNext (a, &ai);
620	    }
621	    else if (ai.ucs4 < bi.ucs4)
622	    {
623		ai.ucs4 = bi.ucs4;
624		FcCharSetIterSet (a, &ai);
625	    }
626	    if (bi.ucs4 < ai.ucs4)
627	    {
628		bi.ucs4 = ai.ucs4;
629		FcCharSetIterSet (b, &bi);
630	    }
631	}
632    }
633    return count;
634}
635
636FcChar32
637FcCharSetCount (const FcCharSet *a)
638{
639    FcCharSetIter   ai;
640    FcChar32	    count = 0;
641
642    if (a)
643    {
644	for (FcCharSetIterStart (a, &ai); ai.leaf; FcCharSetIterNext (a, &ai))
645	{
646	    int		    i = 256/32;
647	    FcChar32	    *am = ai.leaf->map;
648
649	    while (i--)
650		count += FcCharSetPopCount (*am++);
651	}
652    }
653    return count;
654}
655
656FcChar32
657FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b)
658{
659    FcCharSetIter   ai, bi;
660    FcChar32	    count = 0;
661
662    if (a && b)
663    {
664	FcCharSetIterStart (a, &ai);
665	FcCharSetIterStart (b, &bi);
666	while (ai.leaf)
667	{
668	    if (ai.ucs4 <= bi.ucs4)
669	    {
670		FcChar32	*am = ai.leaf->map;
671		int		i = 256/32;
672		if (ai.ucs4 == bi.ucs4)
673		{
674		    FcChar32	*bm = bi.leaf->map;
675		    while (i--)
676			count += FcCharSetPopCount (*am++ & ~*bm++);
677		}
678		else
679		{
680		    while (i--)
681			count += FcCharSetPopCount (*am++);
682		}
683		FcCharSetIterNext (a, &ai);
684	    }
685	    else if (bi.leaf)
686	    {
687		bi.ucs4 = ai.ucs4;
688		FcCharSetIterSet (b, &bi);
689	    }
690	}
691    }
692    return count;
693}
694
695/*
696 * return FcTrue iff a is a subset of b
697 */
698FcBool
699FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
700{
701    int		ai, bi;
702    FcChar16	an, bn;
703
704    if (a == b)
705	return FcTrue;
706    if (!a || !b)
707	return FcFalse;
708    bi = 0;
709    ai = 0;
710    while (ai < a->num && bi < b->num)
711    {
712	an = FcCharSetNumbers(a)[ai];
713	bn = FcCharSetNumbers(b)[bi];
714	/*
715	 * Check matching pages
716	 */
717	if (an == bn)
718	{
719	    FcChar32	*am = FcCharSetLeaf(a, ai)->map;
720	    FcChar32	*bm = FcCharSetLeaf(b, bi)->map;
721
722	    if (am != bm)
723	    {
724		int	i = 256/32;
725		/*
726		 * Does am have any bits not in bm?
727		 */
728		while (i--)
729		    if (*am++ & ~*bm++)
730			return FcFalse;
731	    }
732	    ai++;
733	    bi++;
734	}
735	/*
736	 * Does a have any pages not in b?
737	 */
738	else if (an < bn)
739	    return FcFalse;
740	else
741	{
742	    bi = FcCharSetFindLeafForward (b, bi + 1, an);
743	    if (bi < 0)
744		bi = -bi - 1;
745	}
746    }
747    /*
748     * did we look at every page?
749     */
750    return ai >= a->num;
751}
752
753/*
754 * These two functions efficiently walk the entire charmap for
755 * other software (like pango) that want their own copy
756 */
757
758FcChar32
759FcCharSetNextPage (const FcCharSet  *a,
760		   FcChar32	    map[FC_CHARSET_MAP_SIZE],
761		   FcChar32	    *next)
762{
763    FcCharSetIter   ai;
764    FcChar32	    page;
765
766    if (!a)
767	return FC_CHARSET_DONE;
768    ai.ucs4 = *next;
769    FcCharSetIterSet (a, &ai);
770    if (!ai.leaf)
771	return FC_CHARSET_DONE;
772
773    /*
774     * Save current information
775     */
776    page = ai.ucs4;
777    memcpy (map, ai.leaf->map, sizeof (ai.leaf->map));
778    /*
779     * Step to next page
780     */
781    FcCharSetIterNext (a, &ai);
782    *next = ai.ucs4;
783
784    return page;
785}
786
787FcChar32
788FcCharSetFirstPage (const FcCharSet *a,
789		    FcChar32	    map[FC_CHARSET_MAP_SIZE],
790		    FcChar32	    *next)
791{
792    *next = 0;
793    return FcCharSetNextPage (a, map, next);
794}
795
796/*
797 * old coverage API, rather hard to use correctly
798 */
799
800FcChar32
801FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result)
802{
803    FcCharSetIter   ai;
804
805    ai.ucs4 = page;
806    FcCharSetIterSet (a, &ai);
807    if (!ai.leaf)
808    {
809	memset (result, '\0', 256 / 8);
810	page = 0;
811    }
812    else
813    {
814	memcpy (result, ai.leaf->map, sizeof (ai.leaf->map));
815	FcCharSetIterNext (a, &ai);
816	page = ai.ucs4;
817    }
818    return page;
819}
820
821/*
822 * ASCII representation of charsets.
823 *
824 * Each leaf is represented as 9 32-bit values, the code of the first character followed
825 * by 8 32 bit values for the leaf itself.  Each value is encoded as 5 ASCII characters,
826 * only 85 different values are used to avoid control characters as well as the other
827 * characters used to encode font names.  85**5 > 2^32 so things work out, but
828 * it's not exactly human readable output.  As a special case, 0 is encoded as a space
829 */
830
831static const unsigned char	charToValue[256] = {
832    /*     "" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
833    /*   "\b" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
834    /* "\020" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
835    /* "\030" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
836    /*    " " */ 0xff,  0x00,  0xff,  0x01,  0x02,  0x03,  0x04,  0xff,
837    /*    "(" */ 0x05,  0x06,  0x07,  0x08,  0xff,  0xff,  0x09,  0x0a,
838    /*    "0" */ 0x0b,  0x0c,  0x0d,  0x0e,  0x0f,  0x10,  0x11,  0x12,
839    /*    "8" */ 0x13,  0x14,  0xff,  0x15,  0x16,  0xff,  0x17,  0x18,
840    /*    "@" */ 0x19,  0x1a,  0x1b,  0x1c,  0x1d,  0x1e,  0x1f,  0x20,
841    /*    "H" */ 0x21,  0x22,  0x23,  0x24,  0x25,  0x26,  0x27,  0x28,
842    /*    "P" */ 0x29,  0x2a,  0x2b,  0x2c,  0x2d,  0x2e,  0x2f,  0x30,
843    /*    "X" */ 0x31,  0x32,  0x33,  0x34,  0xff,  0x35,  0x36,  0xff,
844    /*    "`" */ 0xff,  0x37,  0x38,  0x39,  0x3a,  0x3b,  0x3c,  0x3d,
845    /*    "h" */ 0x3e,  0x3f,  0x40,  0x41,  0x42,  0x43,  0x44,  0x45,
846    /*    "p" */ 0x46,  0x47,  0x48,  0x49,  0x4a,  0x4b,  0x4c,  0x4d,
847    /*    "x" */ 0x4e,  0x4f,  0x50,  0x51,  0x52,  0x53,  0x54,  0xff,
848    /* "\200" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
849    /* "\210" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
850    /* "\220" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
851    /* "\230" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
852    /* "\240" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
853    /* "\250" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
854    /* "\260" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
855    /* "\270" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
856    /* "\300" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
857    /* "\310" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
858    /* "\320" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
859    /* "\330" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
860    /* "\340" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
861    /* "\350" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
862    /* "\360" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
863    /* "\370" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
864};
865
866static const FcChar8 valueToChar[0x55] = {
867    /* 0x00 */ '!', '#', '$', '%', '&', '(', ')', '*',
868    /* 0x08 */ '+', '.', '/', '0', '1', '2', '3', '4',
869    /* 0x10 */ '5', '6', '7', '8', '9', ';', '<', '>',
870    /* 0x18 */ '?', '@', 'A', 'B', 'C', 'D', 'E', 'F',
871    /* 0x20 */ 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
872    /* 0x28 */ 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
873    /* 0x30 */ 'W', 'X', 'Y', 'Z', '[', ']', '^', 'a',
874    /* 0x38 */ 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
875    /* 0x40 */ 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q',
876    /* 0x48 */ 'r', 's', 't', 'u', 'v', 'w', 'x', 'y',
877    /* 0x50 */ 'z', '{', '|', '}', '~',
878};
879
880static FcChar8 *
881FcCharSetParseValue (FcChar8 *string, FcChar32 *value)
882{
883    int		i;
884    FcChar32	v;
885    FcChar32	c;
886
887    if (*string == ' ')
888    {
889	v = 0;
890	string++;
891    }
892    else
893    {
894	v = 0;
895	for (i = 0; i < 5; i++)
896	{
897	    if (!(c = (FcChar32) (unsigned char) *string++))
898		return 0;
899	    c = charToValue[c];
900	    if (c == 0xff)
901		return 0;
902	    v = v * 85 + c;
903	}
904    }
905    *value = v;
906    return string;
907}
908
909static FcBool
910FcCharSetUnparseValue (FcStrBuf *buf, FcChar32 value)
911{
912    int	    i;
913    if (value == 0)
914    {
915	return FcStrBufChar (buf, ' ');
916    }
917    else
918    {
919	FcChar8	string[6];
920	FcChar8	*s = string + 5;
921	string[5] = '\0';
922	for (i = 0; i < 5; i++)
923	{
924	    *--s = valueToChar[value % 85];
925	    value /= 85;
926	}
927	for (i = 0; i < 5; i++)
928	    if (!FcStrBufChar (buf, *s++))
929		return FcFalse;
930    }
931    return FcTrue;
932}
933
934FcCharSet *
935FcNameParseCharSet (FcChar8 *string)
936{
937    FcCharSet	*c;
938    FcChar32	ucs4;
939    FcCharLeaf	*leaf;
940    FcCharLeaf	temp;
941    FcChar32	bits;
942    int		i;
943
944    c = FcCharSetCreate ();
945    if (!c)
946	goto bail0;
947    while (*string)
948    {
949	string = FcCharSetParseValue (string, &ucs4);
950	if (!string)
951	    goto bail1;
952	bits = 0;
953	for (i = 0; i < 256/32; i++)
954	{
955	    string = FcCharSetParseValue (string, &temp.map[i]);
956	    if (!string)
957		goto bail1;
958	    bits |= temp.map[i];
959	}
960	if (bits)
961	{
962	    leaf = malloc (sizeof (FcCharLeaf));
963	    if (!leaf)
964		goto bail1;
965	    *leaf = temp;
966	    if (!FcCharSetInsertLeaf (c, ucs4, leaf))
967		goto bail1;
968	}
969    }
970    return c;
971bail1:
972    if (c->num)
973    {
974	FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcCharLeaf *));
975	free (FcCharSetLeaves (c));
976    }
977    if (c->num)
978    {
979	FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcChar16));
980	free (FcCharSetNumbers (c));
981    }
982    FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
983    free (c);
984bail0:
985    return NULL;
986}
987
988FcBool
989FcNameUnparseCharSet (FcStrBuf *buf, const FcCharSet *c)
990{
991    FcCharSetIter   ci;
992    int		    i;
993#ifdef CHECK
994    int		    len = buf->len;
995#endif
996
997    for (FcCharSetIterStart (c, &ci);
998	 ci.leaf;
999	 FcCharSetIterNext (c, &ci))
1000    {
1001	if (!FcCharSetUnparseValue (buf, ci.ucs4))
1002	    return FcFalse;
1003	for (i = 0; i < 256/32; i++)
1004	    if (!FcCharSetUnparseValue (buf, ci.leaf->map[i]))
1005		return FcFalse;
1006    }
1007#ifdef CHECK
1008    {
1009	FcCharSet	*check;
1010	FcChar32	missing;
1011	FcCharSetIter	ci, checki;
1012
1013	/* null terminate for parser */
1014	FcStrBufChar (buf, '\0');
1015	/* step back over null for life after test */
1016	buf->len--;
1017	check = FcNameParseCharSet (buf->buf + len);
1018	FcCharSetIterStart (c, &ci);
1019	FcCharSetIterStart (check, &checki);
1020	while (ci.leaf || checki.leaf)
1021	{
1022	    if (ci.ucs4 < checki.ucs4)
1023	    {
1024		printf ("Missing leaf node at 0x%x\n", ci.ucs4);
1025		FcCharSetIterNext (c, &ci);
1026	    }
1027	    else if (checki.ucs4 < ci.ucs4)
1028	    {
1029		printf ("Extra leaf node at 0x%x\n", checki.ucs4);
1030		FcCharSetIterNext (check, &checki);
1031	    }
1032	    else
1033	    {
1034		int	    i = 256/32;
1035		FcChar32    *cm = ci.leaf->map;
1036		FcChar32    *checkm = checki.leaf->map;
1037
1038		for (i = 0; i < 256; i += 32)
1039		{
1040		    if (*cm != *checkm)
1041			printf ("Mismatching sets at 0x%08x: 0x%08x != 0x%08x\n",
1042				ci.ucs4 + i, *cm, *checkm);
1043		    cm++;
1044		    checkm++;
1045		}
1046		FcCharSetIterNext (c, &ci);
1047		FcCharSetIterNext (check, &checki);
1048	    }
1049	}
1050	if ((missing = FcCharSetSubtractCount (c, check)))
1051	    printf ("%d missing in reparsed result\n", missing);
1052	if ((missing = FcCharSetSubtractCount (check, c)))
1053	    printf ("%d extra in reparsed result\n", missing);
1054	FcCharSetDestroy (check);
1055    }
1056#endif
1057
1058    return FcTrue;
1059}
1060
1061typedef struct _FcCharLeafEnt FcCharLeafEnt;
1062
1063struct _FcCharLeafEnt {
1064    FcCharLeafEnt   *next;
1065    FcChar32	    hash;
1066    FcCharLeaf	    leaf;
1067};
1068
1069#define FC_CHAR_LEAF_BLOCK	(4096 / sizeof (FcCharLeafEnt))
1070#define FC_CHAR_LEAF_HASH_SIZE	257
1071
1072typedef struct _FcCharSetEnt FcCharSetEnt;
1073
1074struct _FcCharSetEnt {
1075    FcCharSetEnt	*next;
1076    FcChar32		hash;
1077    FcCharSet		set;
1078};
1079
1080typedef struct _FcCharSetOrigEnt FcCharSetOrigEnt;
1081
1082struct _FcCharSetOrigEnt {
1083    FcCharSetOrigEnt	*next;
1084    const FcCharSet    	*orig;
1085    const FcCharSet    	*frozen;
1086};
1087
1088#define FC_CHAR_SET_HASH_SIZE    67
1089
1090struct _FcCharSetFreezer {
1091    FcCharLeafEnt   *leaf_hash_table[FC_CHAR_LEAF_HASH_SIZE];
1092    FcCharLeafEnt   **leaf_blocks;
1093    int		    leaf_block_count;
1094    FcCharSetEnt    *set_hash_table[FC_CHAR_SET_HASH_SIZE];
1095    FcCharSetOrigEnt	*orig_hash_table[FC_CHAR_SET_HASH_SIZE];
1096    FcCharLeafEnt   *current_block;
1097    int		    leaf_remain;
1098    int		    leaves_seen;
1099    int		    charsets_seen;
1100    int		    leaves_allocated;
1101    int		    charsets_allocated;
1102};
1103
1104static FcCharLeafEnt *
1105FcCharLeafEntCreate (FcCharSetFreezer *freezer)
1106{
1107    if (!freezer->leaf_remain)
1108    {
1109	FcCharLeafEnt **newBlocks;
1110
1111	freezer->leaf_block_count++;
1112	newBlocks = realloc (freezer->leaf_blocks, freezer->leaf_block_count * sizeof (FcCharLeafEnt *));
1113	if (!newBlocks)
1114	    return 0;
1115	freezer->leaf_blocks = newBlocks;
1116	freezer->current_block = freezer->leaf_blocks[freezer->leaf_block_count-1] = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
1117	if (!freezer->current_block)
1118	    return 0;
1119	FcMemAlloc (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
1120	freezer->leaf_remain = FC_CHAR_LEAF_BLOCK;
1121    }
1122    freezer->leaf_remain--;
1123    freezer->leaves_allocated++;
1124    return freezer->current_block++;
1125}
1126
1127static FcChar32
1128FcCharLeafHash (FcCharLeaf *leaf)
1129{
1130    FcChar32	hash = 0;
1131    int		i;
1132
1133    for (i = 0; i < 256/32; i++)
1134	hash = ((hash << 1) | (hash >> 31)) ^ leaf->map[i];
1135    return hash;
1136}
1137
1138static FcCharLeaf *
1139FcCharSetFreezeLeaf (FcCharSetFreezer *freezer, FcCharLeaf *leaf)
1140{
1141    FcChar32			hash = FcCharLeafHash (leaf);
1142    FcCharLeafEnt		**bucket = &freezer->leaf_hash_table[hash % FC_CHAR_LEAF_HASH_SIZE];
1143    FcCharLeafEnt		*ent;
1144
1145    for (ent = *bucket; ent; ent = ent->next)
1146    {
1147	if (ent->hash == hash && !memcmp (&ent->leaf, leaf, sizeof (FcCharLeaf)))
1148	    return &ent->leaf;
1149    }
1150
1151    ent = FcCharLeafEntCreate(freezer);
1152    if (!ent)
1153	return 0;
1154    ent->leaf = *leaf;
1155    ent->hash = hash;
1156    ent->next = *bucket;
1157    *bucket = ent;
1158    return &ent->leaf;
1159}
1160
1161static FcChar32
1162FcCharSetHash (FcCharSet *fcs)
1163{
1164    FcChar32	hash = 0;
1165    int		i;
1166
1167    /* hash in leaves */
1168    for (i = 0; i < fcs->num; i++)
1169	hash = ((hash << 1) | (hash >> 31)) ^ FcCharLeafHash (FcCharSetLeaf(fcs,i));
1170    /* hash in numbers */
1171    for (i = 0; i < fcs->num; i++)
1172	hash = ((hash << 1) | (hash >> 31)) ^ *FcCharSetNumbers(fcs);
1173    return hash;
1174}
1175
1176static FcBool
1177FcCharSetFreezeOrig (FcCharSetFreezer *freezer, const FcCharSet *orig, const FcCharSet *frozen)
1178{
1179    FcCharSetOrigEnt	**bucket = &freezer->orig_hash_table[((uintptr_t) orig) & FC_CHAR_SET_HASH_SIZE];
1180    FcCharSetOrigEnt	*ent;
1181
1182    ent = malloc (sizeof (FcCharSetOrigEnt));
1183    if (!ent)
1184	return FcFalse;
1185    ent->orig = orig;
1186    ent->frozen = frozen;
1187    ent->next = *bucket;
1188    *bucket = ent;
1189    return FcTrue;
1190}
1191
1192static FcCharSet *
1193FcCharSetFreezeBase (FcCharSetFreezer *freezer, FcCharSet *fcs, const FcCharSet *orig)
1194{
1195    FcChar32		hash = FcCharSetHash (fcs);
1196    FcCharSetEnt	**bucket = &freezer->set_hash_table[hash % FC_CHAR_SET_HASH_SIZE];
1197    FcCharSetEnt	*ent;
1198    int			size;
1199    int			i;
1200
1201    for (ent = *bucket; ent; ent = ent->next)
1202    {
1203	if (ent->hash == hash &&
1204	    ent->set.num == fcs->num &&
1205	    !memcmp (FcCharSetNumbers(&ent->set),
1206		     FcCharSetNumbers(fcs),
1207		     fcs->num * sizeof (FcChar16)))
1208	{
1209	    FcBool ok = FcTrue;
1210	    int i;
1211
1212	    for (i = 0; i < fcs->num; i++)
1213		if (FcCharSetLeaf(&ent->set, i) != FcCharSetLeaf(fcs, i))
1214		    ok = FcFalse;
1215	    if (ok)
1216		return &ent->set;
1217	}
1218    }
1219
1220    size = (sizeof (FcCharSetEnt) +
1221	    fcs->num * sizeof (FcCharLeaf *) +
1222	    fcs->num * sizeof (FcChar16));
1223    ent = malloc (size);
1224    if (!ent)
1225	return 0;
1226    FcMemAlloc (FC_MEM_CHARSET, size);
1227
1228    freezer->charsets_allocated++;
1229
1230    ent->set.ref = FC_REF_CONSTANT;
1231    ent->set.num = fcs->num;
1232    if (fcs->num)
1233    {
1234	intptr_t    *ent_leaves;
1235
1236	ent->set.leaves_offset = sizeof (ent->set);
1237	ent->set.numbers_offset = (ent->set.leaves_offset +
1238				   fcs->num * sizeof (intptr_t));
1239
1240	ent_leaves = FcCharSetLeaves (&ent->set);
1241	for (i = 0; i < fcs->num; i++)
1242	    ent_leaves[i] = FcPtrToOffset (ent_leaves,
1243					   FcCharSetLeaf (fcs, i));
1244	memcpy (FcCharSetNumbers (&ent->set),
1245		FcCharSetNumbers (fcs),
1246		fcs->num * sizeof (FcChar16));
1247    }
1248    else
1249    {
1250	ent->set.leaves_offset = 0;
1251	ent->set.numbers_offset = 0;
1252    }
1253
1254    ent->hash = hash;
1255    ent->next = *bucket;
1256    *bucket = ent;
1257
1258    return &ent->set;
1259}
1260
1261static const FcCharSet *
1262FcCharSetFindFrozen (FcCharSetFreezer *freezer, const FcCharSet *orig)
1263{
1264    FcCharSetOrigEnt    **bucket = &freezer->orig_hash_table[((uintptr_t) orig) & FC_CHAR_SET_HASH_SIZE];
1265    FcCharSetOrigEnt	*ent;
1266
1267    for (ent = *bucket; ent; ent = ent->next)
1268	if (ent->orig == orig)
1269	    return ent->frozen;
1270    return NULL;
1271}
1272
1273const FcCharSet *
1274FcCharSetFreeze (FcCharSetFreezer *freezer, const FcCharSet *fcs)
1275{
1276    FcCharSet	    *b;
1277    const FcCharSet *n = 0;
1278    FcCharLeaf	    *l;
1279    int		    i;
1280
1281    b = FcCharSetCreate ();
1282    if (!b)
1283	goto bail0;
1284    for (i = 0; i < fcs->num; i++)
1285    {
1286	l = FcCharSetFreezeLeaf (freezer, FcCharSetLeaf(fcs, i));
1287	if (!l)
1288	    goto bail1;
1289	if (!FcCharSetInsertLeaf (b, FcCharSetNumbers(fcs)[i] << 8, l))
1290	    goto bail1;
1291    }
1292    n = FcCharSetFreezeBase (freezer, b, fcs);
1293    if (!FcCharSetFreezeOrig (freezer, fcs, n))
1294    {
1295	n = NULL;
1296	goto bail1;
1297    }
1298    freezer->charsets_seen++;
1299    freezer->leaves_seen += fcs->num;
1300bail1:
1301    if (b->num)
1302    {
1303	FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcCharLeaf *));
1304	free (FcCharSetLeaves (b));
1305    }
1306    if (b->num)
1307    {
1308	FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcChar16));
1309	free (FcCharSetNumbers (b));
1310    }
1311    FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
1312    free (b);
1313bail0:
1314    return n;
1315}
1316
1317FcCharSetFreezer *
1318FcCharSetFreezerCreate (void)
1319{
1320    FcCharSetFreezer	*freezer;
1321
1322    freezer = calloc (1, sizeof (FcCharSetFreezer));
1323    return freezer;
1324}
1325
1326void
1327FcCharSetFreezerDestroy (FcCharSetFreezer *freezer)
1328{
1329    int i;
1330
1331    if (FcDebug() & FC_DBG_CACHE)
1332    {
1333	printf ("\ncharsets %d -> %d leaves %d -> %d\n",
1334		freezer->charsets_seen, freezer->charsets_allocated,
1335		freezer->leaves_seen, freezer->leaves_allocated);
1336    }
1337    for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1338    {
1339	FcCharSetEnt	*ent, *next;
1340	for (ent = freezer->set_hash_table[i]; ent; ent = next)
1341	{
1342	    next = ent->next;
1343	    FcMemFree (FC_MEM_CHARSET, (sizeof (FcCharSetEnt) +
1344					ent->set.num * sizeof (FcCharLeaf *) +
1345					ent->set.num * sizeof (FcChar16)));
1346	    free (ent);
1347	}
1348    }
1349
1350    for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1351    {
1352	FcCharSetOrigEnt	*ent, *next;
1353	for (ent = freezer->orig_hash_table[i]; ent; ent = next)
1354	{
1355	    next = ent->next;
1356	    free (ent);
1357	}
1358    }
1359
1360    for (i = 0; i < freezer->leaf_block_count; i++)
1361    {
1362	free (freezer->leaf_blocks[i]);
1363	FcMemFree (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
1364    }
1365
1366    free (freezer->leaf_blocks);
1367    free (freezer);
1368}
1369
1370FcBool
1371FcCharSetSerializeAlloc (FcSerialize *serialize, const FcCharSet *cs)
1372{
1373    intptr_t	    *leaves;
1374    FcChar16	    *numbers;
1375    int		    i;
1376
1377    if (cs->ref != FC_REF_CONSTANT)
1378    {
1379	if (!serialize->cs_freezer)
1380	{
1381	    serialize->cs_freezer = FcCharSetFreezerCreate ();
1382	    if (!serialize->cs_freezer)
1383		return FcFalse;
1384	}
1385	if (FcCharSetFindFrozen (serialize->cs_freezer, cs))
1386	    return FcTrue;
1387
1388        cs = FcCharSetFreeze (serialize->cs_freezer, cs);
1389    }
1390
1391    leaves = FcCharSetLeaves (cs);
1392    numbers = FcCharSetNumbers (cs);
1393
1394    if (!FcSerializeAlloc (serialize, cs, sizeof (FcCharSet)))
1395	return FcFalse;
1396    if (!FcSerializeAlloc (serialize, leaves, cs->num * sizeof (intptr_t)))
1397	return FcFalse;
1398    if (!FcSerializeAlloc (serialize, numbers, cs->num * sizeof (FcChar16)))
1399	return FcFalse;
1400    for (i = 0; i < cs->num; i++)
1401	if (!FcSerializeAlloc (serialize, FcCharSetLeaf(cs, i),
1402			       sizeof (FcCharLeaf)))
1403	    return FcFalse;
1404    return FcTrue;
1405}
1406
1407FcCharSet *
1408FcCharSetSerialize(FcSerialize *serialize, const FcCharSet *cs)
1409{
1410    FcCharSet	*cs_serialized;
1411    intptr_t	*leaves, *leaves_serialized;
1412    FcChar16	*numbers, *numbers_serialized;
1413    FcCharLeaf	*leaf, *leaf_serialized;
1414    int		i;
1415
1416    if (cs->ref != FC_REF_CONSTANT && serialize->cs_freezer)
1417    {
1418	cs = FcCharSetFindFrozen (serialize->cs_freezer, cs);
1419	if (!cs)
1420	    return NULL;
1421    }
1422
1423    cs_serialized = FcSerializePtr (serialize, cs);
1424    if (!cs_serialized)
1425	return NULL;
1426
1427    cs_serialized->ref = FC_REF_CONSTANT;
1428    cs_serialized->num = cs->num;
1429
1430    if (cs->num)
1431    {
1432	leaves = FcCharSetLeaves (cs);
1433	leaves_serialized = FcSerializePtr (serialize, leaves);
1434	if (!leaves_serialized)
1435	    return NULL;
1436
1437	cs_serialized->leaves_offset = FcPtrToOffset (cs_serialized,
1438						      leaves_serialized);
1439
1440	numbers = FcCharSetNumbers (cs);
1441	numbers_serialized = FcSerializePtr (serialize, numbers);
1442	if (!numbers)
1443	    return NULL;
1444
1445	cs_serialized->numbers_offset = FcPtrToOffset (cs_serialized,
1446						       numbers_serialized);
1447
1448	for (i = 0; i < cs->num; i++)
1449	{
1450	    leaf = FcCharSetLeaf (cs, i);
1451	    leaf_serialized = FcSerializePtr (serialize, leaf);
1452	    if (!leaf_serialized)
1453		return NULL;
1454	    *leaf_serialized = *leaf;
1455	    leaves_serialized[i] = FcPtrToOffset (leaves_serialized,
1456						  leaf_serialized);
1457	    numbers_serialized[i] = numbers[i];
1458	}
1459    }
1460    else
1461    {
1462	cs_serialized->leaves_offset = 0;
1463	cs_serialized->numbers_offset = 0;
1464    }
1465
1466    return cs_serialized;
1467}
1468#define __fccharset__
1469#include "fcaliastail.h"
1470#undef __fccharset__
1471