2 * $RCSId: xc/lib/fontconfig/src/fccharset.c,v 1.18 2002/08/22 07:36:44 keithp Exp $
4 * Copyright © 2001 Keith Packard
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.
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.
31 FcCharSetCreate (void)
35 fcs = (FcCharSet *) malloc (sizeof (FcCharSet));
38 FcMemAlloc (FC_MEM_CHARSET, sizeof (FcCharSet));
41 fcs->leaves_offset = 0;
42 fcs->numbers_offset = 0;
49 return FcCharSetCreate ();
53 FcCharSetDestroy (FcCharSet *fcs)
57 if (fcs->ref == FC_REF_CONSTANT)
59 FcCacheObjectDereference (fcs);
64 for (i = 0; i < fcs->num; i++)
66 FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
67 free (FcCharSetLeaf (fcs, i));
71 FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (intptr_t));
72 free (FcCharSetLeaves (fcs));
76 FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
77 free (FcCharSetNumbers (fcs));
79 FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
84 * Locate the leaf containing the specified char, return
85 * its index if it exists, otherwise return negative of
86 * the (position + 1) where it should be inserted
90 FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
92 FcChar16 *numbers = FcCharSetNumbers(fcs);
95 int high = fcs->num - 1;
102 int mid = (low + high) >> 1;
111 if (high < 0 || (high < fcs->num && numbers[high] < ucs4))
117 FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
119 int pos = FcCharSetFindLeafPos (fcs, ucs4);
121 return FcCharSetLeaf(fcs, pos);
126 FcCharSetPutLeaf (FcCharSet *fcs,
131 intptr_t *leaves = FcCharSetLeaves (fcs);
132 FcChar16 *numbers = FcCharSetNumbers (fcs);
138 leaves = malloc (sizeof (*leaves));
141 intptr_t *new_leaves = realloc (leaves, (fcs->num + 1) *
143 intptr_t distance = (intptr_t) new_leaves - (intptr_t) leaves;
145 if (new_leaves && distance)
149 for (i = 0; i < fcs->num; i++)
150 new_leaves[i] -= distance;
158 FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (intptr_t));
159 FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (intptr_t));
160 fcs->leaves_offset = FcPtrToOffset (fcs, leaves);
163 numbers = malloc (sizeof (FcChar16));
165 numbers = realloc (numbers, (fcs->num + 1) * sizeof (FcChar16));
170 FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
171 FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcChar16));
172 fcs->numbers_offset = FcPtrToOffset (fcs, numbers);
174 memmove (leaves + pos + 1, leaves + pos,
175 (fcs->num - pos) * sizeof (*leaves));
176 memmove (numbers + pos + 1, numbers + pos,
177 (fcs->num - pos) * sizeof (*numbers));
178 numbers[pos] = (FcChar16) ucs4;
179 leaves[pos] = FcPtrToOffset (leaves, leaf);
185 * Locate the leaf containing the specified char, creating it
190 FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
195 pos = FcCharSetFindLeafPos (fcs, ucs4);
197 return FcCharSetLeaf(fcs, pos);
199 leaf = calloc (1, sizeof (FcCharLeaf));
204 if (!FcCharSetPutLeaf (fcs, ucs4, leaf, pos))
209 FcMemAlloc (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
214 FcCharSetInsertLeaf (FcCharSet *fcs, FcChar32 ucs4, FcCharLeaf *leaf)
218 pos = FcCharSetFindLeafPos (fcs, ucs4);
221 FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
222 free (FcCharSetLeaf (fcs, pos));
223 FcCharSetLeaves(fcs)[pos] = FcPtrToOffset (FcCharSetLeaves(fcs),
228 return FcCharSetPutLeaf (fcs, ucs4, leaf, pos);
232 FcCharSetAddChar (FcCharSet *fcs, FcChar32 ucs4)
237 if (fcs->ref == FC_REF_CONSTANT)
239 leaf = FcCharSetFindLeafCreate (fcs, ucs4);
242 b = &leaf->map[(ucs4 & 0xff) >> 5];
243 *b |= (1 << (ucs4 & 0x1f));
248 * An iterator for the leaves of a charset
251 typedef struct _fcCharSetIter {
258 * Set iter->leaf to the leaf containing iter->ucs4 or higher
262 FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
264 int pos = FcCharSetFindLeafPos (fcs, iter->ucs4);
275 iter->ucs4 = (FcChar32) FcCharSetNumbers(fcs)[pos] << 8;
277 iter->leaf = FcCharSetLeaf(fcs, pos);
282 FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
284 int pos = iter->pos + 1;
292 iter->ucs4 = (FcChar32) FcCharSetNumbers(fcs)[pos] << 8;
293 iter->leaf = FcCharSetLeaf(fcs, pos);
300 FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
304 FcCharSetIterSet (fcs, iter);
308 FcCharSetCopy (FcCharSet *src)
310 if (src->ref != FC_REF_CONSTANT)
313 FcCacheObjectReference (src);
318 FcCharSetEqual (const FcCharSet *a, const FcCharSet *b)
320 FcCharSetIter ai, bi;
325 for (FcCharSetIterStart (a, &ai), FcCharSetIterStart (b, &bi);
327 FcCharSetIterNext (a, &ai), FcCharSetIterNext (b, &bi))
329 if (ai.ucs4 != bi.ucs4)
331 for (i = 0; i < 256/32; i++)
332 if (ai.leaf->map[i] != bi.leaf->map[i])
335 return ai.leaf == bi.leaf;
339 FcCharSetAddLeaf (FcCharSet *fcs,
343 FcCharLeaf *new = FcCharSetFindLeafCreate (fcs, ucs4);
351 FcCharSetOperate (const FcCharSet *a,
353 FcBool (*overlap) (FcCharLeaf *result,
354 const FcCharLeaf *al,
355 const FcCharLeaf *bl),
360 FcCharSetIter ai, bi;
362 fcs = FcCharSetCreate ();
365 FcCharSetIterStart (a, &ai);
366 FcCharSetIterStart (b, &bi);
367 while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
369 if (ai.ucs4 < bi.ucs4)
373 if (!FcCharSetAddLeaf (fcs, ai.ucs4, ai.leaf))
375 FcCharSetIterNext (a, &ai);
380 FcCharSetIterSet (a, &ai);
383 else if (bi.ucs4 < ai.ucs4 )
387 if (!FcCharSetAddLeaf (fcs, bi.ucs4, bi.leaf))
389 FcCharSetIterNext (b, &bi);
394 FcCharSetIterSet (b, &bi);
401 if ((*overlap) (&leaf, ai.leaf, bi.leaf))
403 if (!FcCharSetAddLeaf (fcs, ai.ucs4, &leaf))
406 FcCharSetIterNext (a, &ai);
407 FcCharSetIterNext (b, &bi);
412 FcCharSetDestroy (fcs);
418 FcCharSetIntersectLeaf (FcCharLeaf *result,
419 const FcCharLeaf *al,
420 const FcCharLeaf *bl)
423 FcBool nonempty = FcFalse;
425 for (i = 0; i < 256/32; i++)
426 if ((result->map[i] = al->map[i] & bl->map[i]))
432 FcCharSetIntersect (const FcCharSet *a, const FcCharSet *b)
434 return FcCharSetOperate (a, b, FcCharSetIntersectLeaf, FcFalse, FcFalse);
438 FcCharSetUnionLeaf (FcCharLeaf *result,
439 const FcCharLeaf *al,
440 const FcCharLeaf *bl)
444 for (i = 0; i < 256/32; i++)
445 result->map[i] = al->map[i] | bl->map[i];
450 FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
452 return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
456 FcCharSetSubtractLeaf (FcCharLeaf *result,
457 const FcCharLeaf *al,
458 const FcCharLeaf *bl)
461 FcBool nonempty = FcFalse;
463 for (i = 0; i < 256/32; i++)
464 if ((result->map[i] = al->map[i] & ~bl->map[i]))
470 FcCharSetSubtract (const FcCharSet *a, const FcCharSet *b)
472 return FcCharSetOperate (a, b, FcCharSetSubtractLeaf, FcTrue, FcFalse);
476 FcCharSetHasChar (const FcCharSet *fcs, FcChar32 ucs4)
478 FcCharLeaf *leaf = FcCharSetFindLeaf (fcs, ucs4);
481 return (leaf->map[(ucs4 & 0xff) >> 5] & (1 << (ucs4 & 0x1f))) != 0;
485 FcCharSetPopCount (FcChar32 c1)
488 FcChar32 c2 = (c1 >> 1) & 033333333333;
489 c2 = c1 - c2 - ((c2 >> 1) & 033333333333);
490 return (((c2 + (c2 >> 3)) & 030707070707) % 077);
494 FcCharSetIntersectCount (const FcCharSet *a, const FcCharSet *b)
496 FcCharSetIter ai, bi;
499 FcCharSetIterStart (a, &ai);
500 FcCharSetIterStart (b, &bi);
501 while (ai.leaf && bi.leaf)
503 if (ai.ucs4 == bi.ucs4)
505 FcChar32 *am = ai.leaf->map;
506 FcChar32 *bm = bi.leaf->map;
509 count += FcCharSetPopCount (*am++ & *bm++);
510 FcCharSetIterNext (a, &ai);
512 else if (ai.ucs4 < bi.ucs4)
515 FcCharSetIterSet (a, &ai);
517 if (bi.ucs4 < ai.ucs4)
520 FcCharSetIterSet (b, &bi);
527 FcCharSetCount (const FcCharSet *a)
532 for (FcCharSetIterStart (a, &ai); ai.leaf; FcCharSetIterNext (a, &ai))
535 FcChar32 *am = ai.leaf->map;
538 count += FcCharSetPopCount (*am++);
544 FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b)
546 FcCharSetIter ai, bi;
549 FcCharSetIterStart (a, &ai);
550 FcCharSetIterStart (b, &bi);
553 if (ai.ucs4 <= bi.ucs4)
555 FcChar32 *am = ai.leaf->map;
557 if (ai.ucs4 == bi.ucs4)
559 FcChar32 *bm = bi.leaf->map;
561 count += FcCharSetPopCount (*am++ & ~*bm++);
566 count += FcCharSetPopCount (*am++);
568 FcCharSetIterNext (a, &ai);
573 FcCharSetIterSet (b, &bi);
580 * return FcTrue iff a is a subset of b
583 FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
588 if (a == b) return FcTrue;
591 while (ai < a->num && bi < b->num)
593 an = FcCharSetNumbers(a)[ai];
594 bn = FcCharSetNumbers(b)[bi];
596 * Check matching pages
600 FcChar32 *am = FcCharSetLeaf(a, ai)->map;
601 FcChar32 *bm = FcCharSetLeaf(b, bi)->map;
607 * Does am have any bits not in bm?
617 * Does a have any pages not in b?
624 int high = b->num - 1;
627 * Search for page 'an' in 'b'
631 int mid = (low + high) >> 1;
632 bn = FcCharSetNumbers(b)[mid];
644 while (bi < b->num && FcCharSetNumbers(b)[bi] < an)
649 * did we look at every page?
655 * These two functions efficiently walk the entire charmap for
656 * other software (like pango) that want their own copy
660 FcCharSetNextPage (const FcCharSet *a,
661 FcChar32 map[FC_CHARSET_MAP_SIZE],
668 FcCharSetIterSet (a, &ai);
670 return FC_CHARSET_DONE;
673 * Save current information
676 memcpy (map, ai.leaf->map, sizeof (ai.leaf->map));
680 FcCharSetIterNext (a, &ai);
687 FcCharSetFirstPage (const FcCharSet *a,
688 FcChar32 map[FC_CHARSET_MAP_SIZE],
692 return FcCharSetNextPage (a, map, next);
696 * old coverage API, rather hard to use correctly
700 FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result)
705 FcCharSetIterSet (a, &ai);
708 memset (result, '\0', 256 / 8);
713 memcpy (result, ai.leaf->map, sizeof (ai.leaf->map));
714 FcCharSetIterNext (a, &ai);
721 * ASCII representation of charsets.
723 * Each leaf is represented as 9 32-bit values, the code of the first character followed
724 * by 8 32 bit values for the leaf itself. Each value is encoded as 5 ASCII characters,
725 * only 85 different values are used to avoid control characters as well as the other
726 * characters used to encode font names. 85**5 > 2^32 so things work out, but
727 * it's not exactly human readable output. As a special case, 0 is encoded as a space
730 static const unsigned char charToValue[256] = {
731 /* "" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
732 /* "\b" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
733 /* "\020" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
734 /* "\030" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
735 /* " " */ 0xff, 0x00, 0xff, 0x01, 0x02, 0x03, 0x04, 0xff,
736 /* "(" */ 0x05, 0x06, 0x07, 0x08, 0xff, 0xff, 0x09, 0x0a,
737 /* "0" */ 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12,
738 /* "8" */ 0x13, 0x14, 0xff, 0x15, 0x16, 0xff, 0x17, 0x18,
739 /* "@" */ 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
740 /* "H" */ 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28,
741 /* "P" */ 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x30,
742 /* "X" */ 0x31, 0x32, 0x33, 0x34, 0xff, 0x35, 0x36, 0xff,
743 /* "`" */ 0xff, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d,
744 /* "h" */ 0x3e, 0x3f, 0x40, 0x41, 0x42, 0x43, 0x44, 0x45,
745 /* "p" */ 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d,
746 /* "x" */ 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0xff,
747 /* "\200" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
748 /* "\210" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
749 /* "\220" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
750 /* "\230" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
751 /* "\240" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
752 /* "\250" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
753 /* "\260" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
754 /* "\270" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
755 /* "\300" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
756 /* "\310" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
757 /* "\320" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
758 /* "\330" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
759 /* "\340" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
760 /* "\350" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
761 /* "\360" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
762 /* "\370" */ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
765 static const FcChar8 valueToChar[0x55] = {
766 /* 0x00 */ '!', '#', '$', '%', '&', '(', ')', '*',
767 /* 0x08 */ '+', '.', '/', '0', '1', '2', '3', '4',
768 /* 0x10 */ '5', '6', '7', '8', '9', ';', '<', '>',
769 /* 0x18 */ '?', '@', 'A', 'B', 'C', 'D', 'E', 'F',
770 /* 0x20 */ 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
771 /* 0x28 */ 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
772 /* 0x30 */ 'W', 'X', 'Y', 'Z', '[', ']', '^', 'a',
773 /* 0x38 */ 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
774 /* 0x40 */ 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q',
775 /* 0x48 */ 'r', 's', 't', 'u', 'v', 'w', 'x', 'y',
776 /* 0x50 */ 'z', '{', '|', '}', '~',
780 FcCharSetParseValue (FcChar8 *string, FcChar32 *value)
794 for (i = 0; i < 5; i++)
796 if (!(c = (FcChar32) (unsigned char) *string++))
809 FcCharSetUnparseValue (FcStrBuf *buf, FcChar32 value)
814 return FcStrBufChar (buf, ' ');
819 FcChar8 *s = string + 5;
821 for (i = 0; i < 5; i++)
823 *--s = valueToChar[value % 85];
826 for (i = 0; i < 5; i++)
827 if (!FcStrBufChar (buf, *s++))
834 FcNameParseCharSet (FcChar8 *string)
843 c = FcCharSetCreate ();
848 string = FcCharSetParseValue (string, &ucs4);
852 for (i = 0; i < 256/32; i++)
854 string = FcCharSetParseValue (string, &temp.map[i]);
861 leaf = malloc (sizeof (FcCharLeaf));
865 if (!FcCharSetInsertLeaf (c, ucs4, leaf))
873 FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcCharLeaf *));
874 free (FcCharSetLeaves (c));
878 FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcChar16));
879 free (FcCharSetNumbers (c));
881 FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
888 FcNameUnparseCharSet (FcStrBuf *buf, const FcCharSet *c)
896 for (FcCharSetIterStart (c, &ci);
898 FcCharSetIterNext (c, &ci))
900 if (!FcCharSetUnparseValue (buf, ci.ucs4))
902 for (i = 0; i < 256/32; i++)
903 if (!FcCharSetUnparseValue (buf, ci.leaf->map[i]))
910 FcCharSetIter ci, checki;
912 /* null terminate for parser */
913 FcStrBufChar (buf, '\0');
914 /* step back over null for life after test */
916 check = FcNameParseCharSet (buf->buf + len);
917 FcCharSetIterStart (c, &ci);
918 FcCharSetIterStart (check, &checki);
919 while (ci.leaf || checki.leaf)
921 if (ci.ucs4 < checki.ucs4)
923 printf ("Missing leaf node at 0x%x\n", ci.ucs4);
924 FcCharSetIterNext (c, &ci);
926 else if (checki.ucs4 < ci.ucs4)
928 printf ("Extra leaf node at 0x%x\n", checki.ucs4);
929 FcCharSetIterNext (check, &checki);
934 FcChar32 *cm = ci.leaf->map;
935 FcChar32 *checkm = checki.leaf->map;
937 for (i = 0; i < 256; i += 32)
940 printf ("Mismatching sets at 0x%08x: 0x%08x != 0x%08x\n",
941 ci.ucs4 + i, *cm, *checkm);
945 FcCharSetIterNext (c, &ci);
946 FcCharSetIterNext (check, &checki);
949 if ((missing = FcCharSetSubtractCount (c, check)))
950 printf ("%d missing in reparsed result\n", missing);
951 if ((missing = FcCharSetSubtractCount (check, c)))
952 printf ("%d extra in reparsed result\n", missing);
953 FcCharSetDestroy (check);
960 typedef struct _FcCharLeafEnt FcCharLeafEnt;
962 struct _FcCharLeafEnt {
968 #define FC_CHAR_LEAF_BLOCK (4096 / sizeof (FcCharLeafEnt))
969 #define FC_CHAR_LEAF_HASH_SIZE 257
971 typedef struct _FcCharSetEnt FcCharSetEnt;
973 struct _FcCharSetEnt {
979 typedef struct _FcCharSetOrigEnt FcCharSetOrigEnt;
981 struct _FcCharSetOrigEnt {
982 FcCharSetOrigEnt *next;
983 const FcCharSet *orig;
984 const FcCharSet *frozen;
987 #define FC_CHAR_SET_HASH_SIZE 67
989 struct _FcCharSetFreezer {
990 FcCharLeafEnt *leaf_hash_table[FC_CHAR_LEAF_HASH_SIZE];
991 FcCharLeafEnt **leaf_blocks;
992 int leaf_block_count;
993 FcCharSetEnt *set_hash_table[FC_CHAR_SET_HASH_SIZE];
994 FcCharSetOrigEnt *orig_hash_table[FC_CHAR_SET_HASH_SIZE];
995 FcCharLeafEnt *current_block;
999 int leaves_allocated;
1000 int charsets_allocated;
1003 static FcCharLeafEnt *
1004 FcCharLeafEntCreate (FcCharSetFreezer *freezer)
1006 if (!freezer->leaf_remain)
1008 FcCharLeafEnt **newBlocks;
1010 freezer->leaf_block_count++;
1011 newBlocks = realloc (freezer->leaf_blocks, freezer->leaf_block_count * sizeof (FcCharLeafEnt *));
1014 freezer->leaf_blocks = newBlocks;
1015 freezer->current_block = freezer->leaf_blocks[freezer->leaf_block_count-1] = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
1016 if (!freezer->current_block)
1018 FcMemAlloc (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
1019 freezer->leaf_remain = FC_CHAR_LEAF_BLOCK;
1021 freezer->leaf_remain--;
1022 freezer->leaves_allocated++;
1023 return freezer->current_block++;
1027 FcCharLeafHash (FcCharLeaf *leaf)
1032 for (i = 0; i < 256/32; i++)
1033 hash = ((hash << 1) | (hash >> 31)) ^ leaf->map[i];
1038 FcCharSetFreezeLeaf (FcCharSetFreezer *freezer, FcCharLeaf *leaf)
1040 FcChar32 hash = FcCharLeafHash (leaf);
1041 FcCharLeafEnt **bucket = &freezer->leaf_hash_table[hash % FC_CHAR_LEAF_HASH_SIZE];
1044 for (ent = *bucket; ent; ent = ent->next)
1046 if (ent->hash == hash && !memcmp (&ent->leaf, leaf, sizeof (FcCharLeaf)))
1050 ent = FcCharLeafEntCreate(freezer);
1055 ent->next = *bucket;
1061 FcCharSetHash (FcCharSet *fcs)
1066 /* hash in leaves */
1067 for (i = 0; i < fcs->num; i++)
1068 hash = ((hash << 1) | (hash >> 31)) ^ FcCharLeafHash (FcCharSetLeaf(fcs,i));
1069 /* hash in numbers */
1070 for (i = 0; i < fcs->num; i++)
1071 hash = ((hash << 1) | (hash >> 31)) ^ *FcCharSetNumbers(fcs);
1076 FcCharSetFreezeOrig (FcCharSetFreezer *freezer, const FcCharSet *orig, const FcCharSet *frozen)
1078 FcCharSetOrigEnt **bucket = &freezer->orig_hash_table[((uintptr_t) orig) & FC_CHAR_SET_HASH_SIZE];
1079 FcCharSetOrigEnt *ent;
1081 ent = malloc (sizeof (FcCharSetOrigEnt));
1085 ent->frozen = frozen;
1086 ent->next = *bucket;
1092 FcCharSetFreezeBase (FcCharSetFreezer *freezer, FcCharSet *fcs, const FcCharSet *orig)
1094 FcChar32 hash = FcCharSetHash (fcs);
1095 FcCharSetEnt **bucket = &freezer->set_hash_table[hash % FC_CHAR_SET_HASH_SIZE];
1100 for (ent = *bucket; ent; ent = ent->next)
1102 if (ent->hash == hash &&
1103 ent->set.num == fcs->num &&
1104 !memcmp (FcCharSetNumbers(&ent->set),
1105 FcCharSetNumbers(fcs),
1106 fcs->num * sizeof (FcChar16)))
1111 for (i = 0; i < fcs->num; i++)
1112 if (FcCharSetLeaf(&ent->set, i) != FcCharSetLeaf(fcs, i))
1119 size = (sizeof (FcCharSetEnt) +
1120 fcs->num * sizeof (FcCharLeaf *) +
1121 fcs->num * sizeof (FcChar16));
1122 ent = malloc (size);
1125 FcMemAlloc (FC_MEM_CHARSET, size);
1127 freezer->charsets_allocated++;
1129 ent->set.ref = FC_REF_CONSTANT;
1130 ent->set.num = fcs->num;
1133 intptr_t *ent_leaves;
1135 ent->set.leaves_offset = sizeof (ent->set);
1136 ent->set.numbers_offset = (ent->set.leaves_offset +
1137 fcs->num * sizeof (intptr_t));
1139 ent_leaves = FcCharSetLeaves (&ent->set);
1140 for (i = 0; i < fcs->num; i++)
1141 ent_leaves[i] = FcPtrToOffset (ent_leaves,
1142 FcCharSetLeaf (fcs, i));
1143 memcpy (FcCharSetNumbers (&ent->set),
1144 FcCharSetNumbers (fcs),
1145 fcs->num * sizeof (FcChar16));
1149 ent->set.leaves_offset = 0;
1150 ent->set.numbers_offset = 0;
1154 ent->next = *bucket;
1160 static const FcCharSet *
1161 FcCharSetFindFrozen (FcCharSetFreezer *freezer, const FcCharSet *orig)
1163 FcCharSetOrigEnt **bucket = &freezer->orig_hash_table[((uintptr_t) orig) & FC_CHAR_SET_HASH_SIZE];
1164 FcCharSetOrigEnt *ent;
1166 for (ent = *bucket; ent; ent = ent->next)
1167 if (ent->orig == orig)
1173 FcCharSetFreeze (FcCharSetFreezer *freezer, const FcCharSet *fcs)
1176 const FcCharSet *n = 0;
1180 b = FcCharSetCreate ();
1183 for (i = 0; i < fcs->num; i++)
1185 l = FcCharSetFreezeLeaf (freezer, FcCharSetLeaf(fcs, i));
1188 if (!FcCharSetInsertLeaf (b, FcCharSetNumbers(fcs)[i] << 8, l))
1191 n = FcCharSetFreezeBase (freezer, b, fcs);
1192 if (!FcCharSetFreezeOrig (freezer, fcs, n))
1197 freezer->charsets_seen++;
1198 freezer->leaves_seen += fcs->num;
1202 FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcCharLeaf *));
1203 free (FcCharSetLeaves (b));
1207 FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcChar16));
1208 free (FcCharSetNumbers (b));
1210 FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
1217 FcCharSetFreezerCreate (void)
1219 FcCharSetFreezer *freezer;
1221 freezer = calloc (1, sizeof (FcCharSetFreezer));
1226 FcCharSetFreezerDestroy (FcCharSetFreezer *freezer)
1230 if (FcDebug() & FC_DBG_CACHE)
1232 printf ("\ncharsets %d -> %d leaves %d -> %d\n",
1233 freezer->charsets_seen, freezer->charsets_allocated,
1234 freezer->leaves_seen, freezer->leaves_allocated);
1236 for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1238 FcCharSetEnt *ent, *next;
1239 for (ent = freezer->set_hash_table[i]; ent; ent = next)
1246 for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1248 FcCharSetOrigEnt *ent, *next;
1249 for (ent = freezer->orig_hash_table[i]; ent; ent = next)
1256 for (i = 0; i < freezer->leaf_block_count; i++)
1257 free (freezer->leaf_blocks[i]);
1259 free (freezer->leaf_blocks);
1264 FcCharSetSerializeAlloc (FcSerialize *serialize, const FcCharSet *cs)
1270 if (cs->ref != FC_REF_CONSTANT)
1272 if (!serialize->cs_freezer)
1274 serialize->cs_freezer = FcCharSetFreezerCreate ();
1275 if (!serialize->cs_freezer)
1278 if (FcCharSetFindFrozen (serialize->cs_freezer, cs))
1281 cs = FcCharSetFreeze (serialize->cs_freezer, cs);
1284 leaves = FcCharSetLeaves (cs);
1285 numbers = FcCharSetNumbers (cs);
1287 if (!FcSerializeAlloc (serialize, cs, sizeof (FcCharSet)))
1289 if (!FcSerializeAlloc (serialize, leaves, cs->num * sizeof (intptr_t)))
1291 if (!FcSerializeAlloc (serialize, numbers, cs->num * sizeof (FcChar16)))
1293 for (i = 0; i < cs->num; i++)
1294 if (!FcSerializeAlloc (serialize, FcCharSetLeaf(cs, i),
1295 sizeof (FcCharLeaf)))
1301 FcCharSetSerialize(FcSerialize *serialize, const FcCharSet *cs)
1303 FcCharSet *cs_serialized;
1304 intptr_t *leaves, *leaves_serialized;
1305 FcChar16 *numbers, *numbers_serialized;
1306 FcCharLeaf *leaf, *leaf_serialized;
1309 if (cs->ref != FC_REF_CONSTANT && serialize->cs_freezer)
1311 cs = FcCharSetFindFrozen (serialize->cs_freezer, cs);
1316 cs_serialized = FcSerializePtr (serialize, cs);
1320 cs_serialized->ref = FC_REF_CONSTANT;
1321 cs_serialized->num = cs->num;
1325 leaves = FcCharSetLeaves (cs);
1326 leaves_serialized = FcSerializePtr (serialize, leaves);
1327 if (!leaves_serialized)
1330 cs_serialized->leaves_offset = FcPtrToOffset (cs_serialized,
1333 numbers = FcCharSetNumbers (cs);
1334 numbers_serialized = FcSerializePtr (serialize, numbers);
1338 cs_serialized->numbers_offset = FcPtrToOffset (cs_serialized,
1339 numbers_serialized);
1341 for (i = 0; i < cs->num; i++)
1343 leaf = FcCharSetLeaf (cs, i);
1344 leaf_serialized = FcSerializePtr (serialize, leaf);
1345 if (!leaf_serialized)
1347 *leaf_serialized = *leaf;
1348 leaves_serialized[i] = FcPtrToOffset (leaves_serialized,
1350 numbers_serialized[i] = numbers[i];
1355 cs_serialized->leaves_offset = 0;
1356 cs_serialized->numbers_offset = 0;
1359 return cs_serialized;
1361 #define __fccharset__
1362 #include "fcaliastail.h"
1363 #undef __fccharset__