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