Line data Source code
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
47 0 : _cairo_cache_entry_is_non_zero (const void *entry)
48 : {
49 0 : 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
89 2 : _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 2 : cache->hash_table = _cairo_hash_table_create (keys_equal);
96 2 : if (unlikely (cache->hash_table == NULL))
97 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
98 :
99 2 : if (predicate == NULL)
100 0 : predicate = _cairo_cache_entry_is_non_zero;
101 2 : cache->predicate = predicate;
102 2 : cache->entry_destroy = entry_destroy;
103 :
104 2 : cache->max_size = max_size;
105 2 : cache->size = 0;
106 :
107 2 : cache->freeze_count = 0;
108 :
109 2 : return CAIRO_STATUS_SUCCESS;
110 : }
111 :
112 : static void
113 0 : _cairo_cache_pluck (void *entry, void *closure)
114 : {
115 0 : _cairo_cache_remove (closure, entry);
116 0 : }
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
128 0 : _cairo_cache_fini (cairo_cache_t *cache)
129 : {
130 0 : _cairo_hash_table_foreach (cache->hash_table,
131 : _cairo_cache_pluck,
132 : cache);
133 0 : assert (cache->size == 0);
134 0 : _cairo_hash_table_destroy (cache->hash_table);
135 0 : }
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
152 7 : _cairo_cache_freeze (cairo_cache_t *cache)
153 : {
154 7 : assert (cache->freeze_count >= 0);
155 :
156 7 : cache->freeze_count++;
157 7 : }
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
174 7 : _cairo_cache_thaw (cairo_cache_t *cache)
175 : {
176 7 : assert (cache->freeze_count > 0);
177 :
178 7 : if (--cache->freeze_count == 0)
179 7 : _cairo_cache_shrink_to_accommodate (cache, 0);
180 7 : }
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 *
197 0 : _cairo_cache_lookup (cairo_cache_t *cache,
198 : cairo_cache_entry_t *key)
199 : {
200 0 : 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
214 0 : _cairo_cache_remove_random (cairo_cache_t *cache)
215 : {
216 : cairo_cache_entry_t *entry;
217 :
218 0 : entry = _cairo_hash_table_random_entry (cache->hash_table,
219 : cache->predicate);
220 0 : if (unlikely (entry == NULL))
221 0 : return FALSE;
222 :
223 0 : _cairo_cache_remove (cache, entry);
224 :
225 0 : 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
239 7 : _cairo_cache_shrink_to_accommodate (cairo_cache_t *cache,
240 : unsigned long additional)
241 : {
242 14 : while (cache->size + additional > cache->max_size) {
243 0 : if (! _cairo_cache_remove_random (cache))
244 0 : 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
261 7 : _cairo_cache_insert (cairo_cache_t *cache,
262 : cairo_cache_entry_t *entry)
263 : {
264 : cairo_status_t status;
265 :
266 7 : if (entry->size && ! cache->freeze_count)
267 0 : _cairo_cache_shrink_to_accommodate (cache, entry->size);
268 :
269 7 : status = _cairo_hash_table_insert (cache->hash_table,
270 : (cairo_hash_entry_t *) entry);
271 7 : if (unlikely (status))
272 0 : return status;
273 :
274 7 : cache->size += entry->size;
275 :
276 7 : 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
287 0 : _cairo_cache_remove (cairo_cache_t *cache,
288 : cairo_cache_entry_t *entry)
289 : {
290 0 : cache->size -= entry->size;
291 :
292 0 : _cairo_hash_table_remove (cache->hash_table,
293 : (cairo_hash_entry_t *) entry);
294 :
295 0 : if (cache->entry_destroy)
296 0 : cache->entry_destroy (entry);
297 0 : }
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
309 0 : _cairo_cache_foreach (cairo_cache_t *cache,
310 : cairo_cache_callback_func_t cache_callback,
311 : void *closure)
312 : {
313 0 : _cairo_hash_table_foreach (cache->hash_table,
314 : cache_callback,
315 : closure);
316 0 : }
317 :
318 : unsigned long
319 14 : _cairo_hash_string (const char *c)
320 : {
321 : /* This is the djb2 hash. */
322 14 : unsigned long hash = _CAIRO_HASH_INIT_VALUE;
323 712 : while (c && *c)
324 684 : hash = ((hash << 5) + hash) + *c++;
325 14 : return hash;
326 : }
327 :
328 : unsigned long
329 0 : _cairo_hash_bytes (unsigned long hash,
330 : const void *ptr,
331 : unsigned int length)
332 : {
333 0 : const uint8_t *bytes = ptr;
334 : /* This is the djb2 hash. */
335 0 : while (length--)
336 0 : hash = ((hash << 5) + hash) + *bytes++;
337 0 : return hash;
338 : }
|
