/*
* $RCSId: xc/lib/fontconfig/src/fccharset.c,v 1.18 2002/08/22 07:36:44 keithp Exp $
*
- * Copyright © 2001 Keith Packard
+ * Copyright © 2001 Keith Packard
*
* Permission to use, copy, modify, distribute, and sell this software and its
* documentation for any purpose is hereby granted without fee, provided that
* PERFORMANCE OF THIS SOFTWARE.
*/
-#include <stdlib.h>
#include "fcint.h"
+#include <stdlib.h>
/* #define CHECK */
FcMemAlloc (FC_MEM_CHARSET, sizeof (FcCharSet));
fcs->ref = 1;
fcs->num = 0;
- fcs->leaves = 0;
- fcs->numbers = 0;
+ fcs->leaves_offset = FcPtrToOffset (fcs, NULL);
+ fcs->numbers_offset = FcPtrToOffset (fcs, NULL);
return fcs;
}
return FcCharSetCreate ();
}
-
void
FcCharSetDestroy (FcCharSet *fcs)
{
int i;
+
if (fcs->ref == FC_REF_CONSTANT)
return;
if (--fcs->ref > 0)
for (i = 0; i < fcs->num; i++)
{
FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
- free (fcs->leaves[i]);
+ free (FcCharSetLeaf (fcs, i));
}
- if (fcs->leaves)
+ if (FcCharSetLeaves (fcs))
{
- FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *));
- free (fcs->leaves);
+ FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (intptr_t));
+ free (FcCharSetLeaves (fcs));
}
- if (fcs->numbers)
+ if (FcCharSetNumbers (fcs))
{
FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
- free (fcs->numbers);
+ free (FcCharSetNumbers (fcs));
}
FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
free (fcs);
static int
FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
{
- FcChar16 *numbers = fcs->numbers;
+ FcChar16 *numbers = FcCharSetNumbers(fcs);
FcChar16 page;
int low = 0;
int high = fcs->num - 1;
{
int pos = FcCharSetFindLeafPos (fcs, ucs4);
if (pos >= 0)
- return fcs->leaves[pos];
+ return FcCharSetLeaf(fcs, pos);
return 0;
}
FcCharLeaf *leaf,
int pos)
{
- FcCharLeaf **leaves;
- FcChar16 *numbers;
+ intptr_t *leaves = FcCharSetLeaves (fcs);
+ FcChar16 *numbers = FcCharSetNumbers (fcs);
ucs4 >>= 8;
if (ucs4 >= 0x10000)
return FcFalse;
- if (!fcs->leaves)
- leaves = malloc (sizeof (FcCharLeaf *));
+ if (!leaves)
+ leaves = malloc (sizeof (*leaves));
else
- leaves = realloc (fcs->leaves, (fcs->num + 1) * sizeof (FcCharLeaf *));
+ {
+ intptr_t *new_leaves = realloc (leaves, (fcs->num + 1) *
+ sizeof (*leaves));
+ intptr_t 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)
return FcFalse;
+
if (fcs->num)
- FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *));
- FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcCharLeaf *));
- fcs->leaves = leaves;
- if (!fcs->numbers)
+ 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 (fcs->numbers, (fcs->num + 1) * sizeof (FcChar16));
+ 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 = numbers;
+ fcs->numbers_offset = FcPtrToOffset (fcs, numbers);
- memmove (fcs->leaves + pos + 1, fcs->leaves + pos,
- (fcs->num - pos) * sizeof (FcCharLeaf *));
- memmove (fcs->numbers + pos + 1, fcs->numbers + pos,
- (fcs->num - pos) * sizeof (FcChar16));
- fcs->numbers[pos] = (FcChar16) ucs4;
- fcs->leaves[pos] = leaf;
+ memmove (leaves + pos + 1, leaves + pos,
+ (fcs->num - pos) * sizeof (*leaves));
+ memmove (numbers + pos + 1, numbers + pos,
+ (fcs->num - pos) * sizeof (*numbers));
+ numbers[pos] = (FcChar16) ucs4;
+ leaves[pos] = FcPtrToOffset (leaves, leaf);
fcs->num++;
return FcTrue;
}
pos = FcCharSetFindLeafPos (fcs, ucs4);
if (pos >= 0)
- return fcs->leaves[pos];
+ return FcCharSetLeaf(fcs, pos);
leaf = calloc (1, sizeof (FcCharLeaf));
if (!leaf)
if (pos >= 0)
{
FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
- free (fcs->leaves[pos]);
- fcs->leaves[pos] = leaf;
+ free (FcCharSetLeaf (fcs, pos));
+ FcCharSetLeaves(fcs)[pos] = FcPtrToOffset (FcCharSetLeaves(fcs),
+ leaf);
return FcTrue;
}
pos = -pos - 1;
iter->leaf = 0;
return;
}
- iter->ucs4 = (FcChar32) fcs->numbers[pos] << 8;
+ iter->ucs4 = (FcChar32) FcCharSetNumbers(fcs)[pos] << 8;
}
- iter->leaf = fcs->leaves[pos];
+ iter->leaf = FcCharSetLeaf(fcs, pos);
iter->pos = pos;
#ifdef CHATTY
printf ("set %08x: %08x\n", iter->ucs4, (FcChar32) iter->leaf);
}
else
{
- iter->ucs4 = (FcChar32) fcs->numbers[pos] << 8;
- iter->leaf = fcs->leaves[pos];
+ iter->ucs4 = (FcChar32) FcCharSetNumbers(fcs)[pos] << 8;
+ iter->leaf = FcCharSetLeaf(fcs, pos);
iter->pos = pos;
}
}
FcCharSetDump (fcs);
#endif
iter->ucs4 = 0;
+ iter->pos = 0;
FcCharSetIterSet (fcs, iter);
}
int i = 256/32;
if (ai.ucs4 == bi.ucs4)
{
- FcChar32 *bm = bi.leaf->map;;
+ FcChar32 *bm = bi.leaf->map;
while (i--)
count += FcCharSetPopCount (*am++ & ~*bm++);
}
ai = 0;
while (ai < a->num && bi < b->num)
{
- an = a->numbers[ai];
- bn = b->numbers[bi];
+ an = FcCharSetNumbers(a)[ai];
+ bn = FcCharSetNumbers(b)[bi];
+ /*
+ * Check matching pages
+ */
if (an == bn)
{
- FcChar32 *am = a->leaves[ai]->map;
- FcChar32 *bm = b->leaves[bi]->map;
+ FcChar32 *am = FcCharSetLeaf(a, ai)->map;
+ FcChar32 *bm = FcCharSetLeaf(b, bi)->map;
if (am != bm)
{
int i = 256/32;
+ /*
+ * Does am have any bits not in bm?
+ */
while (i--)
if (*am++ & ~*bm++)
return FcFalse;
ai++;
bi++;
}
+ /*
+ * Does a have any pages not in b?
+ */
else if (an < bn)
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 = b->numbers[mid];
+ bn = FcCharSetNumbers(b)[mid];
if (bn == an)
{
high = mid;
high = mid - 1;
}
bi = high;
- while (bi < b->num && b->numbers[bi] < an)
+ while (bi < b->num && FcCharSetNumbers(b)[bi] < an)
bi++;
}
}
- return FcTrue;
+ /*
+ * did we look at every page?
+ */
+ return ai >= a->num;
}
/*
};
#define FC_CHAR_LEAF_BLOCK (4096 / sizeof (FcCharLeafEnt))
+static FcCharLeafEnt **FcCharLeafBlocks;
+static int FcCharLeafBlockCount;
static FcCharLeafEnt *
FcCharLeafEntCreate (void)
if (!remain)
{
- block = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
+ FcCharLeafEnt **newBlocks;
+
+ FcCharLeafBlockCount++;
+ newBlocks = realloc (FcCharLeafBlocks, FcCharLeafBlockCount * sizeof (FcCharLeafEnt *));
+ if (!newBlocks)
+ return 0;
+ FcCharLeafBlocks = newBlocks;
+ block = FcCharLeafBlocks[FcCharLeafBlockCount-1] = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
if (!block)
return 0;
FcMemAlloc (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
static int FcCharLeafTotal;
static int FcCharLeafUsed;
+static FcCharLeafEnt *FcCharLeafHashTable[FC_CHAR_LEAF_HASH_SIZE];
+
static FcCharLeaf *
FcCharSetFreezeLeaf (FcCharLeaf *leaf)
{
- static FcCharLeafEnt *hashTable[FC_CHAR_LEAF_HASH_SIZE];
FcChar32 hash = FcCharLeafHash (leaf);
- FcCharLeafEnt **bucket = &hashTable[hash % FC_CHAR_LEAF_HASH_SIZE];
+ FcCharLeafEnt **bucket = &FcCharLeafHashTable[hash % FC_CHAR_LEAF_HASH_SIZE];
FcCharLeafEnt *ent;
FcCharLeafTotal++;
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 {
FcCharSetHash (FcCharSet *fcs)
{
FcChar32 hash = 0;
- FcChar32 *p;
int i;
/* hash in leaves */
- p = (FcChar32 *) fcs->leaves;
- for (i = 0; i < fcs->num * sizeof (FcCharLeaf *) / sizeof (FcChar32); i++)
- hash = ((hash << 1) | (hash >> 31)) ^ *p++;
+ for (i = 0; i < fcs->num * (int) (sizeof (FcCharLeaf *) / sizeof (FcChar32)); i++)
+ hash = ((hash << 1) | (hash >> 31)) ^ (FcChar32)(FcCharSetLeaf(fcs, i)->map);
/* hash in numbers */
for (i = 0; i < fcs->num; i++)
- hash = ((hash << 1) | (hash >> 31)) ^ fcs->numbers[i];
+ hash = ((hash << 1) | (hash >> 31)) ^ *FcCharSetNumbers(fcs);
return hash;
}
static int FcCharSetUsed;
static int FcCharSetTotalEnts, FcCharSetUsedEnts;
+static FcCharSetEnt *FcCharSetHashTable[FC_CHAR_SET_HASH_SIZE];
+
static FcCharSet *
FcCharSetFreezeBase (FcCharSet *fcs)
{
- static FcCharSetEnt *hashTable[FC_CHAR_SET_HASH_SIZE];
FcChar32 hash = FcCharSetHash (fcs);
- FcCharSetEnt **bucket = &hashTable[hash % FC_CHAR_SET_HASH_SIZE];
+ FcCharSetEnt **bucket = &FcCharSetHashTable[hash % FC_CHAR_SET_HASH_SIZE];
FcCharSetEnt *ent;
int size;
+ int i;
FcCharSetTotal++;
FcCharSetTotalEnts += fcs->num;
{
if (ent->hash == hash &&
ent->set.num == fcs->num &&
- !memcmp (ent->set.leaves, fcs->leaves,
- fcs->num * sizeof (FcCharLeaf *)) &&
- !memcmp (ent->set.numbers, fcs->numbers,
+ !memcmp (FcCharSetNumbers(&ent->set),
+ FcCharSetNumbers(fcs),
fcs->num * sizeof (FcChar16)))
{
- return &ent->set;
+ FcBool ok = FcTrue;
+ int i;
+
+ for (i = 0; i < fcs->num; i++)
+ if (FcCharSetLeaf(&ent->set, i) != FcCharSetLeaf(fcs, i))
+ ok = FcFalse;
+ if (ok)
+ return &ent->set;
}
}
ent->set.num = fcs->num;
if (fcs->num)
{
- ent->set.leaves = (FcCharLeaf **) (ent + 1);
- ent->set.numbers = (FcChar16 *) (ent->set.leaves + fcs->num);
- memcpy (ent->set.leaves, fcs->leaves, fcs->num * sizeof (FcCharLeaf *));
- memcpy (ent->set.numbers, fcs->numbers, fcs->num * sizeof (FcChar16));
+ intptr_t *ent_leaves;
+
+ ent->set.leaves_offset = sizeof (ent->set);
+ ent->set.numbers_offset = (ent->set.leaves_offset +
+ fcs->num * sizeof (intptr_t));
+
+ ent_leaves = FcCharSetLeaves (&ent->set);
+ for (i = 0; i < fcs->num; i++)
+ ent_leaves[i] = FcPtrToOffset (ent_leaves,
+ FcCharSetLeaf (fcs, i));
+ memcpy (FcCharSetNumbers (&ent->set),
+ FcCharSetNumbers (fcs),
+ fcs->num * sizeof (FcChar16));
}
else
{
- ent->set.leaves = 0;
- ent->set.numbers = 0;
+ ent->set.leaves_offset = 0;
+ ent->set.numbers_offset = 0;
}
ent->hash = hash;
return &ent->set;
}
+void
+FcCharSetThawAll (void)
+{
+ 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 ();
+}
+
FcCharSet *
FcCharSetFreeze (FcCharSet *fcs)
{
goto bail0;
for (i = 0; i < fcs->num; i++)
{
- l = FcCharSetFreezeLeaf (fcs->leaves[i]);
+ l = FcCharSetFreezeLeaf (FcCharSetLeaf(fcs, i));
if (!l)
goto bail1;
- if (!FcCharSetInsertLeaf (b, fcs->numbers[i] << 8, l))
+ if (!FcCharSetInsertLeaf (b, FcCharSetNumbers(fcs)[i] << 8, l))
goto bail1;
}
n = FcCharSetFreezeBase (b);
bail1:
- if (b->leaves)
+ if (FcCharSetLeaves (b))
{
FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcCharLeaf *));
- free (b->leaves);
+ free (FcCharSetLeaves (b));
}
- if (b->numbers)
+ if (FcCharSetNumbers (b))
{
FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcChar16));
- free (b->numbers);
+ free (FcCharSetNumbers (b));
}
FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
free (b);
#endif
n = FcCharSetFreezeBase (c);
bail1:
- if (c->leaves)
+ if (FcCharSetLeaves (c))
{
FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcCharLeaf *));
- free (c->leaves);
+ free (FcCharSetLeaves (c));
}
- if (c->numbers)
+ if (FcCharSetNumbers (c))
{
FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcChar16));
- free (c->numbers);
+ free (FcCharSetNumbers (c));
}
FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
free (c);
return FcTrue;
}
+
+FcBool
+FcCharSetSerializeAlloc (FcSerialize *serialize, const FcCharSet *cs)
+{
+ intptr_t *leaves = FcCharSetLeaves (cs);
+ FcChar16 *numbers = FcCharSetNumbers (cs);
+ int i;
+
+ if (!FcSerializeAlloc (serialize, cs, sizeof (FcCharSet)))
+ return FcFalse;
+ if (!FcSerializeAlloc (serialize, leaves, cs->num * sizeof (intptr_t)))
+ return FcFalse;
+ if (!FcSerializeAlloc (serialize, numbers, cs->num * sizeof (FcChar16)))
+ return FcFalse;
+ for (i = 0; i < cs->num; i++)
+ if (!FcSerializeAlloc (serialize, FcCharSetLeaf(cs, i),
+ sizeof (FcCharLeaf)))
+ return FcFalse;
+ return FcTrue;
+}
+
+FcCharSet *
+FcCharSetSerialize(FcSerialize *serialize, const FcCharSet *cs)
+{
+ FcCharSet *cs_serialized = FcSerializePtr (serialize, cs);
+ intptr_t *leaves, *leaves_serialized;
+ FcChar16 *numbers, *numbers_serialized;
+ FcCharLeaf *leaf, *leaf_serialized;
+ int i;
+
+ if (!cs_serialized)
+ return NULL;
+
+ cs_serialized->ref = FC_REF_CONSTANT;
+ cs_serialized->num = cs->num;
+
+ leaves = FcCharSetLeaves (cs);
+ leaves_serialized = FcSerializePtr (serialize, leaves);
+ if (!leaves_serialized)
+ return NULL;
+
+ cs_serialized->leaves_offset = FcPtrToOffset (cs_serialized,
+ leaves_serialized);
+
+ numbers = FcCharSetNumbers (cs);
+ numbers_serialized = FcSerializePtr (serialize, numbers);
+ if (!numbers)
+ return NULL;
+
+ cs_serialized->numbers_offset = FcPtrToOffset (cs_serialized,
+ numbers_serialized);
+
+ for (i = 0; i < cs->num; i++)
+ {
+ leaf = FcCharSetLeaf (cs, i);
+ leaf_serialized = FcSerializePtr (serialize, leaf);
+ if (!leaf_serialized)
+ return NULL;
+ *leaf_serialized = *leaf;
+ leaves_serialized[i] = FcPtrToOffset (leaves_serialized,
+ leaf_serialized);
+ numbers_serialized[i] = numbers[i];
+ }
+
+ return cs_serialized;
+}