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 9 * with the License. You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, 14 * software distributed under the License is distributed on an 15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16 * KIND, either express or implied. See the License for the 17 * specific language governing permissions and limitations 18 * under the License. 19 * 20 *************************************************************/ 21 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> 31 32 #include "boost/noncopyable.hpp" 33 #include "osl/diagnose.h" 34 #include "sal/types.h" 35 36 namespace binaryurp { 37 38 namespace cache { 39 40 enum { size = 256, ignore = 0xFFFF }; 41 42 } 43 44 template< typename T > class Cache: private boost::noncopyable { 45 public: 46 explicit Cache(std::size_t size): 47 size_(size), first_(map_.end()), last_(map_.end()) 48 { 49 OSL_ASSERT(size < cache::ignore); 50 } 51 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; 104 } 105 106 private: 107 struct Entry; 108 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_; 123 Map map_; 124 typename Map::iterator first_; 125 typename Map::iterator last_; 126 }; 127 128 } 129 130 #endif 131