Line data Source code
1 : // Copyright (c) 2012-2014 The Bitcoin developers 2 : // Copyright (c) 2019 The PIVX Core developers 3 : // Distributed under the MIT software license, see the accompanying 4 : // file COPYING or http://www.opensource.org/licenses/mit-license.php. 5 : 6 : #ifndef PIVX_LIMITEDMAP_H 7 : #define PIVX_LIMITEDMAP_H 8 : 9 : #include <assert.h> 10 : #include <map> 11 : 12 : /** STL-like map container that only keeps the N elements with the highest value. */ 13 : template <typename K, typename V> 14 : class limitedmap 15 : { 16 : public: 17 : typedef K key_type; 18 : typedef V mapped_type; 19 : typedef std::pair<const key_type, mapped_type> value_type; 20 : typedef typename std::map<K, V>::const_iterator const_iterator; 21 : typedef typename std::map<K, V>::size_type size_type; 22 : 23 : protected: 24 : std::map<K, V> map; 25 : typedef typename std::map<K, V>::iterator iterator; 26 : std::multimap<V, iterator> rmap; 27 : typedef typename std::multimap<V, iterator>::iterator rmap_iterator; 28 : size_type nMaxSize; 29 : 30 : public: 31 : explicit limitedmap(size_type nMaxSizeIn = 0) { nMaxSize = nMaxSizeIn; } 32 : const_iterator begin() const { return map.begin(); } 33 142502 : const_iterator end() const { return map.end(); } 34 : size_type size() const { return map.size(); } 35 : bool empty() const { return map.empty(); } 36 71251 : const_iterator find(const key_type& k) const { return map.find(k); } 37 : size_type count(const key_type& k) const { return map.count(k); } 38 65854 : void insert(const value_type& x) 39 : { 40 65854 : std::pair<iterator, bool> ret = map.insert(x); 41 65854 : if (ret.second) { 42 65854 : if (nMaxSize && map.size() == nMaxSize) { 43 2 : map.erase(rmap.begin()->second); 44 2 : rmap.erase(rmap.begin()); 45 : } 46 65854 : rmap.insert(std::make_pair(x.second, ret.first)); 47 : } 48 65854 : return; 49 : } 50 66307 : void erase(const key_type& k) 51 : { 52 66307 : iterator itTarget = map.find(k); 53 66307 : if (itTarget == map.end()) 54 : return; 55 15539 : std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second); 56 15539 : for (rmap_iterator it = itPair.first; it != itPair.second; ++it) 57 15539 : if (it->second == itTarget) { 58 15539 : rmap.erase(it); 59 15539 : map.erase(itTarget); 60 15539 : return; 61 : } 62 : // Shouldn't ever get here 63 0 : assert(0); 64 : } 65 5397 : void update(const_iterator itIn, const mapped_type& v) 66 : { 67 : // TODO: When we switch to C++11, use map.erase(itIn, itIn) to get the non-const iterator. 68 5397 : iterator itTarget = map.find(itIn->first); 69 5397 : if (itTarget == map.end()) 70 : return; 71 5397 : std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second); 72 5397 : for (rmap_iterator it = itPair.first; it != itPair.second; ++it) 73 : if (it->second == itTarget) { 74 5397 : rmap.erase(it); 75 5397 : itTarget->second = v; 76 5397 : rmap.insert(std::make_pair(v, itTarget)); 77 5397 : return; 78 : } 79 : // Shouldn't ever get here 80 0 : assert(0); 81 : } 82 : size_type max_size() const { return nMaxSize; } 83 : size_type max_size(size_type s) 84 : { 85 : if (s) 86 : while (map.size() > s) { 87 : map.erase(rmap.begin()->second); 88 : rmap.erase(rmap.begin()); 89 : } 90 : nMaxSize = s; 91 : return nMaxSize; 92 : } 93 : }; 94 : 95 : #endif // PIVX_LIMITEDMAP_H