Bitcoin ABC  0.22.12
P2P Digital Currency
limitedmap.h
Go to the documentation of this file.
1 // Copyright (c) 2012-2016 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 <cassert>
9 #include <map>
10 
14 template <typename K, typename V> class limitedmap {
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  assert(nMaxSizeIn > 0);
32  nMaxSize = nMaxSizeIn;
33  }
34  const_iterator begin() const { return map.begin(); }
35  const_iterator end() const { return map.end(); }
36  size_type size() const { return map.size(); }
37  bool empty() const { return map.empty(); }
38  const_iterator find(const key_type &k) const { return map.find(k); }
39  size_type count(const key_type &k) const { return map.count(k); }
40  void insert(const value_type &x) {
41  std::pair<iterator, bool> ret = map.insert(x);
42  if (ret.second) {
43  if (map.size() > nMaxSize) {
44  map.erase(rmap.begin()->second);
45  rmap.erase(rmap.begin());
46  }
47  rmap.insert(make_pair(x.second, ret.first));
48  }
49  }
50  void erase(const key_type &k) {
51  iterator itTarget = map.find(k);
52  if (itTarget == map.end()) {
53  return;
54  }
55  std::pair<rmap_iterator, rmap_iterator> itPair =
56  rmap.equal_range(itTarget->second);
57  for (rmap_iterator it = itPair.first; it != itPair.second; ++it) {
58  if (it->second == itTarget) {
59  rmap.erase(it);
60  map.erase(itTarget);
61  return;
62  }
63  }
64  // Shouldn't ever get here
65  assert(0);
66  }
67  void update(const_iterator itIn, const mapped_type &v) {
68  // Using map::erase() with empty range instead of map::find() to get a
69  // non-const iterator, since it is a constant time operation in C++11.
70  // 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()) return;
75  std::pair<rmap_iterator, rmap_iterator> itPair =
76  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  }
85  // Shouldn't ever get here
86  assert(0);
87  }
88  size_type max_size() const { return nMaxSize; }
89  size_type max_size(size_type s) {
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:37
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:14
void insert(const value_type &x)
Definition: limitedmap.h:40
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:36
limitedmap(size_type nMaxSizeIn)
Definition: limitedmap.h:30
const_iterator find(const key_type &k) const
Definition: limitedmap.h:38
std::multimap< V, iterator >::iterator rmap_iterator
Definition: limitedmap.h:26
const_iterator begin() const
Definition: limitedmap.h:34
const_iterator end() const
Definition: limitedmap.h:35
void erase(const key_type &k)
Definition: limitedmap.h:50
size_type count(const key_type &k) const
Definition: limitedmap.h:39
size_type max_size() const
Definition: limitedmap.h:88
size_type max_size(size_type s)
Definition: limitedmap.h:89
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