Apache Mesos
linkedhashmap.hpp
Go to the documentation of this file.
1 // Licensed under the Apache License, Version 2.0 (the "License");
2 // you may not use this file except in compliance with the License.
3 // You may obtain a copy of the License at
4 //
5 // http://www.apache.org/licenses/LICENSE-2.0
6 //
7 // Unless required by applicable law or agreed to in writing, software
8 // distributed under the License is distributed on an "AS IS" BASIS,
9 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
10 // See the License for the specific language governing permissions and
11 // limitations under the License.
12 
13 #ifndef __STOUT_LINKEDHASHMAP_HPP__
14 #define __STOUT_LINKEDHASHMAP_HPP__
15 
16 #include <list>
17 #include <utility>
18 
19 #include <stout/foreach.hpp>
20 #include <stout/hashmap.hpp>
21 #include <stout/option.hpp>
22 
23 // Implementation of a hashmap that maintains the insertion order of
24 // the keys. Updating a key does not change insertion order.
25 //
26 // TODO(vinod/bmahler): Consider extending from stout::hashmap and/or
27 // having a compatible API with stout::hashmap.
28 template <typename Key, typename Value>
30 {
31 public:
32  typedef std::pair<Key, Value> entry;
33  typedef std::list<entry> list;
35 
36  LinkedHashMap() = default;
37 
39  : entries_(other.entries_)
40  {
41  // Build up the index.
42  for (auto it = entries_.begin(); it != entries_.end(); ++it) {
43  keys_[it->first] = it;
44  }
45  }
46 
48  {
49  clear();
50 
51  entries_ = other.entries_;
52 
53  // Build up the index.
54  for (auto it = entries_.begin(); it != entries_.end(); ++it) {
55  keys_[it->first] = it;
56  }
57 
58  return *this;
59  }
60 
61  // TODO(bmahler): Implement move construction / assignment.
64 
65  Value& operator[] (const Key& key)
66  {
67  if (!keys_.contains(key)) {
68  // Insert a new entry into the list and get a "pointer" to its
69  // location. The initial value is default-constructed.
70  typename list::iterator iter =
71  entries_.insert(entries_.end(), std::make_pair(key, Value()));
72 
73  keys_[key] = iter;
74  }
75 
76  return keys_[key]->second;
77  }
78 
79  Option<Value> get(const Key& key) const
80  {
81  if (keys_.contains(key)) {
82  return keys_.at(key)->second;
83  }
84  return None();
85  }
86 
87  Value& at(const Key& key)
88  {
89  return keys_.at(key)->second;
90  }
91 
92  const Value& at(const Key& key) const
93  {
94  return keys_.at(key)->second;
95  }
96 
97  bool contains(const Key& key) const
98  {
99  return keys_.contains(key);
100  }
101 
102  size_t erase(const Key& key)
103  {
104  if (keys_.contains(key)) {
105  typename list::iterator iter = keys_[key];
106  keys_.erase(key);
107  entries_.erase(iter);
108  return 1;
109  }
110  return 0;
111  }
112 
113  // Returns the keys in the map in insertion order.
114  std::vector<Key> keys() const
115  {
116  std::vector<Key> result;
117  result.reserve(entries_.size());
118 
119  foreach (const entry& entry, entries_) {
120  result.push_back(entry.first);
121  }
122 
123  return result;
124  }
125 
126  // Returns the values in the map in insertion order.
127  std::vector<Value> values() const
128  {
129  std::vector<Value> result;
130  result.reserve(entries_.size());
131 
132  foreach (const entry& entry, entries_) {
133  result.push_back(entry.second);
134  }
135 
136  return result;
137  }
138 
139  size_t size() const
140  {
141  return keys_.size();
142  }
143 
144  bool empty() const
145  {
146  return keys_.empty();
147  }
148 
149  void clear()
150  {
151  entries_.clear();
152  keys_.clear();
153  }
154 
155  // Support for iteration; this allows using `foreachpair` and
156  // related constructs. Note that these iterate over the map in
157  // insertion order.
158  typename list::iterator begin() { return entries_.begin(); }
159  typename list::iterator end() { return entries_.end(); }
160 
161  typename list::const_iterator begin() const { return entries_.cbegin(); }
162  typename list::const_iterator end() const { return entries_.cend(); }
163 
164 private:
165  list entries_; // Key-value pairs ordered by insertion order.
166  map keys_; // Map from key to "pointer" to key's location in list.
167 };
168 
169 
170 #endif // __STOUT_LINKEDHASHMAP_HPP__
bool empty() const
Definition: linkedhashmap.hpp:144
Definition: option.hpp:28
const Value & at(const Key &key) const
Definition: linkedhashmap.hpp:92
LinkedHashMap(const LinkedHashMap< Key, Value > &other)
Definition: linkedhashmap.hpp:38
std::pair< Key, Value > entry
Definition: linkedhashmap.hpp:32
list::const_iterator begin() const
Definition: linkedhashmap.hpp:161
size_t size() const
Definition: linkedhashmap.hpp:139
std::vector< Key > keys() const
Definition: linkedhashmap.hpp:114
list::const_iterator end() const
Definition: linkedhashmap.hpp:162
std::vector< Value > values() const
Definition: linkedhashmap.hpp:127
size_t erase(const Key &key)
Definition: linkedhashmap.hpp:102
hashmap< Key, typename list::iterator > map
Definition: linkedhashmap.hpp:34
list::iterator begin()
Definition: linkedhashmap.hpp:158
Value & at(const Key &key)
Definition: linkedhashmap.hpp:87
Value & operator[](const Key &key)
Definition: linkedhashmap.hpp:65
LinkedHashMap & operator=(const LinkedHashMap< Key, Value > &other)
Definition: linkedhashmap.hpp:47
Definition: none.hpp:27
void clear()
Definition: linkedhashmap.hpp:149
Definition: linkedhashmap.hpp:29
bool contains(const Key &key) const
Definition: linkedhashmap.hpp:97
LinkedHashMap()=default
bool contains(const Key &key) const
Definition: hashmap.hpp:86
list::iterator end()
Definition: linkedhashmap.hpp:159
std::list< entry > list
Definition: linkedhashmap.hpp:33