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