Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #ifndef agent_index_vector_h
       6             : #define agent_index_vector_h
       7             : 
       8             : #include <cassert>
       9             : #include <vector>
      10             : #include <boost/dynamic_bitset.hpp>
      11             : #include <base/logging.h>
      12             : 
      13             : // Index management + Vector holding a pointer at allocated index
      14             : template <typename EntryType>
      15             : class IndexVector {
      16             : public:
      17             :     static const size_t kGrowSize = 32;
      18             : 
      19             :     typedef std::vector<EntryType> EntryTable;
      20             : 
      21       24627 :     IndexVector() {  }
      22       24627 :     ~IndexVector() {
      23             :         // Make sure the bitmap is empty
      24       24627 :         if (bitmap_.count() != bitmap_.size()) {
      25           4 :             LOG(ERROR, "IndexVector has " << bitmap_.size() - bitmap_.count()
      26             :                 << " entries in destructor");
      27             :         }
      28       24627 :         bitmap_.clear();
      29       24627 :     }
      30             : 
      31             :     // Get entry at an index
      32        9641 :     EntryType At(size_t index) const {
      33        9641 :         if (index >= bitmap_.size()) {
      34        1118 :             return EntryType();
      35             :         }
      36        8523 :         return entries_[index];
      37             :     }
      38             : 
      39             :     // Allocate a new index and store entry in vector at allocated index
      40         745 :     size_t Insert(EntryType entry) {
      41         745 :         size_t index = bitmap_.find_first();
      42         745 :         if (index == bitmap_.npos) {
      43          16 :             size_t size = bitmap_.size();
      44          16 :             bitmap_.resize(size + kGrowSize, 1);
      45          16 :             entries_.resize(size + kGrowSize);
      46          16 :             index = bitmap_.find_first();
      47             :         }
      48             : 
      49         745 :         bitmap_.set(index, 0);
      50         745 :         entries_[index] = entry;
      51         745 :         return index;
      52             :     }
      53             : 
      54        5424 :     size_t InsertAtIndex(uint32_t index, EntryType entry) {
      55        5424 :         size_t size = bitmap_.size();
      56        5424 :         if (size == 0 || size <= index) {
      57          49 :             bitmap_.resize(index + kGrowSize, 1);
      58          49 :             entries_.resize(index + kGrowSize);
      59             :         }
      60             : 
      61             :         // TODO(prabhjot) need to enable assertion below
      62             :         // currently disabled due to some issue with MPLS
      63             :         // label allocation
      64             :         // index should not be already in use
      65             :         // assert(bitmap_[index] == 1);
      66             : 
      67        5424 :         bitmap_.set(index, 0);
      68        5424 :         entries_[index] = entry;
      69        5424 :         return index;
      70             :     }
      71             : 
      72             :     void Update(size_t index, EntryType entry) {
      73             :         assert(index < bitmap_.size());
      74             :         assert(bitmap_[index] == 0);
      75             :         entries_[index] = entry;
      76             :     }
      77             : 
      78        1161 :     void Remove(size_t index) {
      79        1161 :         assert(index < bitmap_.size());
      80        1161 :         assert(bitmap_[index] == 0);
      81        1161 :         bitmap_.set(index);
      82        1161 :         entries_[index] = EntryType();
      83        1161 :     }
      84             : 
      85           0 :     bool NoneIndexSet() {
      86           0 :         return (bitmap_.count() == bitmap_.size());
      87             :     }
      88             : 
      89        1311 :     size_t InUseIndexCount() {
      90        1311 :         return (bitmap_.size() - bitmap_.count());
      91             :     }
      92             : 
      93             : private:
      94             :     typedef boost::dynamic_bitset<> Bitmap;
      95             :     Bitmap bitmap_;
      96             :     EntryTable entries_;
      97             :     DISALLOW_COPY_AND_ASSIGN(IndexVector);
      98             : };
      99             : 
     100             : #endif