X-Git-Url: https://git.wh0rd.org/?a=blobdiff_plain;f=src%2Ffccharset.c;h=d30e1614a83d3d8c822271b240d02d43d1f1f211;hb=77f4e60a32971a815b85f187712191724a00b856;hp=d87a720a5f4b31efd6bfd81efc503145377599f1;hpb=f45d39b1fda93c949f4625a9fcee0c482b5cacd7;p=fontconfig.git diff --git a/src/fccharset.c b/src/fccharset.c index d87a720..d30e161 100644 --- a/src/fccharset.c +++ b/src/fccharset.c @@ -1,7 +1,7 @@ /* - * $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 + * 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 @@ -13,22 +13,20 @@ * 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 * PERFORMANCE OF THIS SOFTWARE. */ -#include #include "fcint.h" +#include /* #define CHECK */ -/* #define CHATTY */ - FcCharSet * FcCharSetCreate (void) { @@ -40,129 +38,163 @@ FcCharSetCreate (void) FcMemAlloc (FC_MEM_CHARSET, sizeof (FcCharSet)); fcs->ref = 1; fcs->num = 0; - fcs->leaves = 0; - fcs->numbers = 0; + fcs->leaves_offset = 0; + fcs->numbers_offset = 0; return fcs; } -FcCharSet * -FcCharSetNew (void); - FcCharSet * FcCharSetNew (void) { return FcCharSetCreate (); } - void 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++) { FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf)); - free (fcs->leaves[i]); - } - if (fcs->leaves) - { - FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *)); - free (fcs->leaves); + free (FcCharSetLeaf (fcs, i)); } - if (fcs->numbers) + if (fcs->num) { + /* the numbers here are estimates */ + FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (intptr_t)); + free (FcCharSetLeaves (fcs)); FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16)); - free (fcs->numbers); + free (FcCharSetNumbers (fcs)); } FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet)); free (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 = fcs->numbers; + 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) { int pos = FcCharSetFindLeafPos (fcs, ucs4); if (pos >= 0) - return fcs->leaves[pos]; + return FcCharSetLeaf(fcs, pos); return 0; } +#define FC_IS_ZERO_OR_POWER_OF_TWO(x) (!((x) & ((x)-1))) + static FcBool FcCharSetPutLeaf (FcCharSet *fcs, FcChar32 ucs4, 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 *)); - else - leaves = realloc (fcs->leaves, (fcs->num + 1) * sizeof (FcCharLeaf *)); - 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) - numbers = malloc (sizeof (FcChar16)); - else - numbers = realloc (fcs->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; + + if (FC_IS_ZERO_OR_POWER_OF_TWO (fcs->num)) + { + 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); + } - 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; } @@ -180,7 +212,7 @@ FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4) pos = FcCharSetFindLeafPos (fcs, ucs4); if (pos >= 0) - return fcs->leaves[pos]; + return FcCharSetLeaf(fcs, pos); leaf = calloc (1, sizeof (FcCharLeaf)); if (!leaf) @@ -205,8 +237,9 @@ FcCharSetInsertLeaf (FcCharSet *fcs, FcChar32 ucs4, FcCharLeaf *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; @@ -257,13 +290,10 @@ FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter) 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); -#endif } static void @@ -277,36 +307,18 @@ FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter) } 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; } } -#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); } @@ -315,6 +327,8 @@ FcCharSetCopy (FcCharSet *src) { if (src->ref != FC_REF_CONSTANT) src->ref++; + else + FcCacheObjectReference (src); return src; } @@ -456,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, @@ -488,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 @@ -560,7 +629,7 @@ FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b) 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++); } @@ -594,15 +663,15 @@ FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b) 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) { @@ -624,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 = b->numbers[mid]; - if (bn == an) - { - high = mid; - break; - } - if (bn < an) - low = mid + 1; - else - high = mid - 1; - } - bi = high; - while (bi < b->num && b->numbers[bi] < an) - bi++; + bi = FcCharSetFindLeafForward (b, bi + 1, an); + if (bi < 0) + bi = -bi - 1; } } /* @@ -699,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) @@ -836,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 { @@ -845,27 +1019,63 @@ struct _FcCharLeafEnt { }; #define FC_CHAR_LEAF_BLOCK (4096 / sizeof (FcCharLeafEnt)) +#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) { - block = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt)); - if (!block) + FcCharLeafEnt **newBlocks; + + freezer->leaf_block_count++; + newBlocks = realloc (freezer->leaf_blocks, freezer->leaf_block_count * sizeof (FcCharLeafEnt *)); + if (!newBlocks) + return 0; + 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) { @@ -877,28 +1087,22 @@ FcCharLeafHash (FcCharLeaf *leaf) return hash; } -static int FcCharLeafTotal; -static int FcCharLeafUsed; - static FcCharLeaf * -FcCharSetFreezeLeaf (FcCharLeaf *leaf) +FcCharSetFreezeLeaf (FcCharSetFreezer *freezer, 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 = &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; @@ -906,58 +1110,62 @@ FcCharSetFreezeLeaf (FcCharLeaf *leaf) return &ent->leaf; } -typedef struct _FcCharSetEnt FcCharSetEnt; - -struct _FcCharSetEnt { - FcCharSetEnt *next; - FcChar32 hash; - FcCharSet set; -}; - -#define FC_CHAR_SET_HASH_SIZE 67 - static FcChar32 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; 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)) ^ fcs->numbers[i]; + hash = ((hash << 1) | (hash >> 31)) ^ *FcCharSetNumbers(fcs); return hash; } -static int FcCharSetTotal; -static int FcCharSetUsed; -static int FcCharSetTotalEnts, FcCharSetUsedEnts; +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) { - static FcCharSetEnt *hashTable[FC_CHAR_SET_HASH_SIZE]; FcChar32 hash = FcCharSetHash (fcs); - FcCharSetEnt **bucket = &hashTable[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 && 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; } } @@ -968,60 +1176,89 @@ 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; 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; ent->next = *bucket; *bucket = ent; + return &ent->set; } -FcCharSet * -FcCharSetFreeze (FcCharSet *fcs) +static const FcCharSet * +FcCharSetFindFrozen (FcCharSetFreezer *freezer, const FcCharSet *orig) { - FcCharSet *b; - FcCharSet *n = 0; - FcCharLeaf *l; - int i; + 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; +} + +const FcCharSet * +FcCharSetFreeze (FcCharSetFreezer *freezer, const FcCharSet *fcs) +{ + 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 (fcs->leaves[i]); + l = FcCharSetFreezeLeaf (freezer, 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); + n = FcCharSetFreezeBase (freezer, b, fcs); + if (!FcCharSetFreezeOrig (freezer, fcs, n)) + { + n = NULL; + goto bail1; + } + freezer->charsets_seen++; + freezer->leaves_seen += fcs->num; bail1: - if (b->leaves) + if (b->num) { FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcCharLeaf *)); - free (b->leaves); + free (FcCharSetLeaves (b)); } - if (b->numbers) + if (b->num) { FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcChar16)); - free (b->numbers); + free (FcCharSetNumbers (b)); } FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet)); free (b); @@ -1029,149 +1266,157 @@ 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 (c->leaves) + + for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++) { - FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcCharLeaf *)); - free (c->leaves); + FcCharSetOrigEnt *ent, *next; + for (ent = freezer->orig_hash_table[i]; ent; ent = next) + { + next = ent->next; + free (ent); + } } - if (c->numbers) + + for (i = 0; i < freezer->leaf_block_count; i++) { - FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcChar16)); - free (c->numbers); + 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 (cs->ref != FC_REF_CONSTANT) { - if (!FcCharSetUnparseValue (buf, ci.ucs4)) - return FcFalse; - for (i = 0; i < 256/32; i++) - if (!FcCharSetUnparseValue (buf, ci.leaf->map[i])) + if (!serialize->cs_freezer) + { + serialize->cs_freezer = FcCharSetFreezerCreate (); + if (!serialize->cs_freezer) return FcFalse; + } + if (FcCharSetFindFrozen (serialize->cs_freezer, cs)) + return FcTrue; + + cs = FcCharSetFreeze (serialize->cs_freezer, cs); } -#ifdef CHECK + + leaves = FcCharSetLeaves (cs); + numbers = FcCharSetNumbers (cs); + + 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; + intptr_t *leaves, *leaves_serialized; + FcChar16 *numbers, *numbers_serialized; + FcCharLeaf *leaf, *leaf_serialized; + int i; + + if (cs->ref != FC_REF_CONSTANT && serialize->cs_freezer) { - FcCharSet *check; - FcChar32 missing; - FcCharSetIter ci, checki; + cs = FcCharSetFindFrozen (serialize->cs_freezer, cs); + if (!cs) + return NULL; + } + + cs_serialized = FcSerializePtr (serialize, cs); + if (!cs_serialized) + return NULL; + + cs_serialized->ref = FC_REF_CONSTANT; + cs_serialized->num = cs->num; + + if (cs->num) + { + leaves = FcCharSetLeaves (cs); + leaves_serialized = FcSerializePtr (serialize, leaves); + if (!leaves_serialized) + return NULL; + + cs_serialized->leaves_offset = FcPtrToOffset (cs_serialized, + leaves_serialized); - /* 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) + 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++) { - 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); - } + 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]; } - 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 + else + { + cs_serialized->leaves_offset = 0; + cs_serialized->numbers_offset = 0; + } - return FcTrue; + return cs_serialized; } +#define __fccharset__ +#include "fcaliastail.h" +#undef __fccharset__