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::list<Key> keys() const
115  {
116  std::list<Key> result;
117 
118  foreach (const entry& entry, entries_) {
119  result.push_back(entry.first);
120  }
121 
122  return result;
123  }
124 
125  // Returns the values in the map in insertion order.
126  std::list<Value> values() const
127  {
128  std::list<Value> result;
129 
130  foreach (const entry& entry, entries_) {
131  result.push_back(entry.second);
132  }
133 
134  return result;
135  }
136 
137  size_t size() const
138  {
139  return keys_.size();
140  }
141 
142  bool empty() const
143  {
144  return keys_.empty();
145  }
146 
147  void clear()
148  {
149  entries_.clear();
150  keys_.clear();
151  }
152 
153  // Support for iteration; this allows using `foreachpair` and
154  // related constructs. Note that these iterate over the map in
155  // insertion order.
156  typename list::iterator begin() { return entries_.begin(); }
157  typename list::iterator end() { return entries_.end(); }
158 
159  typename list::const_iterator begin() const { return entries_.cbegin(); }
160  typename list::const_iterator end() const { return entries_.cend(); }
161 
162 private:
163  list entries_; // Key-value pairs ordered by insertion order.
164  map keys_; // Map from key to "pointer" to key's location in list.
165 };
166 
167 
168 #endif // __STOUT_LINKEDHASHMAP_HPP__
bool empty() const
Definition: linkedhashmap.hpp:142
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
std::list< Key > keys() const
Definition: linkedhashmap.hpp:114
list::const_iterator begin() const
Definition: linkedhashmap.hpp:159
size_t size() const
Definition: linkedhashmap.hpp:137
list::const_iterator end() const
Definition: linkedhashmap.hpp:160
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:156
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:147
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:157
std::list< Value > values() const
Definition: linkedhashmap.hpp:126
std::list< entry > list
Definition: linkedhashmap.hpp:33