lru-cache.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_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 <glog/logging.h>
#include <list>
#include <map>
#include <stack>

#include "gutil/macros.h"
#include "util/spinlock.h"

namespace impala {

template<typename Key, typename Value>
class FifoMultimap {
 public:
  typedef std::pair<Key, Value> ValueType;

  typedef void (*DeleterFn)(Value*);

  FifoMultimap(size_t capacity, const DeleterFn& deleter = &FifoMultimap::DummyDeleter)
      : capacity_(capacity), deleter_(deleter) {}

  ~FifoMultimap();

  void Put(const Key& k, const Value& v);

  bool Pop(const Key& k, Value* out);

  size_t size(){
    boost::lock_guard<SpinLock> g(lock_);
    return cache_.size();
  }

  size_t capacity() const { return capacity_; }

 private:
  DISALLOW_COPY_AND_ASSIGN(FifoMultimap);

  const size_t capacity_;

  const DeleterFn deleter_;

  SpinLock lock_;

  typedef std::list<ValueType> ListType;

  ListType lru_list_;

  typedef std::multimap<Key, typename ListType::iterator> MapType;

  MapType cache_;

  void EvictValue();

  static void DummyDeleter(Value* v) {}
};

}

#include "lru-cache.inline.h"

#endif  // IMPALA_UTIL_LRU_CACHE_H_