lru-cache.inline.h

Go to the documentation of this file.

// Copyright 2015 Cloudera Inc.
//
// Licensed 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_INLINE_H_
#define IMPALA_UTIL_LRU_CACHE_INLINE_H_

namespace impala {

template <typename Key, typename Value>
FifoMultimap<Key, Value>::~FifoMultimap() {
  for (typename ListType::iterator b = lru_list_.begin(),
      e = lru_list_.end(); b != e; ++b) {
    deleter_(&(b->second));
  }
}

template <typename Key, typename Value>
void FifoMultimap<Key, Value>::Put(const Key& k, const Value& v) {
  boost::lock_guard<SpinLock> g(lock_);
  if (lru_list_.size() >= capacity_) EvictValue();
  const ValueType& kv_pair = std::make_pair(k, v);
  const typename MapType::value_type& val =
      std::make_pair(k, lru_list_.insert(lru_list_.end(), kv_pair));
  // Find an insert hint to use with the insert operation
  typename MapType::iterator it = cache_.lower_bound(k);
  if (it == cache_.end() || it->first != k) {
    cache_.insert(val);
  } else {
    // If the insert hint is sufficiently good, the element will be inserted before in the
    // sequence of elements having the same key
    cache_.insert(it, val);
  }
}

template <typename Key, typename Value>
bool FifoMultimap<Key, Value>::Pop(const Key& k, Value* out) {
  boost::lock_guard<SpinLock> g(lock_);
  // Find the first value under key k.
  typename MapType::iterator it = cache_.lower_bound(k);
  if (it == cache_.end() || it->first != k) return false;
  typename ListType::iterator lit = it->second;
  cache_.erase(it);
  *out = lit->second;
  lru_list_.erase(lit);
  return true;
}

template <typename Key, typename Value>
void FifoMultimap<Key, Value>::EvictValue() {
  typename ListType::iterator to_evict = lru_list_.begin();
  // Find all elements under this key, until C++11 the order of the elements is not
  // guaranteed.
  std::pair<typename MapType::iterator, typename MapType::iterator> range =
      cache_.equal_range(to_evict->first);
  // Search until the value is found in the range of the same key.
  while (range.first != range.second) {
    if (range.first->second == to_evict) {
      cache_.erase(range.first);
      break;
    }
    ++range.first;
  }
  DCHECK(range.first != range.second); // LCOV_EXCL_LINE
  deleter_(&(*to_evict).second);
  lru_list_.erase(to_evict);
}

}

#endif // IMPALA_UTIL_LRU_CACHE_INLINE_H_