Line data Source code
1 : /* 2 : * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved. 3 : * Copyright Contributors to the OpenSDN project 4 : */ 5 : 6 : #ifndef ctrlplane_index_map_h 7 : #define ctrlplane_index_map_h 8 : 9 : #include <cassert> 10 : #include <map> 11 : #include <vector> 12 : #include "base/bitset.h" 13 : #include "base/util.h" 14 : 15 : // 16 : // An key, value map associated with an index. 17 : // 18 : template <typename KeyType, typename ValueType, 19 : typename BitsetType = BitSet> 20 : class IndexMap { 21 : public: 22 : typedef std::vector<ValueType *> VectorType; 23 : typedef std::map<KeyType, ValueType *> MapType; 24 : typedef typename MapType::iterator iterator; 25 : typedef typename MapType::const_iterator const_iterator; 26 : 27 77793 : IndexMap() { } 28 77793 : ~IndexMap() { 29 77793 : STLDeleteValues(&values_); 30 77793 : } 31 : 32 2140287 : ValueType *At(int index) const { 33 2140287 : return values_[index]; 34 : } 35 2288170 : ValueType *Find(const KeyType &key) const { 36 2288170 : typename MapType::const_iterator loc = map_.find(key); 37 2288038 : if (loc != map_.end()) { 38 2064229 : return loc->second; 39 : } 40 223769 : return NULL; 41 : } 42 : 43 21 : void ReserveBit(int index) { 44 21 : if (bits_.test(index)) 45 0 : assert(!values_[index]); 46 21 : bits_.set(index); 47 21 : values_.resize(values_.size() + 1); 48 21 : } 49 : 50 : // Allocate a new index associated with the new key. 51 219321 : size_t Insert(const KeyType &key, ValueType *value, int index = -1) { 52 : std::pair<typename MapType::iterator, bool> result = 53 219321 : map_.insert(std::make_pair(key, value)); 54 219321 : if (!result.second) { 55 0 : return -1; 56 : } 57 219321 : size_t bit = index; 58 219321 : if (index == -1) 59 219301 : bit = bits_.find_first_clear(); 60 219321 : if (bit >= values_.size()) { 61 211483 : assert(bit == values_.size()); 62 211483 : values_.push_back(value); 63 : } else { 64 7838 : values_[bit] = value; 65 : } 66 219321 : bits_.set(bit); 67 219321 : return bit; 68 : } 69 : 70 219221 : void Remove(const KeyType &key, int index, bool clear_bit = true) { 71 219221 : typename MapType::iterator loc = map_.find(key); 72 219221 : assert(loc != map_.end()); 73 219221 : assert(loc->second == values_[index]); 74 219221 : map_.erase(loc); 75 219221 : if (clear_bit) 76 219155 : ResetBit(index); 77 219221 : } 78 : 79 219321 : void ResetBit(int index) { 80 219321 : bits_.reset(index); 81 219321 : ValueType *value = values_[index]; 82 219321 : values_[index] = NULL; 83 219321 : delete value; 84 430825 : for (int64_t i = values_.size() - 1; i >= 0; i--) { 85 396648 : if (values_[i] != NULL) { 86 185144 : break; 87 : } 88 211504 : values_.pop_back(); 89 : } 90 219321 : } 91 : 92 737618 : ValueType *Locate(const KeyType &key) { 93 737618 : ValueType *value = Find(key); 94 737618 : if (value == NULL) { 95 219089 : value = new ValueType(key); 96 219089 : value->set_index(Insert(key, value)); 97 : } 98 737618 : return value; 99 : } 100 : 101 2831 : size_t size() const { return values_.size(); } 102 76 : size_t count() const { return map_.size(); } 103 79150 : bool empty() const { return map_.empty(); } 104 : 105 20 : void clear() { 106 20 : bits_.clear(); 107 20 : STLDeleteValues(&values_); 108 20 : map_.clear(); 109 20 : } 110 : 111 564 : const BitsetType &bits() const { return bits_; } 112 : 113 : iterator begin() { return map_.begin(); } 114 : iterator end() { return map_.end(); } 115 : iterator lower_bound(const KeyType &key) { 116 : return map_.lower_bound(key); 117 : } 118 : const_iterator cbegin() { return map_.begin(); } 119 : const_iterator cend() { return map_.end(); } 120 : const_iterator clower_bound(const KeyType &key) { 121 : return map_.lower_bound(key); 122 : } 123 : 124 : private: 125 : BitsetType bits_; 126 : VectorType values_; 127 : MapType map_; 128 : DISALLOW_COPY_AND_ASSIGN(IndexMap); 129 : }; 130 : 131 : #endif