1 /** 2 * @file sparse_array.h 3 * Auto-expanding sparse array type 4 * 5 * @remark Copyright 2007 OProfile authors 6 * @remark Copyright (c) International Business Machines, 2007. 7 * @remark Read the file COPYING 8 * 9 * @author Dave Nomura <dcnltc@us.ibm.com> 10 */ 11 12 #ifndef SPARSE_ARRAY_H 13 #define SPARSE_ARRAY_H 14 15 template <typename I, typename T> class sparse_array { 16 public: 17 typedef std::map<I, T> container_type; 18 typedef typename container_type::size_type size_type; 19 20 /** 21 * Index into the map for a value. 22 * NOTE: since std::map does/can not have a const member function for 23 * operator[], this const member function simply returns 0 for 24 * profile classes that aren't represented in the map. 25 * This member function will only be invoked for queries of the 26 * sparse array. 27 */ 28 T operator[](size_type index) const { 29 typename container_type::const_iterator it = container.find(index); 30 if (it != container.end()) 31 return it->second; 32 else 33 return 0; 34 } 35 36 37 /** 38 * Index into the vector for a value. If the index is larger than 39 * the current max index, a new array entry is created. 40 */ 41 T & operator[](size_type index) { 42 return container[index]; 43 } 44 45 46 /** 47 * vectorized += operator 48 */ 49 sparse_array & operator+=(sparse_array const & rhs) { 50 typename container_type::const_iterator it = rhs.container.begin(); 51 typename container_type::const_iterator it_end = rhs.container.end(); 52 for ( ; it != it_end; it++) 53 container[it->first] += it->second; 54 55 return *this; 56 } 57 58 59 /** 60 * vectorized -= operator, overflow shouldn't occur during substraction 61 * (iow: for each components lhs[i] >= rhs[i] 62 */ 63 sparse_array & operator-=(sparse_array const & rhs) { 64 typename container_type::const_iterator it = rhs.container.begin(); 65 typename container_type::const_iterator it_end = rhs.container.end(); 66 for ( ; it != it_end; it++) 67 container[it->first] -= it->second; 68 69 return *this; 70 } 71 72 73 /** 74 * return the maximum index of the array + 1 or 0 if the array 75 * is empty. 76 */ size()77 size_type size() const { 78 if (container.size() == 0) 79 return 0; 80 typename container_type::const_iterator last = container.end(); 81 --last; 82 return last->first + 1; 83 } 84 85 86 /// return true if all elements have the default constructed value zero()87 bool zero() const { 88 typename container_type::const_iterator it = container.begin(); 89 typename container_type::const_iterator it_end = container.end(); 90 for ( ; it != it_end; it++) 91 if (it->second != 0) 92 return false; 93 return true; 94 } 95 96 private: 97 container_type container; 98 }; 99 100 #endif // SPARSE_ARRAY_H 101