मैंने एक समान ध्वनि प्रकार लागू किया है जिसे मैंने डायनामिक कैश कहा है। मूल रूप से यह निर्माण तिथि द्वारा क्रमबद्ध सूची में डेटा संग्रहीत करता है। इसे आसानी से अंतिम एक्सेस तिथि में बदला जा सकता है। मेरे कैश का उद्देश्य उन डेटाबेस आइटम्स को कैश करना है जो अक्सर नहीं बदलते हैं। यह 5 मिनट के लिए वस्तुओं को कैश करता है, फिर उन्हें अगली एक्सेस होने पर उन्हें फिर से पढ़ने के लिए हटा देता है।
कैश लुकअप एक मानचित्र का उपयोग करता है जो कुंजी और एक पुनरावर्तक को सूची में संग्रहीत करता है। लुकअप सूची में डेटा खोजने के लिए मानचित्र का उपयोग करता है, फिर आइटम वापस आने से पहले सूची के अंत से सभी पुरानी वस्तुओं को हटा देता है। यदि कोई आइटम कैश में नहीं है तो डेटा प्रदान करने के लिए कारखाने को बुलाया जाता है।
यह दृष्टिकोण, के रूप में नक्शे में iterators हमेशा मान्य होना चाहिए डाटा स्टोर करने के लिए एक सूची का उपयोग करता है, तो यह एक Deque iterators एक डालने के बाद अवैध जा सकता है इस्तेमाल किया जाना चाहिए। सूची डेटा, कुंजी, जिस समय बनाई गई थी (अंतिम बार नहीं पहुंची गई) को स्टोर करने के लिए एक स्ट्रक्चर का उपयोग करती है और अंततः डेटा मौजूद है।
struct Record
{
KeyT key;
DataT data;
time_t createTime;
bool exists;
};
यदि आपका डेटा स्थिर है और आप को बचाने के लिये हाल ही में पहुंचे तो आप struct के लिए एक उपयोग समय सदस्य जोड़ सकते हैं, और प्रत्येक बार इस तक पहुंच सूची के शीर्ष पर आइटम ले जाएं।
यहाँ मेरी कोड है, यह थोड़ा जटिल दिखता है, लेकिन यह मुख्य रूप से टेम्पलेट मापदंडों और एक पाठक लेखक ताला कारण होता है।
#include "BWThread/BWReadersWriterLock.h"
#include <list>
#include <map>
#include <ctime>
#include <memory>
#include <boost/scoped_ptr.hpp>
/**
* This is a Generic Cache implementation.
*
* To implement a cache using this class create a new class
* derived from CacheFactory and implement the lookup method.
* If the datasource supports updating implement update and
* remove method.
*
* EG
* typedef NameCache DynamicCache<int, BWString>;
* NameCacheFactory : NameCache::Factory
* {
* public:
* virtual bool lookup(int, BWString *);
* };
*
* NameCache cache(new NameCacheFactory, "<cache name>");
*
* --------------------------------------------------------
* Implementation note:
* This class uses a list as an efficient way to remove stale items from
* the cache. The map stores a key and an iterators to the data in the list.
* The list and the map are updated together.
*/
template <class KeyT, class DataT>
class CacheFactory
{
public:
virtual ~CacheFactory() {}
// Lookup the data for from the data source.
// Return true if the data is found.
virtual bool lookup(const KeyT & key, DataT * data) = 0;
// Update or insert the data in the data source.
// Return true if the data can be updated.
// Returning false means the cache is not updated either.
virtual bool update(const KeyT & key, const DataT & data) { return false; }
// Remove the data in the data source.
// Return true if the data can be deleted weather it exists or not.
// Returning false means the cache is not updated either.
virtual bool remove(const KeyT & key) { return false; }
};
template <class KeyT, class DataT>
class DynamicCache
{
public:
typedef CacheFactory<KeyT, DataT> Factory;
DynamicCache(Factory * f, const std::string & name, time_t t = (5 * 60)) :
factory(f), timeout(t), lastClean(std::time(0)), lock(name + " DynamicCache") {}
/*
* Lookup a key in the cache, the cached version is returned if it is
* present and the value is not old. If the value is old or is not
* present then use the factory to create it and insert the value in the
* cache for future lookups. If the factory cannot create it cache this
* fact too so we will ignore future lookups. Afterwards any entries in
* the cache longer than timeout are removed.
*
* This is the main method and entry point for the cache. All locking is
* performed inside the child methods.
*/
bool lookup(const KeyT & key, DataT * data, time_t now = std::time(0))
{
bool found = false;
FindStatus status = find(key, data, now);
switch(status & EntryStatus) {
case Found:
found = true;
break;
case Create:
found = build(key, data, now);
break;
}
if (status & CleanRequired) {
cleanOldEntries(now);
}
return found;
}
bool update(const KeyT & key, const DataT & data, time_t now = std::time(0))
{
if (factory->update(key, data))
{
Record record;
record.key = key;
record.createTime = now;
record.data = data;
record.exists = true;
BWReadersWriterLock::WriteLockGuard guard(lock, __FILE__, __LINE__);
updateEntry(key, record);
return true;
}
return false;
}
bool remove(const KeyT & key, time_t now = std::time(0))
{
if (factory->remove(key))
{
Record record;
record.key = key;
record.createTime = now;
record.exists = false;
BWReadersWriterLock::WriteLockGuard guard(lock, __FILE__, __LINE__);
updateEntry(key, record);
return true;
}
return false;
}
/**
* Return the size of the cache (only really useful for unit testing).
*/
size_t size() const
{
BWReadersWriterLock::ReadLockGuard guard(lock, __FILE__, __LINE__);
return map.size();
}
Factory * getFactory()
{
return factory.get();
}
private:
// Cache record
struct Record
{
KeyT key;
DataT data;
time_t createTime;
bool exists;
};
// Find and Clean status
// CleanRequired is part of this so that searching the cache and finding
// stale items in the cache can be automic (use a single readlock).
enum FindStatus {
None,
Found,
Create, //Add
NotExist,
EntryStatus=Found|Create|NotExist,
CleanRequired = 8
};
typedef std::list<Record> List;
typedef typename List::iterator Iterator;
typedef std::map<KeyT, typename Iterator> Map;
//
// The following methods all use and require explicit locking.
//
FindStatus find(const KeyT & key, DataT * data, time_t now)
{
BWReadersWriterLock::ReadLockGuard guard(lock, __FILE__, __LINE__);
Iterator itr = getEntry(key);
if (isValid(itr) && !isOld(itr, now)) {
if (itr->exists) {
*data = itr->data;
return FindStatus(Found | cleanRequired(now));
}
else {
return FindStatus(NotExist | cleanRequired(now));
}
}
return FindStatus(Create | cleanRequired(now));
}
bool build(const KeyT & key, DataT * data, time_t now)
{
Record record;
record.key = key;
record.createTime = now;
record.exists = factory->lookup(key, &record.data);
BWReadersWriterLock::WriteLockGuard guard(lock, __FILE__, __LINE__);
if (record.exists) {
*data = record.data;
}
updateEntry(key, record);
return record.exists;
}
void cleanOldEntries(time_t now)
{
BWReadersWriterLock::WriteLockGuard guard(lock, __FILE__, __LINE__);
lastClean = now;
time_t old = now - timeout;
typename List::reverse_iterator itr = list.rbegin();
while(!list.empty() && list.back().createTime < old) {
removeEntry(getEntry(list.back().key));
}
}
//
// The following methods don't use locking but require the calling
// method to already have aquired a lock.
//
Iterator getEntry(const KeyT & key)
{
typename Map::const_iterator itr = map.find(key);
if (itr != map.end()) {
return map.find(key)->second;
}
return list.end();
}
bool updateEntry(const KeyT key, const Record & record)
{
Iterator itr = getEntry(key);
if (isValid(itr)) {
removeEntry(itr);
}
insertEntry(record);
return record.exists;
}
bool isValid(Iterator itr) const
{
typename List::const_iterator constItr(itr);
return constItr != list.end();
}
bool isOld(Iterator itr, time_t now) const
{
// isOld or time_t has wrapped
return ((itr->createTime + timeout) < now) || (now < itr->createTime);
}
Iterator insertEntry(const Record & record)
{
list.push_front(record);
Iterator itr = list.begin();
map.insert(typename Map::value_type(record.key, itr));
return itr;
}
void removeEntry(Iterator itr)
{
map.erase(itr->key);
list.erase(itr);
}
FindStatus cleanRequired(time_t now) const
{
return (lastClean + timeout) < now ? CleanRequired : None;
}
List list;
Map map;
time_t timeout;
time_t lastClean;
boost::scoped_ptr<CacheFactory<KeyT, DataT> > factory;
mutable BWReadersWriterLock lock;
};
धन्यवाद यह वही दिखता है जो मुझे चाहिए! – Stowelly
यहां एक समस्या है। आप एक बार से अधिक एक आइटम का उपयोग करते हैं, तो Deque अपनी इटरेटर अपनी एकाधिक प्रतिलिपियाँ शामिल, एक ही आइटम दो बार मिटा करने की कोशिश कर में जिसके परिणामस्वरूप (अपरिभाषित व्यवहार के कारण) होगा। आपको आइटम को एक्सेस पर हटाने और फ्रंट पर फिर से डालने की आवश्यकता है। इसके लिए एक डेक की तुलना में एक सूची अधिक कुशल होगी। –
एक डेक छोटे संग्रह (~ 100/~ 1000 आइटम) के लिए पर्याप्त तेज़ है। हम इसके बाद इटेटर (पॉइंटर्स) बात कर रहे हैं। –