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 "libxfontint.h"
35#include    <X11/fonts/fontmisc.h>
36#include    <X11/fonts/fontstruct.h>
37
38/*
39 * Static sized hash table for looking up font name patterns
40 *
41 * LRU entries, reusing old entries
42 */
43
44#define NBUCKETS	16
45#define NENTRIES	64
46
47#define UNSET		(NENTRIES+1)
48
49typedef unsigned char	EntryPtr;
50
51typedef struct _FontPatternCacheEntry {
52    struct _FontPatternCacheEntry   *next, **prev;
53    short			    patlen;
54    const char			    *pattern;
55    int				    hash;
56    FontPtr			    pFont;	/* associated font */
57} FontPatternCacheEntryRec, *FontPatternCacheEntryPtr;
58
59typedef struct _xfont2_pattern_cache {
60    FontPatternCacheEntryPtr	buckets[NBUCKETS];
61    FontPatternCacheEntryRec	entries[NENTRIES];
62    FontPatternCacheEntryPtr	free;
63} xfont2_pattern_cache_rec;
64
65/* Empty cache (for rehash) */
66void
67xfont2_empty_font_pattern_cache(xfont2_pattern_cache_ptr cache)
68{
69    int	    i;
70
71    for (i = 0; i < NBUCKETS; i++)
72	cache->buckets[i] = 0;
73    for (i = 0; i < NENTRIES; i++)
74    {
75	cache->entries[i].next = &cache->entries[i+1];
76	cache->entries[i].prev = 0;
77	cache->entries[i].pFont = 0;
78	free ((void *) cache->entries[i].pattern);
79	cache->entries[i].pattern = 0;
80	cache->entries[i].patlen = 0;
81    }
82    cache->free = &cache->entries[0];
83    cache->entries[NENTRIES - 1].next = 0;
84}
85
86/* Create and initialize cache */
87xfont2_pattern_cache_ptr
88xfont2_make_font_pattern_cache(void)
89{
90    xfont2_pattern_cache_ptr	cache;
91    int			i;
92    cache = malloc (sizeof *cache);
93    if (!cache)
94	return 0;
95    for (i = 0; i < NENTRIES; i++) {
96	cache->entries[i].patlen = 0;
97	cache->entries[i].pattern = 0;
98	cache->entries[i].pFont = 0;
99    }
100    xfont2_empty_font_pattern_cache (cache);
101    return cache;
102}
103
104/* toss cache */
105void
106xfont2_free_font_pattern_cache(xfont2_pattern_cache_ptr cache)
107{
108    int	    i;
109
110    for (i = 0; i < NENTRIES; i++)
111	free ((void *) cache->entries[i].pattern);
112    free (cache);
113}
114
115/* compute id for string */
116static int
117Hash (const char *string, int len)
118{
119    int	hash;
120
121    hash = 0;
122    while (len--)
123	hash = (hash << 1) ^ *string++;
124    if (hash < 0)
125	hash = -hash;
126    return hash;
127}
128
129/* add entry */
130void
131xfont2_cache_font_pattern(xfont2_pattern_cache_ptr cache,
132			  const char * pattern,
133			  int patlen,
134			  FontPtr pFont)
135{
136    FontPatternCacheEntryPtr	e;
137    char			*newpat;
138    int				i;
139
140    newpat = malloc (patlen);
141    if (!newpat)
142	return;
143    if (cache->free)
144    {
145	e = cache->free;
146	cache->free = e->next;
147    }
148    else
149    {
150    	i = rand ();
151    	if (i < 0)
152	    i = -i;
153    	i %= NENTRIES;
154	e = &cache->entries[i];
155	if (e->next)
156	    e->next->prev = e->prev;
157	*e->prev = e->next;
158	free ((void *) e->pattern);
159    }
160    /* set pattern */
161    memcpy (newpat, pattern, patlen);
162    e->pattern = newpat;
163    e->patlen = patlen;
164    /* link to new hash chain */
165    e->hash = Hash (pattern, patlen);
166    i = e->hash % NBUCKETS;
167    e->next = cache->buckets[i];
168    if (e->next)
169	e->next->prev = &(e->next);
170    cache->buckets[i] = e;
171    e->prev = &(cache->buckets[i]);
172    e->pFont = pFont;
173}
174
175/* find matching entry */
176FontPtr
177xfont2_find_cached_font_pattern(xfont2_pattern_cache_ptr cache,
178				const char * pattern,
179				int patlen)
180{
181    int				hash;
182    int				i;
183    FontPatternCacheEntryPtr	e;
184
185    hash = Hash (pattern, patlen);
186    i = hash % NBUCKETS;
187    for (e = cache->buckets[i]; e; e = e->next)
188    {
189	if (e->patlen == patlen && e->hash == hash &&
190	    !memcmp (e->pattern, pattern, patlen))
191	{
192	    return e->pFont;
193	}
194    }
195    return 0;
196}
197
198void
199xfont2_remove_cached_font_pattern(xfont2_pattern_cache_ptr cache,
200				  FontPtr pFont)
201{
202    FontPatternCacheEntryPtr	e;
203    int				i;
204
205    for (i = 0; i < NENTRIES; i++)
206    {
207	if ((e = &cache->entries[i])->pFont == pFont)
208	{
209	    e->pFont = 0;
210	    if (e->next)
211		e->next->prev = e->prev;
212	    *e->prev = e->next;
213	    e->next = cache->free;
214	    cache->free = e;
215	    free ((void *) e->pattern);
216	    e->pattern = 0;
217	}
218    }
219}
220