Improved cache management for movie clips from tomato branch

Replace pseudo-LRU approach of determining which buffer
to remove when running out of space allowed for cache
with approach which would remove the frame which is most
far away from newly added frame.

This is still a bit tricky because it's impossible to
distinguish which frame to delete in situation of:

        CCCC...CC
           ^

it's either user wants to extend left segment of cached
frames and buffers from right segment should be removed
or he wants to join this two segments and in that case
buffers from right segment should be removed.

Would need a bit more investigation which situation
is more common in general usecase.

Additional changes:

- Cleanup some memutil files (which are familiar to cache limiter)

- Add option to make moviecache verbose. If DEBUG_MESSAGES is
  defined in moviecache.c detailed logs would be printed to the
  console.

- Movie caches are now named which helps reading debug messages.

3 files changed, 213 insertions, 130 deletions

diff --git a/intern/memutil/MEM_CacheLimiter.h b/intern/memutil/MEM_CacheLimiter.h
index 9a36b67aa2f..801ee154d40 100644
--- a/intern/memutil/MEM_CacheLimiter.h
+++ b/intern/memutil/MEM_CacheLimiter.h
@@ -32,7 +32,7 @@
  * @section MEM_CacheLimiter
  * This class defines a generic memory cache management system
  * to limit memory usage to a fixed global maximum.
- * 
+ *
  * Please use the C-API in MEM_CacheLimiterC-Api.h for code written in C.
  *
  * Usage example:
@@ -41,12 +41,12 @@
  * public:
  *       ~BigFatImage() { tell_everyone_we_are_gone(this); }
  * };
- * 
+ *
  * void doit() {
  *     MEM_Cache<BigFatImage> BigFatImages;
  *
  *     MEM_Cache_Handle<BigFatImage>* h = BigFatImages.insert(new BigFatImage);
- * 
+ *
  *     BigFatImages.enforce_limits();
  *     h->ref();
  *
@@ -58,6 +58,8 @@
  */
 
 #include <list>
+#include <queue>
+#include <vector>
 #include "MEM_Allocator.h"
 
 template<class T>
@@ -65,36 +67,44 @@ class MEM_CacheLimiter;
 
 #ifndef __MEM_CACHELIMITERC_API_H__
 extern "C" {
-	extern void MEM_CacheLimiter_set_maximum(size_t m);
-	extern size_t MEM_CacheLimiter_get_maximum();
+	void MEM_CacheLimiter_set_maximum(size_t m);
+	size_t MEM_CacheLimiter_get_maximum();
 };
 #endif
 
 template<class T>
 class MEM_CacheLimiterHandle {
 public:
-	explicit MEM_CacheLimiterHandle(T * data_, 
-					 MEM_CacheLimiter<T> * parent_) 
-		: data(data_), refcount(0), parent(parent_) { }
+	explicit MEM_CacheLimiterHandle(T * data_,MEM_CacheLimiter<T> *parent_) :
+		data(data_),
+		refcount(0),
+		parent(parent_)
+	{ }
 
-	void ref() { 
-		refcount++; 
+	void ref() {
+		refcount++;
 	}
-	void unref() { 
-		refcount--; 
+
+	void unref() {
+		refcount--;
 	}
-	T * get() { 
-		return data; 
+
+	T *get() {
+		return data;
 	}
-	const T * get() const { 
-		return data; 
+
+	const T *get() const {
+		return data;
 	}
-	int get_refcount() const { 
-		return refcount; 
+
+	int get_refcount() const {
+		return refcount;
 	}
-	bool can_destroy() const { 
-		return !data || !refcount; 
+
+	bool can_destroy() const {
+		return !data || !refcount;
 	}
+
 	bool destroy_if_possible() {
 		if (can_destroy()) {
 			delete data;
@@ -104,48 +114,64 @@ public:
 		}
 		return false;
 	}
+
 	void unmanage() {
 		parent->unmanage(this);
 	}
+
 	void touch() {
 		parent->touch(this);
 	}
+
+	void set_priority(int priority) {
+		this->priority = priority;
+	}
+
+	int get_priority(void) {
+		return this->priority;
+	}
+
 private:
 	friend class MEM_CacheLimiter<T>;
 
 	T * data;
 	int refcount;
-	typename std::list<MEM_CacheLimiterHandle<T> *,
-	  MEM_Allocator<MEM_CacheLimiterHandle<T> *> >::iterator me;
+	int priority;
+	typename std::list<MEM_CacheLimiterHandle<T> *, MEM_Allocator<MEM_CacheLimiterHandle<T> *> >::iterator me;
 	MEM_CacheLimiter<T> * parent;
 };
 
 template<class T>
 class MEM_CacheLimiter {
 public:
-	typedef typename std::list<MEM_CacheLimiterHandle<T> *,
-	  MEM_Allocator<MEM_CacheLimiterHandle<T> *> >::iterator iterator;
 	typedef size_t (*MEM_CacheLimiter_DataSize_Func) (void *data);
+	typedef int    (*MEM_CacheLimiter_ItemPriority_Func) (void *item, int default_priority);
+
 	MEM_CacheLimiter(MEM_CacheLimiter_DataSize_Func getDataSize_)
 		: getDataSize(getDataSize_) {
 	}
+
 	~MEM_CacheLimiter() {
 		for (iterator it = queue.begin(); it != queue.end(); it++) {
 			delete *it;
 		}
 	}
-	MEM_CacheLimiterHandle<T> * insert(T * elem) {
+
+	MEM_CacheLimiterHandle<T> *insert(T * elem) {
 		queue.push_back(new MEM_CacheLimiterHandle<T>(elem, this));
 		iterator it = queue.end();
 		--it;
 		queue.back()->me = it;
 		return queue.back();
 	}
-	void unmanage(MEM_CacheLimiterHandle<T> * handle) {
+
+	void unmanage(MEM_CacheLimiterHandle<T> *handle) {
 		queue.erase(handle->me);
 		delete handle;
 	}
+
 	void enforce_limits() {
+		MEM_CachePriorityQueue priority_queue;
 		size_t max = MEM_CacheLimiter_get_maximum();
 		size_t mem_in_use, cur_size;
 
@@ -159,27 +185,33 @@ public:
 			mem_in_use = MEM_get_memory_in_use();
 		}
 
-		for (iterator it = queue.begin(); 
-		     it != queue.end() && mem_in_use > max;)
-		{
-			iterator jt = it;
-			++it;
+		if (mem_in_use <= max) {
+			return;
+		}
 
-			if(getDataSize) {
-				cur_size= getDataSize((*jt)->get()->get_data());
-			} else {
-				cur_size= mem_in_use;
-			}
+		priority_queue = get_priority_queue();
+
+		while (!priority_queue.empty() && mem_in_use > max) {
+			MEM_CacheElementPtr elem = priority_queue.top();
 
-			(*jt)->destroy_if_possible();
+			priority_queue.pop();
 
 			if(getDataSize) {
-				mem_in_use-= cur_size;
+				cur_size = getDataSize(elem->get()->get_data());
 			} else {
-				mem_in_use-= cur_size - MEM_get_memory_in_use();
+				cur_size = mem_in_use;
+			}
+
+			if (elem->destroy_if_possible()) {
+				if (getDataSize) {
+					mem_in_use -= cur_size;
+				} else {
+					mem_in_use -= cur_size - MEM_get_memory_in_use();
+				}
 			}
 		}
 	}
+
 	void touch(MEM_CacheLimiterHandle<T> * handle) {
 		queue.push_back(handle);
 		queue.erase(handle->me);
@@ -187,7 +219,24 @@ public:
 		--it;
 		handle->me = it;
 	}
+
+	void set_item_priority_func(MEM_CacheLimiter_ItemPriority_Func item_priority_func) {
+		getItemPriority = item_priority_func;
+	}
+
 private:
+	typedef MEM_CacheLimiterHandle<T> *MEM_CacheElementPtr;
+	typedef std::list<MEM_CacheElementPtr, MEM_Allocator<MEM_CacheElementPtr> > MEM_CacheQueue;
+	typedef typename MEM_CacheQueue::iterator iterator;
+
+	struct compare_element_priority : public std::binary_function<MEM_CacheElementPtr, MEM_CacheElementPtr, bool> {
+		bool operator()(const MEM_CacheElementPtr left_elem, const MEM_CacheElementPtr right_elem) const {
+			return left_elem->get_priority() > right_elem->get_priority();
+		}
+	};
+
+	typedef std::priority_queue<MEM_CacheElementPtr, std::vector<MEM_CacheElementPtr>, compare_element_priority > MEM_CachePriorityQueue;
+
 	size_t total_size() {
 		size_t size = 0;
 		for (iterator it = queue.begin(); it != queue.end(); it++) {
@@ -196,9 +245,33 @@ private:
 		return size;
 	}
 
-	std::list<MEM_CacheLimiterHandle<T>*,
-	  MEM_Allocator<MEM_CacheLimiterHandle<T> *> > queue;
+	MEM_CachePriorityQueue get_priority_queue(void) {
+		MEM_CachePriorityQueue priority_queue;
+		iterator it;
+		int i;
+
+		for (it = queue.begin(), i = 0; it != queue.end(); it++, i++) {
+			MEM_CacheElementPtr elem = *it;
+			int priority;
+
+			/* by default 0 means higherst priority element */
+			priority = -(queue.size() - i - 1);
+
+			if (getItemPriority) {
+				priority = getItemPriority(elem->get()->get_data(), priority);
+			}
+
+			elem->set_priority(priority);
+
+			priority_queue.push(elem);
+		}
+
+		return priority_queue;
+	}
+
+	MEM_CacheQueue queue;
 	MEM_CacheLimiter_DataSize_Func getDataSize;
+	MEM_CacheLimiter_ItemPriority_Func getItemPriority;
 };
 
 #endif // __MEM_CACHELIMITER_H__
diff --git a/intern/memutil/MEM_CacheLimiterC-Api.h b/intern/memutil/MEM_CacheLimiterC-Api.h
index 4ed692fb55f..1ae5e9df1c6 100644
--- a/intern/memutil/MEM_CacheLimiterC-Api.h
+++ b/intern/memutil/MEM_CacheLimiterC-Api.h
@@ -31,7 +31,7 @@
 #ifdef __cplusplus
 extern "C" {
 #endif
-	
+
 struct MEM_CacheLimiter_s;
 struct MEM_CacheLimiterHandle_s;
 
@@ -39,106 +39,111 @@ typedef struct MEM_CacheLimiter_s MEM_CacheLimiterC;
 typedef struct MEM_CacheLimiterHandle_s MEM_CacheLimiterHandleC;
 
 /* function used to remove data from memory */
-typedef void(*MEM_CacheLimiter_Destruct_Func)(void*);
+typedef void (*MEM_CacheLimiter_Destruct_Func)(void*);
 
 /* function used to measure stored data element size */
-typedef size_t(*MEM_CacheLimiter_DataSize_Func) (void*);
+typedef size_t (*MEM_CacheLimiter_DataSize_Func) (void*);
+
+/* function used to measure priority of item when freeing memory */
+typedef int (*MEM_CacheLimiter_ItemPriority_Func) (void*, int);
 
 #ifndef __MEM_CACHELIMITER_H__
-extern void MEM_CacheLimiter_set_maximum(size_t m);
-extern int MEM_CacheLimiter_get_maximum(void);
+void MEM_CacheLimiter_set_maximum(size_t m);
+int MEM_CacheLimiter_get_maximum(void);
 #endif /* __MEM_CACHELIMITER_H__ */
-/** 
- * Create new MEM_CacheLimiter object 
+
+/**
+ * Create new MEM_CacheLimiter object
  * managed objects are destructed with the data_destructor
  *
  * @param data_destructor
  * @return A new MEM_CacheLimter object
  */
 
-extern MEM_CacheLimiterC * new_MEM_CacheLimiter(
-	MEM_CacheLimiter_Destruct_Func data_destructor,
-	MEM_CacheLimiter_DataSize_Func data_size);
+MEM_CacheLimiterC *new_MEM_CacheLimiter(MEM_CacheLimiter_Destruct_Func data_destructor,
+                                         MEM_CacheLimiter_DataSize_Func data_size);
 
-/** 
+/**
  * Delete MEM_CacheLimiter
- * 
+ *
  * Frees the memory of the CacheLimiter but does not touch managed objects!
  *
  * @param This "This" pointer
  */
 
-extern void delete_MEM_CacheLimiter(MEM_CacheLimiterC * This);
+void delete_MEM_CacheLimiter(MEM_CacheLimiterC *This);
 
-/** 
+/**
  * Manage object
- * 
+ *
  * @param This "This" pointer, data data object to manage
  * @return CacheLimiterHandle to ref, unref, touch the managed object
  */
-	
-extern MEM_CacheLimiterHandleC * MEM_CacheLimiter_insert(
-	MEM_CacheLimiterC * This, void * data);
 
-/** 
+MEM_CacheLimiterHandleC *MEM_CacheLimiter_insert(MEM_CacheLimiterC * This, void * data);
+
+/**
  * Free objects until memory constraints are satisfied
- * 
+ *
  * @param This "This" pointer
  */
 
-extern void MEM_CacheLimiter_enforce_limits(MEM_CacheLimiterC * This);
+void MEM_CacheLimiter_enforce_limits(MEM_CacheLimiterC *This);
 
-/** 
- * Unmanage object previously inserted object. 
+/**
+ * Unmanage object previously inserted object.
  * Does _not_ delete managed object!
- * 
+ *
  * @param This "This" pointer, handle of object
  */
-	
-extern void MEM_CacheLimiter_unmanage(MEM_CacheLimiterHandleC * handle);
 
+void MEM_CacheLimiter_unmanage(MEM_CacheLimiterHandleC *handle);
 
-/** 
+
+/**
  * Raise priority of object (put it at the tail of the deletion chain)
- * 
+ *
  * @param handle of object
  */
-	
-extern void MEM_CacheLimiter_touch(MEM_CacheLimiterHandleC * handle);
 
-/** 
+void MEM_CacheLimiter_touch(MEM_CacheLimiterHandleC *handle);
+
+/**
  * Increment reference counter. Objects with reference counter != 0 are _not_
  * deleted.
- * 
+ *
  * @param handle of object
  */
-	
-extern void MEM_CacheLimiter_ref(MEM_CacheLimiterHandleC * handle);
 
-/** 
+void MEM_CacheLimiter_ref(MEM_CacheLimiterHandleC *handle);
+
+/**
  * Decrement reference counter. Objects with reference counter != 0 are _not_
  * deleted.
- * 
+ *
  * @param handle of object
  */
-	
-extern void MEM_CacheLimiter_unref(MEM_CacheLimiterHandleC * handle);
 
-/** 
+void MEM_CacheLimiter_unref(MEM_CacheLimiterHandleC *handle);
+
+/**
  * Get reference counter.
- * 
+ *
  * @param This "This" pointer, handle of object
  */
-	
-extern int MEM_CacheLimiter_get_refcount(MEM_CacheLimiterHandleC * handle);
 
-/** 
+int MEM_CacheLimiter_get_refcount(MEM_CacheLimiterHandleC *handle);
+
+/**
  * Get pointer to managed object
- * 
+ *
  * @param handle of object
  */
-	
-extern void * MEM_CacheLimiter_get(MEM_CacheLimiterHandleC * handle);
+
+void * MEM_CacheLimiter_get(MEM_CacheLimiterHandleC *handle);
+
+void MEM_CacheLimiter_ItemPriority_Func_set(MEM_CacheLimiterC *This,
+                                            MEM_CacheLimiter_ItemPriority_Func item_priority_func);
 
 #ifdef __cplusplus
 }
diff --git a/intern/memutil/intern/MEM_CacheLimiterC-Api.cpp b/intern/memutil/intern/MEM_CacheLimiterC-Api.cpp
index cfa6a207e1c..81a1ce670ae 100644
--- a/intern/memutil/intern/MEM_CacheLimiterC-Api.cpp
+++ b/intern/memutil/intern/MEM_CacheLimiterC-Api.cpp
@@ -31,7 +31,7 @@
 
 static size_t & get_max()
 {
-	static size_t m = 32*1024*1024;
+	static size_t m = 32 * 1024 * 1024;
 	return m;
 }
 
@@ -50,8 +50,7 @@ class MEM_CacheLimiterCClass;
 
 typedef MEM_CacheLimiterHandle<MEM_CacheLimiterHandleCClass> handle_t;
 typedef MEM_CacheLimiter<MEM_CacheLimiterHandleCClass> cache_t;
-typedef std::list<MEM_CacheLimiterHandleCClass*,
-		  MEM_Allocator<MEM_CacheLimiterHandleCClass* > > list_t;
+typedef std::list<MEM_CacheLimiterHandleCClass*, MEM_Allocator<MEM_CacheLimiterHandleCClass* > > list_t;
 
 class MEM_CacheLimiterCClass {
 public:
@@ -59,11 +58,10 @@ public:
 		: data_destructor(data_destructor_), cache(data_size) {
 	}
 	~MEM_CacheLimiterCClass();
-	
+
 	handle_t * insert(void * data);
 
-	void destruct(void * data,
-	              list_t::iterator it);
+	void destruct(void * data, list_t::iterator it);
 
 	cache_t * get_cache() {
 		return &cache;
@@ -72,42 +70,48 @@ private:
 	MEM_CacheLimiter_Destruct_Func data_destructor;
 
 	MEM_CacheLimiter<MEM_CacheLimiterHandleCClass> cache;
-	
+
 	list_t cclass_list;
 };
 
 class MEM_CacheLimiterHandleCClass {
 public:
-	MEM_CacheLimiterHandleCClass(void * data_,
-	                             MEM_CacheLimiterCClass * parent_)
-	    : data(data_), parent(parent_) { }
+	MEM_CacheLimiterHandleCClass(void * data_, MEM_CacheLimiterCClass * parent_) :
+		data(data_),
+		parent(parent_)
+	{ }
+
 	~MEM_CacheLimiterHandleCClass();
+
 	void set_iter(list_t::iterator it_) {
 		it = it_;
 	}
+
 	void set_data(void * data_) {
 		data = data_;
 	}
-	void * get_data() const {
+
+	void *get_data() const {
 		return data;
 	}
+
 private:
-	void * data;
-	MEM_CacheLimiterCClass * parent;
+	void *data;
+	MEM_CacheLimiterCClass *parent;
 	list_t::iterator it;
 };
 
-handle_t * MEM_CacheLimiterCClass::insert(void * data) 
+handle_t *MEM_CacheLimiterCClass::insert(void * data)
 {
 	cclass_list.push_back(new MEM_CacheLimiterHandleCClass(data, this));
 	list_t::iterator it = cclass_list.end();
 	--it;
 	cclass_list.back()->set_iter(it);
-	
+
 	return cache.insert(cclass_list.back());
 }
 
-void MEM_CacheLimiterCClass::destruct(void * data, list_t::iterator it) 
+void MEM_CacheLimiterCClass::destruct(void * data, list_t::iterator it)
 {
 	data_destructor(data);
 	cclass_list.erase(it);
@@ -123,77 +127,78 @@ MEM_CacheLimiterHandleCClass::~MEM_CacheLimiterHandleCClass()
 MEM_CacheLimiterCClass::~MEM_CacheLimiterCClass()
 {
 	// should not happen, but don't leak memory in this case...
-	for (list_t::iterator it = cclass_list.begin();
-	     it != cclass_list.end(); it++) {
+	for (list_t::iterator it = cclass_list.begin(); it != cclass_list.end(); it++) {
 		(*it)->set_data(0);
+
 		delete *it;
 	}
 }
 
 // ----------------------------------------------------------------------
 
-static inline MEM_CacheLimiterCClass* cast(MEM_CacheLimiterC * l)
+static inline MEM_CacheLimiterCClass *cast(MEM_CacheLimiterC *l)
 {
-	return (MEM_CacheLimiterCClass*) l;
+	return (MEM_CacheLimiterCClass *) l;
 }
 
-static inline handle_t* cast(MEM_CacheLimiterHandleC * l)
+static inline handle_t *cast(MEM_CacheLimiterHandleC *l)
 {
-	return (handle_t*) l;
+	return (handle_t *) l;
 }
 
-MEM_CacheLimiterC * new_MEM_CacheLimiter(
-	MEM_CacheLimiter_Destruct_Func data_destructor,
-	MEM_CacheLimiter_DataSize_Func data_size)
+MEM_CacheLimiterC *new_MEM_CacheLimiter(MEM_CacheLimiter_Destruct_Func data_destructor,
+                                        MEM_CacheLimiter_DataSize_Func data_size)
 {
-	return (MEM_CacheLimiterC*) new MEM_CacheLimiterCClass(
-		data_destructor,
-		data_size);
+	return (MEM_CacheLimiterC *) new MEM_CacheLimiterCClass(data_destructor, data_size);
 }
 
-void delete_MEM_CacheLimiter(MEM_CacheLimiterC * This)
+void delete_MEM_CacheLimiter(MEM_CacheLimiterC *This)
 {
 	delete cast(This);
 }
 
-MEM_CacheLimiterHandleC * MEM_CacheLimiter_insert(
-	MEM_CacheLimiterC * This, void * data)
+MEM_CacheLimiterHandleC *MEM_CacheLimiter_insert(MEM_CacheLimiterC *This, void *data)
 {
 	return (MEM_CacheLimiterHandleC *) cast(This)->insert(data);
 }
 
-void MEM_CacheLimiter_enforce_limits(MEM_CacheLimiterC * This)
+void MEM_CacheLimiter_enforce_limits(MEM_CacheLimiterC *This)
 {
 	cast(This)->get_cache()->enforce_limits();
 }
-	
-void MEM_CacheLimiter_unmanage(MEM_CacheLimiterHandleC * handle)
+
+void MEM_CacheLimiter_unmanage(MEM_CacheLimiterHandleC *handle)
 {
 	cast(handle)->unmanage();
 }
-	
-void MEM_CacheLimiter_touch(MEM_CacheLimiterHandleC * handle)
+
+void MEM_CacheLimiter_touch(MEM_CacheLimiterHandleC *handle)
 {
 	cast(handle)->touch();
 }
-	
-void MEM_CacheLimiter_ref(MEM_CacheLimiterHandleC * handle)
+
+void MEM_CacheLimiter_ref(MEM_CacheLimiterHandleC *handle)
 {
 	cast(handle)->ref();
 }
-	
-void MEM_CacheLimiter_unref(MEM_CacheLimiterHandleC * handle)
+
+void MEM_CacheLimiter_unref(MEM_CacheLimiterHandleC *handle)
 {
 	cast(handle)->unref();
 }
 
-int MEM_CacheLimiter_get_refcount(MEM_CacheLimiterHandleC * handle)
+int MEM_CacheLimiter_get_refcount(MEM_CacheLimiterHandleC *handle)
 {
 	return cast(handle)->get_refcount();
 }
 
-	
-void * MEM_CacheLimiter_get(MEM_CacheLimiterHandleC * handle)
+void *MEM_CacheLimiter_get(MEM_CacheLimiterHandleC *handle)
 {
 	return cast(handle)->get()->get_data();
 }
+
+void MEM_CacheLimiter_ItemPriority_Func_set(MEM_CacheLimiterC *This,
+                                            MEM_CacheLimiter_ItemPriority_Func item_priority_func)
+{
+	cast(This)->get_cache()->set_item_priority_func(item_priority_func);
+}