1 /*
2
3 Copyright 1991, 1998 The Open Group
4
5 Permission to use, copy, modify, distribute, and sell this software and its
6 documentation for any purpose is hereby granted without fee, provided that
7 the above copyright notice appear in all copies and that both that
8 copyright notice and this permission notice appear in supporting
9 documentation.
10
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21 Except as contained in this notice, the name of The Open Group shall not be
22 used in advertising or otherwise to promote the sale, use or other dealings
23 in 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
49 typedef unsigned char EntryPtr;
50
51 typedef 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
59 typedef 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) */
66 void
xfont2_empty_font_pattern_cache(xfont2_pattern_cache_ptr cache)67 xfont2_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 */
87 xfont2_pattern_cache_ptr
xfont2_make_font_pattern_cache(void)88 xfont2_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 */
105 void
xfont2_free_font_pattern_cache(xfont2_pattern_cache_ptr cache)106 xfont2_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 */
116 static int
Hash(const char * string,int len)117 Hash (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 */
130 void
xfont2_cache_font_pattern(xfont2_pattern_cache_ptr cache,const char * pattern,int patlen,FontPtr pFont)131 xfont2_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 */
176 FontPtr
xfont2_find_cached_font_pattern(xfont2_pattern_cache_ptr cache,const char * pattern,int patlen)177 xfont2_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
198 void
xfont2_remove_cached_font_pattern(xfont2_pattern_cache_ptr cache,FontPtr pFont)199 xfont2_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