summaryrefslogtreecommitdiffstats
path: root/ksvg/impl/LRUCache.h
diff options
context:
space:
mode:
authortoma <toma@283d02a7-25f6-0310-bc7c-ecb5cbfe19da>2009-11-25 17:56:58 +0000
committertoma <toma@283d02a7-25f6-0310-bc7c-ecb5cbfe19da>2009-11-25 17:56:58 +0000
commit47d455dd55be855e4cc691c32f687f723d9247ee (patch)
tree52e236aaa2576bdb3840ebede26619692fed6d7d /ksvg/impl/LRUCache.h
downloadtdegraphics-47d455dd55be855e4cc691c32f687f723d9247ee.tar.gz
tdegraphics-47d455dd55be855e4cc691c32f687f723d9247ee.zip
Copy the KDE 3.5 branch to branches/trinity for new KDE 3.5 features.
BUG:215923 git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/kdegraphics@1054174 283d02a7-25f6-0310-bc7c-ecb5cbfe19da
Diffstat (limited to 'ksvg/impl/LRUCache.h')
-rw-r--r--ksvg/impl/LRUCache.h169
1 files changed, 169 insertions, 0 deletions
diff --git a/ksvg/impl/LRUCache.h b/ksvg/impl/LRUCache.h
new file mode 100644
index 00000000..879f1856
--- /dev/null
+++ b/ksvg/impl/LRUCache.h
@@ -0,0 +1,169 @@
+/*
+ Copyright (C) 2003 KSVG Team
+ This file is part of the KDE project
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Library General Public
+ License as published by the Free Software Foundation; either
+ version 2 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Library General Public License for more details.
+
+ You should have received a copy of the GNU Library General Public License
+ aint with this library; see the file COPYING.LIB. If not, write to
+ the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
+*/
+
+#ifndef LRUCACHE_H
+#define LRUCACHE_H
+
+#include <qvaluelist.h>
+
+namespace KSVG
+{
+
+// A value-based LRU cache with a maximum total cost constraint, but with the exception that the
+// most recently added item is kept in the cache even if its cost exceeds the maximum total cost.
+template<class keyType, class valueType>
+class MinOneLRUCache
+{
+public:
+ MinOneLRUCache(int maxTotalCost = 0) : m_maxTotalCost(maxTotalCost), m_totalCost(0) {}
+ virtual ~MinOneLRUCache() {}
+
+ void insert(const keyType& key, const valueType& value, int cost);
+ bool find(const keyType& key, valueType& result);
+
+ void setMaxTotalCost(int maxTotalCost);
+ int maxTotalCost() const { return m_maxTotalCost; }
+ int totalCost() const { return m_totalCost; }
+
+ void clear();
+
+protected:
+ class CacheItem
+ {
+ public:
+ CacheItem() : m_cost(0) {}
+ CacheItem(const keyType& key, const valueType& value, int cost) : m_key(key), m_value(value), m_cost(cost) {}
+
+ const keyType& key() const { return m_key; }
+ const valueType& value() const { return m_value; }
+ int cost() const { return m_cost; }
+
+ private:
+ keyType m_key;
+ valueType m_value;
+ int m_cost;
+ };
+
+ typedef QValueList<CacheItem> CacheItemList;
+
+ typename CacheItemList::iterator find(const keyType& key);
+ void enforceCostConstraint();
+
+ CacheItemList m_items;
+ int m_maxTotalCost;
+ int m_totalCost;
+};
+
+template<class keyType, class valueType>
+void MinOneLRUCache<keyType, valueType>::insert(const keyType& key, const valueType& value, int cost)
+{
+ typename CacheItemList::iterator it = find(key);
+
+ if(it != m_items.end())
+ {
+ // Replace the existing item.
+ m_totalCost -= (*it).cost();
+ m_items.erase(it);
+ }
+
+ // We always hold the most recently added item in the cache, even if it exceeds
+ // the maximum total cost.
+ m_items.push_front(CacheItem(key, value, cost));
+ m_totalCost += cost;
+ enforceCostConstraint();
+}
+
+template<class keyType, class valueType>
+bool MinOneLRUCache<keyType, valueType>::find(const keyType& key, valueType& result)
+{
+ bool foundKey = false;
+ typename CacheItemList::iterator it = find(key);
+
+ if(it != m_items.end())
+ {
+ CacheItem item = *it;
+ result = item.value();
+
+ if(it != m_items.begin())
+ {
+ // This is now the most recently used item.
+ m_items.erase(it);
+ m_items.push_front(item);
+ }
+
+ foundKey = true;
+ }
+
+ return foundKey;
+}
+
+template<class keyType, class valueType>
+typename MinOneLRUCache<keyType, valueType>::CacheItemList::iterator MinOneLRUCache<keyType, valueType>::find(const keyType& key)
+{
+ typename CacheItemList::iterator it;
+
+ for(it = m_items.begin(); it != m_items.end(); it++)
+ {
+ if((*it).key() == key)
+ break;
+ }
+
+ return it;
+}
+
+template<class keyType, class valueType>
+void MinOneLRUCache<keyType, valueType>::enforceCostConstraint()
+{
+ if(m_totalCost > m_maxTotalCost && m_items.size() > 1)
+ {
+ typename CacheItemList::iterator it = m_items.begin();
+ m_totalCost = (*it).cost();
+ ++it;
+
+ while(it != m_items.end() && m_totalCost + (*it).cost() <= m_maxTotalCost)
+ {
+ m_totalCost += (*it).cost();
+ ++it;
+ }
+
+ // Remove the remainder
+ while(it != m_items.end())
+ it = m_items.erase(it);
+ }
+}
+
+template<class keyType, class valueType>
+void MinOneLRUCache<keyType, valueType>::setMaxTotalCost(int maxTotalCost)
+{
+ m_maxTotalCost = maxTotalCost;
+ enforceCostConstraint();
+}
+
+template<class keyType, class valueType>
+void MinOneLRUCache<keyType, valueType>::clear()
+{
+ m_items.clear();
+ m_totalCost = 0;
+}
+
+}
+
+#endif
+