1/********************************************************************
2 * Copyright (c) 2013 - 2014, Pivotal Inc.
3 * All rights reserved.
4 *
5 * Author: Zhanwei Wang
6 ********************************************************************/
7/********************************************************************
8 * 2014 -
9 * open source under Apache License Version 2.0
10 ********************************************************************/
11/**
12 * Licensed to the Apache Software Foundation (ASF) under one
13 * or more contributor license agreements. See the NOTICE file
14 * distributed with this work for additional information
15 * regarding copyright ownership. The ASF licenses this file
16 * to you under the Apache License, Version 2.0 (the
17 * "License"); you may not use this file except in compliance
18 * with the License. You may obtain a copy of the License at
19 *
20 * http://www.apache.org/licenses/LICENSE-2.0
21 *
22 * Unless required by applicable law or agreed to in writing, software
23 * distributed under the License is distributed on an "AS IS" BASIS,
24 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
25 * See the License for the specific language governing permissions and
26 * limitations under the License.
27 */
28#ifndef _HDFS_LIBHDFS3_COMMON_LRUMAP_H_
29#define _HDFS_LIBHDFS3_COMMON_LRUMAP_H_
30
31#include "Unordered.h"
32#include "Thread.h"
33
34#include <list>
35
36namespace Hdfs {
37namespace Internal {
38
39template <typename K, typename V>
40class LruMap {
41public:
42 typedef K KeyType;
43 typedef V ValueType;
44 typedef std::pair<K, V> ItmeType;
45 typedef std::list<ItmeType> ListType;
46 typedef unordered_map<K, typename ListType::iterator> MapType;
47
48public:
49 LruMap() : count(0), maxSize(1000) {
50 }
51
52 LruMap(size_t size) : count(0), maxSize(size) {
53 }
54
55 ~LruMap() {
56 lock_guard<mutex> lock(mut);
57 map.clear();
58 list.clear();
59 }
60
61 void setMaxSize(size_t s) {
62 lock_guard<mutex> lock(mut);
63 maxSize = s;
64
65 for (size_t i = count; i > s; --i) {
66 map.erase(list.back().first);
67 list.pop_back();
68 --count;
69 }
70 }
71
72 void insert(const KeyType& key, const ValueType& value) {
73 lock_guard<mutex> lock(mut);
74 typename MapType::iterator it = map.find(key);
75
76 if (it != map.end()) {
77 --count;
78 list.erase(it->second);
79 }
80
81 list.push_front(std::make_pair(key, value));
82 map[key] = list.begin();
83 ++count;
84
85 if (count > maxSize) {
86 map.erase(list.back().first);
87 list.pop_back();
88 --count;
89 }
90 }
91
92 void erase(const KeyType& key) {
93 lock_guard<mutex> lock(mut);
94 typename MapType::iterator it = map.find(key);
95
96 if (it != map.end()) {
97 list.erase(it->second);
98 map.erase(it);
99 --count;
100 }
101 }
102
103 bool find(const KeyType& key, ValueType* value) {
104 lock_guard<mutex> lock(mut);
105 return findAndEraseInternal(key, value, false);
106 }
107
108 bool findAndErase(const KeyType& key, ValueType* value) {
109 lock_guard<mutex> lock(mut);
110 return findAndEraseInternal(key, value, true);
111 }
112
113 size_t size() {
114 lock_guard<mutex> lock(mut);
115 return count;
116 }
117
118private:
119 bool findAndEraseInternal(const KeyType& key, ValueType* value,
120 bool erase) {
121 typename MapType::iterator it = map.find(key);
122
123 if (it != map.end()) {
124 *value = it->second->second;
125 list.erase(it->second);
126
127 if (erase) {
128 map.erase(it);
129 --count;
130 } else {
131 list.push_front(std::make_pair(key, *value));
132 map[key] = list.begin();
133 }
134
135 return true;
136 }
137
138 return false;
139 }
140
141private:
142 size_t count;
143 size_t maxSize;
144 ListType list;
145 MapType map;
146 mutex mut;
147};
148}
149}
150#endif /* _HDFS_LIBHDFS3_COMMON_LRU_H_ */
151