1 /************************************************************************* 2 * 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * Copyright 2000, 2011 Oracle and/or its affiliates. 6 * 7 * OpenOffice.org - a multi-platform office productivity suite 8 * 9 * This file is part of OpenOffice.org. 10 * 11 * OpenOffice.org is free software: you can redistribute it and/or modify 12 * it under the terms of the GNU Lesser General Public License version 3 13 * only, as published by the Free Software Foundation. 14 * 15 * OpenOffice.org is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License version 3 for more details 19 * (a copy is included in the LICENSE file that accompanied this code). 20 * 21 * You should have received a copy of the GNU Lesser General Public License 22 * version 3 along with OpenOffice.org. If not, see 23 * <http://www.openoffice.org/license.html> 24 * for a copy of the LGPLv3 License. 25 * 26 ************************************************************************/ 27 28 #ifndef INCLUDED_BINARYURP_SOURCE_CACHE_HXX 29 #define INCLUDED_BINARYURP_SOURCE_CACHE_HXX 30 31 #include "sal/config.h" 32 33 #include <cstddef> 34 #include <map> 35 36 #include "boost/noncopyable.hpp" 37 #include "osl/diagnose.h" 38 #include "sal/types.h" 39 40 namespace binaryurp { 41 42 namespace cache { 43 44 enum { size = 256, ignore = 0xFFFF }; 45 46 } 47 48 template< typename T > class Cache: private boost::noncopyable { 49 public: 50 explicit Cache(std::size_t size): 51 size_(size), first_(map_.end()), last_(map_.end()) 52 { 53 OSL_ASSERT(size < cache::ignore); 54 } 55 56 sal_uInt16 add(T const & content, bool * found) { 57 OSL_ASSERT(found != 0); 58 typename Map::iterator i(map_.find(content)); 59 *found = i != map_.end(); 60 if (i == map_.end()) { 61 typename Map::size_type n = map_.size(); 62 if (n < size_) { 63 i = 64 (map_.insert( 65 typename Map::value_type( 66 content, 67 Entry( 68 static_cast< sal_uInt16 >(n), map_.end(), 69 first_)))). 70 first; 71 if (first_ == map_.end()) { 72 last_ = i; 73 } else { 74 first_->second.prev = i; 75 } 76 first_ = i; 77 } else if (last_ != map_.end()) { 78 i = 79 (map_.insert( 80 typename Map::value_type( 81 content, 82 Entry(last_->second.index, map_.end(), first_)))). 83 first; 84 first_->second.prev = i; 85 first_ = i; 86 typename Map::iterator j(last_); 87 last_ = last_->second.prev; 88 last_->second.next = map_.end(); 89 map_.erase(j); 90 } else { 91 // Reached iff size_ == 0: 92 return cache::ignore; 93 } 94 } else if (i != first_) { 95 // Move to front (reached only if size_ > 1): 96 i->second.prev->second.next = i->second.next; 97 if (i->second.next == map_.end()) { 98 last_ = i->second.prev; 99 } else { 100 i->second.next->second.prev = i->second.prev; 101 } 102 i->second.prev = map_.end(); 103 i->second.next = first_; 104 first_->second.prev = i; 105 first_ = i; 106 } 107 return i->second.index; 108 } 109 110 private: 111 struct Entry; 112 113 typedef std::map< T, Entry > Map; 114 115 struct Entry { 116 sal_uInt16 index; 117 typename Map::iterator prev; 118 typename Map::iterator next; 119 120 Entry( 121 sal_uInt16 theIndex, typename Map::iterator thePrev, 122 typename Map::iterator theNext): 123 index(theIndex), prev(thePrev), next(theNext) {} 124 }; 125 126 std::size_t size_; 127 Map map_; 128 typename Map::iterator first_; 129 typename Map::iterator last_; 130 }; 131 132 } 133 134 #endif 135