fcpat.c 47.2 KB
Newer Older
Keith Packard's avatar
Keith Packard committed
1
/*
Keith Packard's avatar
Keith Packard committed
2
 * $RCSId: xc/lib/fontconfig/src/fcpat.c,v 1.18 2002/09/18 17:11:46 tsi Exp $
Keith Packard's avatar
Keith Packard committed
3
 *
4
 * Copyright © 2000 Keith Packard
Keith Packard's avatar
Keith Packard committed
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of Keith Packard not be used in
 * advertising or publicity pertaining to distribution of the software without
 * specific, written prior permission.  Keith Packard makes no
 * 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,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
 * EVENT SHALL KEITH PACKARD 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 <stdlib.h>
#include <string.h>
27
#include <assert.h>
Keith Packard's avatar
Keith Packard committed
28
29
#include "fcint.h"

30
static FcPattern ** _fcPatterns = 0;
31
static int fcpattern_bank_count = 0, fcpattern_ptr, fcpattern_count;
32
FcPatternElt ** _fcPatternElts = 0;
33
static int fcpatternelt_ptr, fcpatternelt_count;
34
FcValueList ** _fcValueLists = 0;
35
static int fcvaluelist_bank_count = 0, fcvaluelist_ptr, fcvaluelist_count;
36
37
38

static FcPatternEltPtr
FcPatternEltPtrCreateDynamic (FcPatternElt * e);
39
40
static FcBool
FcStrHashed (const FcChar8 *name);
41

42
43
44
static const char *
FcPatternFindFullFname (const FcPattern *p);

45
46
47
48
49
50
51
/* If you are trying to duplicate an FcPattern which will be used for
 * rendering, be aware that (internally) you also have to use
 * FcPatternTransferFullFname to transfer the associated filename.  If
 * you are copying the font (externally) using FcPatternGetString,
 * then everything's fine; this caveat only applies if you're copying
 * the bits individually.  */

Keith Packard's avatar
Keith Packard committed
52
53
54
55
56
57
58
59
60
61
62
FcPattern *
FcPatternCreate (void)
{
    FcPattern	*p;

    p = (FcPattern *) malloc (sizeof (FcPattern));
    if (!p)
	return 0;
    FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPattern));
    p->num = 0;
    p->size = 0;
63
    p->elts = FcPatternEltPtrCreateDynamic(0);
64
    p->bank = FC_BANK_DYNAMIC;
65
    p->ref = 1;
Keith Packard's avatar
Keith Packard committed
66
67
68
69
70
71
72
73
    return p;
}

void
FcValueDestroy (FcValue v)
{
    switch (v.type) {
    case FcTypeString:
74
75
        if (!FcStrHashed (v.u.s))
            FcStrFree ((FcChar8 *) v.u.s);
Keith Packard's avatar
Keith Packard committed
76
77
	break;
    case FcTypeMatrix:
78
	FcMatrixFree ((FcMatrix *) v.u.m);
Keith Packard's avatar
Keith Packard committed
79
80
	break;
    case FcTypeCharSet:
81
	FcCharSetDestroy ((FcCharSet *) v.u.c);
Keith Packard's avatar
Keith Packard committed
82
	break;
83
    case FcTypeLangSet:
84
	FcLangSetDestroy ((FcLangSet *) v.u.l);
85
	break;
Keith Packard's avatar
Keith Packard committed
86
87
88
89
90
    default:
	break;
    }
}

91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
FcValue
FcValueCanonicalize (const FcValue *v)
{
    if (v->type & FC_STORAGE_STATIC)
    {
	FcValue new = *v;

	switch (v->type & ~FC_STORAGE_STATIC)
	{
	case FcTypeString:
	    new.u.s = fc_value_string(v);
	    new.type = FcTypeString;
	    break;
	case FcTypeCharSet:
	    new.u.c = fc_value_charset(v);
	    new.type = FcTypeCharSet;
	    break;
	case FcTypeLangSet:
	    new.u.l = fc_value_langset(v);
	    new.type = FcTypeLangSet;
	    break;
	}
	return new;
    }
    return *v;
}

Keith Packard's avatar
Keith Packard committed
118
119
120
121
122
FcValue
FcValueSave (FcValue v)
{
    switch (v.type) {
    case FcTypeString:
123
124
	v.u.s = FcStrCopy (v.u.s);
	if (!v.u.s)
Keith Packard's avatar
Keith Packard committed
125
126
127
	    v.type = FcTypeVoid;
	break;
    case FcTypeMatrix:
128
129
	v.u.m = FcMatrixCopy (v.u.m);
	if (!v.u.m)
Keith Packard's avatar
Keith Packard committed
130
131
132
	    v.type = FcTypeVoid;
	break;
    case FcTypeCharSet:
133
134
	v.u.c = FcCharSetCopy ((FcCharSet *) v.u.c);
	if (!v.u.c)
Keith Packard's avatar
Keith Packard committed
135
136
	    v.type = FcTypeVoid;
	break;
137
    case FcTypeLangSet:
138
139
	v.u.l = FcLangSetCopy (v.u.l);
	if (!v.u.l)
140
141
	    v.type = FcTypeVoid;
	break;
Keith Packard's avatar
Keith Packard committed
142
143
144
145
146
147
148
    default:
	break;
    }
    return v;
}

void
149
FcValueListDestroy (FcValueListPtr l)
Keith Packard's avatar
Keith Packard committed
150
{
151
152
    FcValueListPtr next;
    for (; FcValueListPtrU(l); l = next)
Keith Packard's avatar
Keith Packard committed
153
    {
154
	switch (FcValueListPtrU(l)->value.type) {
Keith Packard's avatar
Keith Packard committed
155
	case FcTypeString:
156
157
            if (!FcStrHashed ((FcChar8 *)FcValueListPtrU(l)->value.u.s))
                FcStrFree ((FcChar8 *)FcValueListPtrU(l)->value.u.s);
Keith Packard's avatar
Keith Packard committed
158
159
	    break;
	case FcTypeMatrix:
160
	    FcMatrixFree ((FcMatrix *)FcValueListPtrU(l)->value.u.m);
Keith Packard's avatar
Keith Packard committed
161
162
	    break;
	case FcTypeCharSet:
163
	    FcCharSetDestroy 
164
		((FcCharSet *) (FcValueListPtrU(l)->value.u.c));
Keith Packard's avatar
Keith Packard committed
165
	    break;
166
	case FcTypeLangSet:
167
	    FcLangSetDestroy 
168
		((FcLangSet *) (FcValueListPtrU(l)->value.u.l));
169
	    break;
Keith Packard's avatar
Keith Packard committed
170
171
172
	default:
	    break;
	}
173
	next = FcValueListPtrU(l)->next;
Keith Packard's avatar
Keith Packard committed
174
	FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
175
	if (l.bank == FC_BANK_DYNAMIC)
176
	    free(l.u.dyn);
Keith Packard's avatar
Keith Packard committed
177
178
179
    }
}

180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
FcBool
FcValueEqual (FcValue va, FcValue vb)
{
    if (va.type != vb.type)
    {
	if (va.type == FcTypeInteger)
	{
	    va.type = FcTypeDouble;
	    va.u.d = va.u.i;
	}
	if (vb.type == FcTypeInteger)
	{
	    vb.type = FcTypeDouble;
	    vb.u.d = vb.u.i;
	}
	if (va.type != vb.type)
	    return FcFalse;
    }
    switch (va.type) {
    case FcTypeVoid:
	return FcTrue;
    case FcTypeInteger:
	return va.u.i == vb.u.i;
    case FcTypeDouble:
	return va.u.d == vb.u.d;
    case FcTypeString:
206
	return FcStrCmpIgnoreCase (va.u.s, vb.u.s) == 0;
207
208
209
    case FcTypeBool:
	return va.u.b == vb.u.b;
    case FcTypeMatrix:
210
	return FcMatrixEqual (va.u.m, vb.u.m);
211
    case FcTypeCharSet:
212
	return FcCharSetEqual (va.u.c, vb.u.c);
213
214
    case FcTypeFTFace:
	return va.u.f == vb.u.f;
215
    case FcTypeLangSet:
216
	return FcLangSetEqual (va.u.l, vb.u.l);
217
218
219
220
    }
    return FcFalse;
}

221
222
223
224
225
226
227
228
229
230
static FcChar32
FcDoubleHash (double d)
{
    if (d < 0)
	d = -d;
    if (d > 0xffffffff)
	d = 0xffffffff;
    return (FcChar32) d;
}

231
FcChar32
232
233
234
235
236
237
238
239
240
241
242
243
FcStringHash (const FcChar8 *s)
{
    FcChar8	c;
    FcChar32	h = 0;
    
    if (s)
	while ((c = *s++))
	    h = ((h << 1) | (h >> 31)) ^ c;
    return h;
}

static FcChar32
244
FcValueHash (const FcValue *v0)
245
{
246
    FcValue v = FcValueCanonicalize(v0);
247
248
249
250
251
252
253
254
    switch (v.type) {
    case FcTypeVoid:
	return 0;
    case FcTypeInteger:
	return (FcChar32) v.u.i;
    case FcTypeDouble:
	return FcDoubleHash (v.u.d);
    case FcTypeString:
255
	return FcStringHash (v.u.s);
256
257
258
    case FcTypeBool:
	return (FcChar32) v.u.b;
    case FcTypeMatrix:
259
260
261
262
	return (FcDoubleHash (v.u.m->xx) ^ 
		FcDoubleHash (v.u.m->xy) ^ 
		FcDoubleHash (v.u.m->yx) ^ 
		FcDoubleHash (v.u.m->yy));
263
    case FcTypeCharSet:
264
	return (FcChar32) v.u.c->num;
265
266
267
    case FcTypeFTFace:
	return FcStringHash ((const FcChar8 *) ((FT_Face) v.u.f)->family_name) ^
	       FcStringHash ((const FcChar8 *) ((FT_Face) v.u.f)->style_name);
268
    case FcTypeLangSet:
269
	return FcLangSetHash (v.u.l);
270
271
272
273
    }
    return FcFalse;
}

274
static FcBool
275
FcValueListEqual (FcValueListPtr la, FcValueListPtr lb)
276
{
277
    if (FcValueListPtrU(la) == FcValueListPtrU(lb))
278
279
	return FcTrue;

280
    while (FcValueListPtrU(la) && FcValueListPtrU(lb))
281
    {
282
283
	if (!FcValueEqual (FcValueListPtrU(la)->value, 
			   FcValueListPtrU(lb)->value))
284
	    return FcFalse;
285
286
	la = FcValueListPtrU(la)->next;
	lb = FcValueListPtrU(lb)->next;
287
    }
288
    if (FcValueListPtrU(la) || FcValueListPtrU(lb))
289
290
291
292
	return FcFalse;
    return FcTrue;
}

293
static FcChar32
294
FcValueListHash (FcValueListPtr l)
295
296
297
{
    FcChar32	hash = 0;
    
298
    while (FcValueListPtrU(l))
299
    {
300
	hash = ((hash << 1) | (hash >> 31)) ^ 
301
	    FcValueHash (&FcValueListPtrU(l)->value);
302
	l = FcValueListPtrU(l)->next;
303
304
305
306
    }
    return hash;
}

Keith Packard's avatar
Keith Packard committed
307
308
309
310
311
void
FcPatternDestroy (FcPattern *p)
{
    int		    i;
    
312
    if (p->ref == FC_REF_CONSTANT || --p->ref > 0)
313
314
	return;

315
316
    if (FcPatternFindFullFname (p))
    {
317
	FcStrFree ((FcChar8 *)FcPatternFindFullFname (p));
318
319
320
	FcPatternAddFullFname (p, 0);
    }

Keith Packard's avatar
Keith Packard committed
321
    for (i = 0; i < p->num; i++)
322
	FcValueListDestroy ((FcPatternEltU(p->elts)+i)->values);
Keith Packard's avatar
Keith Packard committed
323
324

    p->num = 0;
325
    if (FcPatternEltU(p->elts) && p->elts.bank == FC_BANK_DYNAMIC)
Keith Packard's avatar
Keith Packard committed
326
327
    {
	FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
328
329
	free (FcPatternEltU(p->elts));
	p->elts = FcPatternEltPtrCreateDynamic(0);
Keith Packard's avatar
Keith Packard committed
330
331
332
333
334
335
    }
    p->size = 0;
    FcMemFree (FC_MEM_PATTERN, sizeof (FcPattern));
    free (p);
}

336
337
338
339
340
341
342
#define FC_VALUE_LIST_HASH_SIZE	    257
#define FC_PATTERN_HASH_SIZE	    67

typedef struct _FcValueListEnt FcValueListEnt;

struct _FcValueListEnt {
    FcValueListEnt  *next;
343
    FcValueListPtr  list;
344
    FcChar32	    hash, pad;
345
346
};

Keith Packard's avatar
Keith Packard committed
347
348
349
350
351
typedef union _FcValueListAlign {
    FcValueListEnt  ent;
    FcValueList	    list;
} FcValueListAlign;

352
353
static int	    FcValueListFrozenCount[FcTypeLangSet + 1];
static int	    FcValueListFrozenBytes[FcTypeLangSet + 1];
Patrick Lam's avatar
Patrick Lam committed
354
static char	    FcValueListFrozenName[][8] = {
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
    "Void", 
    "Integer", 
    "Double", 
    "String", 
    "Bool",
    "Matrix",
    "CharSet",
    "FTFace",
    "LangSet"
};

void
FcValueListReport (void);
    
void
FcValueListReport (void)
{
    FcType  t;

    printf ("Fc Frozen Values:\n");
    printf ("\t%8s %9s %9s\n", "Type", "Count", "Bytes");
    for (t = FcTypeVoid; t <= FcTypeLangSet; t++)
	printf ("\t%8s %9d %9d\n", FcValueListFrozenName[t],
		FcValueListFrozenCount[t], FcValueListFrozenBytes[t]);
}

static FcValueListEnt *
382
FcValueListEntCreate (FcValueListPtr h)
383
{
Keith Packard's avatar
Keith Packard committed
384
    FcValueListAlign	*ea;
385
    FcValueListEnt  *e;
386
387
    FcValueListPtr  l;
    FcValueList     *new;
388
389
390
391
    int		    n;
    int		    size;

    n = 0;
392
    for (l = h; FcValueListPtrU(l); l = FcValueListPtrU(l)->next)
393
	n++;
394
    size = sizeof (FcValueListAlign) + n * sizeof (FcValueList);
395
396
397
398
    FcValueListFrozenCount[FcValueListPtrU(h)->value.type]++;
    FcValueListFrozenBytes[FcValueListPtrU(h)->value.type] += size;
    // this leaks for some reason
    ea = malloc (sizeof (FcValueListAlign));
Keith Packard's avatar
Keith Packard committed
399
    if (!ea)
400
	return 0;
401
402
403
404
    new = malloc (n * sizeof (FcValueList));
    if (!new)
        return 0;
    memset(new, 0, n * sizeof (FcValueList));
405
    FcMemAlloc (FC_MEM_VALLIST, size);
Keith Packard's avatar
Keith Packard committed
406
    e = &ea->ent;
407
408
409
    e->list = (FcValueListPtr) FcValueListPtrCreateDynamic(new);
    for (l = h; FcValueListPtrU(l); 
	 l = FcValueListPtrU(l)->next, new++)
410
    {
411
	if ((FcValueListPtrU(l)->value.type & ~FC_STORAGE_STATIC) == FcTypeString)
412
413
	{
	    new->value.type = FcTypeString;
414
	    new->value.u.s = FcStrStaticName
415
		(fc_value_string(&FcValueListPtrU(l)->value));
416
417
	}
	else
418
	{
419
420
	    new->value = FcValueSave (FcValueCanonicalize
				      (&FcValueListPtrU(l)->value));
421
422
423
424
425
	}
	new->binding = FcValueListPtrU(l)->binding;
	if (FcValueListPtrU(FcValueListPtrU(l)->next))
	{
	    new->next = FcValueListPtrCreateDynamic(new + 1);
426
	}
427
	else
428
429
430
	{
	    new->next = FcValueListPtrCreateDynamic(0);
	}
431
432
433
434
    }
    return e;
}

435
436
437
static void
FcValueListEntDestroy (FcValueListEnt *e)
{
438
    FcValueListPtr	l;
439

440
    FcValueListFrozenCount[FcValueListPtrU(e->list)->value.type]--;
441
442
443
444
445
446
447
448
449
450

    /* XXX: We should perform these two operations with "size" as
       computed in FcValueListEntCreate, but we don't have access to
       that value here. Without this, the FcValueListFrozenBytes
       values will be wrong as will the FcMemFree counts.

       FcValueListFrozenBytes[e->list->value.type] -= size;
       FcMemFree (FC_MEM_VALLIST, size);
    */

451
452
    for (l = e->list; FcValueListPtrU(l); 
	 l = FcValueListPtrU(l)->next)
453
    {
454
455
	if (FcValueListPtrU(l)->value.type != FcTypeString)
	    FcValueDestroy (FcValueListPtrU(l)->value);
456
457
458
459
460
461
462
    }
    /* XXX: Are we being too chummy with the implementation here to
       free(e) when it was actually the enclosing FcValueListAlign
       that was allocated? */
    free (e);
}

463
464
465
static int	FcValueListTotal;
static int	FcValueListUsed;

466
467
static FcValueListEnt   *FcValueListHashTable[FC_VALUE_LIST_HASH_SIZE];

468
469
static FcValueListPtr
FcValueListFreeze (FcValueListPtr l)
470
471
{
    FcChar32		    hash = FcValueListHash (l);
472
    FcValueListEnt	    **bucket = &FcValueListHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
473
474
475
476
477
478
479
480
481
482
483
    FcValueListEnt	    *ent;

    FcValueListTotal++;
    for (ent = *bucket; ent; ent = ent->next)
    {
	if (ent->hash == hash && FcValueListEqual (ent->list, l))
	    return ent->list;
    }

    ent = FcValueListEntCreate (l);
    if (!ent)
484
	return FcValueListPtrCreateDynamic(0);
485
486
487
488
489
490
491
492

    FcValueListUsed++;
    ent->hash = hash;
    ent->next = *bucket;
    *bucket = ent;
    return ent->list;
}

493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
static void
FcValueListThawAll (void)
{
    int i;
    FcValueListEnt	*ent, *next;

    for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
    {
	for (ent = FcValueListHashTable[i]; ent; ent = next)
	{
	    next = ent->next;
	    FcValueListEntDestroy (ent);
	}
	FcValueListHashTable[i] = 0;
    }

    FcValueListTotal = 0;
    FcValueListUsed = 0;
}

513
514
515
516
517
518
519
static FcChar32
FcPatternBaseHash (FcPattern *b)
{
    FcChar32	hash = b->num;
    int		i;

    for (i = 0; i < b->num; i++)
520
521
	hash = ((hash << 1) | (hash >> 31)) ^ 
	    (long) (FcValueListPtrU((FcPatternEltU(b->elts)+i)->values));
522
523
524
525
526
527
528
529
    return hash;
}

typedef struct _FcPatternEnt FcPatternEnt;

struct _FcPatternEnt {
    FcPatternEnt    *next;
    FcChar32	    hash;
530
    FcPattern  	    *pattern;
531
532
533
534
535
};

static int	FcPatternTotal;
static int	FcPatternUsed;

536
537
static FcPatternEnt	*FcPatternHashTable[FC_VALUE_LIST_HASH_SIZE];

538
539
540
static FcPattern *
FcPatternBaseFreeze (FcPattern *b)
{
541
542
    FcPattern           *ep;
    FcPatternElt	*epp;
543
    FcChar32		hash = FcPatternBaseHash (b);
544
    FcPatternEnt	**bucket = &FcPatternHashTable[hash % FC_VALUE_LIST_HASH_SIZE];
545
546
547
548
549
550
    FcPatternEnt	*ent;
    int			i;

    FcPatternTotal++;
    for (ent = *bucket; ent; ent = ent->next)
    {
551
552
        if (ent->hash == hash && b->num == ent->pattern->num)
        {
553
554
	    for (i = 0; i < b->num; i++)
	    {
555
556
		if (FcObjectPtrCompare((FcPatternEltU(b->elts)+i)->object,
				       (FcPatternEltU(ent->pattern->elts)+i)->object) != 0)
557
		    break;
558
559
		if (FcValueListPtrU((FcPatternEltU(b->elts)+i)->values) != 
                    FcValueListPtrU((FcPatternEltU(ent->pattern->elts)+i)->values))
560
561
562
		    break;
	    }
	    if (i == b->num)
563
		return ent->pattern;
564
565
566
567
	}
    }

    /*
568
     * Compute size of pattern + elts
569
     */
570
    ent = malloc (sizeof (FcPatternEnt));
571
572
573
    if (!ent)
	return 0;

574
    FcMemAlloc (FC_MEM_PATTERN, sizeof (FcPatternEnt));
575
576
    FcPatternUsed++;

577
578
579
580
581
582
583
584
585
586
587
588
589
590
    ep = FcPatternCreate();
    if (!ep)
        return 0;
    ent->pattern = ep;
    epp = malloc(b->num * sizeof (FcPatternElt));
    if (!epp)
        goto bail;
    ep->elts = FcPatternEltPtrCreateDynamic(epp);

    FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));

    ep->num = b->num;
    ep->size = b->num;
    ep->ref = FC_REF_CONSTANT;
591
592
593

    for (i = 0; i < b->num; i++)
    {
594
595
596
597
	(FcPatternEltU(ep->elts)+i)->values = 
	    (FcPatternEltU(b->elts)+i)->values;
	(FcPatternEltU(ep->elts)+i)->object = 
	    (FcPatternEltU(b->elts)+i)->object;
598
599
    }

600
601
602
    if (FcPatternFindElt (b, FC_FILE))
	FcPatternTransferFullFname (ep, b);

603
604
605
    ent->hash = hash;
    ent->next = *bucket;
    *bucket = ent;
606
607
608
609
610
611
    return ent->pattern;
 bail:
    free(ent);
    FcMemFree (FC_MEM_PATTERN, sizeof (FcPatternEnt));
    FcPatternUsed--;
    return 0;
612
613
}

614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
static void
FcPatternBaseThawAll (void)
{
    int i;
    FcPatternEnt	*ent, *next;

    for (i = 0; i < FC_VALUE_LIST_HASH_SIZE; i++)
    {
	for (ent = FcPatternHashTable[i]; ent; ent = next)
	{
	    next = ent->next;
	    free (ent);
	}
	FcPatternHashTable[i] = 0;
    }

    FcPatternTotal = 0;
    FcPatternUsed = 0;
}

634
635
636
637
FcPattern *
FcPatternFreeze (FcPattern *p)
{
    FcPattern	*b, *n = 0;
638
    FcPatternElt *e;
639
640
    int		i;
    
641
642
643
    if (p->ref == FC_REF_CONSTANT)
       return p;

644
    b = FcPatternCreate();
645
    if (!b)
646
647
        return 0;

648
649
650
    b->num = p->num;
    b->size = b->num;
    b->ref = 1;
651
652
653
654
655
656
657

    e = malloc(b->num * sizeof (FcPatternElt));
    if (!e)
        return 0;
    b->elts = FcPatternEltPtrCreateDynamic(e);
    FcMemAlloc (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));

658
659
660
661
662
    /*
     * Freeze object lists
     */
    for (i = 0; i < p->num; i++)
    {
663
664
665
666
667
	(FcPatternEltU(b->elts)+i)->object = 
	    (FcPatternEltU(p->elts)+i)->object;
	(FcPatternEltU(b->elts)+i)->values = 
	    FcValueListFreeze((FcPatternEltU(p->elts)+i)->values);
	if (!FcValueListPtrU((FcPatternEltU(p->elts)+i)->values))
668
669
	    goto bail;
    }
670
671
672
673

    if (FcPatternFindElt (p, FC_FILE))
	FcPatternTransferFullFname (b, p);

674
675
676
677
678
679
680
681
682
683
684
    /*
     * Freeze base
     */
    n = FcPatternBaseFreeze (b);
#ifdef CHATTY
    if (FcDebug() & FC_DBG_MEMORY)
    {
	printf ("ValueLists: total %9d used %9d\n", FcValueListTotal, FcValueListUsed);
	printf ("Patterns:   total %9d used %9d\n", FcPatternTotal, FcPatternUsed);
    }
#endif
685
686
687
688
689
 bail:
    free(FcPatternEltU(b->elts));
    b->elts = FcPatternEltPtrCreateDynamic(0);
    FcMemFree (FC_MEM_PATELT, sizeof (FcPatternElt)*(b->num));
    b->num = -1;
690
691
692
693
694
695
#ifdef DEBUG
    assert (FcPatternEqual (n, p));
#endif
    return n;
}

696
697
static int
FcPatternPosition (const FcPattern *p, const char *object)
Keith Packard's avatar
Keith Packard committed
698
{
699
    int	    low, high, mid, c;
700
    FcObjectPtr obj;
701

702
    obj = FcObjectToPtr(object);
703
    low = 0;
704
705
706
707
    high = p->num - 1;
    c = 1;
    mid = 0;
    while (low <= high)
Keith Packard's avatar
Keith Packard committed
708
    {
709
	mid = (low + high) >> 1;
710
	c = FcObjectPtrCompare((FcPatternEltU(p->elts)+mid)->object, obj);
711
712
713
714
	if (c == 0)
	    return mid;
	if (c < 0)
	    low = mid + 1;
715
	else
716
	    high = mid - 1;
Keith Packard's avatar
Keith Packard committed
717
    }
718
719
720
721
    if (c < 0)
	mid++;
    return -(mid + 1);
}
Keith Packard's avatar
Keith Packard committed
722

723
724
725
726
727
FcPatternElt *
FcPatternFindElt (const FcPattern *p, const char *object)
{
    int	    i = FcPatternPosition (p, object);
    if (i < 0)
728
	return 0;
729
    return FcPatternEltU(p->elts)+i;
730
}
Keith Packard's avatar
Keith Packard committed
731

732
733
734
735
736
737
738
739
FcPatternElt *
FcPatternInsertElt (FcPattern *p, const char *object)
{
    int		    i;
    FcPatternElt   *e;
    
    i = FcPatternPosition (p, object);
    if (i < 0)
Keith Packard's avatar
Keith Packard committed
740
    {
741
742
	i = -i - 1;
    
743
	/* reallocate array */
744
	if (p->num + 1 >= p->size)
Keith Packard's avatar
Keith Packard committed
745
	{
746
	    int s = p->size + 16;
747
748
749
750
751
752
753
754
755
756
757
	    if (FcPatternEltU(p->elts))
	    {
		FcPatternElt *e0 = FcPatternEltU(p->elts);
		e = (FcPatternElt *) realloc (e0, s * sizeof (FcPatternElt));
		if (!e) /* maybe it was mmapped */
		{
		    e = malloc(s * sizeof (FcPatternElt));
		    if (e)
			memcpy(e, e0, p->num * sizeof (FcPatternElt));
		}
	    }
758
759
760
761
	    else
		e = (FcPatternElt *) malloc (s * sizeof (FcPatternElt));
	    if (!e)
		return FcFalse;
762
	    p->elts = FcPatternEltPtrCreateDynamic(e);
763
764
765
766
767
	    if (p->size)
		FcMemFree (FC_MEM_PATELT, p->size * sizeof (FcPatternElt));
	    FcMemAlloc (FC_MEM_PATELT, s * sizeof (FcPatternElt));
	    while (p->size < s)
	    {
768
		(FcPatternEltU(p->elts)+p->size)->object = 0;
769
770
		(FcPatternEltU(p->elts)+p->size)->values = 
		    FcValueListPtrCreateDynamic(0);
771
772
		p->size++;
	    }
Keith Packard's avatar
Keith Packard committed
773
	}
774
775
	
	/* move elts up */
776
777
	memmove (FcPatternEltU(p->elts) + i + 1,
		 FcPatternEltU(p->elts) + i,
778
779
780
781
782
783
		 sizeof (FcPatternElt) *
		 (p->num - i));
		 
	/* bump count */
	p->num++;
	
784
	(FcPatternEltU(p->elts)+i)->object = FcObjectToPtr (object);
785
	(FcPatternEltU(p->elts)+i)->values = FcValueListPtrCreateDynamic(0);
Keith Packard's avatar
Keith Packard committed
786
787
    }
    
788
    return FcPatternEltU(p->elts)+i;
Keith Packard's avatar
Keith Packard committed
789
790
}

791
FcBool
792
FcPatternEqual (const FcPattern *pa, const FcPattern *pb)
793
794
795
{
    int	i;

796
797
798
    if (pa == pb)
	return FcTrue;

799
800
801
802
    if (pa->num != pb->num)
	return FcFalse;
    for (i = 0; i < pa->num; i++)
    {
803
804
	if (FcObjectPtrCompare((FcPatternEltU(pa->elts)+i)->object,
			       (FcPatternEltU(pb->elts)+i)->object) != 0)
805
	    return FcFalse;
806
807
	if (!FcValueListEqual ((FcPatternEltU(pa->elts)+i)->values, 
			       (FcPatternEltU(pb->elts)+i)->values))
808
809
810
811
812
	    return FcFalse;
    }
    return FcTrue;
}

813
814
815
816
817
818
819
820
821
FcChar32
FcPatternHash (const FcPattern *p)
{
    int		i;
    FcChar32	h = 0;

    for (i = 0; i < p->num; i++)
    {
	h = (((h << 1) | (h >> 31)) ^ 
822
	     FcStringHash ((FcChar8 *)FcObjectPtrU ((FcPatternEltU(p->elts)+i)->object)) ^
823
	     FcValueListHash ((FcPatternEltU(p->elts)+i)->values));
824
825
826
827
    }
    return h;
}

828
FcBool
829
FcPatternEqualSubset (const FcPattern *pai, const FcPattern *pbi, const FcObjectSet *os)
830
831
832
833
834
835
{
    FcPatternElt    *ea, *eb;
    int		    i;
    
    for (i = 0; i < os->nobject; i++)
    {
836
837
	ea = FcPatternFindElt (pai, os->objects[i]);
	eb = FcPatternFindElt (pbi, os->objects[i]);
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
	if (ea)
	{
	    if (!eb)
		return FcFalse;
	    if (!FcValueListEqual (ea->values, eb->values))
		return FcFalse;
	}
	else
	{
	    if (eb)
		return FcFalse;
	}
    }
    return FcTrue;
}

Keith Packard's avatar
Keith Packard committed
854
FcBool
855
856
857
858
859
FcPatternAddWithBinding  (FcPattern	    *p,
			  const char	    *object,
			  FcValue	    value,
			  FcValueBinding    binding,
			  FcBool	    append)
Keith Packard's avatar
Keith Packard committed
860
861
{
    FcPatternElt   *e;
862
    FcValueListPtr new, *prev;
863
864
    FcValueList    *newp;
    FcObjectPtr    objectPtr;
Keith Packard's avatar
Keith Packard committed
865

866
867
868
    if (p->ref == FC_REF_CONSTANT)
	goto bail0;

869
870
    newp = malloc (sizeof (FcValueList));
    if (!newp)
Keith Packard's avatar
Keith Packard committed
871
872
	goto bail0;

873
874
    memset(newp, 0, sizeof (FcValueList));
    new = FcValueListPtrCreateDynamic(newp);
Keith Packard's avatar
Keith Packard committed
875
876
877
878
879
880
    FcMemAlloc (FC_MEM_VALLIST, sizeof (FcValueList));
    /* dup string */
    value = FcValueSave (value);
    if (value.type == FcTypeVoid)
	goto bail1;

881
882
883
884
885
886
    /* quick and dirty hack to enable FcCompareFamily/FcCompareString
     * speedup: only allow strings to be added under the FC_FAMILY,
     * FC_FOUNDRY, FC_STYLE, FC_RASTERIZER keys.  
     * and charsets under FC_CHARSET key.
     * This is slightly semantically different from the old behaviour,
     * but fonts shouldn't be getting non-strings here anyway.
887
     * a better hack would use FcBaseObjectTypes to check all objects. */
888
889
890
891
892
893
894
895
896
    objectPtr = FcObjectToPtr(object);
    if ((objectPtr == FcObjectToPtr(FC_FAMILY)
         || objectPtr == FcObjectToPtr(FC_FOUNDRY)
         || objectPtr == FcObjectToPtr(FC_STYLE)
         || objectPtr == FcObjectToPtr(FC_RASTERIZER))
        && value.type != FcTypeString)
        goto bail1;
    if (objectPtr == FcObjectToPtr(FC_CHARSET)
        && value.type != FcTypeCharSet)
897
898
        goto bail1;

899
900
901
    FcValueListPtrU(new)->value = value;
    FcValueListPtrU(new)->binding = binding;
    FcValueListPtrU(new)->next = FcValueListPtrCreateDynamic(0);
Keith Packard's avatar
Keith Packard committed
902
    
903
    e = FcPatternInsertElt (p, object);
Keith Packard's avatar
Keith Packard committed
904
905
906
907
908
    if (!e)
	goto bail2;
    
    if (append)
    {
909
910
	for (prev = &e->values; FcValueListPtrU(*prev); prev = &FcValueListPtrU(*prev)->next)
	    ;
Keith Packard's avatar
Keith Packard committed
911
912
913
914
	*prev = new;
    }
    else
    {
915
	FcValueListPtrU(new)->next = e->values;
Keith Packard's avatar
Keith Packard committed
916
917
918
919
920
921
922
923
	e->values = new;
    }
    
    return FcTrue;

bail2:    
    switch (value.type) {
    case FcTypeString:
924
	FcStrFree ((FcChar8 *) value.u.s);
Keith Packard's avatar
Keith Packard committed
925
926
	break;
    case FcTypeMatrix:
927
	FcMatrixFree ((FcMatrix *) value.u.m);
Keith Packard's avatar
Keith Packard committed
928
929
	break;
    case FcTypeCharSet:
930
	FcCharSetDestroy ((FcCharSet *) value.u.c);
Keith Packard's avatar
Keith Packard committed
931
	break;
932
    case FcTypeLangSet:
933
	FcLangSetDestroy ((FcLangSet *) value.u.l);
934
	break;
Keith Packard's avatar
Keith Packard committed
935
936
937
938
939
    default:
	break;
    }
bail1:
    FcMemFree (FC_MEM_VALLIST, sizeof (FcValueList));
940
    free (FcValueListPtrU(new));
Keith Packard's avatar
Keith Packard committed
941
942
943
944
bail0:
    return FcFalse;
}

945
946
947
948
949
950
951
952
953
954
955
956
FcBool
FcPatternAdd (FcPattern *p, const char *object, FcValue value, FcBool append)
{
    return FcPatternAddWithBinding (p, object, value, FcValueBindingStrong, append);
}

FcBool
FcPatternAddWeak  (FcPattern *p, const char *object, FcValue value, FcBool append)
{
    return FcPatternAddWithBinding (p, object, value, FcValueBindingWeak, append);
}

Keith Packard's avatar
Keith Packard committed
957
958
959
960
961
FcBool
FcPatternDel (FcPattern *p, const char *object)
{
    FcPatternElt   *e;

962
    e = FcPatternFindElt (p, object);
Keith Packard's avatar
Keith Packard committed
963
964
965
966
967
968
969
    if (!e)
	return FcFalse;

    /* destroy value */
    FcValueListDestroy (e->values);
    
    /* shuffle existing ones down */
970
971
972
    memmove (e, e+1, 
	     (FcPatternEltU(p->elts) + p->num - (e + 1)) * 
	     sizeof (FcPatternElt));
Keith Packard's avatar
Keith Packard committed
973
    p->num--;
974
    (FcPatternEltU(p->elts)+p->num)->object = 0;
975
    (FcPatternEltU(p->elts)+p->num)->values = FcValueListPtrCreateDynamic(0);
Keith Packard's avatar
Keith Packard committed
976
977
978
    return FcTrue;
}

979
980
981
FcBool
FcPatternRemove (FcPattern *p, const char *object, int id)
{
982
983
    FcPatternElt    *e;
    FcValueListPtr  *prev, l;
984
985
986
987

    e = FcPatternFindElt (p, object);
    if (!e)
	return FcFalse;
988
989
990
    for (prev = &e->values; 
	 FcValueListPtrU(l = *prev); 
	 prev = &FcValueListPtrU(l)->next)
991
992
993
    {
	if (!id)
	{
994
995
	    *prev = FcValueListPtrU(l)->next;
	    FcValueListPtrU(l)->next = FcValueListPtrCreateDynamic(0);
996
	    FcValueListDestroy (l);
997
	    if (!FcValueListPtrU(e->values))
998
999
1000
1001
1002
1003
1004
1005
		FcPatternDel (p, object);
	    return FcTrue;
	}
	id--;
    }
    return FcFalse;
}

Keith Packard's avatar
Keith Packard committed
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
FcBool
FcPatternAddInteger (FcPattern *p, const char *object, int i)
{
    FcValue	v;

    v.type = FcTypeInteger;
    v.u.i = i;
    return FcPatternAdd (p, object, v, FcTrue);
}

FcBool
FcPatternAddDouble (FcPattern *p, const char *object, double d)
{
    FcValue	v;

    v.type = FcTypeDouble;
    v.u.d = d;
    return FcPatternAdd (p, object, v, FcTrue);
}


FcBool
1028
FcPatternAddString (FcPattern *p, const char *object, const FcChar8 *s)
Keith Packard's avatar
Keith Packard committed
1029
1030
1031
{
    FcValue	v;

1032
1033
1034
1035
1036
1037
1038
    if (!s)
    {
	v.type = FcTypeVoid;
	v.u.s = 0;
	return FcPatternAdd (p, object, v, FcTrue);
    }

Keith Packard's avatar
Keith Packard committed
1039
    v.type = FcTypeString;
1040
    v.u.s = FcStrStaticName(s);
Keith Packard's avatar
Keith Packard committed
1041
1042
1043
1044
1045
1046
1047
1048
1049
    return FcPatternAdd (p, object, v, FcTrue);
}

FcBool
FcPatternAddMatrix (FcPattern *p, const char *object, const FcMatrix *s)
{
    FcValue	v;

    v.type = FcTypeMatrix;
1050
    v.u.m = s;
Keith Packard's avatar
Keith Packard committed
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
    return FcPatternAdd (p, object, v, FcTrue);
}


FcBool
FcPatternAddBool (FcPattern *p, const char *object, FcBool b)
{
    FcValue	v;

    v.type = FcTypeBool;
    v.u.b = b;
    return FcPatternAdd (p, object, v, FcTrue);
}

FcBool
FcPatternAddCharSet (FcPattern *p, const char *object, const FcCharSet *c)
{
    FcValue	v;

    v.type = FcTypeCharSet;
1071
    v.u.c = (FcCharSet *)c;
Keith Packard's avatar
Keith Packard committed
1072
1073
1074
    return FcPatternAdd (p, object, v, FcTrue);
}

1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
FcBool
FcPatternAddFTFace (FcPattern *p, const char *object, const FT_Face f)
{
    FcValue	v;

    v.type = FcTypeFTFace;
    v.u.f = (void *) f;
    return FcPatternAdd (p, object, v, FcTrue);
}

1085
1086
1087
1088
1089
1090
FcBool
FcPatternAddLangSet (FcPattern *p, const char *object, const FcLangSet *ls)
{
    FcValue	v;

    v.type = FcTypeLangSet;
1091
    v.u.l = (FcLangSet *)ls;
1092
1093
1094
    return FcPatternAdd (p, object, v, FcTrue);
}

Keith Packard's avatar
Keith Packard committed
1095
FcResult
1096
FcPatternGet (const FcPattern *p, const char *object, int id, FcValue *v)
Keith Packard's avatar
Keith Packard committed
1097
1098
{
    FcPatternElt   *e;
1099
    FcValueListPtr l;
Keith Packard's avatar
Keith Packard committed
1100

1101
    e = FcPatternFindElt (p, object);
Keith Packard's avatar
Keith Packard committed
1102
1103
    if (!e)
	return FcResultNoMatch;
1104
    for (l = e->values; FcValueListPtrU(l); l = FcValueListPtrU(l)->next)
Keith Packard's avatar
Keith Packard committed
1105
1106
1107
    {
	if (!id)
	{
1108
	    *v = FcValueCanonicalize(&FcValueListPtrU(l)->value);
Keith Packard's avatar
Keith Packard committed
1109
1110
1111
1112
1113
1114
1115
1116
	    return FcResultMatch;
	}
	id--;
    }
    return FcResultNoId;
}

FcResult
1117
FcPatternGetInteger (const FcPattern *p, const char *object, int id, int *i)
Keith Packard's avatar
Keith Packard committed
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
{
    FcValue	v;
    FcResult	r;

    r = FcPatternGet (p, object, id, &v);
    if (r != FcResultMatch)
	return r;
    switch (v.type) {
    case FcTypeDouble:
	*i = (int) v.u.d;
	break;
    case FcTypeInteger:
	*i = v.u.i;
	break;
    default:
        return FcResultTypeMismatch;
    }
    return FcResultMatch;
}

FcResult
1139
FcPatternGetDouble (const FcPattern *p, const char *object, int id, double *d)
Keith Packard's avatar
Keith Packard committed
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
{
    FcValue	v;
    FcResult	r;

    r = FcPatternGet (p, object, id, &v);
    if (r != FcResultMatch)
	return r;
    switch (v.type) {
    case FcTypeDouble:
	*d = v.u.d;
	break;
    case FcTypeInteger:
	*d = (double) v.u.i;
	break;
    default:
        return FcResultTypeMismatch;
    }
    return FcResultMatch;
}

FcResult
1161
FcPatternGetString (const FcPattern *p, const char *object, int id, FcChar8 ** s)
Keith Packard's avatar
Keith Packard committed
1162
1163
1164
1165
1166
1167
1168
1169
1170
{
    FcValue	v;
    FcResult	r;

    r = FcPatternGet (p, object, id, &v);
    if (r != FcResultMatch)
	return r;
    if (v.type != FcTypeString)
        return FcResultTypeMismatch;
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206

    if (FcObjectToPtr(object) == FcObjectToPtr(FC_FILE))
    {
	const char *fn, *fpath;
	FcChar8 *fname;
	int size;

	fn = FcPatternFindFullFname(p);
	if (fn)
	{
	    *s = (FcChar8 *) fn;
	    return FcResultMatch;
	}

	if (!p->bank)
	{
	    *s = (FcChar8 *) v.u.s;
	    return FcResultMatch;
	}

	fpath = FcCacheFindBankDir (p->bank);
	size = strlen((char*)fpath) + 1 + strlen ((char *)v.u.s) + 1;
	fname = malloc (size);
	if (!fname)
	    return FcResultOutOfMemory;

	FcMemAlloc (FC_MEM_STRING, size);
	strcpy ((char *)fname, (char *)fpath);
	strcat ((char *)fname, "/");
	strcat ((char *)fname, (char *)v.u.s);
	
	FcPatternAddFullFname (p, (const char *)fname);
	*s = (FcChar8 *)fname;
	return FcResultMatch;
    }

1207
    *s = (FcChar8 *) v.u.s;
Keith Packard's avatar
Keith Packard committed
1208
1209
1210
1211
    return FcResultMatch;
}

FcResult
1212
FcPatternGetMatrix(const FcPattern *p, const char *object, int id, FcMatrix **m)
Keith Packard's avatar
Keith Packard committed
1213
1214
1215
1216
1217
1218
1219
1220
1221
{
    FcValue	v;
    FcResult	r;

    r = FcPatternGet (p, object, id, &v);
    if (r != FcResultMatch)
	return r;
    if (v.type != FcTypeMatrix)
        return FcResultTypeMismatch;
1222
    *m = (FcMatrix *)v.u.m;
Keith Packard's avatar
Keith Packard committed
1223
1224
1225
1226
1227
    return FcResultMatch;
}


FcResult