diff options
author | Herbert Dürr <hdu@apache.org> | 2013-05-08 17:26:08 +0000 |
---|---|---|
committer | Tor Lillqvist <tml@iki.fi> | 2013-05-28 09:27:01 +0300 |
commit | 08bb8fca4144608237418d64b1479840c408256f (patch) | |
tree | d9ccc0b7af4e6fa8020573e863c8e83dc3915c89 /binaryurp/source/cache.hxx | |
parent | da1dea9ae24fd4b17c54646f158c617a098291aa (diff) |
#i122208# replace the binaryurp cache for improved C++ compatibility
Failing to instantiatie incomplete types like the Map::iterator in
binaryurp Cache's Entry members is allowed by the C++ standard.
The rewrite makes it more compliant with other C++ compilers/STLs.
And interesting alternative would be to use boost's multi_index_container.
git-svn-id: http://svn.apache.org/repos/asf/openoffice/branches/rejuvenate01@1480367 13f79535-47bb-0310-9956-ffa450edef68
Diffstat (limited to 'binaryurp/source/cache.hxx')
-rw-r--r-- | binaryurp/source/cache.hxx | 112 |
1 files changed, 41 insertions, 71 deletions
diff --git a/binaryurp/source/cache.hxx b/binaryurp/source/cache.hxx index 05c0069a41f7..7e5ba899cc92 100644 --- a/binaryurp/source/cache.hxx +++ b/binaryurp/source/cache.hxx @@ -25,6 +25,7 @@ #include <cassert> #include <cstddef> #include <map> +#include <list> #include "boost/noncopyable.hpp" #include "sal/types.h" @@ -37,88 +38,57 @@ enum { size = 256, ignore = 0xFFFF }; } -template< typename T > class Cache: private boost::noncopyable { +template< typename T > class Cache : private boost::noncopyable { public: + typedef sal_uInt16 IdxType; + explicit Cache(std::size_t size): - size_(size), first_(map_.end()), last_(map_.end()) + size_(size) { assert(size < cache::ignore); } - sal_uInt16 add(T const & content, bool * found) { - assert(found != 0); - typename Map::iterator i(map_.find(content)); - *found = i != map_.end(); - if (i == map_.end()) { - typename Map::size_type n = map_.size(); - if (n < size_) { - i = - (map_.insert( - typename Map::value_type( - content, - Entry( - static_cast< sal_uInt16 >(n), map_.end(), - first_)))). - first; - if (first_ == map_.end()) { - last_ = i; - } else { - first_->second.prev = i; - } - first_ = i; - } else if (last_ != map_.end()) { - i = - (map_.insert( - typename Map::value_type( - content, - Entry(last_->second.index, map_.end(), first_)))). - first; - first_->second.prev = i; - first_ = i; - typename Map::iterator j(last_); - last_ = last_->second.prev; - last_->second.next = map_.end(); - map_.erase(j); - } else { - // Reached iff size_ == 0: - return cache::ignore; - } - } else if (i != first_) { - // Move to front (reached only if size_ > 1): - i->second.prev->second.next = i->second.next; - if (i->second.next == map_.end()) { - last_ = i->second.prev; - } else { - i->second.next->second.prev = i->second.prev; - } - i->second.prev = map_.end(); - i->second.next = first_; - first_->second.prev = i; - first_ = i; - } - return i->second.index; + IdxType add( const T& rContent, bool* pbFound) { + assert( pbFound != NULL); + if( !size_) { + *pbFound = false; + return cache::ignore; + } + // try to insert into the map + list_.push_front( rContent); // create a temp entry + typedef std::pair<typename LruList::iterator, IdxType> MappedType; + typedef std::pair<typename LruItMap::iterator,bool> MapPair; + MapPair aMP = map_.insert( MappedType( list_.begin(), 0)); + *pbFound = !aMP.second; + + if( !aMP.second) { // insertion not needed => found the entry + list_.pop_front(); // remove the temp entry + list_.splice( list_.begin(), list_, aMP.first->first); // the found entry is moved to front + return aMP.first->second; + } + + // test insertion successful => it was new so we keep it + IdxType n = static_cast<IdxType>( map_.size() - 1); + if( n >= size_) { // cache full => replace the LRU entry + // find the least recently used element in the map + typename LruItMap::iterator it = map_.find( --list_.end()); + n = it->second; + map_.erase( it); // remove it from the map + list_.pop_back(); // remove from the list + } + aMP.first->second = n; + return n; } private: - struct Entry; - - typedef std::map< T, Entry > Map; - - struct Entry { - sal_uInt16 index; - typename Map::iterator prev; - typename Map::iterator next; - - Entry( - sal_uInt16 theIndex, typename Map::iterator thePrev, - typename Map::iterator theNext): - index(theIndex), prev(thePrev), next(theNext) {} - }; + typedef std::list<T> LruList; // last recently used list + typedef typename LruList::iterator LruListIt; + struct CmpT{ bool operator()( const LruListIt& rA, const LruListIt& rB) const { return (*rA<*rB);}}; + typedef ::std::map< LruListIt, IdxType, CmpT > LruItMap; // a map into a LruList std::size_t size_; - Map map_; - typename Map::iterator first_; - typename Map::iterator last_; + LruItMap map_; + LruList list_; }; } |