X-Git-Url: https://git.wh0rd.org/?p=fontconfig.git;a=blobdiff_plain;f=src%2Ffccharset.c;h=d30e1614a83d3d8c822271b240d02d43d1f1f211;hp=3a93c4a96cec00723e6a696a817f3530a2803507;hb=77f4e60a32971a815b85f187712191724a00b856;hpb=2d3387fd720f33f80847ae6cbb83d94c9a52fde3

diff --git a/src/fccharset.c b/src/fccharset.c
index 3a93c4a..d30e161 100644
--- a/src/fccharset.c
+++ b/src/fccharset.c
@@ -1,5 +1,5 @@
 /*
- * $RCSId: xc/lib/fontconfig/src/fccharset.c,v 1.18 2002/08/22 07:36:44 keithp Exp $
+ * fontconfig/src/fccharset.c
  *
  * Copyright © 2001 Keith Packard
  *
@@ -13,9 +13,9 @@
  * representations about the suitability of this software for any purpose.  It
  * is provided "as is" without express or implied warranty.
  *
- * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
- * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
@@ -27,8 +27,6 @@
 
 /* #define CHECK */
 
-/* #define CHATTY */
-
 FcCharSet *
 FcCharSetCreate (void)
 {
@@ -40,14 +38,11 @@ FcCharSetCreate (void)
     FcMemAlloc (FC_MEM_CHARSET, sizeof (FcCharSet));
     fcs->ref = 1;
     fcs->num = 0;
-    fcs->leaves_offset = FcPtrToOffset (fcs, NULL);
-    fcs->numbers_offset = FcPtrToOffset (fcs, NULL);
+    fcs->leaves_offset = 0;
+    fcs->numbers_offset = 0;
     return fcs;
 }
 
-FcCharSet *
-FcCharSetNew (void);
-    
 FcCharSet *
 FcCharSetNew (void)
 {
@@ -60,7 +55,10 @@ FcCharSetDestroy (FcCharSet *fcs)
     int i;
     
     if (fcs->ref == FC_REF_CONSTANT)
+    {
+	FcCacheObjectDereference (fcs);
 	return;
+    }
     if (--fcs->ref > 0)
 	return;
     for (i = 0; i < fcs->num; i++)
@@ -68,13 +66,11 @@ FcCharSetDestroy (FcCharSet *fcs)
 	FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
 	free (FcCharSetLeaf (fcs, i));
     }
-    if (FcCharSetLeaves (fcs))
+    if (fcs->num)
     {
+        /* the numbers here are estimates */
 	FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (intptr_t));
 	free (FcCharSetLeaves (fcs));
-    }
-    if (FcCharSetNumbers (fcs))
-    {
 	FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
 	free (FcCharSetNumbers (fcs));
     }
@@ -83,38 +79,50 @@ FcCharSetDestroy (FcCharSet *fcs)
 }
 
 /*
- * Locate the leaf containing the specified char, return
- * its index if it exists, otherwise return negative of
+ * Search for the leaf containing with the specified num.
+ * Return its index if it exists, otherwise return negative of
  * the (position + 1) where it should be inserted
  */
 
+
 static int
-FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
+FcCharSetFindLeafForward (const FcCharSet *fcs, int start, FcChar16 num)
 {
     FcChar16		*numbers = FcCharSetNumbers(fcs);
     FcChar16		page;
-    int			low = 0;
+    int			low = start;
     int			high = fcs->num - 1;
 
     if (!numbers)
 	return -1;
-    ucs4 >>= 8;
     while (low <= high)
     {
 	int mid = (low + high) >> 1;
 	page = numbers[mid];
-	if (page == ucs4)
+	if (page == num)
 	    return mid;
-	if (page < ucs4)
+	if (page < num)
 	    low = mid + 1;
 	else
 	    high = mid - 1;
     }
-    if (high < 0 || (high < fcs->num && numbers[high] < ucs4))
+    if (high < 0 || (high < fcs->num && numbers[high] < num))
 	high++;
     return -(high + 1);
 }
 
+/*
+ * Locate the leaf containing the specified char, return
+ * its index if it exists, otherwise return negative of
+ * the (position + 1) where it should be inserted
+ */
+
+static int
+FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
+{
+    return FcCharSetFindLeafForward (fcs, 0, ucs4 >> 8);
+}
+
 static FcCharLeaf *
 FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
 {
@@ -124,6 +132,8 @@ FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
     return 0;
 }
 
+#define FC_IS_ZERO_OR_POWER_OF_TWO(x) (!((x) & ((x)-1)))
+
 static FcBool
 FcCharSetPutLeaf (FcCharSet	*fcs, 
 		  FcChar32	ucs4,
@@ -136,42 +146,48 @@ FcCharSetPutLeaf (FcCharSet	*fcs,
     ucs4 >>= 8;
     if (ucs4 >= 0x10000)
 	return FcFalse;
-    if (!leaves)
-	leaves = malloc (sizeof (*leaves));
-    else
+
+    if (FC_IS_ZERO_OR_POWER_OF_TWO (fcs->num))
     {
-	intptr_t    *new_leaves = realloc (leaves, (fcs->num + 1) * 
-					   sizeof (*leaves));
-	intptr_t    distance = (intptr_t) new_leaves - (intptr_t) leaves;
-	
+      if (!fcs->num)
+      {
+        unsigned int alloced = 8;
+	leaves = malloc (alloced * sizeof (*leaves));
+	numbers = malloc (alloced * sizeof (*numbers));
+	FcMemAlloc (FC_MEM_CHARSET, alloced * sizeof (*leaves));
+	FcMemAlloc (FC_MEM_CHARSET, alloced * sizeof (*numbers));
+      }
+      else
+      {
+        unsigned int alloced = fcs->num;
+	intptr_t *new_leaves, distance;
+
+	FcMemFree (FC_MEM_CHARSET, alloced * sizeof (*leaves));
+	FcMemFree (FC_MEM_CHARSET, alloced * sizeof (*numbers));
+
+	alloced *= 2;
+	new_leaves = realloc (leaves, alloced * sizeof (*leaves));
+	numbers = realloc (numbers, alloced * sizeof (*numbers));
+
+	FcMemAlloc (FC_MEM_CHARSET, alloced * sizeof (*leaves));
+	FcMemAlloc (FC_MEM_CHARSET, alloced * sizeof (*numbers));
+
+	distance = (intptr_t) new_leaves - (intptr_t) leaves;
 	if (new_leaves && distance)
 	{
 	    int i;
-
 	    for (i = 0; i < fcs->num; i++)
 		new_leaves[i] -= distance;
 	}
 	leaves = new_leaves;
+      }
+
+      if (!leaves || !numbers)
+	  return FcFalse;
+
+      fcs->leaves_offset = FcPtrToOffset (fcs, leaves);
+      fcs->numbers_offset = FcPtrToOffset (fcs, numbers);
     }
-    if (!leaves)
-	return FcFalse;
-    
-    if (fcs->num)
-	FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (intptr_t));
-    FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (intptr_t));
-    fcs->leaves_offset = FcPtrToOffset (fcs, leaves);
-    
-    if (!numbers)
-	numbers = malloc (sizeof (FcChar16));
-    else
-	numbers = realloc (numbers, (fcs->num + 1) * sizeof (FcChar16));
-    if (!numbers)
-	return FcFalse;
-    
-    if (fcs->num)
-	FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
-    FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcChar16));
-    fcs->numbers_offset = FcPtrToOffset (fcs, numbers);
     
     memmove (leaves + pos + 1, leaves + pos, 
 	     (fcs->num - pos) * sizeof (*leaves));
@@ -278,9 +294,6 @@ FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
     }
     iter->leaf = FcCharSetLeaf(fcs, pos);
     iter->pos = pos;
-#ifdef CHATTY
-    printf ("set %08x: %08x\n", iter->ucs4, (FcChar32) iter->leaf);
-#endif
 }
 
 static void
@@ -300,29 +313,10 @@ FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
     }
 }
 
-#ifdef CHATTY
-static void
-FcCharSetDump (const FcCharSet *fcs)
-{
-    int		pos;
-
-    printf ("fcs %08x:\n", (FcChar32) fcs);
-    for (pos = 0; pos < fcs->num; pos++)
-    {
-	FcCharLeaf	*leaf = fcs->leaves[pos];
-	FcChar32	ucs4 = (FcChar32) fcs->numbers[pos] << 8;
-	
-	printf ("    %08x: %08x\n", ucs4, (FcChar32) leaf);
-    }
-}
-#endif
 
 static void
 FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
 {
-#ifdef CHATTY
-    FcCharSetDump (fcs);
-#endif
     iter->ucs4 = 0;
     iter->pos = 0;
     FcCharSetIterSet (fcs, iter);
@@ -333,6 +327,8 @@ FcCharSetCopy (FcCharSet *src)
 {
     if (src->ref != FC_REF_CONSTANT)
 	src->ref++;
+    else
+	FcCacheObjectReference (src);
     return src;
 }
 
@@ -474,6 +470,57 @@ FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
     return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
 }
 
+FcBool
+FcCharSetMerge (FcCharSet *a, const FcCharSet *b, FcBool *changed)
+{
+    int		ai = 0, bi = 0;
+    FcChar16	an, bn;
+
+    if (a->ref == FC_REF_CONSTANT) {
+	if (changed)
+	    *changed = FcFalse;
+	return FcFalse;
+    }
+
+    if (changed) {
+	*changed = !FcCharSetIsSubset(b, a);
+	if (!*changed)
+	    return FcTrue;
+    }
+
+    while (bi < b->num)
+    {
+	an = ai < a->num ? FcCharSetNumbers(a)[ai] : ~0;
+	bn = FcCharSetNumbers(b)[bi];
+
+	if (an < bn)
+	{
+	    ai = FcCharSetFindLeafForward (a, ai + 1, bn);
+	    if (ai < 0)
+		ai = -ai - 1;
+	}
+	else
+	{
+	    FcCharLeaf *bl = FcCharSetLeaf(b, bi);
+	    if (bn < an)
+	    {
+		if (!FcCharSetAddLeaf (a, bn << 8, bl))
+		    return FcFalse;
+	    }
+	    else
+	    {
+		FcCharLeaf *al = FcCharSetLeaf(a, ai);
+		FcCharSetUnionLeaf (al, al, bl);
+	    }
+
+	    ai++;
+	    bi++;
+	}
+    }
+
+    return FcTrue;
+}
+
 static FcBool
 FcCharSetSubtractLeaf (FcCharLeaf *result,
 		       const FcCharLeaf *al,
@@ -506,10 +553,14 @@ FcCharSetHasChar (const FcCharSet *fcs, FcChar32 ucs4)
 static FcChar32
 FcCharSetPopCount (FcChar32 c1)
 {
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+    return __builtin_popcount (c1);
+#else
     /* hackmem 169 */
     FcChar32	c2 = (c1 >> 1) & 033333333333;
     c2 = c1 - c2 - ((c2 >> 1) & 033333333333);
     return (((c2 + (c2 >> 3)) & 030707070707) % 077);
+#endif
 }
 
 FcChar32
@@ -642,29 +693,9 @@ FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
 	    return FcFalse;
 	else
 	{
-	    int	    low = bi + 1;
-	    int	    high = b->num - 1;
-
-	    /*
-	     * Search for page 'an' in 'b'
-	     */
-	    while (low <= high)
-	    {
-		int mid = (low + high) >> 1;
-		bn = FcCharSetNumbers(b)[mid];
-		if (bn == an)
-		{
-		    high = mid;
-		    break;
-		}
-		if (bn < an)
-		    low = mid + 1;
-		else
-		    high = mid - 1;
-	    }
-	    bi = high;
-	    while (bi < b->num && FcCharSetNumbers(b)[bi] < an)
-		bi++;
+	    bi = FcCharSetFindLeafForward (b, bi + 1, an);
+	    if (bi < 0)
+		bi = -bi - 1;
 	}
     }
     /*
@@ -717,8 +748,6 @@ FcCharSetFirstPage (const FcCharSet *a,
 /*
  * old coverage API, rather hard to use correctly
  */
-FcChar32
-FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result);
     
 FcChar32
 FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result)
@@ -854,6 +883,133 @@ FcCharSetUnparseValue (FcStrBuf *buf, FcChar32 value)
     return FcTrue;
 }
 
+FcCharSet *
+FcNameParseCharSet (FcChar8 *string)
+{
+    FcCharSet	*c;
+    FcChar32	ucs4;
+    FcCharLeaf	*leaf;
+    FcCharLeaf	temp;
+    FcChar32	bits;
+    int		i;
+
+    c = FcCharSetCreate ();
+    if (!c)
+	goto bail0;
+    while (*string)
+    {
+	string = FcCharSetParseValue (string, &ucs4);
+	if (!string)
+	    goto bail1;
+	bits = 0;
+	for (i = 0; i < 256/32; i++)
+	{
+	    string = FcCharSetParseValue (string, &temp.map[i]);
+	    if (!string)
+		goto bail1;
+	    bits |= temp.map[i];
+	}
+	if (bits)
+	{
+	    leaf = malloc (sizeof (FcCharLeaf));
+	    if (!leaf)
+		goto bail1;
+	    *leaf = temp;
+	    if (!FcCharSetInsertLeaf (c, ucs4, leaf))
+		goto bail1;
+	}
+    }
+    return c;
+bail1:
+    if (c->num)
+    {
+	FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcCharLeaf *));
+	free (FcCharSetLeaves (c));
+    }
+    if (c->num)
+    {
+	FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcChar16));
+	free (FcCharSetNumbers (c));
+    }
+    FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
+    free (c);
+bail0:
+    return NULL;
+}
+
+FcBool
+FcNameUnparseCharSet (FcStrBuf *buf, const FcCharSet *c)
+{
+    FcCharSetIter   ci;
+    int		    i;
+#ifdef CHECK
+    int		    len = buf->len;
+#endif
+
+    for (FcCharSetIterStart (c, &ci);
+	 ci.leaf;
+	 FcCharSetIterNext (c, &ci))
+    {
+	if (!FcCharSetUnparseValue (buf, ci.ucs4))
+	    return FcFalse;
+	for (i = 0; i < 256/32; i++)
+	    if (!FcCharSetUnparseValue (buf, ci.leaf->map[i]))
+		return FcFalse;
+    }
+#ifdef CHECK
+    {
+	FcCharSet	*check;
+	FcChar32	missing;
+	FcCharSetIter	ci, checki;
+	
+	/* null terminate for parser */
+	FcStrBufChar (buf, '\0');
+	/* step back over null for life after test */
+	buf->len--;
+	check = FcNameParseCharSet (buf->buf + len);
+	FcCharSetIterStart (c, &ci);
+	FcCharSetIterStart (check, &checki);
+	while (ci.leaf || checki.leaf)
+	{
+	    if (ci.ucs4 < checki.ucs4)
+	    {
+		printf ("Missing leaf node at 0x%x\n", ci.ucs4);
+		FcCharSetIterNext (c, &ci);
+	    }
+	    else if (checki.ucs4 < ci.ucs4)
+	    {
+		printf ("Extra leaf node at 0x%x\n", checki.ucs4);
+		FcCharSetIterNext (check, &checki);
+	    }
+	    else
+	    {
+		int	    i = 256/32;
+		FcChar32    *cm = ci.leaf->map;
+		FcChar32    *checkm = checki.leaf->map;
+
+		for (i = 0; i < 256; i += 32)
+		{
+		    if (*cm != *checkm)
+			printf ("Mismatching sets at 0x%08x: 0x%08x != 0x%08x\n",
+				ci.ucs4 + i, *cm, *checkm);
+		    cm++;
+		    checkm++;
+		}
+		FcCharSetIterNext (c, &ci);
+		FcCharSetIterNext (check, &checki);
+	    }
+	}
+	if ((missing = FcCharSetSubtractCount (c, check)))
+	    printf ("%d missing in reparsed result\n", missing);
+	if ((missing = FcCharSetSubtractCount (check, c)))
+	    printf ("%d extra in reparsed result\n", missing);
+	FcCharSetDestroy (check);
+    }
+#endif
+    
+    return FcTrue;
+}
+
 typedef struct _FcCharLeafEnt FcCharLeafEnt;
 
 struct _FcCharLeafEnt {
@@ -863,36 +1019,63 @@ struct _FcCharLeafEnt {
 };
 
 #define FC_CHAR_LEAF_BLOCK	(4096 / sizeof (FcCharLeafEnt))
-static FcCharLeafEnt **FcCharLeafBlocks;
-static int FcCharLeafBlockCount;
+#define FC_CHAR_LEAF_HASH_SIZE	257
+
+typedef struct _FcCharSetEnt FcCharSetEnt;
+
+struct _FcCharSetEnt {
+    FcCharSetEnt	*next;
+    FcChar32		hash;
+    FcCharSet		set;
+};
+
+typedef struct _FcCharSetOrigEnt FcCharSetOrigEnt;
+
+struct _FcCharSetOrigEnt {
+    FcCharSetOrigEnt	*next;
+    const FcCharSet    	*orig;
+    const FcCharSet    	*frozen;
+};
+
+#define FC_CHAR_SET_HASH_SIZE    67
+
+struct _FcCharSetFreezer {
+    FcCharLeafEnt   *leaf_hash_table[FC_CHAR_LEAF_HASH_SIZE];
+    FcCharLeafEnt   **leaf_blocks;
+    int		    leaf_block_count;
+    FcCharSetEnt    *set_hash_table[FC_CHAR_SET_HASH_SIZE];
+    FcCharSetOrigEnt	*orig_hash_table[FC_CHAR_SET_HASH_SIZE];
+    FcCharLeafEnt   *current_block;
+    int		    leaf_remain;
+    int		    leaves_seen;
+    int		    charsets_seen;
+    int		    leaves_allocated;
+    int		    charsets_allocated;
+};
 
 static FcCharLeafEnt *
-FcCharLeafEntCreate (void)
+FcCharLeafEntCreate (FcCharSetFreezer *freezer)
 {
-    static FcCharLeafEnt    *block;
-    static int		    remain;
-
-    if (!remain)
+    if (!freezer->leaf_remain)
     {
 	FcCharLeafEnt **newBlocks;
 
-	FcCharLeafBlockCount++;
-	newBlocks = realloc (FcCharLeafBlocks, FcCharLeafBlockCount * sizeof (FcCharLeafEnt *));
+	freezer->leaf_block_count++;
+	newBlocks = realloc (freezer->leaf_blocks, freezer->leaf_block_count * sizeof (FcCharLeafEnt *));
 	if (!newBlocks)
 	    return 0;
-	FcCharLeafBlocks = newBlocks;
-	block = FcCharLeafBlocks[FcCharLeafBlockCount-1] = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
-	if (!block)
+	freezer->leaf_blocks = newBlocks;
+	freezer->current_block = freezer->leaf_blocks[freezer->leaf_block_count-1] = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
+	if (!freezer->current_block)
 	    return 0;
 	FcMemAlloc (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
-	remain = FC_CHAR_LEAF_BLOCK;
+	freezer->leaf_remain = FC_CHAR_LEAF_BLOCK;
     }
-    remain--;
-    return block++;
+    freezer->leaf_remain--;
+    freezer->leaves_allocated++;
+    return freezer->current_block++;
 }
 
-#define FC_CHAR_LEAF_HASH_SIZE	257
-
 static FcChar32
 FcCharLeafHash (FcCharLeaf *leaf)
 {
@@ -904,29 +1087,22 @@ FcCharLeafHash (FcCharLeaf *leaf)
     return hash;
 }
 
-static int	FcCharLeafTotal;
-static int	FcCharLeafUsed;
-
-static FcCharLeafEnt	*FcCharLeafHashTable[FC_CHAR_LEAF_HASH_SIZE];
-
 static FcCharLeaf *
-FcCharSetFreezeLeaf (FcCharLeaf *leaf)
+FcCharSetFreezeLeaf (FcCharSetFreezer *freezer, FcCharLeaf *leaf)
 {
     FcChar32			hash = FcCharLeafHash (leaf);
-    FcCharLeafEnt		**bucket = &FcCharLeafHashTable[hash % FC_CHAR_LEAF_HASH_SIZE];
+    FcCharLeafEnt		**bucket = &freezer->leaf_hash_table[hash % FC_CHAR_LEAF_HASH_SIZE];
     FcCharLeafEnt		*ent;
     
-    FcCharLeafTotal++;
     for (ent = *bucket; ent; ent = ent->next)
     {
 	if (ent->hash == hash && !memcmp (&ent->leaf, leaf, sizeof (FcCharLeaf)))
 	    return &ent->leaf;
     }
 
-    ent = FcCharLeafEntCreate();
+    ent = FcCharLeafEntCreate(freezer);
     if (!ent)
 	return 0;
-    FcCharLeafUsed++;
     ent->leaf = *leaf;
     ent->hash = hash;
     ent->next = *bucket;
@@ -934,35 +1110,6 @@ FcCharSetFreezeLeaf (FcCharLeaf *leaf)
     return &ent->leaf;
 }
 
-static void
-FcCharSetThawAllLeaf (void)
-{
-    int i;
-
-    for (i = 0; i < FC_CHAR_LEAF_HASH_SIZE; i++)
-	FcCharLeafHashTable[i] = 0;
-
-    FcCharLeafTotal = 0;
-    FcCharLeafUsed = 0;
-
-    for (i = 0; i < FcCharLeafBlockCount; i++)
-	free (FcCharLeafBlocks[i]);
-
-    free (FcCharLeafBlocks);
-    FcCharLeafBlocks = 0;
-    FcCharLeafBlockCount = 0;
-}
-
-typedef struct _FcCharSetEnt FcCharSetEnt;
-
-struct _FcCharSetEnt {
-    FcCharSetEnt	*next;
-    FcChar32		hash;
-    FcCharSet		set;
-};
-
-#define FC_CHAR_SET_HASH_SIZE    67
-
 static FcChar32
 FcCharSetHash (FcCharSet *fcs)
 {
@@ -970,31 +1117,39 @@ FcCharSetHash (FcCharSet *fcs)
     int		i;
 
     /* hash in leaves */
-    for (i = 0; i < fcs->num * (int) (sizeof (FcCharLeaf *) / sizeof (FcChar32)); i++)
-	hash = ((hash << 1) | (hash >> 31)) ^ (FcChar32)(FcCharSetLeaf(fcs, i)->map);
+    for (i = 0; i < fcs->num; i++)
+	hash = ((hash << 1) | (hash >> 31)) ^ FcCharLeafHash (FcCharSetLeaf(fcs,i));
     /* hash in numbers */
     for (i = 0; i < fcs->num; i++)
 	hash = ((hash << 1) | (hash >> 31)) ^ *FcCharSetNumbers(fcs);
     return hash;
 }
 
-static int	FcCharSetTotal;
-static int	FcCharSetUsed;
-static int	FcCharSetTotalEnts, FcCharSetUsedEnts;
-
-static FcCharSetEnt	*FcCharSetHashTable[FC_CHAR_SET_HASH_SIZE];
+static FcBool
+FcCharSetFreezeOrig (FcCharSetFreezer *freezer, const FcCharSet *orig, const FcCharSet *frozen)
+{
+    FcCharSetOrigEnt	**bucket = &freezer->orig_hash_table[((uintptr_t) orig) & FC_CHAR_SET_HASH_SIZE];
+    FcCharSetOrigEnt	*ent;
+    
+    ent = malloc (sizeof (FcCharSetOrigEnt));
+    if (!ent)
+	return FcFalse;
+    ent->orig = orig;
+    ent->frozen = frozen;
+    ent->next = *bucket;
+    *bucket = ent;
+    return FcTrue;
+}
 
 static FcCharSet *
-FcCharSetFreezeBase (FcCharSet *fcs)
+FcCharSetFreezeBase (FcCharSetFreezer *freezer, FcCharSet *fcs, const FcCharSet *orig)
 {
     FcChar32		hash = FcCharSetHash (fcs);
-    FcCharSetEnt	**bucket = &FcCharSetHashTable[hash % FC_CHAR_SET_HASH_SIZE];
+    FcCharSetEnt	**bucket = &freezer->set_hash_table[hash % FC_CHAR_SET_HASH_SIZE];
     FcCharSetEnt	*ent;
     int			size;
     int			i;
 
-    FcCharSetTotal++;
-    FcCharSetTotalEnts += fcs->num;
     for (ent = *bucket; ent; ent = ent->next)
     {
 	if (ent->hash == hash &&
@@ -1021,8 +1176,8 @@ FcCharSetFreezeBase (FcCharSet *fcs)
     if (!ent)
 	return 0;
     FcMemAlloc (FC_MEM_CHARSET, size);
-    FcCharSetUsed++;
-    FcCharSetUsedEnts += fcs->num;
+    
+    freezer->charsets_allocated++;
     
     ent->set.ref = FC_REF_CONSTANT;
     ent->set.num = fcs->num;
@@ -1051,60 +1206,56 @@ FcCharSetFreezeBase (FcCharSet *fcs)
     ent->hash = hash;
     ent->next = *bucket;
     *bucket = ent;
+
     return &ent->set;
 }
 
-void
-FcCharSetThawAll (void)
+static const FcCharSet *
+FcCharSetFindFrozen (FcCharSetFreezer *freezer, const FcCharSet *orig)
 {
-    int i;
-    FcCharSetEnt	*ent, *next;
-
-    for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
-    {
-	for (ent = FcCharSetHashTable[i]; ent; ent = next)
-	{
-	    next = ent->next;
-	    free (ent);
-	}
-	FcCharSetHashTable[i] = 0;
-    }
-
-    FcCharSetTotal = 0;
-    FcCharSetTotalEnts = 0;
-    FcCharSetUsed = 0;
-    FcCharSetUsedEnts = 0;
-
-    FcCharSetThawAllLeaf ();
+    FcCharSetOrigEnt    **bucket = &freezer->orig_hash_table[((uintptr_t) orig) & FC_CHAR_SET_HASH_SIZE];
+    FcCharSetOrigEnt	*ent;
+    
+    for (ent = *bucket; ent; ent = ent->next)
+	if (ent->orig == orig)
+	    return ent->frozen;
+    return NULL;
 }
 
-FcCharSet *
-FcCharSetFreeze (FcCharSet *fcs)
+const FcCharSet *
+FcCharSetFreeze (FcCharSetFreezer *freezer, const FcCharSet *fcs)
 {
-    FcCharSet	*b;
-    FcCharSet	*n = 0;
-    FcCharLeaf	*l;
-    int		i;
+    FcCharSet	    *b;
+    const FcCharSet *n = 0;
+    FcCharLeaf	    *l;
+    int		    i;
 
     b = FcCharSetCreate ();
     if (!b)
 	goto bail0;
     for (i = 0; i < fcs->num; i++)
     {
-	l = FcCharSetFreezeLeaf (FcCharSetLeaf(fcs, i));
+	l = FcCharSetFreezeLeaf (freezer, FcCharSetLeaf(fcs, i));
 	if (!l)
 	    goto bail1;
 	if (!FcCharSetInsertLeaf (b, FcCharSetNumbers(fcs)[i] << 8, l))
 	    goto bail1;
     }
-    n = FcCharSetFreezeBase (b);
+    n = FcCharSetFreezeBase (freezer, b, fcs);
+    if (!FcCharSetFreezeOrig (freezer, fcs, n))
+    {
+	n = NULL;
+	goto bail1;
+    }
+    freezer->charsets_seen++;
+    freezer->leaves_seen += fcs->num;
 bail1:
-    if (FcCharSetLeaves (b))
+    if (b->num)
     {
 	FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcCharLeaf *));
 	free (FcCharSetLeaves (b));
     }
-    if (FcCharSetNumbers (b))
+    if (b->num)
     {
 	FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcChar16));
 	free (FcCharSetNumbers (b));
@@ -1115,159 +1266,82 @@ bail0:
     return n;
 }
 
-FcCharSet *
-FcNameParseCharSet (FcChar8 *string)
+FcCharSetFreezer *
+FcCharSetFreezerCreate (void)
 {
-    FcCharSet	*c, *n = 0;
-    FcChar32	ucs4;
-    FcCharLeaf	*leaf;
-    FcCharLeaf	temp;
-    FcChar32	bits;
-    int		i;
+    FcCharSetFreezer	*freezer;
 
-    c = FcCharSetCreate ();
-    if (!c)
-	goto bail0;
-    while (*string)
+    freezer = calloc (1, sizeof (FcCharSetFreezer));
+    return freezer;
+}
+
+void
+FcCharSetFreezerDestroy (FcCharSetFreezer *freezer)
+{
+    int i;
+
+    if (FcDebug() & FC_DBG_CACHE)
     {
-	string = FcCharSetParseValue (string, &ucs4);
-	if (!string)
-	    goto bail1;
-	bits = 0;
-	for (i = 0; i < 256/32; i++)
-	{
-	    string = FcCharSetParseValue (string, &temp.map[i]);
-	    if (!string)
-		goto bail1;
-	    bits |= temp.map[i];
-	}
-	if (bits)
+	printf ("\ncharsets %d -> %d leaves %d -> %d\n",
+		freezer->charsets_seen, freezer->charsets_allocated,
+		freezer->leaves_seen, freezer->leaves_allocated);
+    }
+    for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
+    {
+	FcCharSetEnt	*ent, *next;
+	for (ent = freezer->set_hash_table[i]; ent; ent = next)
 	{
-	    leaf = FcCharSetFreezeLeaf (&temp);
-	    if (!leaf)
-		goto bail1;
-	    if (!FcCharSetInsertLeaf (c, ucs4, leaf))
-		goto bail1;
+	    next = ent->next;
+	    FcMemFree (FC_MEM_CHARSET, (sizeof (FcCharSetEnt) +
+					ent->set.num * sizeof (FcCharLeaf *) +
+					ent->set.num * sizeof (FcChar16)));
+	    free (ent);
 	}
     }
-#ifdef CHATTY
-    printf ("          %8s %8s %8s %8s\n", "total", "totalmem", "new", "newmem");
-    printf ("Leaves:   %8d %8d %8d %8d\n",
-	    FcCharLeafTotal, sizeof (FcCharLeaf) * FcCharLeafTotal,
-	    FcCharLeafUsed, sizeof (FcCharLeaf) * FcCharLeafUsed);
-    printf ("Charsets: %8d %8d %8d %8d\n",
-	    FcCharSetTotal, sizeof (FcCharSet) * FcCharSetTotal,
-	    FcCharSetUsed, sizeof (FcCharSet) * FcCharSetUsed);
-    printf ("Tables:   %8d %8d %8d %8d\n",
-	    FcCharSetTotalEnts, FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
-	    FcCharSetUsedEnts, FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
-    printf ("Total:    %8s %8d %8s %8d\n", 
-	    "", 
-	    sizeof (FcCharLeaf) * FcCharLeafTotal +
-	    sizeof (FcCharSet) * FcCharSetTotal +
-	    FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
-	    "",
-	    sizeof (FcCharLeaf) * FcCharLeafUsed +
-	    sizeof (FcCharSet) * FcCharSetUsed +
-	    FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
-#endif
-    n = FcCharSetFreezeBase (c);
-bail1:
-    if (FcCharSetLeaves (c))
+
+    for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
     {
-	FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcCharLeaf *));
-	free (FcCharSetLeaves (c));
+	FcCharSetOrigEnt	*ent, *next;
+	for (ent = freezer->orig_hash_table[i]; ent; ent = next)
+	{
+	    next = ent->next;
+	    free (ent);
+	}
     }
-    if (FcCharSetNumbers (c))
+
+    for (i = 0; i < freezer->leaf_block_count; i++)
     {
-	FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcChar16));
-	free (FcCharSetNumbers (c));
+	free (freezer->leaf_blocks[i]);
+	FcMemFree (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
     }
-    FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
-    free (c);
-bail0:
-    return n;
+
+    free (freezer->leaf_blocks);
+    free (freezer);
 }
 
 FcBool
-FcNameUnparseCharSet (FcStrBuf *buf, const FcCharSet *c)
+FcCharSetSerializeAlloc (FcSerialize *serialize, const FcCharSet *cs)
 {
-    FcCharSetIter   ci;
+    intptr_t	    *leaves;
+    FcChar16	    *numbers;
     int		    i;
-#ifdef CHECK
-    int		    len = buf->len;
-#endif
-
-    for (FcCharSetIterStart (c, &ci);
-	 ci.leaf;
-	 FcCharSetIterNext (c, &ci))
-    {
-	if (!FcCharSetUnparseValue (buf, ci.ucs4))
-	    return FcFalse;
-	for (i = 0; i < 256/32; i++)
-	    if (!FcCharSetUnparseValue (buf, ci.leaf->map[i]))
-		return FcFalse;
-    }
-#ifdef CHECK
+    
+    if (cs->ref != FC_REF_CONSTANT)
     {
-	FcCharSet	*check;
-	FcChar32	missing;
-	FcCharSetIter	ci, checki;
-	
-	/* null terminate for parser */
-	FcStrBufChar (buf, '\0');
-	/* step back over null for life after test */
-	buf->len--;
-	check = FcNameParseCharSet (buf->buf + len);
-	FcCharSetIterStart (c, &ci);
-	FcCharSetIterStart (check, &checki);
-	while (ci.leaf || checki.leaf)
+	if (!serialize->cs_freezer)
 	{
-	    if (ci.ucs4 < checki.ucs4)
-	    {
-		printf ("Missing leaf node at 0x%x\n", ci.ucs4);
-		FcCharSetIterNext (c, &ci);
-	    }
-	    else if (checki.ucs4 < ci.ucs4)
-	    {
-		printf ("Extra leaf node at 0x%x\n", checki.ucs4);
-		FcCharSetIterNext (check, &checki);
-	    }
-	    else
-	    {
-		int	    i = 256/32;
-		FcChar32    *cm = ci.leaf->map;
-		FcChar32    *checkm = checki.leaf->map;
-
-		for (i = 0; i < 256; i += 32)
-		{
-		    if (*cm != *checkm)
-			printf ("Mismatching sets at 0x%08x: 0x%08x != 0x%08x\n",
-				ci.ucs4 + i, *cm, *checkm);
-		    cm++;
-		    checkm++;
-		}
-		FcCharSetIterNext (c, &ci);
-		FcCharSetIterNext (check, &checki);
-	    }
+	    serialize->cs_freezer = FcCharSetFreezerCreate ();
+	    if (!serialize->cs_freezer)
+		return FcFalse;
 	}
-	if ((missing = FcCharSetSubtractCount (c, check)))
-	    printf ("%d missing in reparsed result\n", missing);
-	if ((missing = FcCharSetSubtractCount (check, c)))
-	    printf ("%d extra in reparsed result\n", missing);
-	FcCharSetDestroy (check);
+	if (FcCharSetFindFrozen (serialize->cs_freezer, cs))
+	    return FcTrue;
+    
+        cs = FcCharSetFreeze (serialize->cs_freezer, cs);
     }
-#endif
     
-    return FcTrue;
-}
-
-FcBool
-FcCharSetSerializeAlloc (FcSerialize *serialize, const FcCharSet *cs)
-{
-    intptr_t	    *leaves = FcCharSetLeaves (cs);
-    FcChar16	    *numbers = FcCharSetNumbers (cs);
-    int		    i;
+    leaves = FcCharSetLeaves (cs);
+    numbers = FcCharSetNumbers (cs);
     
     if (!FcSerializeAlloc (serialize, cs, sizeof (FcCharSet)))
 	return FcFalse;
@@ -1285,12 +1359,20 @@ FcCharSetSerializeAlloc (FcSerialize *serialize, const FcCharSet *cs)
 FcCharSet *
 FcCharSetSerialize(FcSerialize *serialize, const FcCharSet *cs)
 {
-    FcCharSet	*cs_serialized = FcSerializePtr (serialize, cs);
+    FcCharSet	*cs_serialized;
     intptr_t	*leaves, *leaves_serialized;
     FcChar16	*numbers, *numbers_serialized;
     FcCharLeaf	*leaf, *leaf_serialized;
     int		i;
 
+    if (cs->ref != FC_REF_CONSTANT && serialize->cs_freezer)
+    {
+	cs = FcCharSetFindFrozen (serialize->cs_freezer, cs);
+	if (!cs)
+	    return NULL;
+    }
+		    
+    cs_serialized = FcSerializePtr (serialize, cs);
     if (!cs_serialized)
 	return NULL;
     
@@ -1335,3 +1417,6 @@ FcCharSetSerialize(FcSerialize *serialize, const FcCharSet *cs)
     
     return cs_serialized;
 }
+#define __fccharset__
+#include "fcaliastail.h"
+#undef __fccharset__