1 /* cairo - a vector graphics library with display and print output
2 *
3 * Copyright © 2004 Red Hat, Inc.
4 * Copyright © 2005 Red Hat, Inc.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it either under the terms of the GNU Lesser General Public
8 * License version 2.1 as published by the Free Software Foundation
9 * (the "LGPL") or, at your option, under the terms of the Mozilla
10 * Public License Version 1.1 (the "MPL"). If you do not alter this
11 * notice, a recipient may use your version of this file under either
12 * the MPL or the LGPL.
13 *
14 * You should have received a copy of the LGPL along with this library
15 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17 * You should have received a copy of the MPL along with this library
18 * in the file COPYING-MPL-1.1
19 *
20 * The contents of this file are subject to the Mozilla Public License
21 * Version 1.1 (the "License"); you may not use this file except in
22 * compliance with the License. You may obtain a copy of the License at
23 * http://www.mozilla.org/MPL/
24 *
25 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27 * the specific language governing rights and limitations.
28 *
29 * The Original Code is the cairo graphics library.
30 *
31 * The Initial Developer of the Original Code is Red Hat, Inc.
32 *
33 * Contributor(s):
34 * Keith Packard <keithp@keithp.com>
35 * Graydon Hoare <graydon@redhat.com>
36 * Carl Worth <cworth@cworth.org>
37 */
38
39 #include "cairoint.h"
40 #include "cairo-error-private.h"
41
42 static void
43 _cairo_cache_shrink_to_accommodate (cairo_cache_t *cache,
44 unsigned long additional);
45
46 static cairo_bool_t
_cairo_cache_entry_is_non_zero(const void * entry)47 _cairo_cache_entry_is_non_zero (const void *entry)
48 {
49 return ((const cairo_cache_entry_t *) entry)->size;
50 }
51
52
53 /**
54 * _cairo_cache_init:
55 * @cache: the #cairo_cache_t to initialise
56 * @keys_equal: a function to return %TRUE if two keys are equal
57 * @entry_destroy: destroy notifier for cache entries
58 * @max_size: the maximum size for this cache
59 * Returns: the newly created #cairo_cache_t
60 *
61 * Creates a new cache using the keys_equal() function to determine
62 * the equality of entries.
63 *
64 * Data is provided to the cache in the form of user-derived version
65 * of #cairo_cache_entry_t. A cache entry must be able to hold hash
66 * code, a size, and the key/value pair being stored in the
67 * cache. Sometimes only the key will be necessary, (as in
68 * _cairo_cache_lookup()), and in these cases the value portion of the
69 * entry need not be initialized.
70 *
71 * The units for max_size can be chosen by the caller, but should be
72 * consistent with the units of the size field of cache entries. When
73 * adding an entry with _cairo_cache_insert() if the total size of
74 * entries in the cache would exceed max_size then entries will be
75 * removed at random until the new entry would fit or the cache is
76 * empty. Then the new entry is inserted.
77 *
78 * There are cases in which the automatic removal of entries is
79 * undesired. If the cache entries have reference counts, then it is a
80 * simple matter to use the reference counts to ensure that entries
81 * continue to live even after being ejected from the cache. However,
82 * in some cases the memory overhead of adding a reference count to
83 * the entry would be objectionable. In such cases, the
84 * _cairo_cache_freeze() and _cairo_cache_thaw() calls can be
85 * used to establish a window during which no automatic removal of
86 * entries will occur.
87 **/
88 cairo_status_t
_cairo_cache_init(cairo_cache_t * cache,cairo_cache_keys_equal_func_t keys_equal,cairo_cache_predicate_func_t predicate,cairo_destroy_func_t entry_destroy,unsigned long max_size)89 _cairo_cache_init (cairo_cache_t *cache,
90 cairo_cache_keys_equal_func_t keys_equal,
91 cairo_cache_predicate_func_t predicate,
92 cairo_destroy_func_t entry_destroy,
93 unsigned long max_size)
94 {
95 cache->hash_table = _cairo_hash_table_create (keys_equal);
96 if (unlikely (cache->hash_table == NULL))
97 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
98
99 if (predicate == NULL)
100 predicate = _cairo_cache_entry_is_non_zero;
101 cache->predicate = predicate;
102 cache->entry_destroy = entry_destroy;
103
104 cache->max_size = max_size;
105 cache->size = 0;
106
107 cache->freeze_count = 0;
108
109 return CAIRO_STATUS_SUCCESS;
110 }
111
112 static void
_cairo_cache_pluck(void * entry,void * closure)113 _cairo_cache_pluck (void *entry, void *closure)
114 {
115 _cairo_cache_remove (closure, entry);
116 }
117
118 /**
119 * _cairo_cache_fini:
120 * @cache: a cache to destroy
121 *
122 * Immediately destroys the given cache, freeing all resources
123 * associated with it. As part of this process, the entry_destroy()
124 * function, (as passed to _cairo_cache_init()), will be called for
125 * each entry in the cache.
126 **/
127 void
_cairo_cache_fini(cairo_cache_t * cache)128 _cairo_cache_fini (cairo_cache_t *cache)
129 {
130 _cairo_hash_table_foreach (cache->hash_table,
131 _cairo_cache_pluck,
132 cache);
133 assert (cache->size == 0);
134 _cairo_hash_table_destroy (cache->hash_table);
135 }
136
137 /**
138 * _cairo_cache_freeze:
139 * @cache: a cache with some precious entries in it (or about to be
140 * added)
141 *
142 * Disable the automatic ejection of entries from the cache. For as
143 * long as the cache is "frozen", calls to _cairo_cache_insert() will
144 * add new entries to the cache regardless of how large the cache
145 * grows. See _cairo_cache_thaw().
146 *
147 * Note: Multiple calls to _cairo_cache_freeze() will stack, in that
148 * the cache will remain "frozen" until a corresponding number of
149 * calls are made to _cairo_cache_thaw().
150 **/
151 void
_cairo_cache_freeze(cairo_cache_t * cache)152 _cairo_cache_freeze (cairo_cache_t *cache)
153 {
154 assert (cache->freeze_count >= 0);
155
156 cache->freeze_count++;
157 }
158
159 /**
160 * _cairo_cache_thaw:
161 * @cache: a cache, just after the entries in it have become less
162 * precious
163 *
164 * Cancels the effects of _cairo_cache_freeze().
165 *
166 * When a number of calls to _cairo_cache_thaw() is made corresponding
167 * to the number of calls to _cairo_cache_freeze() the cache will no
168 * longer be "frozen". If the cache had grown larger than max_size
169 * while frozen, entries will immediately be ejected (by random) from
170 * the cache until the cache is smaller than max_size. Also, the
171 * automatic ejection of entries on _cairo_cache_insert() will resume.
172 **/
173 void
_cairo_cache_thaw(cairo_cache_t * cache)174 _cairo_cache_thaw (cairo_cache_t *cache)
175 {
176 assert (cache->freeze_count > 0);
177
178 if (--cache->freeze_count == 0)
179 _cairo_cache_shrink_to_accommodate (cache, 0);
180 }
181
182 /**
183 * _cairo_cache_lookup:
184 * @cache: a cache
185 * @key: the key of interest
186 * @entry_return: pointer for return value
187 *
188 * Performs a lookup in @cache looking for an entry which has a key
189 * that matches @key, (as determined by the keys_equal() function
190 * passed to _cairo_cache_init()).
191 *
192 * Return value: %TRUE if there is an entry in the cache that matches
193 * @key, (which will now be in *entry_return). %FALSE otherwise, (in
194 * which case *entry_return will be %NULL).
195 **/
196 void *
_cairo_cache_lookup(cairo_cache_t * cache,cairo_cache_entry_t * key)197 _cairo_cache_lookup (cairo_cache_t *cache,
198 cairo_cache_entry_t *key)
199 {
200 return _cairo_hash_table_lookup (cache->hash_table,
201 (cairo_hash_entry_t *) key);
202 }
203
204 /**
205 * _cairo_cache_remove_random:
206 * @cache: a cache
207 *
208 * Remove a random entry from the cache.
209 *
210 * Return value: %TRUE if an entry was successfully removed.
211 * %FALSE if there are no entries that can be removed.
212 **/
213 static cairo_bool_t
_cairo_cache_remove_random(cairo_cache_t * cache)214 _cairo_cache_remove_random (cairo_cache_t *cache)
215 {
216 cairo_cache_entry_t *entry;
217
218 entry = _cairo_hash_table_random_entry (cache->hash_table,
219 cache->predicate);
220 if (unlikely (entry == NULL))
221 return FALSE;
222
223 _cairo_cache_remove (cache, entry);
224
225 return TRUE;
226 }
227
228 /**
229 * _cairo_cache_shrink_to_accommodate:
230 * @cache: a cache
231 * @additional: additional size requested in bytes
232 *
233 * If cache is not frozen, eject entries randomly until the size of
234 * the cache is at least @additional bytes less than
235 * cache->max_size. That is, make enough room to accommodate a new
236 * entry of size @additional.
237 **/
238 static void
_cairo_cache_shrink_to_accommodate(cairo_cache_t * cache,unsigned long additional)239 _cairo_cache_shrink_to_accommodate (cairo_cache_t *cache,
240 unsigned long additional)
241 {
242 while (cache->size + additional > cache->max_size) {
243 if (! _cairo_cache_remove_random (cache))
244 return;
245 }
246 }
247
248 /**
249 * _cairo_cache_insert:
250 * @cache: a cache
251 * @entry: an entry to be inserted
252 *
253 * Insert @entry into the cache. If an entry exists in the cache with
254 * a matching key, then the old entry will be removed first, (and the
255 * entry_destroy() callback will be called on it).
256 *
257 * Return value: %CAIRO_STATUS_SUCCESS if successful or
258 * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available.
259 **/
260 cairo_status_t
_cairo_cache_insert(cairo_cache_t * cache,cairo_cache_entry_t * entry)261 _cairo_cache_insert (cairo_cache_t *cache,
262 cairo_cache_entry_t *entry)
263 {
264 cairo_status_t status;
265
266 if (entry->size && ! cache->freeze_count)
267 _cairo_cache_shrink_to_accommodate (cache, entry->size);
268
269 status = _cairo_hash_table_insert (cache->hash_table,
270 (cairo_hash_entry_t *) entry);
271 if (unlikely (status))
272 return status;
273
274 cache->size += entry->size;
275
276 return CAIRO_STATUS_SUCCESS;
277 }
278
279 /**
280 * _cairo_cache_remove:
281 * @cache: a cache
282 * @entry: an entry that exists in the cache
283 *
284 * Remove an existing entry from the cache.
285 **/
286 void
_cairo_cache_remove(cairo_cache_t * cache,cairo_cache_entry_t * entry)287 _cairo_cache_remove (cairo_cache_t *cache,
288 cairo_cache_entry_t *entry)
289 {
290 cache->size -= entry->size;
291
292 _cairo_hash_table_remove (cache->hash_table,
293 (cairo_hash_entry_t *) entry);
294
295 if (cache->entry_destroy)
296 cache->entry_destroy (entry);
297 }
298
299 /**
300 * _cairo_cache_foreach:
301 * @cache: a cache
302 * @cache_callback: function to be called for each entry
303 * @closure: additional argument to be passed to @cache_callback
304 *
305 * Call @cache_callback for each entry in the cache, in a
306 * non-specified order.
307 **/
308 void
_cairo_cache_foreach(cairo_cache_t * cache,cairo_cache_callback_func_t cache_callback,void * closure)309 _cairo_cache_foreach (cairo_cache_t *cache,
310 cairo_cache_callback_func_t cache_callback,
311 void *closure)
312 {
313 _cairo_hash_table_foreach (cache->hash_table,
314 cache_callback,
315 closure);
316 }
317
318 unsigned long
_cairo_hash_string(const char * c)319 _cairo_hash_string (const char *c)
320 {
321 /* This is the djb2 hash. */
322 unsigned long hash = _CAIRO_HASH_INIT_VALUE;
323 while (c && *c)
324 hash = ((hash << 5) + hash) + *c++;
325 return hash;
326 }
327
328 unsigned long
_cairo_hash_bytes(unsigned long hash,const void * ptr,unsigned int length)329 _cairo_hash_bytes (unsigned long hash,
330 const void *ptr,
331 unsigned int length)
332 {
333 const uint8_t *bytes = ptr;
334 /* This is the djb2 hash. */
335 while (length--)
336 hash = ((hash << 5) + hash) + *bytes++;
337 return hash;
338 }
339