3 * \brief least recently used cache
6 * Copyright (C) 2007-2012 Ushodaya Enterprises Limited
7 * \author Dan Dennedy <dan@dennedy.org>
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.
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.
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
24 #include "mlt_types.h"
26 #include "mlt_properties.h"
27 #include "mlt_cache.h"
28 #include "mlt_frame.h"
33 /** the maximum number of data objects to cache per line */
34 #define MAX_CACHE_SIZE (200)
36 /** the default number of data objects to cache per line */
37 #define DEFAULT_CACHE_SIZE (4)
39 /** \brief Cache item class
41 * A cache item is a structure holding information about a data object including
42 * a reference count that is used to control its lifetime. When you get a
43 * a cache item from the cache, you hold a reference that prevents the data
44 * from being released when the cache is full and something new is added.
45 * When you close the cache item, the reference count is decremented.
46 * The data object is destroyed when all cache items are closed and the cache
47 * releases its reference.
50 typedef struct mlt_cache_item_s
52 mlt_cache cache; /**< a reference to the cache to which this belongs */
53 void *object; /**< a parent object to the cache data that uniquely identifies this cached item */
54 void *data; /**< the opaque pointer to the cached data */
55 int size; /**< the size of the cached data */
56 int refcount; /**< a reference counter to control when destructor is called */
57 mlt_destructor destructor; /**< a function to release or destroy the cached data */
60 /** \brief Cache class
62 * This is a utility class for implementing a Least Recently Used (LRU) cache
63 * of data blobs indexed by the address of some other object (e.g., a service).
64 * Instead of sorting and manipulating linked lists, it tries to be simple and
65 * elegant by copying pointers between two arrays of fixed size to shuffle the
68 * This class is useful if you have a service that wants to cache something
69 * somewhat large, but will not scale if there are many instances of the service.
70 * Of course, the service will need to know how to recreate the cached element
71 * if it gets flushed from the cache,
73 * The most obvious examples are the pixbuf and qimage producers that cache their
74 * respective objects representing a picture read from a file. If the picture
75 * is no longer in the cache, it can simply re-read it from file. However, a
76 * picture is often repeated over many frames and makes sense to cache instead
77 * of continually reading, parsing, and decoding. On the other hand, you might
78 * want to load hundreds of pictures as individual producers, which would use
79 * a lot of memory if every picture is held in memory!
84 int count; /**< the number of items currently in the cache */
85 int size; /**< the maximum number of items permitted in the cache <= \p MAX_CACHE_SIZE */
86 int is_frames; /**< indicates if this cache is used to cache frames */
87 void* *current; /**< pointer to the current array of pointers */
88 void* A[ MAX_CACHE_SIZE ];
89 void* B[ MAX_CACHE_SIZE ];
90 pthread_mutex_t mutex; /**< a mutex to prevent multi-threaded race conditions */
91 mlt_properties active; /**< a list of cache items some of which may no longer
92 be in \p current but to which there are
93 outstanding references */
94 mlt_properties garbage;/**< a list cache items pending release. A cache item
95 is copied to this list when it is updated but there
96 are outstanding references to the old data object. */
99 /** Get the data pointer from the cache item.
101 * \public \memberof mlt_cache_s
102 * \param item a cache item
103 * \param[out] size the number of bytes pointed at, if supplied when putting the data into the cache
104 * \return the data pointer
107 void *mlt_cache_item_data( mlt_cache_item item, int *size )
111 return item? item->data : NULL;
114 /** Close a cache item given its parent object pointer.
116 * \private \memberof mlt_cache_s
117 * \param cache a cache
118 * \param object the object to which the data object belongs
119 * \param data the data object, which might be in the garbage list (optional)
122 static void cache_object_close( mlt_cache cache, void *object, void* data )
126 if ( cache->is_frames )
128 // Frame caches are easy - just close the object as mlt_frame.
129 mlt_frame_close( object );
133 // Fetch the cache item from the active list by its owner's address
134 sprintf( key, "%p", object );
135 mlt_cache_item item = mlt_properties_get_data( cache->active, key, NULL );
138 mlt_log( NULL, MLT_LOG_DEBUG, "%s: item %p object %p data %p refcount %d\n", __FUNCTION__,
139 item, item->object, item->data, item->refcount );
140 if ( item->destructor && --item->refcount <= 0 )
142 // Destroy the data object
143 item->destructor( item->data );
145 item->destructor = NULL;
146 // Do not dispose of the cache item because it could likely be used
151 // Fetch the cache item from the garbage collection by its data address
154 sprintf( key, "%p", data );
155 item = mlt_properties_get_data( cache->garbage, key, NULL );
158 mlt_log( NULL, MLT_LOG_DEBUG, "collecting garbage item %p object %p data %p refcount %d\n",
159 item, item->object, item->data, item->refcount );
160 if ( item->destructor && --item->refcount <= 0 )
162 item->destructor( item->data );
164 item->destructor = NULL;
165 // We do not need the garbage-collected cache item
166 mlt_properties_set_data( cache->garbage, key, NULL, 0, NULL, NULL );
172 /** Close a cache item.
174 * Release a reference and call the destructor on the data object when all
175 * references are released.
177 * \public \memberof mlt_cache_item_s
178 * \param item a cache item
181 void mlt_cache_item_close( mlt_cache_item item )
185 pthread_mutex_lock( &item->cache->mutex );
186 cache_object_close( item->cache, item->object, item->data );
187 pthread_mutex_unlock( &item->cache->mutex );
191 /** Create a new cache.
193 * The default size is \p DEFAULT_CACHE_SIZE.
194 * \public \memberof mlt_cache_s
195 * \return a new cache or NULL if there was an error
198 mlt_cache mlt_cache_init()
200 mlt_cache result = calloc( 1, sizeof( struct mlt_cache_s ) );
203 result->size = DEFAULT_CACHE_SIZE;
204 result->current = result->A;
205 pthread_mutex_init( &result->mutex, NULL );
206 result->active = mlt_properties_new();
207 result->garbage = mlt_properties_new();
212 /** Set the numer of items to cache.
214 * This must be called before using the cache. The size can not be more
215 * than \p MAX_CACHE_SIZE.
216 * \public \memberof mlt_cache_s
217 * \param cache the cache to adjust
218 * \param size the new size of the cache
221 void mlt_cache_set_size( mlt_cache cache, int size )
223 if ( size <= MAX_CACHE_SIZE )
227 /** Get the numer of possible cache items.
229 * \public \memberof mlt_cache_s
230 * \param cache the cache to check
231 * \return the current maximum size of the cache
234 int mlt_cache_get_size( mlt_cache cache )
241 * \public \memberof mlt_cache_s
242 * \param cache the cache to destroy
245 void mlt_cache_close( mlt_cache cache )
249 while ( cache->count-- )
251 void *object = cache->current[ cache->count ];
252 mlt_log( NULL, MLT_LOG_DEBUG, "%s: %d = %p\n", __FUNCTION__, cache->count, object );
253 cache_object_close( cache, object, NULL );
255 mlt_properties_close( cache->active );
256 mlt_properties_close( cache->garbage );
257 pthread_mutex_destroy( &cache->mutex );
262 /** Remove cache entries for an object.
264 * \public \memberof mlt_cache_s
265 * \param cache a cache
266 * \param object the object that owns the cached data
269 void mlt_cache_purge( mlt_cache cache, void *object )
272 pthread_mutex_lock( &cache->mutex );
273 if ( cache && object )
276 void **alt = cache->current == cache->A ? cache->B : cache->A;
278 for ( i = 0, j = 0; i < cache->count; i++ )
280 void *o = cache->current[ i ];
284 cache_object_close( cache, o, NULL );
292 cache->current = alt;
294 pthread_mutex_unlock( &cache->mutex );
297 /** Shuffle the cache entries between the two arrays and return the cache entry for an object.
299 * \private \memberof mlt_cache_s
300 * \param cache a cache object
301 * \param object the object that owns the cached data
302 * \return a cache entry if there was a hit or NULL for a miss
305 static void** shuffle_get_hit( mlt_cache cache, void *object )
307 int i = cache->count;
308 int j = cache->count - 1;
310 void **alt = cache->current == cache->A ? cache->B : cache->A;
312 if ( cache->count > 0 && cache->count < cache->size )
314 // first determine if we have a hit
315 while ( i-- && !hit )
317 void **o = &cache->current[ i ];
321 // if there was no hit, we will not be shuffling out an entry
322 // and are still filling the cache
330 // shuffle the existing entries to the alternate array
333 void **o = &cache->current[ i ];
335 if ( !hit && *o == object )
342 // mlt_log( NULL, MLT_LOG_DEBUG, "%s: shuffle %d = %p\n", __FUNCTION__, j, alt[j] );
348 /** Put a chunk of data in the cache.
350 * This function and mlt_cache_get() are not scalable with a large volume
351 * of unique \p object paramter values. Therefore, it does not make sense
352 * to use it for a frame/image cache using the frame position for \p object.
353 * Instead, use mlt_cache_put_frame() for that.
355 * \public \memberof mlt_cache_s
356 * \param cache a cache object
357 * \param object the object to which this data belongs
358 * \param data an opaque pointer to the data to cache
359 * \param size the size of the data in bytes
360 * \param destructor a pointer to a function that can destroy or release a reference to the data.
363 void mlt_cache_put( mlt_cache cache, void *object, void* data, int size, mlt_destructor destructor )
365 pthread_mutex_lock( &cache->mutex );
366 void **hit = shuffle_get_hit( cache, object );
367 void **alt = cache->current == cache->A ? cache->B : cache->A;
369 // add the object to the cache
372 // release the old data
373 cache_object_close( cache, *hit, NULL );
374 // the MRU end gets the updated data
375 hit = &alt[ cache->count - 1 ];
377 else if ( cache->count < cache->size )
379 // more room in cache, add it to MRU end
380 hit = &alt[ cache->count++ ];
384 // release the entry at the LRU end
385 cache_object_close( cache, cache->current[0], NULL );
387 // The MRU end gets the new item
388 hit = &alt[ cache->count - 1 ];
391 mlt_log( NULL, MLT_LOG_DEBUG, "%s: put %d = %p, %p\n", __FUNCTION__, cache->count - 1, object, data );
393 // Fetch the cache item
395 sprintf( key, "%p", object );
396 mlt_cache_item item = mlt_properties_get_data( cache->active, key, NULL );
399 item = calloc( 1, sizeof( mlt_cache_item_s ) );
401 mlt_properties_set_data( cache->active, key, item, 0, free, NULL );
405 // If updating the cache item but not all references are released
406 // copy the item to the garbage collection.
407 if ( item->refcount > 0 && item->data )
409 mlt_cache_item orphan = calloc( 1, sizeof( mlt_cache_item_s ) );
412 mlt_log( NULL, MLT_LOG_DEBUG, "adding to garbage collection object %p data %p\n", item->object, item->data );
414 sprintf( key, "%p", orphan->data );
415 // We store in the garbage collection by data address, not the owner's!
416 mlt_properties_set_data( cache->garbage, key, orphan, 0, free, NULL );
420 // Set/update the cache item
422 item->object = object;
425 item->destructor = destructor;
429 // swap the current array
430 cache->current = alt;
431 pthread_mutex_unlock( &cache->mutex );
434 /** Get a chunk of data from the cache.
436 * \public \memberof mlt_cache_s
437 * \param cache a cache object
438 * \param object the object for which you are trying to locate the data
439 * \return a mlt_cache_item if found or NULL if not found or has been flushed from the cache
442 mlt_cache_item mlt_cache_get( mlt_cache cache, void *object )
444 mlt_cache_item result = NULL;
445 pthread_mutex_lock( &cache->mutex );
446 void **hit = shuffle_get_hit( cache, object );
447 void **alt = cache->current == cache->A ? cache->B : cache->A;
451 // copy the hit to the MRU end
452 alt[ cache->count - 1 ] = *hit;
453 hit = &alt[ cache->count - 1 ];
456 sprintf( key, "%p", *hit );
457 result = mlt_properties_get_data( cache->active, key, NULL );
458 if ( result && result->data )
461 mlt_log( NULL, MLT_LOG_DEBUG, "%s: get %d = %p, %p\n", __FUNCTION__, cache->count - 1, *hit, result->data );
464 // swap the current array
465 cache->current = alt;
467 pthread_mutex_unlock( &cache->mutex );
472 /** Shuffle the cache entries between the two arrays and return the frame for a position.
474 * \private \memberof mlt_cache_s
475 * \param cache a cache object
476 * \param position the position of the frame that you want
477 * \return a frame if there was a hit or NULL for a miss
480 static mlt_frame* shuffle_get_frame( mlt_cache cache, mlt_position position )
482 int i = cache->count;
483 int j = cache->count - 1;
484 mlt_frame *hit = NULL;
485 mlt_frame *alt = (mlt_frame*) ( cache->current == cache->A ? cache->B : cache->A );
487 if ( cache->count > 0 && cache->count < cache->size )
489 // first determine if we have a hit
490 while ( i-- && !hit )
492 mlt_frame *o = (mlt_frame*) &cache->current[ i ];
493 if ( mlt_frame_get_position( *o ) == position )
496 // if there was no hit, we will not be shuffling out an entry
497 // and are still filling the cache
505 // shuffle the existing entries to the alternate array
508 mlt_frame *o = (mlt_frame*) &cache->current[ i ];
510 if ( !hit && mlt_frame_get_position( *o ) == position )
517 // mlt_log( NULL, MLT_LOG_DEBUG, "%s: shuffle %d = %p\n", __FUNCTION__, j, alt[j] );
523 /** Put a frame in the cache.
525 * Unlike mlt_cache_put() this version is more suitable for caching frames
526 * and their data - like images. However, this version does not use reference
527 * counting and garbage collection. Rather, frames are cloned with deep copy
528 * to avoid those things.
530 * \public \memberof mlt_cache_s
531 * \param cache a cache object
532 * \param frame the frame to cache
533 * \see mlt_frame_get_frame
536 void mlt_cache_put_frame( mlt_cache cache, mlt_frame frame )
538 pthread_mutex_lock( &cache->mutex );
539 mlt_frame *hit = shuffle_get_frame( cache, mlt_frame_get_position( frame ) );
540 mlt_frame *alt = (mlt_frame*) ( cache->current == cache->A ? cache->B : cache->A );
542 // add the frame to the cache
545 // release the old data
546 mlt_frame_close( *hit );
547 // the MRU end gets the updated data
548 hit = &alt[ cache->count - 1 ];
550 else if ( cache->count < cache->size )
552 // more room in cache, add it to MRU end
553 hit = &alt[ cache->count++ ];
557 // release the entry at the LRU end
558 mlt_frame_close( cache->current[0] );
560 // The MRU end gets the new item
561 hit = &alt[ cache->count - 1 ];
563 *hit = mlt_frame_clone( frame, 1 );
564 mlt_log( NULL, MLT_LOG_DEBUG, "%s: put %d = %p\n", __FUNCTION__, cache->count - 1, frame );
566 // swap the current array
567 cache->current = (void**) alt;
568 cache->is_frames = 1;
569 pthread_mutex_unlock( &cache->mutex );
572 /** Get a frame from the cache.
574 * You must call mlt_frame_close() on the frame you receive from this.
576 * \public \memberof mlt_cache_s
577 * \param cache a cache object
578 * \param position the position of the frame that you want
579 * \return a frame if found or NULL if not found or has been flushed from the cache
580 * \see mlt_frame_put_frame
583 mlt_frame mlt_cache_get_frame( mlt_cache cache, mlt_position position )
585 mlt_frame result = NULL;
586 pthread_mutex_lock( &cache->mutex );
587 mlt_frame *hit = shuffle_get_frame( cache, position );
588 mlt_frame *alt = (mlt_frame*) ( cache->current == cache->A ? cache->B : cache->A );
592 // copy the hit to the MRU end
593 alt[ cache->count - 1 ] = *hit;
594 hit = &alt[ cache->count - 1 ];
596 result = mlt_frame_clone( *hit, 1 );
597 mlt_log( NULL, MLT_LOG_DEBUG, "%s: get %d = %p\n", __FUNCTION__, cache->count - 1, *hit );
599 // swap the current array
600 cache->current = (void**) alt;
602 pthread_mutex_unlock( &cache->mutex );