Line data    Source code

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