Bitcoin Core  0.18.99
P2P Digital Currency
limitedmap.h
Go to the documentation of this file.
1 // Copyright (c) 2012-2018 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #ifndef BITCOIN_LIMITEDMAP_H
6 #define BITCOIN_LIMITEDMAP_H
7 
8 #include <assert.h>
9 #include <map>
10 
12 template <typename K, typename V>
14 {
15 public:
16  typedef K key_type;
17  typedef V mapped_type;
18  typedef std::pair<const key_type, mapped_type> value_type;
19  typedef typename std::map<K, V>::const_iterator const_iterator;
20  typedef typename std::map<K, V>::size_type size_type;
21 
22 protected:
23  std::map<K, V> map;
24  typedef typename std::map<K, V>::iterator iterator;
25  std::multimap<V, iterator> rmap;
26  typedef typename std::multimap<V, iterator>::iterator rmap_iterator;
27  size_type nMaxSize;
28 
29 public:
30  explicit limitedmap(size_type nMaxSizeIn)
31  {
32  assert(nMaxSizeIn > 0);
33  nMaxSize = nMaxSizeIn;
34  }
35  const_iterator begin() const { return map.begin(); }
36  const_iterator end() const { return map.end(); }
37  size_type size() const { return map.size(); }
38  bool empty() const { return map.empty(); }
39  const_iterator find(const key_type& k) const { return map.find(k); }
40  size_type count(const key_type& k) const { return map.count(k); }
41  void insert(const value_type& x)
42  {
43  std::pair<iterator, bool> ret = map.insert(x);
44  if (ret.second) {
45  if (map.size() > nMaxSize) {
46  map.erase(rmap.begin()->second);
47  rmap.erase(rmap.begin());
48  }
49  rmap.insert(make_pair(x.second, ret.first));
50  }
51  }
52  void erase(const key_type& k)
53  {
54  iterator itTarget = map.find(k);
55  if (itTarget == map.end())
56  return;
57  std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second);
58  for (rmap_iterator it = itPair.first; it != itPair.second; ++it)
59  if (it->second == itTarget) {
60  rmap.erase(it);
61  map.erase(itTarget);
62  return;
63  }
64  // Shouldn't ever get here
65  assert(0);
66  }
67  void update(const_iterator itIn, const mapped_type& v)
68  {
69  // Using map::erase() with empty range instead of map::find() to get a non-const iterator,
70  // since it is a constant time operation in C++11. For more details, see
71  // https://stackoverflow.com/questions/765148/how-to-remove-constness-of-const-iterator
72  iterator itTarget = map.erase(itIn, itIn);
73 
74  if (itTarget == map.end())
75  return;
76  std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second);
77  for (rmap_iterator it = itPair.first; it != itPair.second; ++it)
78  if (it->second == itTarget) {
79  rmap.erase(it);
80  itTarget->second = v;
81  rmap.insert(make_pair(v, itTarget));
82  return;
83  }
84  // Shouldn't ever get here
85  assert(0);
86  }
87  size_type max_size() const { return nMaxSize; }
88  size_type max_size(size_type s)
89  {
90  assert(s > 0);
91  while (map.size() > s) {
92  map.erase(rmap.begin()->second);
93  rmap.erase(rmap.begin());
94  }
95  nMaxSize = s;
96  return nMaxSize;
97  }
98 };
99 
100 #endif // BITCOIN_LIMITEDMAP_H
std::map< K, V >::const_iterator const_iterator
Definition: limitedmap.h:19
bool empty() const
Definition: limitedmap.h:38
std::pair< const key_type, mapped_type > value_type
Definition: limitedmap.h:18
std::map< K, V > map
Definition: limitedmap.h:23
STL-like map container that only keeps the N elements with the highest value.
Definition: limitedmap.h:13
void insert(const value_type &x)
Definition: limitedmap.h:41
std::multimap< V, iterator > rmap
Definition: limitedmap.h:25
void update(const_iterator itIn, const mapped_type &v)
Definition: limitedmap.h:67
size_type size() const
Definition: limitedmap.h:37
limitedmap(size_type nMaxSizeIn)
Definition: limitedmap.h:30
const_iterator find(const key_type &k) const
Definition: limitedmap.h:39
std::multimap< V, iterator >::iterator rmap_iterator
Definition: limitedmap.h:26
const_iterator begin() const
Definition: limitedmap.h:35
const_iterator end() const
Definition: limitedmap.h:36
void erase(const key_type &k)
Definition: limitedmap.h:52
size_type count(const key_type &k) const
Definition: limitedmap.h:40
size_type max_size() const
Definition: limitedmap.h:87
size_type max_size(size_type s)
Definition: limitedmap.h:88
size_type nMaxSize
Definition: limitedmap.h:27
std::map< K, V >::iterator iterator
Definition: limitedmap.h:24
std::map< K, V >::size_type size_type
Definition: limitedmap.h:20