// $Id $ // // Copyright (C) 2005 Christian Kreibich . // // Permission is hereby granted, free of charge, to any person obtaining a copy // of this software and associated documentation files (the "Software"), to // deal in the Software without restriction, including without limitation the // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or // sell copies of the Software, and to permit persons to whom the Software is // furnished to do so, subject to the following conditions: // // The above copyright notice and this permission notice shall be included in // all copies of the Software and its documentation and acknowledgment shall be // given in the documentation and software packages that this Software was // used. // // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL // THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER // IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN // CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. // #ifndef _EXT_CACHE_H #define _EXT_CACHE_H 1 // cache -- an STL-style cache implementation. // Version: 1.0, released Wed Jan 18 17:39:00 GMT 2006 // // This is a reasonably generic implementation of a cache mapping keys to // values. Think of it as a size-limited map with LRU eviction policy, plus some // additional features for tracking eviction of members and gathering statistics. // // Its implementation wraps keys and values type in a "node" structure that // also maintains the LRU pointer, and abstracts away this encapsulation at // the user-visible interface. Internally, the cache is implemented as a // set of the node structures. Lookup times are therfore like in std::sets, // and there are *no* additional assignment overheads due to the encapsulation. // // This code is trying to follow the STL coding style laid out at // http://gcc.gnu.org/onlinedocs/libstdc++/17_intro/C++STYLE // // ChangeLog: // // - Wed Jan 18 17:39:00 GMT 2006 // * Fixed a bug in the age list. // Not currently used, but pulled in for compatible use of namespace // #include #include // A cache is a set on steriods. #include // for less<>. // Default cache size. // #define CACHE_MAX_SIZE 10000 namespace std { template class cache_iterator; template > class cache { private: // These are the key-encapsulating "node" structures. They are // optimized to minimize copying. For lookup purposes, no real // key assignment is done, only reference assignment. For storing // values, this is not enough, so the derived _FullNode struct // can store full keys. _FullNode is further optimized by storing // key and value in a pair, ready for use in dereferencing as a // std::pair. // struct _Node { _Node(const _Key& __key) : _M_prev(0), _M_next(0), _M_key_ref(__key) { } _Node *_M_prev; _Node *_M_next; const _Key& _M_key_ref; // reference only }; struct _FullNode : public _Node { _FullNode(const _Key& __key, _Val& __val) : _Node(_M_item.first), _M_item(__key,__val) { } pair _M_item; // full storage! }; // Comparison operator that works on pointers to _Nodes and // only looks at the _Key. // struct _NodeCmp : public binary_function<_Node*,_Node*,bool> { _NodeCmp(const _KeyCmp& __key_cmp) : _M_key_cmp(__key_cmp) { } bool operator()(_Node* const& __n1, _Node* const& __n2) const { return _M_key_cmp(__n1->_M_key_ref, __n2->_M_key_ref); } _KeyCmp _M_key_cmp; }; typedef set<_Node*,_NodeCmp> _Set; typedef typename _Set::iterator _SetIt; typedef typename _SetIt::value_type _SetItValue; public: typedef cache<_Key,_Val,_KeyCmp> cache_type; typedef cache_iterator<_Key,_Val,_KeyCmp,_SetIt> iterator; typedef typename _Set::size_type size_type; typedef pair value_type; friend class cache_iterator<_Key,_Val,_KeyCmp,_SetIt>; // A structure for gathering operational statistics. // struct stats { stats() : win(0),hit_rate(0) { } unsigned int win; double hit_rate; }; // Prototype of callbacks for notification of member // eviction. You need this callback in case you need to // manually clean up the key and/or value types stored // in the cache. See cache::set_evict_cb(). // typedef void (*evict_cb_type)(cache_type&, _Key&, _Val&); // Prototype of callbacks for cache hit statistics. // See cache::set_stats_cb(). // typedef void (*stats_cb_type)(cache_type&, const stats&); // Default constructor. // cache() : _M_set(_NodeCmp(_KeyCmp())), _M_max_size(CACHE_MAX_SIZE), _M_youngest(0), _M_oldest(0), _M_evict_cb(0), _M_stats_cb(0), _M_accs(0), _M_succ(0) { } // Constructor with maximum size limit and (optionally) // callback pointers. // cache(unsigned int __max_size, evict_cb_type __evict_cb = 0, stats_cb_type __stats_cb = 0) : _M_set(_NodeCmp(_KeyCmp())), _M_max_size(__max_size), _M_youngest(0), _M_oldest(0), _M_evict_cb(__evict_cb), _M_stats_cb(__stats_cb), _M_accs(0), _M_succ(0) { } ~cache() { for(_SetIt it = _M_set.begin(); it != _M_set.end(); ++it) { _FullNode *node = (_FullNode*) *it; if (_M_evict_cb) _M_evict_cb(*this, const_cast<_Key&>(node->_M_item.first), node->_M_item.second); delete node; } } bool empty() const { return _M_set.empty(); } size_type size() const { return _M_set.size(); } // Adjusts the new maximum number of items contained in the cache. // If the new value is smaller than the old one and items have to // removed in order to get to the new limit, the number of removed // items is returned. // unsigned int _M_adjust_max_size(unsigned int __max_size) { unsigned int __count = 0; _M_max_size = __max_size; while (_M_set.size() > __max_size) { __count++; _M_evict_oldest(); } return __count; } // void set_evict_cb(evict_cb_type __evict_cb) { _M_evict_cb = __evict_cb; } void set_stats_cb(stats_cb_type __stats_cb, unsigned int __stats_win) { _M_reset_stats(); _M_stats_cb = __stats_cb; _M_stats.win = __stats_win; } // Lookup of an element. If the element does not exist, a // default element is created and stored under the given // key. If you want to use this for insertion, note that // it is somewhat slower than insert() below: the additional // cost is one assignment of _Val. // _Val& operator[](const _Key& __key) { _Val __dummy; _FullNode *__node = new _FullNode(__key,__dummy); _SetIt __it = _M_set.find(__node); if (__it == _M_set.end()) { _M_touch(__node); _M_set.insert(__node); if (_M_set.size() > _M_max_size) _M_evict_oldest(); return __node->_M_item.second; } _Val& __result = ((_FullNode*)(*__it))->_M_item.second; delete __node; return __result; } // Attempts to insert a std::pair into the set. // See set::insert()'s documentation for details. // pair insert(const value_type& __x) { _Node *node = new _FullNode(__x.first,const_cast<_Val&>(__x.second)); pair<_SetIt,bool> tmp = _M_set.insert(node); if (tmp.second) { _M_touch(*tmp.first); if (_M_set.size() > _M_max_size) _M_evict_oldest(); } else delete node; return pair(iterator(tmp.first,*this),tmp.second); } // Returns an iterator for the given key. iterator find(const _Key& __key) { // Reference-only -- no copying involved. _Node node(__key); if (_M_stats.win > 0) { _SetIt it = _M_set.find(&node); if (it != _M_set.end()) _M_succ++; _M_accs++; if (_M_accs == _M_stats.win) { if (_M_stats_cb) _M_stats_cb(*this, _M_stats); _M_reset_stats(); } return iterator(it, *this); } return iterator(_M_set.find(&node), *this); } // Begin and end iterators. iterator begin() { return iterator(_M_set.begin(),*this); } iterator end() { return iterator(_M_set.end(),*this); } private: // _M_touch() updates a node's position in the age list, // and inserts new nodes (with both _M_next and _M_prev // equal to 0) as the new youngest node. // void _M_touch(_Node *__node) { // No nodes in age list yet. if ( ! _M_youngest ) { _M_youngest = _M_oldest = __node; __node->_M_prev = __node->_M_next = 0; return; } // Youngest node already, nothing to do. if ( __node == _M_youngest ) return; // Adjust neighbourhood of existing node. if ( __node->_M_prev ) __node->_M_prev->_M_next = __node->_M_next; if ( __node->_M_next ) __node->_M_next->_M_prev = __node->_M_prev; // If it's the oldest node, adjust oldest-node pointer. if ( __node == _M_oldest ) _M_oldest = __node->_M_prev; // Hook in node as new youngest. __node->_M_next = _M_youngest; _M_youngest->_M_prev = __node; __node->_M_prev = 0; _M_youngest = __node; } void _M_evict_oldest() { if ( ! _M_oldest ) return; // Look up the oldest element, and erase it. // Note: we know that the lookup will succeed. _FullNode *__node = (_FullNode*) _M_oldest; // Delete node from set. Do this *before* the callback, since // set::erase() will require accessing the key/val pair, which the evict // callback might destroy. set::erase() won't damage __node though, // since it's a pointer. // _M_set.erase(__node); // Trigger callback, if registered. if ( _M_evict_cb ) _M_evict_cb(*this, const_cast<_Key&>(__node->_M_item.first), __node->_M_item.second); // Adjust age list and delete the node. _M_oldest = _M_oldest->_M_prev; if (_M_oldest) _M_oldest->_M_next = 0; else _M_youngest = 0; delete __node; } void _M_reset_stats() { _M_stats.win = 0; _M_stats.hit_rate = 0; } _Set _M_set; unsigned int _M_max_size; _Node *_M_youngest; _Node *_M_oldest; evict_cb_type _M_evict_cb; stats_cb_type _M_stats_cb; stats _M_stats; unsigned int _M_accs; unsigned int _M_succ; }; template class cache_iterator { public: typedef cache<_Key,_Val,_KeyCmp> cache_type; typedef pair value_type; typedef value_type& reference; typedef value_type* pointer; cache_iterator(_Iterator __it, cache_type& __cache) : _M_it(__it), _M_cache(__cache) { } reference operator*() const { // We brute-force a downcast. We apologize for any inconvenience caused. typename cache_type::_FullNode *__node = (typename cache_type::_FullNode *) *_M_it; // We're using an item in the cache, so make sure to update the // age list. // _M_cache._M_touch(__node); return __node->_M_item; } pointer operator->() const { return &(operator*()); } cache_iterator& operator++() { ++_M_it; return *this; } cache_iterator operator++(int) { return cache_iterator(_M_it++, _M_cache); } cache_iterator& operator--() { --_M_it; return *this; } cache_iterator operator--(int) { return cache_iterator(_M_it--, _M_cache); } const _Iterator& base() const { return _M_it; } private: // _ValType is the type of elements the "real" iterator // works on: just a pointer to cache_type::_Node*s. // typedef typename cache_type::_Node* _ValType; _Iterator _M_it; cache_type& _M_cache; }; template inline bool operator==(const cache_iterator<_Key,_Val,_KeyCmp,_Iterator>& __lhs, const cache_iterator<_Key,_Val,_KeyCmp,_Iterator>& __rhs) { return __lhs.base() == __rhs.base(); } template inline bool operator!=(const cache_iterator<_Key,_Val,_KeyCmp,_Iterator>& __lhs, const cache_iterator<_Key,_Val,_KeyCmp,_Iterator>& __rhs) { return __lhs.base() != __rhs.base(); } } // namespace std #endif /* _EXT_CACHE_H */