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      119988 :     IndexMap() { }
      28      119988 :     ~IndexMap() {
      29      119988 :         STLDeleteValues(&values_);
      30      119988 :     }
      31             : 
      32     4208508 :     ValueType *At(int index) const {
      33     4208508 :         return values_[index];
      34             :     }
      35     4962298 :     ValueType *Find(const KeyType &key) const {
      36     4962298 :         typename MapType::const_iterator loc = map_.find(key);
      37     4961701 :         if (loc != map_.end()) {
      38     4540224 :             return loc->second;
      39             :         }
      40      421348 :         return NULL;
      41             :     }
      42             : 
      43        8050 :     void ReserveBit(int index) {
      44        8050 :         if (bits_.test(index))
      45           0 :             assert(!values_[index]);
      46        8050 :         bits_.set(index);
      47        8050 :         values_.resize(values_.size() + 1);
      48        8050 :     }
      49             : 
      50             :     // Allocate a new index associated with the new key.
      51      360989 :     size_t Insert(const KeyType &key, ValueType *value, int index = -1) {
      52             :         std::pair<typename MapType::iterator, bool> result =
      53      360989 :             map_.insert(std::make_pair(key, value));
      54      360989 :         if (!result.second) {
      55           0 :             return -1;
      56             :         }
      57      360989 :         size_t bit = index;
      58      360989 :         if (index == -1)
      59      352958 :             bit = bits_.find_first_clear();
      60      360989 :         if (bit >= values_.size()) {
      61      340336 :             assert(bit == values_.size());
      62      340336 :             values_.push_back(value);
      63             :         } else {
      64       20653 :             values_[bit] = value;
      65             :         }
      66      360989 :         bits_.set(bit);
      67      360989 :         return bit;
      68             :     }
      69             : 
      70      320711 :     void Remove(const KeyType &key, int index, bool clear_bit = true) {
      71      320711 :         typename MapType::iterator loc = map_.find(key);
      72      320711 :         assert(loc != map_.end());
      73      320711 :         assert(loc->second == values_[index]);
      74      320711 :         map_.erase(loc);
      75      320711 :         if (clear_bit)
      76      310322 :             ResetBit(index);
      77      320711 :     }
      78             : 
      79      360866 :     void ResetBit(int index) {
      80      360866 :         bits_.reset(index);
      81      360866 :         ValueType *value = values_[index];
      82      360866 :         values_[index] = NULL;
      83      360866 :         delete value;
      84      709102 :         for (int64_t i = values_.size() - 1; i >= 0; i--) {
      85      632865 :             if (values_[i] != NULL) {
      86      284629 :                 break;
      87             :             }
      88      348236 :             values_.pop_back();
      89             :         }
      90      360866 :     }
      91             : 
      92      828777 :     ValueType *Locate(const KeyType &key) {
      93      828777 :         ValueType *value = Find(key);
      94      828777 :         if (value == NULL) {
      95      310256 :             value = new ValueType(key);
      96      310256 :             value->set_index(Insert(key, value));
      97             :         }
      98      828777 :         return value;
      99             :     }
     100             : 
     101       25928 :     size_t size() const { return values_.size(); }
     102          76 :     size_t count() const { return map_.size(); }
     103      170101 :     bool empty() const { return map_.empty(); }
     104             :     
     105        8049 :     void clear() {
     106        8049 :         bits_.clear();
     107        8049 :         STLDeleteValues(&values_);
     108        8049 :         map_.clear();
     109        8049 :     }
     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