cache.hxx (3638366c) | cache.hxx (7f80ef06) |
---|---|
1/************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance --- 13 unchanged lines hidden (view full) --- 22 23 24#ifndef INCLUDED_BINARYURP_SOURCE_CACHE_HXX 25#define INCLUDED_BINARYURP_SOURCE_CACHE_HXX 26 27#include "sal/config.h" 28 29#include <cstddef> | 1/************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance --- 13 unchanged lines hidden (view full) --- 22 23 24#ifndef INCLUDED_BINARYURP_SOURCE_CACHE_HXX 25#define INCLUDED_BINARYURP_SOURCE_CACHE_HXX 26 27#include "sal/config.h" 28 29#include <cstddef> |
30#include <map> | 30#include <list> 31#ifdef USE_UNORDERED_MAP 32 #include <unordered_map> 33#else 34 #include <map> 35#endif |
31 32#include "boost/noncopyable.hpp" 33#include "osl/diagnose.h" 34#include "sal/types.h" 35 36namespace binaryurp { 37 38namespace cache { 39 40enum { size = 256, ignore = 0xFFFF }; 41 42} 43 | 36 37#include "boost/noncopyable.hpp" 38#include "osl/diagnose.h" 39#include "sal/types.h" 40 41namespace binaryurp { 42 43namespace cache { 44 45enum { size = 256, ignore = 0xFFFF }; 46 47} 48 |
44template< typename T > class Cache: private boost::noncopyable { | 49template< typename T > class Cache : private boost::noncopyable { |
45public: | 50public: |
51 typedef sal_uInt16 IdxType; 52 |
|
46 explicit Cache(std::size_t size): | 53 explicit Cache(std::size_t size): |
47 size_(size), first_(map_.end()), last_(map_.end()) | 54 size_(size) |
48 { 49 OSL_ASSERT(size < cache::ignore); 50 } 51 | 55 { 56 OSL_ASSERT(size < cache::ignore); 57 } 58 |
52 sal_uInt16 add(T const & content, bool * found) { 53 OSL_ASSERT(found != 0); 54 typename Map::iterator i(map_.find(content)); 55 *found = i != map_.end(); 56 if (i == map_.end()) { 57 typename Map::size_type n = map_.size(); 58 if (n < size_) { 59 i = 60 (map_.insert( 61 typename Map::value_type( 62 content, 63 Entry( 64 static_cast< sal_uInt16 >(n), map_.end(), 65 first_)))). 66 first; 67 if (first_ == map_.end()) { 68 last_ = i; 69 } else { 70 first_->second.prev = i; 71 } 72 first_ = i; 73 } else if (last_ != map_.end()) { 74 i = 75 (map_.insert( 76 typename Map::value_type( 77 content, 78 Entry(last_->second.index, map_.end(), first_)))). 79 first; 80 first_->second.prev = i; 81 first_ = i; 82 typename Map::iterator j(last_); 83 last_ = last_->second.prev; 84 last_->second.next = map_.end(); 85 map_.erase(j); 86 } else { 87 // Reached iff size_ == 0: 88 return cache::ignore; 89 } 90 } else if (i != first_) { 91 // Move to front (reached only if size_ > 1): 92 i->second.prev->second.next = i->second.next; 93 if (i->second.next == map_.end()) { 94 last_ = i->second.prev; 95 } else { 96 i->second.next->second.prev = i->second.prev; 97 } 98 i->second.prev = map_.end(); 99 i->second.next = first_; 100 first_->second.prev = i; 101 first_ = i; 102 } 103 return i->second.index; | 59 IdxType add( const T& rContent, bool* pbFound) { 60 OSL_ASSERT( pbFound != NULL); 61 if( !size_) { 62 *pbFound = false; 63 return cache::ignore; 64 } 65 // try to insert into the map 66 list_.push_front( rContent); // create a temp entry 67 typedef std::pair<typename LruList::iterator, IdxType> MappedType; 68 typedef std::pair<typename LruItMap::iterator,bool> MapPair; 69 MapPair aMP = map_.insert( MappedType( list_.begin(), 0)); 70 *pbFound = !aMP.second; 71 72 if( !aMP.second) { // insertion not needed => found the entry 73 list_.pop_front(); // remove the temp entry 74 list_.splice( list_.begin(), list_, aMP.first->first); // the found entry is moved to front 75 return aMP.first->second; 76 } 77 78 // test insertion successful => it was new so we keep it 79 IdxType n = static_cast<IdxType>( map_.size() - 1); 80 if( n >= size_) { // cache full => replace the LRU entry 81 // find the least recently used element in the map 82 typename LruItMap::iterator it = map_.find( --list_.end()); 83 n = it->second; 84 map_.erase( it); // remove it from the map 85 list_.pop_back(); // remove from the list 86 } 87 aMP.first->second = n; 88 return n; |
104 } 105 106private: | 89 } 90 91private: |
107 struct Entry; | 92 typedef std::list<T> LruList; // last recently used list 93 typedef typename LruList::iterator LruListIt; 94#ifdef URPCACHE_USES_UNORDERED_MAP 95 struct HashT{ size_t operator()( const LruListIt& rA) const { return hash(*rA;);}; 96 struct EqualT{ bool operator()( const LruListIt& rA, const LruListIt& rB) const { return *rA==*rB;}}; 97 typedef ::std::unordered_map< LruListIt, IdxType, HashT, EqualT > LruItMap; // a map into a LruList 98#else 99 struct CmpT{ bool operator()( const LruListIt& rA, const LruListIt& rB) const { return (*rA<*rB);}}; 100 typedef ::std::map< LruListIt, IdxType, CmpT > LruItMap; // a map into a LruList 101#endif |
108 | 102 |
109 typedef std::map< T, Entry > Map; 110 111 struct Entry { 112 sal_uInt16 index; 113 typename Map::iterator prev; 114 typename Map::iterator next; 115 116 Entry( 117 sal_uInt16 theIndex, typename Map::iterator thePrev, 118 typename Map::iterator theNext): 119 index(theIndex), prev(thePrev), next(theNext) {} 120 }; 121 | |
122 std::size_t size_; | 103 std::size_t size_; |
123 Map map_; 124 typename Map::iterator first_; 125 typename Map::iterator last_; | 104 LruItMap map_; 105 LruList list_; |
126}; 127 128} 129 130#endif | 106}; 107 108} 109 110#endif |
111 |
|