00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #include <pthread.h>
00034
00035 #include "TimeUtil.h"
00036 #include "ScopedLock.h"
00037 #include "mstring.h"
00038 #include "m_map.h"
00039
00040 #ifndef LRUCACHE_H
00041 #define LRUCACHE_H
00042
00049 namespace mace {
00050
00067 template <typename K, typename D>
00068 class LRUCache {
00069
00070 class CacheEntry {
00071 public:
00072 CacheEntry(const K& index, const D& d, bool dirty, time_t t) :
00073 index(index), data(d), dirty(dirty), init(t), prev(0), next(0) {
00074 }
00075
00076 virtual ~CacheEntry() {
00077 }
00078
00079 public:
00080 K index;
00081 D data;
00082 bool dirty;
00083 time_t init;
00084 CacheEntry* prev;
00085 CacheEntry* next;
00086 };
00087
00088
00089 typedef map<K, CacheEntry*, SoftState> LRUCacheIndexMap;
00090
00091 public:
00098 LRUCache(unsigned capacity = 32, time_t timeout = 0) :
00099 capacity(capacity), timeout(timeout), size(0), dirtyCount(0), cache(0) {
00100
00101 pthread_mutexattr_t ma;
00102 ASSERT(pthread_mutexattr_init(&ma) == 0);
00103 ASSERT(pthread_mutexattr_settype(&ma, PTHREAD_MUTEX_RECURSIVE) == 0);
00104 pthread_mutex_init(&lrulock, &ma);
00105 ASSERT(pthread_mutexattr_destroy(&ma) == 0);
00106 }
00107
00108 virtual ~LRUCache() {
00109 ASSERT(pthread_mutex_lock(&lrulock) == 0);
00110 while (cache != 0) {
00111 CacheEntry* tmp = cache;
00112 cache = cache->next;
00113 indexMap.erase(tmp->index);
00114 delete tmp;
00115 tmp = 0;
00116 }
00117 ASSERT(pthread_mutex_unlock(&lrulock) == 0);
00118 pthread_mutex_destroy(&lrulock);
00119 }
00120
00128 void addDirty(const K& index, const D& buf) {
00129 add(index, buf, true);
00130 }
00131
00139 void add(const K& index, const D& buf, bool dirty = false) {
00140 ScopedLock sl(lrulock);
00141 typename LRUCacheIndexMap::iterator i = indexMap.find(index);
00142 if (i != indexMap.end()) {
00143
00144
00145
00146 CacheEntry* e = i->second;
00147 e->data = buf;
00148 if (e->dirty && !dirty) {
00149 dirtyCount--;
00150 }
00151 else if (!e->dirty && dirty) {
00152 dirtyCount++;
00153 }
00154 e->dirty = dirty;
00155 moveToHead(e);
00156 return;
00157 }
00158
00159
00160
00161
00162
00163
00164
00165
00166 ASSERT(!isFullDirty());
00167
00168 if (size == capacity) {
00169
00170 CacheEntry* last = cache->prev;
00171 while (last->dirty) {
00172 last = last->prev;
00173 }
00174
00175 remove(last->index);
00176 }
00177
00178 ASSERT(size < capacity);
00179
00180 size++;
00181 if (dirty) {
00182 dirtyCount++;
00183 }
00184
00185 time_t now = TimeUtil::time();
00186 CacheEntry* e = new CacheEntry(index, buf, dirty, now);
00187 if (cache == 0) {
00188 e->prev = e;
00189 }
00190 else {
00191 e->next = cache;
00192 e->prev = cache->prev;
00193 cache->prev = e;
00194 }
00195 cache = e;
00196 indexMap[index] = e;
00197 }
00198
00200 void remove(const K& index) {
00201 ScopedLock sl(lrulock);
00202 typename LRUCacheIndexMap::iterator i = indexMap.find(index);
00203 if (i != indexMap.end()) {
00204 CacheEntry* e = i->second;
00205
00206 clearDirty(e);
00207
00208 if (e->next) {
00209 e->next->prev = e->prev;
00210 }
00211 else {
00212 cache->prev = e->prev;
00213 }
00214
00215 if (cache == e) {
00216 cache = e->next;
00217 }
00218 else {
00219
00220 e->prev->next = e->next;
00221 }
00222
00223 delete e;
00224 e = 0;
00225 indexMap.erase(i);
00226 size--;
00227
00228 ASSERT(indexMap.size() == size);
00229 if (size == 0) {
00230 ASSERT(cache == 0);
00231 }
00232 }
00233 }
00234
00240 bool get(const K& index, D& data) {
00241 ScopedLock sl(lrulock);
00242 typename LRUCacheIndexMap::iterator i = indexMap.find(index);
00243 if (i == indexMap.end()) {
00244 return false;
00245 }
00246
00247 CacheEntry* e = i->second;
00248 moveToHead(e);
00249 data = e->data;
00250 return true;
00251 }
00252
00258 D& get(const K& index) {
00259 ScopedLock sl(lrulock);
00260 typename LRUCacheIndexMap::iterator i = indexMap.find(index);
00261 ASSERT(i != indexMap.end());
00262
00263 CacheEntry* e = i->second;
00264 moveToHead(e);
00265 return e->data;
00266 }
00267
00273 D& operator[](const K& index) {
00274 return get(index);
00275 }
00276
00277 bool containsKey(const K& index) {
00278 ScopedLock sl(lrulock);
00279 typename LRUCacheIndexMap::iterator i = indexMap.find(index);
00280 bool c = (i != indexMap.end());
00281 if (c && (timeout != 0)) {
00282 time_t now = time(0);
00283 CacheEntry* e = i->second;
00284 if ((now - e->init) > timeout) {
00285 remove(index);
00286 return false;
00287 }
00288 }
00289
00290 return c;
00291 }
00292
00294 bool isFullDirty() const {
00295 return (dirtyCount == capacity);
00296 }
00297
00299 bool hasDirty() const {
00300 return (dirtyCount > 0);
00301 }
00302
00304 const K& getLastDirtyKey() const {
00305 ScopedLock sl(lrulock);
00306 ASSERT(hasDirty());
00307
00308 CacheEntry* last = cache->prev;
00309 while (!last->dirty) {
00310 last = last->prev;
00311 }
00312
00313 return last->index;
00314 }
00315
00317 D& getLastDirty() const {
00318 ScopedLock sl(lrulock);
00319 CacheEntry* last = getLastDirtyEntry();
00320 return last->data;
00321 }
00322
00324 bool getLastDirty(K& k, D& d) const {
00325 ScopedLock sl(lrulock);
00326 if (!hasDirty()) {
00327 return false;
00328 }
00329
00330 CacheEntry* last = getLastDirtyEntry();
00331 k = last->index;
00332 d = last->data;
00333 return true;
00334 }
00335
00337 void clearLastDirty() {
00338 ScopedLock sl(lrulock);
00339 clearDirty(getLastDirtyEntry());
00340 }
00341
00343 void clearDirty(const K& index) {
00344 ScopedLock sl(lrulock);
00345 typename LRUCacheIndexMap::iterator i = indexMap.find(index);
00346 ASSERT(i != indexMap.end());
00347 CacheEntry* e = i->second;
00348 clearDirty(e);
00349 }
00350
00356 D& getDirty(const K& index) {
00357
00358 ScopedLock sl(lrulock);
00359 typename LRUCacheIndexMap::iterator i = indexMap.find(index);
00360 ASSERT(i != indexMap.end());
00361 CacheEntry* e = i->second;
00362 return e->data;
00363 }
00364
00365 private:
00366
00367 CacheEntry* getLastDirtyEntry() const {
00368 ASSERT(hasDirty());
00369 CacheEntry* last = cache->prev;
00370 while (!last->dirty) {
00371 last = last->prev;
00372 }
00373 return last;
00374 }
00375
00376 void clearDirty(CacheEntry* e) {
00377 if (e->dirty) {
00378 dirtyCount--;
00379 e->dirty = false;
00380 }
00381 }
00382
00383 void moveToHead(CacheEntry* e) {
00384 if (e->index == cache->index) {
00385 ASSERT(cache == e);
00386 return;
00387 }
00388 e->prev->next = e->next;
00389 if (e->next) {
00390 e->next->prev = e->prev;
00391 e->prev = cache->prev;
00392 }
00393 e->next = cache;
00394 cache->prev = e;
00395 cache = e;
00396 }
00397
00398 private:
00399 unsigned capacity;
00400 time_t timeout;
00401 unsigned size;
00402 unsigned dirtyCount;
00403 CacheEntry* cache;
00404 LRUCacheIndexMap indexMap;
00405 mutable pthread_mutex_t lrulock;
00406 };
00407
00408
00409 }
00410
00411 #endif // LRUCACHE_H