patcache.c revision 23a0898a 
1/* $Xorg: patcache.c,v 1.4 2001/02/09 02:04:04 xorgcvs Exp $ */
2
3/*
4
5Copyright 1991, 1998  The Open Group
6
7Permission to use, copy, modify, distribute, and sell this software and its
8documentation for any purpose is hereby granted without fee, provided that
9the above copyright notice appear in all copies and that both that
10copyright notice and this permission notice appear in supporting
11documentation.
12
13The above copyright notice and this permission notice shall be included in
14all copies or substantial portions of the Software.
15
16THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
19OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
20AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22
23Except as contained in this notice, the name of The Open Group shall not be
24used in advertising or otherwise to promote the sale, use or other dealings
25in this Software without prior written authorization from The Open Group.
26
27*/
28/* $XFree86: xc/lib/font/util/patcache.c,v 3.4 2001/01/17 19:43:33 dawes Exp $ */
29
30/*
31 * Author:  Keith Packard, MIT X Consortium
32 */
33
34#ifdef HAVE_CONFIG_H
35#include <config.h>
36#endif
37#include    <X11/fonts/fontmisc.h>
38#include    <X11/fonts/fontstruct.h>
39
40/*
41 * Static sized hash table for looking up font name patterns
42 *
43 * LRU entries, reusing old entries
44 */
45
46#define NBUCKETS	16
47#define NENTRIES	64
48
49#define UNSET		(NENTRIES+1)
50
51typedef unsigned char	EntryPtr;
52
53typedef struct _FontPatternCacheEntry {
54    struct _FontPatternCacheEntry   *next, **prev;
55    short			    patlen;
56    char			    *pattern;
57    int				    hash;
58    FontPtr			    pFont;	/* associated font */
59} FontPatternCacheEntryRec, *FontPatternCacheEntryPtr;
60
61typedef struct _FontPatternCache {
62    FontPatternCacheEntryPtr	buckets[NBUCKETS];
63    FontPatternCacheEntryRec	entries[NENTRIES];
64    FontPatternCacheEntryPtr	free;
65} FontPatternCacheRec;
66
67/* Empty cache (for rehash) */
68void
69EmptyFontPatternCache (FontPatternCachePtr cache)
70{
71    int	    i;
72
73    for (i = 0; i < NBUCKETS; i++)
74	cache->buckets[i] = 0;
75    for (i = 0; i < NENTRIES; i++)
76    {
77	cache->entries[i].next = &cache->entries[i+1];
78	cache->entries[i].prev = 0;
79	cache->entries[i].pFont = 0;
80	xfree (cache->entries[i].pattern);
81	cache->entries[i].pattern = 0;
82	cache->entries[i].patlen = 0;
83    }
84    cache->free = &cache->entries[0];
85    cache->entries[NENTRIES - 1].next = 0;
86}
87
88/* Create and initialize cache */
89FontPatternCachePtr
90MakeFontPatternCache (void)
91{
92    FontPatternCachePtr	cache;
93    int			i;
94    cache = (FontPatternCachePtr) xalloc (sizeof *cache);
95    if (!cache)
96	return 0;
97    for (i = 0; i < NENTRIES; i++) {
98	cache->entries[i].patlen = 0;
99	cache->entries[i].pattern = 0;
100	cache->entries[i].pFont = 0;
101    }
102    EmptyFontPatternCache (cache);
103    return cache;
104}
105
106/* toss cache */
107void
108FreeFontPatternCache (FontPatternCachePtr cache)
109{
110    int	    i;
111
112    for (i = 0; i < NENTRIES; i++)
113	xfree (cache->entries[i].pattern);
114    xfree (cache);
115}
116
117/* compute id for string */
118static int
119Hash (const char *string, int len)
120{
121    int	hash;
122
123    hash = 0;
124    while (len--)
125	hash = (hash << 1) ^ *string++;
126    if (hash < 0)
127	hash = -hash;
128    return hash;
129}
130
131/* add entry */
132void
133CacheFontPattern (FontPatternCachePtr cache,
134		  char *pattern,
135		  int patlen,
136		  FontPtr pFont)
137{
138    FontPatternCacheEntryPtr	e;
139    char			*newpat;
140    int				i;
141
142    newpat = (char *) xalloc (patlen);
143    if (!newpat)
144	return;
145    if (cache->free)
146    {
147	e = cache->free;
148	cache->free = e->next;
149    }
150    else
151    {
152    	i = rand ();
153    	if (i < 0)
154	    i = -i;
155    	i %= NENTRIES;
156	e = &cache->entries[i];
157	if (e->next)
158	    e->next->prev = e->prev;
159	*e->prev = e->next;
160	xfree (e->pattern);
161    }
162    /* set pattern */
163    memcpy (newpat, pattern, patlen);
164    e->pattern = newpat;
165    e->patlen = patlen;
166    /* link to new hash chain */
167    e->hash = Hash (pattern, patlen);
168    i = e->hash % NBUCKETS;
169    e->next = cache->buckets[i];
170    if (e->next)
171	e->next->prev = &(e->next);
172    cache->buckets[i] = e;
173    e->prev = &(cache->buckets[i]);
174    e->pFont = pFont;
175}
176
177/* find matching entry */
178FontPtr
179FindCachedFontPattern (FontPatternCachePtr cache,
180		       char *pattern,
181		       int patlen)
182{
183    int				hash;
184    int				i;
185    FontPatternCacheEntryPtr	e;
186
187    hash = Hash (pattern, patlen);
188    i = hash % NBUCKETS;
189    for (e = cache->buckets[i]; e; e = e->next)
190    {
191	if (e->patlen == patlen && e->hash == hash &&
192	    !memcmp (e->pattern, pattern, patlen))
193	{
194	    return e->pFont;
195	}
196    }
197    return 0;
198}
199
200void
201RemoveCachedFontPattern (FontPatternCachePtr cache,
202			 FontPtr pFont)
203{
204    FontPatternCacheEntryPtr	e;
205    int				i;
206
207    for (i = 0; i < NENTRIES; i++)
208    {
209	if ((e = &cache->entries[i])->pFont == pFont)
210	{
211	    e->pFont = 0;
212	    if (e->next)
213		e->next->prev = e->prev;
214	    *e->prev = e->next;
215	    e->next = cache->free;
216	    cache->free = e;
217	    xfree (e->pattern);
218	    e->pattern = 0;
219	}
220    }
221}
222