Cache.h

Go to the documentation of this file.
00001 /*
00002  *    Copyright 2006 Intel Corporation
00003  * 
00004  *    Licensed under the Apache License, Version 2.0 (the "License");
00005  *    you may not use this file except in compliance with the License.
00006  *    You may obtain a copy of the License at
00007  * 
00008  *        http://www.apache.org/licenses/LICENSE-2.0
00009  * 
00010  *    Unless required by applicable law or agreed to in writing, software
00011  *    distributed under the License is distributed on an "AS IS" BASIS,
00012  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00013  *    See the License for the specific language governing permissions and
00014  *    limitations under the License.
00015  */
00016 
00017 #ifndef __CACHE_H__
00018 #define __CACHE_H__
00019 
00020 #include <map>
00021 
00022 #include "../debug/InlineFormatter.h"
00023 #include "../debug/Logger.h"
00024 #include "../thread/SpinLock.h"
00025 #include "../util/LRUList.h"
00026 
00027 
00028 namespace oasys {
00029 
00037 template<typename _Key, typename _Val, typename _EvictFcn>
00038 class Cache : Logger {
00039 public:
00043     struct LRUListEnt {
00044         LRUListEnt(const _Key& key,
00045                    const _Val& val,
00046                    int pin_count = 0)
00047             : key_(key), val_(val), pin_count_(pin_count)
00048         {}
00049 
00050         _Key key_;
00051         _Val val_;
00052         int  pin_count_;
00053     };
00054 
00055     typedef LRUList<LRUListEnt> CacheList;
00056     typedef std::map<_Key, typename CacheList::iterator> CacheMap;
00057 
00061     Cache(const char* logpath, size_t max)
00062         : Logger("Cache", logpath), max_(max) {}
00063 
00070     bool get(const _Key& key, _Val* valp, bool pin = false,
00071              typename CacheList::iterator* iter = NULL)
00072     {
00073         ScopeLock l(&lock_, "Cache::get_and_pin");
00074         
00075         typename CacheMap::iterator i = cache_map_.find(key);
00076         if (i == cache_map_.end()) 
00077         {
00078             log_debug("get(%s): not in cache",
00079                       InlineFormatter<_Key>().format(key));
00080             return false;
00081         }
00082         
00083         cache_list_.move_to_back(i->second);
00084         if (pin) {
00085             ++(i->second->pin_count_);
00086         }
00087         
00088         log_debug("get(%s): got entry pin_count=%d size=%zu",
00089                   InlineFormatter<_Key>().format(key), 
00090                   i->second->pin_count_,
00091                   cache_map_.size());
00092 
00093         *valp = i->second->val_;
00094 
00095         if (iter != NULL) {
00096             *iter = i->second;
00097         }
00098         
00099         return true;
00100     }
00101 
00105     bool get_and_pin(const _Key& key, _Val* valp)
00106     {
00107         return get(key, valp, true);
00108     }
00109 
00113     void unpin(const _Key& key) 
00114     {
00115         ScopeLock l(&lock_, "Cache::unpin");
00116 
00117         typename CacheMap::iterator i = cache_map_.find(key);
00118         ASSERT(i != cache_map_.end());
00119         
00120         --(i->second->pin_count_);
00121 
00122         log_debug("unpin(%s): unpinned entry pin_count=%d size=%zu",
00123                   InlineFormatter<_Key>().format(key),
00124                   i->second->pin_count_,
00125                   cache_map_.size());
00126     }
00127 
00135     bool put_and_pin(const _Key& key, const _Val& val,
00136                      typename CacheList::iterator* iter = NULL) 
00137     {
00138         ScopeLock l(&lock_, "Cache::put_and_pin");
00139 
00140         typename CacheMap::iterator i = cache_map_.find(key);
00141         if (i != cache_map_.end()) {
00142             log_debug("put_and_pin(%s): key already in cache",
00143                       InlineFormatter<_Key>().format(key));
00144             return false;
00145         }
00146 
00147         while (cache_map_.size() + 1 > max_) 
00148         {
00149             if (! evict_last()) {
00150                 break;
00151             }
00152         }
00153         
00154         // start off with pin count 1
00155         typename CacheList::iterator new_ent =
00156             cache_list_.insert(cache_list_.end(),
00157                                LRUListEnt(key, val, 1));
00158 
00159         if (iter) {
00160             *iter = new_ent;
00161         }
00162 
00163         log_debug("put_and_pin(%s): added entry pin_count=%d size=%zu",
00164                   InlineFormatter<_Key>().format(key),
00165                   new_ent->pin_count_,
00166                   cache_map_.size());
00167 
00168         cache_map_[key] = new_ent;
00169 
00170         return val;
00171     }
00172 
00176     void evict(const _Key& key) 
00177     {
00178         ScopeLock l(&lock_, "Cache::evict");
00179         
00180         typename CacheMap::iterator i = cache_map_.find(key);
00181 
00182         if (i == cache_map_.end()) 
00183         {
00184             return;
00185         }
00186 
00187         ASSERT(key == i->second->key_);
00188         _EvictFcn e;
00189         e(key, i->second->val_);
00190         log_debug("evict(%s): evicted entry size=%zu",
00191                   InlineFormatter<_Key>().format(key),
00192                   cache_map_.size());
00193         
00194         cache_list_.erase(i->second);
00195         cache_map_.erase(i);       
00196     }
00197     
00201     void evict_all() {
00202         ScopeLock l(&lock_, "Cache::evict_all");
00203         
00204         log_debug("evict_all(): %zu open vals", cache_list_.size());
00205         
00206         for (typename CacheList::iterator i = cache_list_.begin(); 
00207              i != cache_list_.end(); ++i)
00208         {
00209             if (i->pin_count_ > 0) {
00210                 log_warn("evict_all(): evicting %s with pin count %d",
00211                          InlineFormatter<_Key>().format(i->key_),
00212                          i->pin_count_);
00213             } else {
00214                 log_debug("evict_all(): evicting %s",
00215                           InlineFormatter<_Key>().format(i->key_));
00216             }
00217 
00218             _EvictFcn e;
00219             e(i->key_, i->val_);
00220         }
00221 
00222         cache_list_.clear();
00223         cache_map_.clear();
00224     }
00225 
00229     class ScopedUnpin {
00230     public:
00231         ScopedUnpin(Cache* cache, const _Key& key)
00232             : cache_(cache), key_(key) {}
00233 
00234         ~ScopedUnpin()
00235         {
00236             cache_->unpin(key_);
00237         }
00238 
00239     private:
00240         Cache* cache_;
00241         _Key   key_;
00242     };
00243 
00244 
00245 private:
00246     SpinLock lock_;
00247 
00248     CacheList cache_list_;
00249     CacheMap  cache_map_;
00250 
00251     size_t max_;
00252 
00259     bool evict_last()
00260     {
00261         bool found = false;
00262         typename CacheList::iterator i;
00263         for (i = cache_list_.begin(); i != cache_list_.end(); ++i)
00264         {
00265             if (i->pin_count_ == 0) {
00266                 found = true;
00267                 break;
00268             }
00269         }
00270         
00271         if (found) 
00272         {
00273             log_debug("evict_last(): evicting %s size=%zu",
00274                       InlineFormatter<_Key>().format(i->key_),
00275                       cache_map_.size());
00276             _EvictFcn e;
00277             e(i->key_, i->val_);
00278             cache_map_.erase(i->key_);
00279             cache_list_.erase(i);
00280         }
00281         else
00282         {
00283             log_warn("evict_last(): all entries are busy! size=%zu",
00284                      cache_map_.size());
00285             return false;
00286         }
00287         
00288         return true;
00289     }
00290 };
00291 
00292 } // namespace oasys
00293 
00294 #endif /* __CACHE_H__ */

Generated on Thu Jun 7 12:54:26 2007 for DTN Reference Implementation by  doxygen 1.5.1