Storage Engine API
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
fast_map_noalloc.h
Go to the documentation of this file.
1 
29 #pragma once
30 
31 #include <deque>
32 
33 #include "mongo/base/static_assert.h"
34 #include "mongo/util/assert_util.h"
35 
36 namespace mongo {
37 
51 template <class KeyType, class ValueType>
53 private:
58  struct PreallocEntry {
59  bool inUse = false;
60 
61  KeyType key;
62  ValueType value;
63  };
64 
65  typedef typename std::deque<PreallocEntry> Container;
66 
67  typedef typename Container::size_type size_type;
68 
69  typedef typename Container::iterator map_iterator;
70 
71  typedef typename Container::const_iterator const_map_iterator;
72 
73 
78  template <class MapType, class IteratorValueType, class IteratorType>
79  class IteratorImpl {
80  public:
81  //
82  // Operators
83  //
84 
85  operator bool() const {
86  return !finished();
87  }
88 
89  IteratorValueType& operator*() const {
90  return *objAddr();
91  }
92 
93  IteratorValueType* operator->() const {
94  return objAddr();
95  }
96 
97 
98  //
99  // Other methods
100  //
101 
106  bool finished() const {
107  return (_it == _map._fastAccess.end());
108  }
109 
114  IteratorValueType* objAddr() const {
115  invariant(!finished());
116 
117  return &(_it->value);
118  }
119 
124  const KeyType& key() const {
125  invariant(!finished());
126 
127  return _it->key;
128  }
129 
134  void next() {
135  invariant(!finished());
136  while (++_it != _map._fastAccess.end()) {
137  if (_it->inUse) {
138  return;
139  }
140  }
141  }
142 
147  void remove() {
148  invariant(!finished());
149  invariant(_it->inUse);
150 
151  _it->inUse = false;
152  _map._fastAccessUsedSize--;
153 
154  next();
155  }
156 
157 
158  private:
159  friend class FastMapNoAlloc<KeyType, ValueType>;
160 
161  // Used for iteration of the complete map
162  IteratorImpl(MapType& map) : _map(map), _it(map._fastAccess.begin()) {
163  while (_it != _map._fastAccess.end()) {
164  if (_it->inUse) {
165  return;
166  }
167  ++_it;
168  }
169  }
170 
171  // Used for iterator starting at a position
172  IteratorImpl(MapType& map, IteratorType it) : _map(map), _it(std::move(it)) {
173  invariant(_it != _map._fastAccess.end());
174  }
175 
176  // Used for iteration starting at a particular key
177  IteratorImpl(MapType& map, const KeyType& key) : _map(map), _it(_map._fastAccess.begin()) {
178  while (_it != _map._fastAccess.end()) {
179  if (_it->inUse && _it->key == key) {
180  return;
181  }
182 
183  ++_it;
184  }
185  }
186 
187 
188  // The map being iterated on
189  MapType& _map;
190 
191  // Iterator on the map
192  IteratorType _it;
193  };
194 
195 public:
196  typedef IteratorImpl<FastMapNoAlloc<KeyType, ValueType>, ValueType, map_iterator> Iterator;
197 
198  typedef IteratorImpl<const FastMapNoAlloc<KeyType, ValueType>,
199  const ValueType,
200  const_map_iterator>
202 
204 
209  Iterator insert(const KeyType& key) {
210  if (_fastAccessUsedSize == _fastAccess.size()) {
211  // Place the new entry in the front so the below map iteration is faster.
212  _fastAccess.emplace_front();
213  }
214 
215  map_iterator it = _fastAccess.begin();
216  while (it != _fastAccess.end() && it->inUse) {
217  ++it;
218  }
219 
220  invariant(it != _fastAccess.end() && !(it->inUse));
221 
222  it->inUse = true;
223  it->key = key;
225 
226  return Iterator(*this, it);
227  }
228 
232  Iterator begin() {
233  return Iterator(*this);
234  }
235 
237  return ConstIterator(*this);
238  }
239 
249  Iterator find(const KeyType& key) {
250  return Iterator(*this, key);
251  }
252 
253  ConstIterator find(const KeyType& key) const {
254  return ConstIterator(*this, key);
255  }
256 
257  size_t size() const {
258  return _fastAccessUsedSize;
259  }
260  bool empty() const {
261  return (_fastAccessUsedSize == 0);
262  }
263 
264 private:
265  // We chose a deque data structure because it maintains the validity of existing
266  // pointers/references to its contents when it allocates more memory. Deque also gives us O(1)
267  // emplace_front() in insert().
268  std::deque<PreallocEntry> _fastAccess;
269 
271 };
272 
273 } // namespace mongo
void next()
Advances the iterator to the next entry.
Definition: fast_map_noalloc.h:134
std::deque< PreallocEntry > Container
Definition: fast_map_noalloc.h:65
Container::iterator map_iterator
Definition: fast_map_noalloc.h:69
bool empty() const
Definition: fast_map_noalloc.h:260
NOTE: This structure should not be used for anything other than the Lock Manager. ...
Definition: fast_map_noalloc.h:52
Forward-only iterator.
Definition: fast_map_noalloc.h:79
IteratorImpl< const FastMapNoAlloc< KeyType, ValueType >, const ValueType, const_map_iterator > ConstIterator
Definition: fast_map_noalloc.h:201
bool inUse
Definition: fast_map_noalloc.h:59
ConstIterator find(const KeyType &key) const
Definition: fast_map_noalloc.h:253
Copyright (C) 2014 MongoDB Inc.
Definition: bson_collection_catalog_entry.cpp:38
MapType & _map
Definition: fast_map_noalloc.h:189
IteratorType _it
Definition: fast_map_noalloc.h:192
KeyType key
Definition: fast_map_noalloc.h:61
Map entry through which we avoid releasing memory: we mark it as inUse or not.
Definition: fast_map_noalloc.h:58
IteratorValueType & operator*() const
Definition: fast_map_noalloc.h:89
Iterator begin()
Returns an iterator to the first element in the map.
Definition: fast_map_noalloc.h:232
const KeyType & key() const
Returns the key of the value at the current position.
Definition: fast_map_noalloc.h:124
IteratorImpl(MapType &map, IteratorType it)
Definition: fast_map_noalloc.h:172
Iterator find(const KeyType &key)
Returns an iterator pointing to the first position, which has entry with the specified key...
Definition: fast_map_noalloc.h:249
IndexSet::const_iterator it
Definition: ephemeral_for_test_btree_impl.cpp:458
ValueType value
Definition: fast_map_noalloc.h:62
Container::const_iterator const_map_iterator
Definition: fast_map_noalloc.h:71
IndexSet::const_iterator _it
Definition: ephemeral_for_test_btree_impl.cpp:452
ConstIterator begin() const
Definition: fast_map_noalloc.h:236
size_t size() const
Definition: fast_map_noalloc.h:257
IteratorImpl< FastMapNoAlloc< KeyType, ValueType >, ValueType, map_iterator > Iterator
Definition: fast_map_noalloc.h:196
IteratorValueType * operator->() const
Definition: fast_map_noalloc.h:93
IteratorImpl(MapType &map, const KeyType &key)
Definition: fast_map_noalloc.h:177
FastMapNoAlloc()
Definition: fast_map_noalloc.h:203
Iterator insert(const KeyType &key)
Inserts the specified entry in the map and returns a reference to the memory for the entry just inser...
Definition: fast_map_noalloc.h:209
IteratorValueType * objAddr() const
Returns the address of the object at the current position.
Definition: fast_map_noalloc.h:114
size_type _fastAccessUsedSize
Definition: fast_map_noalloc.h:270
bool finished() const
Returns whether the iterator has been exhausted through calls to next.
Definition: fast_map_noalloc.h:106
IteratorImpl(MapType &map)
Definition: fast_map_noalloc.h:162
std::deque< PreallocEntry > _fastAccess
Definition: fast_map_noalloc.h:268
Container::size_type size_type
Definition: fast_map_noalloc.h:67