tools/gn/unique_vector.h

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef TOOLS_GN_UNIQUE_VECTOR_H_
   6 #define TOOLS_GN_UNIQUE_VECTOR_H_
   7
   8 #include <algorithm>
   9
  10 #include "base/containers/hash_tables.h"
  11
  12 namespace internal {
  13
  14 // This lass allows us to insert things by reference into a hash table which
  15 // avoids copies. The hash function of a UniquifyRef is that of the object it
  16 // points to.
  17 //
  18 // There are two ways it can store data: (1) by (vector*, index) which is used
  19 // to refer to the array in UniqueVector and make it work even when the
  20 // underlying vector is reallocated; (2) by T* which is used to do lookups
  21 // into the hash table of things that aren't in a vector yet.
  22 //
  23 // It also caches the hash value which allows us to query and then insert
  24 // without recomputing the hash.
  25 template<typename T>
  26 class UniquifyRef {
  27  public:
  28   UniquifyRef()
  29       : value_(NULL),
  30         vect_(NULL),
  31         index_(static_cast<size_t>(-1)),
  32         hash_val_(0) {
  33   }
  34
  35   // Initialize with a pointer to a value.
  36   UniquifyRef(const T* v)
  37       : value_(v),
  38         vect_(NULL),
  39         index_(static_cast<size_t>(-1)) {
  40     FillHashValue();
  41   }
  42
  43   // Initialize with an array + index.
  44   UniquifyRef(const std::vector<T>* v, size_t i)
  45       : value_(NULL),
  46         vect_(v),
  47         index_(i) {
  48     FillHashValue();
  49   }
  50
  51   // Initialize with an array + index and a known hash value to prevent
  52   // re-hashing.
  53   UniquifyRef(const std::vector<T>* v, size_t i, size_t hash_value)
  54       : value_(NULL),
  55         vect_(v),
  56         index_(i),
  57         hash_val_(hash_value) {
  58   }
  59
  60   const T& value() const { return value_ ? *value_ : (*vect_)[index_]; }
  61   size_t hash_val() const { return hash_val_; }
  62   size_t index() const { return index_; }
  63
  64  private:
  65   void FillHashValue() {
  66 #if defined(COMPILER_GCC)
  67     BASE_HASH_NAMESPACE::hash<T> h;
  68     hash_val_ = h(value());
  69 #elif defined(COMPILER_MSVC)
  70     hash_val_ = BASE_HASH_NAMESPACE::hash_value(value());
  71 #else
  72     #error write me
  73 #endif  // COMPILER...
  74   }
  75
  76   // When non-null, points to the object.
  77   const T* value_;
  78
  79   // When value is null these are used.
  80   const std::vector<T>* vect_;
  81   size_t index_;
  82
  83   size_t hash_val_;
  84 };
  85
  86 template<typename T> inline bool operator==(const UniquifyRef<T>& a,
  87                                             const UniquifyRef<T>& b) {
  88   return a.value() == b.value();
  89 }
  90
  91 template<typename T> inline bool operator<(const UniquifyRef<T>& a,
  92                                            const UniquifyRef<T>& b) {
  93   return a.value() < b.value();
  94 }
  95
  96 }  // namespace internal
  97
  98 namespace BASE_HASH_NAMESPACE {
  99
 100 #if defined(COMPILER_GCC)
 101 template<typename T> struct hash< internal::UniquifyRef<T> > {
 102   std::size_t operator()(const internal::UniquifyRef<T>& v) const {
 103     return v.hash_val();
 104   }
 105 };
 106 #elif defined(COMPILER_MSVC)
 107 template<typename T>
 108 inline size_t hash_value(const internal::UniquifyRef<T>& v) {
 109   return v.hash_val();
 110 }
 111 #endif  // COMPILER...
 112
 113 }  // namespace BASE_HASH_NAMESPACE
 114
 115 // An ordered set optimized for GN's usage. Such sets are used to store lists
 116 // of configs and libraries, and are appended to but not randomly inserted
 117 // into.
 118 template<typename T>
 119 class UniqueVector {
 120  public:
 121   typedef std::vector<T> Vector;
 122   typedef typename Vector::iterator iterator;
 123   typedef typename Vector::const_iterator const_iterator;
 124
 125   const Vector& vector() const { return vector_; }
 126   size_t size() const { return vector_.size(); }
 127   bool empty() const { return vector_.empty(); }
 128   void clear() { vector_.clear(); set_.clear(); }
 129   void reserve(size_t s) { vector_.reserve(s); }
 130
 131   const T& operator[](size_t index) const { return vector_[index]; }
 132
 133   const_iterator begin() const { return vector_.begin(); }
 134   iterator begin() { return vector_.begin(); }
 135   const_iterator end() const { return vector_.end(); }
 136   iterator end() { return vector_.end(); }
 137
 138   // Returns true if the item was appended, false if it already existed (and
 139   // thus the vector was not modified).
 140   bool push_back(const T& t) {
 141     Ref ref(&t);
 142     if (set_.find(ref) != set_.end())
 143       return false;  // Already have this one.
 144
 145     vector_.push_back(t);
 146     set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val()));
 147     return true;
 148   }
 149
 150   // Like push_back but swaps in the type to avoid a copy.
 151   bool PushBackViaSwap(T* t) {
 152     using std::swap;
 153
 154     Ref ref(t);
 155     if (set_.find(ref) != set_.end())
 156       return false;  // Already have this one.
 157
 158     size_t new_index = vector_.size();
 159     vector_.resize(new_index + 1);
 160     swap(vector_[new_index], *t);
 161     set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val()));
 162     return true;
 163   }
 164
 165   // Appends a range of items from an iterator.
 166   template<typename iter> void Append(const iter& begin, const iter& end) {
 167     for (iter i = begin; i != end; ++i)
 168       push_back(*i);
 169   }
 170
 171   // Returns the index of the item matching the given value in the list, or
 172   // (size_t)(-1) if it's not found.
 173   size_t IndexOf(const T& t) const {
 174     Ref ref(&t);
 175     typename HashSet::const_iterator found = set_.find(ref);
 176     if (found == set_.end())
 177       return static_cast<size_t>(-1);
 178     return found->index();
 179   }
 180
 181  private:
 182   typedef internal::UniquifyRef<T> Ref;
 183   typedef base::hash_set<Ref> HashSet;
 184
 185   HashSet set_;
 186   Vector vector_;
 187 };
 188
 189 #endif  // TOOLS_GN_UNIQUE_VECTOR_H_