| // Licensed to the Apache Software Foundation (ASF) under one |
| // or more contributor license agreements. See the NOTICE file |
| // distributed with this work for additional information |
| // regarding copyright ownership. The ASF licenses this file |
| // to you under the Apache License, Version 2.0 (the |
| // "License"); you may not use this file except in compliance |
| // with the License. You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, |
| // software distributed under the License is distributed on an |
| // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| // KIND, either express or implied. See the License for the |
| // specific language governing permissions and limitations |
| // under the License. |
| |
| #ifndef IMPALA_UTIL_LRU_CACHE_H_ |
| #define IMPALA_UTIL_LRU_CACHE_H_ |
| |
| #include <boost/optional.hpp> |
| #include <boost/thread.hpp> |
| #include <boost/thread/mutex.hpp> |
| #include <boost/unordered_map.hpp> |
| #include <list> |
| #include <map> |
| #include <stack> |
| |
| #include "gutil/macros.h" |
| #include "util/spinlock.h" |
| |
| namespace impala { |
| |
| /// Implementation of a FifoMultimap. |
| /// |
| /// The FifoMultimap is a cache-like data structure that keeps `capacity` number of |
| /// key-value pairs organized and accessible by key allowing multiple values per key. If |
| /// capacity is reached, key-value pairs are evicted in the least recently added order. |
| /// |
| /// When accessing the values that have identical keys (via Pop(k)), values are typically |
| /// returned in LIFO order of this key. However, this property can only be guaranteed when |
| /// compiled with C++11 enabled. The motivation for accessing values in this particular |
| /// order is to avoid keeping all values of a particular key hot, even though only a |
| /// subset of the values is actually used. |
| /// |
| /// On destruction of this class all resources are freed using the optional deleter |
| /// function. |
| /// |
| /// This class is thread-safe and some methods may block under contention. This class |
| /// cannot be copied or assigned. |
| /// |
| /// Example of a cache with capacity 3: |
| /// |
| /// * First `<K1, V1>` is added to the cache, then `<K2, V2>`, `<K2, V3>`. |
| /// |
| /// Eviction case: If a new key value pair is added `<K1, V1>` will be evicted as it |
| /// is the oldest entry. (FIFO) |
| /// |
| /// Element access: If `K2` is accessed, `V3` will be returned first. (LIFO) |
| /// |
| /// This class is thread-safe and protects its members using a spin lock. |
| template<typename Key, typename Value> |
| class FifoMultimap { |
| public: |
| typedef std::pair<Key, Value> ValueType; |
| |
| /// Deleter function type used to allow cleanup of resources held by Value when it is |
| /// evicted. This method should only be used if it is not possible to embed the |
| /// cleanup logic in the Value class itself. |
| typedef void (*DeleterFn)(Value*); |
| |
| /// Instantiates the collection with an upper bound of `capacity` key-value pairs stored |
| /// in the FifoMultimap and a `deleter` function pointer that can be used to free resources |
| /// when a value is evicted from the FifoMultimap. |
| FifoMultimap(size_t capacity, const DeleterFn& deleter = &FifoMultimap::DummyDeleter) |
| : capacity_(capacity), deleter_(deleter), size_(0) {} |
| |
| /// Walk the list of elements and call the deleter function for each element. |
| ~FifoMultimap(); |
| |
| /// Add a key-value pair to the collection. Uniqueness of keys is not enforced. If the |
| /// capacity is exceeded the oldest element will be evicted. |
| void Put(const Key& k, const Value& v); |
| |
| /// Accesses an element of the collection by key and returns the value. In the process |
| /// the key-value pair is removed from the collection. If the element is not found, |
| /// returns boost::none. |
| /// |
| /// Typically, this will return the last element that was added under key `k` in case of |
| /// duplicate keys. |
| bool Pop(const Key& k, Value* out); |
| |
| /// Returns the total number of entries in the collection. |
| size_t size(){ |
| boost::lock_guard<SpinLock> g(lock_); |
| return cache_.size(); |
| } |
| |
| /// Returns the capacity of the cache |
| size_t capacity() const { return capacity_; } |
| |
| private: |
| DISALLOW_COPY_AND_ASSIGN(FifoMultimap); |
| |
| /// Total capacity, cannot be changed at run-time. |
| const size_t capacity_; |
| |
| const DeleterFn deleter_; |
| |
| /// Protects access to cache_ and lru_list_. |
| SpinLock lock_; |
| |
| typedef std::list<ValueType> ListType; |
| |
| /// The least recently added item is stored at the beginning of the list. The length of |
| /// the list is limited to `capacity` number of elements. New elements are always |
| /// appended to the end of the list. |
| ListType lru_list_; |
| |
| typedef std::multimap<Key, typename ListType::iterator> MapType; |
| |
| /// Underlying associative container, that maps a key to an entry in the recently used |
| /// list. The iterator on the list is only invalidated if the key-value pair is removed. |
| MapType cache_; |
| |
| /// Number of elements stored in the cache. |
| size_t size_; |
| |
| /// Evicts the least recently added element from the cache. First, the element is |
| /// removed from both internal collections and as a last step the `deleter_` function is |
| /// called to free potentially acquired resources. |
| void EvictValue(); |
| |
| static void DummyDeleter(Value* v) {} |
| }; |
| |
| } |
| |
| #include "lru-cache.inline.h" |
| |
| #endif // IMPALA_UTIL_LRU_CACHE_H_ |