Constness changes
[melted] / src / framework / mlt_cache.c
1 /**
2 * \file mlt_profile.c
3 * \brief least recently used cache
4 * \see mlt_profile_s
5 *
6 * Copyright (C) 2007-2009 Ushodaya Enterprises Limited
7 * \author Dan Dennedy <dan@dennedy.org>
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
13 *
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
18 *
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this library; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 */
23
24 #include "mlt_types.h"
25 #include "mlt_log.h"
26 #include "mlt_properties.h"
27 #include "mlt_cache.h"
28
29 #include <stdlib.h>
30 #include <pthread.h>
31
32 /** the maximum number of data objects to cache per line */
33 #define CACHE_SIZE (10)
34
35 /** \brief Cache item class
36 *
37 * A cache item is a structure holding information about a data object including
38 * a reference count that is used to control its lifetime. When you get a
39 * a cache item from the cache, you hold a reference that prevents the data
40 * from being released when the cache is full and something new is added.
41 * When you close the cache item, the reference count is decremented.
42 * The data object is destroyed when all cache items are closed and the cache
43 * releases its reference.
44 */
45
46 typedef struct mlt_cache_item_s
47 {
48 mlt_cache cache; /**< a reference to the cache to which this belongs */
49 void *object; /**< a parent object to the cache data that uniquely identifies this cached item */
50 void *data; /**< the opaque pointer to the cached data */
51 int size; /**< the size of the cached data */
52 int refcount; /**< a reference counter to control when destructor is called */
53 mlt_destructor destructor; /**< a function to release or destroy the cached data */
54 } mlt_cache_item_s;
55
56 /** \brief Cache class
57 *
58 * This is a utility class for implementing a Least Recently Used (LRU) cache
59 * of data blobs indexed by the address of some other object (e.g., a service).
60 * Instead of sorting and manipulating linked lists, it tries to be simple and
61 * elegant by copying pointers between two arrays of fixed size to shuffle the
62 * order of elements.
63 *
64 * This class is useful if you have a service that wants to cache something
65 * somewhat large, but will not scale if there are many instances of the service.
66 * Of course, the service will need to know how to recreate the cached element
67 * if it gets flushed from the cache,
68 *
69 * The most obvious examples are the pixbuf and qimage producers that cache their
70 * respective objects representing a picture read from a file. If the picture
71 * is no longer in the cache, it can simply re-read it from file. However, a
72 * picture is often repeated over many frames and makes sense to cache instead
73 * of continually reading, parsing, and decoding. On the other hand, you might
74 * want to load hundreds of pictures as individual producers, which would use
75 * a lot of memory if every picture is held in memory!
76 */
77
78 struct mlt_cache_s
79 {
80 int count; /**< the number of items currently in the cache */
81 void* *current; /**< pointer to the current array of pointers */
82 void* A[ CACHE_SIZE ];
83 void* B[ CACHE_SIZE ];
84 pthread_mutex_t mutex; /**< a mutex to prevent multi-threaded race conditions */
85 mlt_properties active; /**< a list of cache items some of which may no longer
86 be in \p current but to which there are
87 outstanding references */
88 mlt_properties garbage;/**< a list cache items pending release. A cache item
89 is copied to this list when it is updated but there
90 are outstanding references to the old data object. */
91 };
92
93 /** Get the data pointer from the cache item.
94 *
95 * \public \memberof mlt_cache_s
96 * \param item a cache item
97 * \param[out] size the number of bytes pointed at, if supplied when putting the data into the cache
98 * \return the data pointer
99 */
100
101 void *mlt_cache_item_data( mlt_cache_item item, int *size )
102 {
103 if ( size && item )
104 *size = item->size;
105 return item? item->data : NULL;
106 }
107
108 /** Close a cache item given its parent object pointer.
109 *
110 * \private \memberof mlt_cache_s
111 * \param cache a cache
112 * \param object the object to which the data object belongs
113 * \param data the data object, which might be in the garbage list (optional)
114 */
115
116 static void cache_object_close( mlt_cache cache, void *object, void* data )
117 {
118 char key[19];
119
120 // Fetch the cache item from the active list by its owner's address
121 sprintf( key, "%p", object );
122 pthread_mutex_lock( &cache->mutex );
123 mlt_cache_item item = mlt_properties_get_data( cache->active, key, NULL );
124 if ( item )
125 {
126 mlt_log( NULL, MLT_LOG_DEBUG, "%s: item %p object %p data %p refcount %d\n", __FUNCTION__,
127 item, item->object, item->data, item->refcount );
128 if ( item->destructor && --item->refcount <= 0 )
129 {
130 // Destroy the data object
131 item->destructor( item->data );
132 item->data = NULL;
133 item->destructor = NULL;
134 // Do not dispose of the cache item because it could likely be used
135 // again.
136 }
137 }
138
139 // Fetch the cache item from the garbage collection by its data address
140 if ( data )
141 {
142 sprintf( key, "%p", data );
143 item = mlt_properties_get_data( cache->garbage, key, NULL );
144 if ( item )
145 {
146 mlt_log( NULL, MLT_LOG_DEBUG, "collecting garbage item %p object %p data %p refcount %d\n",
147 item, item->object, item->data, item->refcount );
148 if ( item->destructor && --item->refcount <= 0 )
149 {
150 item->destructor( item->data );
151 item->data = NULL;
152 item->destructor = NULL;
153 // We do not need the garbage-collected cache item
154 mlt_properties_set_data( cache->garbage, key, NULL, 0, NULL, NULL );
155 }
156 }
157 }
158 pthread_mutex_unlock( &cache->mutex );
159 }
160
161 /** Close a cache item.
162 *
163 * Release a reference and call the destructor on the data object when all
164 * references are released.
165 *
166 * \public \memberof mlt_cache_item_s
167 * \param item a cache item
168 */
169
170 void mlt_cache_item_close( mlt_cache_item item )
171 {
172 if ( item )
173 cache_object_close( item->cache, item->object, item->data );
174 }
175
176 /** Create a new cache.
177 *
178 * \public \memberof mlt_cache_s
179 * \return a new cache or NULL if there was an error
180 */
181
182 mlt_cache mlt_cache_init()
183 {
184 mlt_cache result = calloc( 1, sizeof( struct mlt_cache_s ) );
185 if ( result )
186 {
187 result->current = result->A;
188 pthread_mutex_init( &result->mutex, NULL );
189 result->active = mlt_properties_new();
190 result->garbage = mlt_properties_new();
191 }
192 return result;
193 }
194
195 /** Destroy a cache.
196 *
197 * \public \memberof mlt_cache_s
198 * \param cache the cache to detroy
199 */
200
201 void mlt_cache_close( mlt_cache cache )
202 {
203 if ( cache )
204 {
205 while ( cache->count-- )
206 {
207 void *object = cache->current[ cache->count ];
208 mlt_log( NULL, MLT_LOG_DEBUG, "%s: %d = %p\n", __FUNCTION__, cache->count, object );
209 cache_object_close( cache, object, NULL );
210 }
211 mlt_properties_close( cache->active );
212 mlt_properties_close( cache->garbage );
213 pthread_mutex_destroy( &cache->mutex );
214 free( cache );
215 }
216 }
217
218 /** Remove cache entries for an object.
219 *
220 * \public \memberof mlt_cache_s
221 * \param cache a cache
222 * \param object the object that owns the cached data
223 */
224
225 void mlt_cache_purge( mlt_cache cache, void *object )
226 {
227 pthread_mutex_lock( &cache->mutex );
228 if ( cache && object )
229 {
230 int i, j;
231 void **alt = cache->current == cache->A ? cache->B : cache->A;
232
233 for ( i = 0, j = 0; i < cache->count; i++ )
234 {
235 void *o = cache->current[ i ];
236
237 if ( o == object )
238 {
239 pthread_mutex_unlock( &cache->mutex );
240 cache_object_close( cache, o, NULL );
241 pthread_mutex_lock( &cache->mutex );
242 }
243 else
244 {
245 alt[ j++ ] = o;
246 }
247 }
248 cache->count = j;
249 cache->current = alt;
250
251 // Remove the object's data from the active list regardless of refcount
252 char key[19];
253 sprintf( key, "%p", object );
254 mlt_cache_item item = mlt_properties_get_data( cache->active, key, NULL );
255 if ( item && item->destructor )
256 {
257 item->destructor( item->data );
258 item->data = NULL;
259 item->destructor = NULL;
260 mlt_properties_set_data( cache->active, key, NULL, 0, NULL, NULL );
261 }
262
263 // Remove the object's items from the garbage collection regardless of refcount
264 i = mlt_properties_count( cache->garbage );
265 while ( i-- )
266 {
267 item = mlt_properties_get_data_at( cache->garbage, i, NULL );
268 if ( object == item->object && item->destructor )
269 {
270 sprintf( key, "%p", item->data );
271 item->destructor( item->data );
272 item->data = NULL;
273 item->destructor = NULL;
274 mlt_properties_set_data( cache->garbage, key, NULL, 0, NULL, NULL );
275 }
276 }
277 }
278 pthread_mutex_unlock( &cache->mutex );
279 }
280
281 /** Shuffle the cache entries between the two arrays and return the cache entry for an object.
282 *
283 * \private \memberof mlt_cache_s
284 * \param cache a cache object
285 * \param object the object that owns the cached data
286 * \return a cache entry if there was a hit or NULL for a miss
287 */
288
289 static void** shuffle_get_hit( mlt_cache cache, void *object )
290 {
291 int i = cache->count;
292 int j = cache->count - 1;
293 void **hit = NULL;
294 void **alt = cache->current == cache->A ? cache->B : cache->A;
295
296 if ( cache->count > 0 && cache->count < CACHE_SIZE )
297 {
298 // first determine if we have a hit
299 while ( i-- && !hit )
300 {
301 void **o = &cache->current[ i ];
302 if ( *o == object )
303 hit = o;
304 }
305 // if there was no hit, we will not be shuffling out an entry
306 // and are still filling the cache
307 if ( !hit )
308 ++j;
309 // reset these
310 i = cache->count;
311 hit = NULL;
312 }
313
314 // shuffle the existing entries to the alternate array
315 while ( i-- )
316 {
317 void **o = &cache->current[ i ];
318
319 if ( !hit && *o == object )
320 {
321 hit = o;
322 }
323 else if ( j > 0 )
324 {
325 alt[ --j ] = *o;
326 // mlt_log( NULL, MLT_LOG_DEBUG, "%s: shuffle %d = %p\n", __FUNCTION__, j, alt[j] );
327 }
328 }
329 return hit;
330 }
331
332 /** Put a chunk of data in the cache.
333 *
334 * \public \memberof mlt_cache_s
335 * \param cache a cache object
336 * \param object the object to which this data belongs
337 * \param data an opaque pointer to the data to cache
338 * \param size the size of the data in bytes
339 * \param destructor a pointer to a function that can destroy or release a reference to the data.
340 */
341
342 void mlt_cache_put( mlt_cache cache, void *object, void* data, int size, mlt_destructor destructor )
343 {
344 pthread_mutex_lock( &cache->mutex );
345 void **hit = shuffle_get_hit( cache, object );
346 void **alt = cache->current == cache->A ? cache->B : cache->A;
347
348 // add the object to the cache
349 if ( hit )
350 {
351 // release the old data
352 pthread_mutex_unlock( &cache->mutex );
353 cache_object_close( cache, *hit, NULL );
354 pthread_mutex_lock( &cache->mutex );
355 // the MRU end gets the updated data
356 hit = &alt[ cache->count - 1 ];
357 }
358 else if ( cache->count < CACHE_SIZE )
359 {
360 // more room in cache, add it to MRU end
361 hit = &alt[ cache->count++ ];
362 }
363 else
364 {
365 // release the entry at the LRU end
366 pthread_mutex_unlock( &cache->mutex );
367 cache_object_close( cache, cache->current[0], NULL );
368 pthread_mutex_lock( &cache->mutex );
369
370 // The MRU end gets the new item
371 hit = &alt[ cache->count - 1 ];
372 }
373 *hit = object;
374 mlt_log( NULL, MLT_LOG_DEBUG, "%s: put %d = %p, %p\n", __FUNCTION__, cache->count - 1, object, data );
375
376 // Fetch the cache item
377 char key[19];
378 sprintf( key, "%p", object );
379 mlt_cache_item item = mlt_properties_get_data( cache->active, key, NULL );
380 if ( !item )
381 {
382 item = calloc( 1, sizeof( mlt_cache_item_s ) );
383 if ( item )
384 mlt_properties_set_data( cache->active, key, item, 0, free, NULL );
385 }
386 if ( item )
387 {
388 // If updating the cache item but not all references are released
389 // copy the item to the garbage collection.
390 if ( item->refcount > 0 && item->data )
391 {
392 mlt_cache_item orphan = calloc( 1, sizeof( mlt_cache_item_s ) );
393 if ( orphan )
394 {
395 mlt_log( NULL, MLT_LOG_DEBUG, "adding to garbage collection object %p data %p\n", item->object, item->data );
396 *orphan = *item;
397 sprintf( key, "%p", orphan->data );
398 // We store in the garbage collection by data address, not the owner's!
399 mlt_properties_set_data( cache->garbage, key, orphan, 0, free, NULL );
400 }
401 }
402
403 // Set/update the cache item
404 item->cache = cache;
405 item->object = object;
406 item->data = data;
407 item->size = size;
408 item->destructor = destructor;
409 item->refcount = 1;
410 }
411
412 // swap the current array
413 cache->current = alt;
414 pthread_mutex_unlock( &cache->mutex );
415 }
416
417 /** Get a chunk of data from the cache.
418 *
419 * \public \memberof mlt_cache_s
420 * \param cache a cache object
421 * \param object the object for which you are trying to locate the data
422 * \return a mlt_cache_item if found or NULL if not found or has been flushed from the cache
423 */
424
425 mlt_cache_item mlt_cache_get( mlt_cache cache, void *object )
426 {
427 mlt_cache_item result = NULL;
428 pthread_mutex_lock( &cache->mutex );
429 void **hit = shuffle_get_hit( cache, object );
430 void **alt = cache->current == cache->A ? cache->B : cache->A;
431
432 if ( hit )
433 {
434 // copy the hit to the MRU end
435 alt[ cache->count - 1 ] = *hit;
436 hit = &alt[ cache->count - 1 ];
437
438 char key[19];
439 sprintf( key, "%p", *hit );
440 result = mlt_properties_get_data( cache->active, key, NULL );
441 if ( result && result->data )
442 result->refcount++;
443 mlt_log( NULL, MLT_LOG_DEBUG, "%s: get %d = %p, %p\n", __FUNCTION__, cache->count - 1, *hit, result->data );
444
445 // swap the current array
446 cache->current = alt;
447 }
448 pthread_mutex_unlock( &cache->mutex );
449
450 return result;
451 }