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);
+}