|
Impala
Impalaistheopensource,nativeanalyticdatabaseforApacheHadoop.
|
|
Impala
Impalaistheopensource,nativeanalyticdatabaseforApacheHadoop.
|
#include <lru-cache.h>
Public Types | |
| typedef std::pair< Key, Value > | ValueType |
| typedef void(* | DeleterFn )(Value *) |
Public Member Functions | |
| FifoMultimap (size_t capacity, const DeleterFn &deleter=&FifoMultimap::DummyDeleter) | |
| ~FifoMultimap () | |
| Walk the list of elements and call the deleter function for each element. More... | |
| void | Put (const Key &k, const Value &v) |
| bool | Pop (const Key &k, Value *out) |
| size_t | size () |
| Returns the total number of entries in the collection. More... | |
| size_t | capacity () const |
| Returns the capacity of the cache. More... | |
Private Types | |
| typedef std::list< ValueType > | ListType |
| typedef std::multimap< Key, typename ListType::iterator > | MapType |
Private Member Functions | |
| DISALLOW_COPY_AND_ASSIGN (FifoMultimap) | |
| void | EvictValue () |
Static Private Member Functions | |
| static void | DummyDeleter (Value *v) |
Private Attributes | |
| const size_t | capacity_ |
| Total capacity, cannot be changed at run-time. More... | |
| const DeleterFn | deleter_ |
| SpinLock | lock_ |
| Protects access to cache_ and lru_list_. More... | |
| ListType | lru_list_ |
| MapType | cache_ |
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:
<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.
Definition at line 61 of file lru-cache.h.
| typedef void(* impala::FifoMultimap< Key, Value >::DeleterFn)(Value *) |
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.
Definition at line 68 of file lru-cache.h.
|
private |
Definition at line 111 of file lru-cache.h.
|
private |
Definition at line 118 of file lru-cache.h.
| typedef std::pair<Key, Value> impala::FifoMultimap< Key, Value >::ValueType |
Definition at line 63 of file lru-cache.h.
|
inline |
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.
Definition at line 73 of file lru-cache.h.
| impala::FifoMultimap< Key, Value >::~FifoMultimap | ( | ) |
Walk the list of elements and call the deleter function for each element.
Definition at line 21 of file lru-cache.inline.h.
|
inline |
Returns the capacity of the cache.
Definition at line 98 of file lru-cache.h.
References impala::FifoMultimap< Key, Value >::capacity_.
Referenced by TEST().
|
private |
|
inlinestaticprivate |
Definition at line 129 of file lru-cache.h.
|
private |
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.
Definition at line 60 of file lru-cache.inline.h.
| bool impala::FifoMultimap< Key, Value >::Pop | ( | const Key & | k, |
| Value * | out | ||
| ) |
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.
Definition at line 47 of file lru-cache.inline.h.
References impala::lock_.
Referenced by ParallelPut(), and TEST().
| void impala::FifoMultimap< Key, Value >::Put | ( | const Key & | k, |
| const Value & | v | ||
| ) |
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.
Definition at line 29 of file lru-cache.inline.h.
References impala::lock_.
Referenced by ParallelPut(), and TEST().
|
inline |
Returns the total number of entries in the collection.
Definition at line 92 of file lru-cache.h.
References impala::FifoMultimap< Key, Value >::cache_, and impala::FifoMultimap< Key, Value >::lock_.
Referenced by TEST().
|
private |
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.
Definition at line 122 of file lru-cache.h.
Referenced by impala::FifoMultimap< Key, Value >::size().
|
private |
Total capacity, cannot be changed at run-time.
Definition at line 104 of file lru-cache.h.
Referenced by impala::FifoMultimap< Key, Value >::capacity().
|
private |
Definition at line 106 of file lru-cache.h.
|
private |
Protects access to cache_ and lru_list_.
Definition at line 109 of file lru-cache.h.
Referenced by impala::FifoMultimap< Key, Value >::size().
|
private |
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.
Definition at line 116 of file lru-cache.h.
1.8.6