source: trunk/poppler/fontconfig-2.3.2-os2/src/fclist.c @ 2

Last change on this file since 2 was 2, checked in by Eugene Romanenko, 15 years ago

First import

File size: 10.8 KB
Line 
1/*
2 * $RCSId: xc/lib/fontconfig/src/fclist.c,v 1.11tsi Exp $
3 *
4 * Copyright © 2000 Keith Packard
5 *
6 * Permission to use, copy, modify, distribute, and sell this software and its
7 * documentation for any purpose is hereby granted without fee, provided that
8 * the above copyright notice appear in all copies and that both that
9 * copyright notice and this permission notice appear in supporting
10 * documentation, and that the name of 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.
15 *
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.
23 */
24
25#include <stdlib.h>
26#include "fcint.h"
27
28FcObjectSet *
29FcObjectSetCreate (void)
30{
31    FcObjectSet    *os;
32
33    os = (FcObjectSet *) malloc (sizeof (FcObjectSet));
34    if (!os)
35        return 0;
36    FcMemAlloc (FC_MEM_OBJECTSET, sizeof (FcObjectSet));
37    os->nobject = 0;
38    os->sobject = 0;
39    os->objects = 0;
40    return os;
41}
42
43FcBool
44FcObjectSetAdd (FcObjectSet *os, const char *object)
45{
46    int         s;
47    const char  **objects;
48    int         high, low, mid, c;
49   
50    if (os->nobject == os->sobject)
51    {
52        s = os->sobject + 4;
53        if (os->objects)
54            objects = (const char **) realloc ((void *) os->objects,
55                                               s * sizeof (const char *));
56        else
57            objects = (const char **) malloc (s * sizeof (const char *));
58        if (!objects)
59            return FcFalse;
60        if (os->sobject)
61            FcMemFree (FC_MEM_OBJECTPTR, os->sobject * sizeof (const char *));
62        FcMemAlloc (FC_MEM_OBJECTPTR, s * sizeof (const char *));
63        os->objects = objects;
64        os->sobject = s;
65    }
66    high = os->nobject - 1;
67    low = 0;
68    mid = 0;
69    c = 1;
70    object = FcObjectStaticName (object);
71    while (low <= high)
72    {
73        mid = (low + high) >> 1;
74        c = os->objects[mid] - object;
75        if (c == 0)
76            return FcTrue;
77        if (c < 0)
78            low = mid + 1;
79        else
80            high = mid - 1;
81    }
82    if (c < 0)
83        mid++;
84    memmove (os->objects + mid + 1, os->objects + mid, 
85             (os->nobject - mid) * sizeof (const char *));
86    os->objects[mid] = object;
87    os->nobject++;
88    return FcTrue;
89}
90
91void
92FcObjectSetDestroy (FcObjectSet *os)
93{
94    if (os->objects)
95    {
96        FcMemFree (FC_MEM_OBJECTPTR, os->sobject * sizeof (const char *));
97        free ((void *) os->objects);
98    }
99    FcMemFree (FC_MEM_OBJECTSET, sizeof (FcObjectSet));
100    free (os);
101}
102
103FcObjectSet *
104FcObjectSetVaBuild (const char *first, va_list va)
105{
106    FcObjectSet    *ret;
107
108    FcObjectSetVapBuild (ret, first, va);
109    return ret;
110}
111
112FcObjectSet *
113FcObjectSetBuild (const char *first, ...)
114{
115    va_list         va;
116    FcObjectSet    *os;
117
118    va_start (va, first);
119    FcObjectSetVapBuild (os, first, va);
120    va_end (va);
121    return os;
122}
123
124/*
125 * Font must have a containing value for every value in the pattern
126 */
127static FcBool
128FcListValueListMatchAny (FcValueList *patOrig,      /* pattern */
129                         FcValueList *fntOrig)      /* font */
130{
131    FcValueList     *pat, *fnt;
132
133    for (pat = patOrig; pat; pat = pat->next)
134    {
135        for (fnt = fntOrig; fnt; fnt = fnt->next)
136        {
137            /*
138             * make sure the font 'contains' the pattern.
139             * (OpListing is OpContains except for strings
140             *  where it requires an exact match)
141             */
142            if (FcConfigCompareValue (fnt->value,
143                                      FcOpListing, 
144                                      pat->value)) 
145                break;
146        }
147        if (!fnt)
148            return FcFalse;
149    }
150    return FcTrue;
151}
152
153static FcBool
154FcListValueListEqual (FcValueList   *v1orig,
155                      FcValueList   *v2orig)
156{
157    FcValueList     *v1, *v2;
158
159    for (v1 = v1orig; v1; v1 = v1->next)
160    {
161        for (v2 = v2orig; v2; v2 = v2->next)
162            if (FcValueEqual (v1->value, v2->value))
163                break;
164        if (!v2)
165            return FcFalse;
166    }
167    for (v2 = v2orig; v2; v2 = v2->next)
168    {
169        for (v1 = v1orig; v1; v1 = v1->next)
170            if (FcValueEqual (v1->value, v2->value))
171                break;
172        if (!v1)
173            return FcFalse;
174    }
175    return FcTrue;
176}
177
178static FcBool
179FcListPatternEqual (FcPattern   *p1,
180                    FcPattern   *p2,
181                    FcObjectSet *os)
182{
183    int             i;
184    FcPatternElt    *e1, *e2;
185
186    for (i = 0; i < os->nobject; i++)
187    {
188        e1 = FcPatternFindElt (p1, os->objects[i]);
189        e2 = FcPatternFindElt (p2, os->objects[i]);
190        if (!e1 && !e2)
191            continue;
192        if (!e1 || !e2)
193            return FcFalse;
194        if (!FcListValueListEqual (e1->values, e2->values))
195            return FcFalse;
196    }
197    return FcTrue;
198}
199
200/*
201 * FcTrue iff all objects in "p" match "font"
202 */
203
204FcBool
205FcListPatternMatchAny (const FcPattern *p,
206                       const FcPattern *font)
207{
208    int             i;
209    FcPatternElt   *e;
210
211    for (i = 0; i < p->num; i++)
212    {
213        e = FcPatternFindElt (font, p->elts[i].object);
214        if (!e)
215            return FcFalse;
216        if (!FcListValueListMatchAny (p->elts[i].values,    /* pat elts */
217                                      e->values))           /* font elts */
218            return FcFalse;
219    }
220    return FcTrue;
221}
222
223static FcChar32
224FcListMatrixHash (const FcMatrix *m)
225{
226    int     xx = (int) (m->xx * 100), 
227            xy = (int) (m->xy * 100), 
228            yx = (int) (m->yx * 100),
229            yy = (int) (m->yy * 100);
230
231    return ((FcChar32) xx) ^ ((FcChar32) xy) ^ ((FcChar32) yx) ^ ((FcChar32) yy);
232}
233
234static FcChar32
235FcListValueHash (FcValue    v)
236{
237    switch (v.type) {
238    case FcTypeVoid:
239        return 0;
240    case FcTypeInteger:
241        return (FcChar32) v.u.i;
242    case FcTypeDouble:
243        return (FcChar32) (int) v.u.d;
244    case FcTypeString:
245        return FcStrHashIgnoreCase (v.u.s);
246    case FcTypeBool:
247        return (FcChar32) v.u.b;
248    case FcTypeMatrix:
249        return FcListMatrixHash (v.u.m);
250    case FcTypeCharSet:
251        return FcCharSetCount (v.u.c);
252    case FcTypeFTFace:
253        return (long) v.u.f;
254    case FcTypeLangSet:
255        return FcLangSetHash (v.u.l);
256    }
257    return 0;
258}
259
260static FcChar32
261FcListValueListHash (FcValueList    *list)
262{
263    FcChar32    h = 0;
264   
265    while (list)
266    {
267        h = h ^ FcListValueHash (list->value);
268        list = list->next;
269    }
270    return h;
271}
272
273static FcChar32
274FcListPatternHash (FcPattern    *font,
275                   FcObjectSet  *os)
276{
277    int             n;
278    FcPatternElt    *e;
279    FcChar32        h = 0;
280
281    for (n = 0; n < os->nobject; n++)
282    {
283        e = FcPatternFindElt (font, os->objects[n]);
284        if (e)
285            h = h ^ FcListValueListHash (e->values);
286    }
287    return h;
288}
289
290typedef struct _FcListBucket {
291    struct _FcListBucket    *next;
292    FcChar32                hash;
293    FcPattern               *pattern;
294} FcListBucket;
295
296#define FC_LIST_HASH_SIZE   4099
297
298typedef struct _FcListHashTable {
299    int             entries;
300    FcListBucket    *buckets[FC_LIST_HASH_SIZE];
301} FcListHashTable;
302   
303static void
304FcListHashTableInit (FcListHashTable *table)
305{
306    table->entries = 0;
307    memset (table->buckets, '\0', sizeof (table->buckets));
308}
309
310static void
311FcListHashTableCleanup (FcListHashTable *table)
312{
313    int i;
314    FcListBucket    *bucket, *next;
315
316    for (i = 0; i < FC_LIST_HASH_SIZE; i++)
317    {
318        for (bucket = table->buckets[i]; bucket; bucket = next)
319        {
320            next = bucket->next;
321            FcPatternDestroy (bucket->pattern);
322            FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
323            free (bucket);
324        }
325        table->buckets[i] = 0;
326    }
327    table->entries = 0;
328}
329
330static FcBool
331FcListAppend (FcListHashTable   *table,
332              FcPattern         *font,
333              FcObjectSet       *os)
334{
335    int             o;
336    FcPatternElt    *e;
337    FcValueList     *v;
338    FcChar32        hash;
339    FcListBucket    **prev, *bucket;
340
341    hash = FcListPatternHash (font, os);
342    for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
343         (bucket = *prev); prev = &(bucket->next))
344    {
345        if (bucket->hash == hash && 
346            FcListPatternEqual (bucket->pattern, font, os))
347            return FcTrue;
348    }
349    bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
350    if (!bucket)
351        goto bail0;
352    FcMemAlloc (FC_MEM_LISTBUCK, sizeof (FcListBucket));
353    bucket->next = 0;
354    bucket->hash = hash;
355    bucket->pattern = FcPatternCreate ();
356    if (!bucket->pattern)
357        goto bail1;
358   
359    for (o = 0; o < os->nobject; o++)
360    {
361        e = FcPatternFindElt (font, os->objects[o]);
362        if (e)
363        {
364            for (v = e->values; v; v = v->next)
365            {
366                if (!FcPatternAdd (bucket->pattern, 
367                                   os->objects[o], 
368                                   v->value, FcTrue))
369                    goto bail2;
370            }
371        }
372    }
373    *prev = bucket;
374    ++table->entries;
375
376    return FcTrue;
377   
378bail2:
379    FcPatternDestroy (bucket->pattern);
380bail1:
381    FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
382    free (bucket);
383bail0:
384    return FcFalse;
385}
386
387FcFontSet *
388FcFontSetList (FcConfig     *config,
389               FcFontSet    **sets,
390               int          nsets,
391               FcPattern    *p,
392               FcObjectSet  *os)
393{
394    FcFontSet       *ret;
395    FcFontSet       *s;
396    int             f;
397    int             set;
398    FcListHashTable table;
399    int             i;
400    FcListBucket    *bucket;
401
402    if (!config)
403    {
404        if (!FcInitBringUptoDate ())
405            goto bail0;
406
407        config = FcConfigGetCurrent ();
408        if (!config)
409            goto bail0;
410    }
411    FcListHashTableInit (&table);
412    /*
413     * Walk all available fonts adding those that
414     * match to the hash table
415     */
416    for (set = 0; set < nsets; set++)
417    {
418        s = sets[set];
419        if (!s)
420            continue;
421        for (f = 0; f < s->nfont; f++)
422            if (FcListPatternMatchAny (p,               /* pattern */
423                                       s->fonts[f]))    /* font */
424                if (!FcListAppend (&table, s->fonts[f], os))
425                    goto bail1;
426    }
427#if 0
428    {
429        int     max = 0;
430        int     full = 0;
431        int     ents = 0;
432        int     len;
433        for (i = 0; i < FC_LIST_HASH_SIZE; i++)
434        {
435            if ((bucket = table.buckets[i]))
436            {
437                len = 0;
438                for (; bucket; bucket = bucket->next)
439                {
440                    ents++;
441                    len++;
442                }
443                if (len > max)
444                    max = len;
445                full++;
446            }
447        }
448        printf ("used: %d max: %d avg: %g\n", full, max,
449                (double) ents / FC_LIST_HASH_SIZE);
450    }
451#endif
452    /*
453     * Walk the hash table and build
454     * a font set
455     */
456    ret = FcFontSetCreate ();
457    if (!ret)
458        goto bail0;
459    for (i = 0; i < FC_LIST_HASH_SIZE; i++)
460        while ((bucket = table.buckets[i]))
461        {
462            if (!FcFontSetAdd (ret, bucket->pattern))
463                goto bail2;
464            table.buckets[i] = bucket->next;
465            FcMemFree (FC_MEM_LISTBUCK, sizeof (FcListBucket));
466            free (bucket);
467        }
468   
469    return ret;
470
471bail2:
472    FcFontSetDestroy (ret);
473bail1:
474    FcListHashTableCleanup (&table);
475bail0:
476    return 0;
477}
478
479FcFontSet *
480FcFontList (FcConfig    *config,
481            FcPattern   *p,
482            FcObjectSet *os)
483{
484    FcFontSet   *sets[2];
485    int         nsets;
486
487    if (!config)
488    {
489        config = FcConfigGetCurrent ();
490        if (!config)
491            return 0;
492    }
493    nsets = 0;
494    if (config->fonts[FcSetSystem])
495        sets[nsets++] = config->fonts[FcSetSystem];
496    if (config->fonts[FcSetApplication])
497        sets[nsets++] = config->fonts[FcSetApplication];
498    return FcFontSetList (config, sets, nsets, p, os);
499}
Note: See TracBrowser for help on using the repository browser.