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  if (this != &other) {
50  clear();
51 
52  entries_ = other.entries_;
53 
54  // Build up the index.
55  for (auto it = entries_.begin(); it != entries_.end(); ++it) {
56  keys_[it->first] = it;
57  }
58  }
59 
60  return *this;
61  }
62 
63  // TODO(bmahler): Implement move construction / assignment.
66 
67  Value& operator[] (const Key& key)
68  {
69  if (!keys_.contains(key)) {
70  // Insert a new entry into the list and get a "pointer" to its
71  // location. The initial value is default-constructed.
72  typename list::iterator iter =
73  entries_.insert(entries_.end(), std::make_pair(key, Value()));
74 
75  keys_[key] = iter;
76  }
77 
78  return keys_[key]->second;
79  }
80 
81  Option<Value> get(const Key& key) const
82  {
83  if (keys_.contains(key)) {
84  return keys_.at(key)->second;
85  }
86  return None();
87  }
88 
89  Value& at(const Key& key)
90  {
91  return keys_.at(key)->second;
92  }
93 
94  const Value& at(const Key& key) const
95  {
96  return keys_.at(key)->second;
97  }
98 
99  bool contains(const Key& key) const
100  {
101  return keys_.contains(key);
102  }
103 
104  size_t erase(const Key& key)
105  {
106  if (keys_.contains(key)) {
107  typename list::iterator iter = keys_[key];
108  keys_.erase(key);
109  entries_.erase(iter);
110  return 1;
111  }
112  return 0;
113  }
114 
115  // Returns the keys in the map in insertion order.
116  std::vector<Key> keys() const
117  {
118  std::vector<Key> result;
119  result.reserve(entries_.size());
120 
121  foreach (const entry& entry, entries_) {
122  result.push_back(entry.first);
123  }
124 
125  return result;
126  }
127 
128  // Returns the values in the map in insertion order.
129  std::vector<Value> values() const
130  {
131  std::vector<Value> result;
132  result.reserve(entries_.size());
133 
134  foreach (const entry& entry, entries_) {
135  result.push_back(entry.second);
136  }
137 
138  return result;
139  }
140 
141  size_t size() const
142  {
143  return keys_.size();
144  }
145 
146  bool empty() const
147  {
148  return keys_.empty();
149  }
150 
151  void clear()
152  {
153  entries_.clear();
154  keys_.clear();
155  }
156 
157  // Support for iteration; this allows using `foreachpair` and
158  // related constructs. Note that these iterate over the map in
159  // insertion order.
160  typename list::iterator begin() { return entries_.begin(); }
161  typename list::iterator end() { return entries_.end(); }
162 
163  typename list::const_iterator begin() const { return entries_.cbegin(); }
164  typename list::const_iterator end() const { return entries_.cend(); }
165 
166 private:
167  list entries_; // Key-value pairs ordered by insertion order.
168  map keys_; // Map from key to "pointer" to key's location in list.
169 };
170 
171 
172 #endif // __STOUT_LINKEDHASHMAP_HPP__
bool empty() const
Definition: linkedhashmap.hpp:146
Definition: option.hpp:29
const Value & at(const Key &key) const
Definition: linkedhashmap.hpp:94
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:163
size_t size() const
Definition: linkedhashmap.hpp:141
std::vector< Key > keys() const
Definition: linkedhashmap.hpp:116
list::const_iterator end() const
Definition: linkedhashmap.hpp:164
std::vector< Value > values() const
Definition: linkedhashmap.hpp:129
size_t erase(const Key &key)
Definition: linkedhashmap.hpp:104
hashmap< Key, typename list::iterator > map
Definition: linkedhashmap.hpp:34
list::iterator begin()
Definition: linkedhashmap.hpp:160
Value & at(const Key &key)
Definition: linkedhashmap.hpp:89
Value & operator[](const Key &key)
Definition: linkedhashmap.hpp:67
LinkedHashMap & operator=(const LinkedHashMap< Key, Value > &other)
Definition: linkedhashmap.hpp:47
Definition: none.hpp:27
void clear()
Definition: linkedhashmap.hpp:151
Definition: linkedhashmap.hpp:29
bool contains(const Key &key) const
Definition: linkedhashmap.hpp:99
LinkedHashMap()=default
bool contains(const Key &key) const
Definition: hashmap.hpp:86
list::iterator end()
Definition: linkedhashmap.hpp:161
std::list< entry > list
Definition: linkedhashmap.hpp:33