Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4349 | Serge | 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 |
||
35 | * Graydon Hoare |
||
36 | * Carl Worth |
||
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 | _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 |
||
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 |
||
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 |
||
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 |
||
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 |
||
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 * |
||
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 |
||
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 |
||
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 |
||
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 |
||
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 |
||
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 |
||
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 |
||
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 | }><>><> |