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      120061 :     IndexMap() { }
      27      120061 :     ~IndexMap() {
      28      120061 :         STLDeleteValues(&values_);
      29      120061 :     }
      30             : 
      31     4271836 :     ValueType *At(int index) const {
      32     4271836 :         return values_[index];
      33             :     }
      34     5001167 :     ValueType *Find(const KeyType &key) const {
      35     5001167 :         typename MapType::const_iterator loc = map_.find(key);
      36     5000928 :         if (loc != map_.end()) {
      37     4578882 :             return loc->second;
      38             :         }
      39      421997 :         return NULL;
      40             :     }
      41             : 
      42        8049 :     void ReserveBit(int index) {
      43        8049 :         if (bits_.test(index))
      44           0 :             assert(!values_[index]);
      45        8049 :         bits_.set(index);
      46        8049 :         values_.resize(values_.size() + 1);
      47        8049 :     }
      48             : 
      49             :     // Allocate a new index associated with the new key.
      50      361615 :     size_t Insert(const KeyType &key, ValueType *value, int index = -1) {
      51             :         std::pair<typename MapType::iterator, bool> result =
      52      361615 :             map_.insert(std::make_pair(key, value));
      53      361615 :         if (!result.second) {
      54           0 :             return -1;
      55             :         }
      56      361615 :         size_t bit = index;
      57      361615 :         if (index == -1)
      58      353585 :             bit = bits_.find_first_clear();
      59      361615 :         if (bit >= values_.size()) {
      60      340821 :             assert(bit == values_.size());
      61      340821 :             values_.push_back(value);
      62             :         } else {
      63       20794 :             values_[bit] = value;
      64             :         }
      65      361615 :         bits_.set(bit);
      66      361615 :         return bit;
      67             :     }
      68             : 
      69      321340 :     void Remove(const KeyType &key, int index, bool clear_bit = true) {
      70      321340 :         typename MapType::iterator loc = map_.find(key);
      71      321340 :         assert(loc != map_.end());
      72      321340 :         assert(loc->second == values_[index]);
      73      321340 :         map_.erase(loc);
      74      321340 :         if (clear_bit)
      75      310950 :             ResetBit(index);
      76      321340 :     }
      77             : 
      78      361492 :     void ResetBit(int index) {
      79      361492 :         bits_.reset(index);
      80      361492 :         ValueType *value = values_[index];
      81      361492 :         values_[index] = NULL;
      82      361492 :         delete value;
      83      710212 :         for (int64_t i = values_.size() - 1; i >= 0; i--) {
      84      633702 :             if (values_[i] != NULL) {
      85      284982 :                 break;
      86             :             }
      87      348720 :             values_.pop_back();
      88             :         }
      89      361492 :     }
      90             : 
      91      829425 :     ValueType *Locate(const KeyType &key) {
      92      829425 :         ValueType *value = Find(key);
      93      829425 :         if (value == NULL) {
      94      310884 :             value = new ValueType(key);
      95      310884 :             value->set_index(Insert(key, value));
      96             :         }
      97      829425 :         return value;
      98             :     }
      99             : 
     100       25674 :     size_t size() const { return values_.size(); }
     101          76 :     size_t count() const { return map_.size(); }
     102      170165 :     bool empty() const { return map_.empty(); }
     103             :     
     104        8048 :     void clear() {
     105        8048 :         bits_.clear();
     106        8048 :         STLDeleteValues(&values_);
     107        8048 :         map_.clear();
     108        8048 :     }
     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