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
12namespace 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.
25template<typename T>
26class 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
86template<typename T> inline bool operator==(const UniquifyRef<T>& a,
87                                            const UniquifyRef<T>& b) {
88  return a.value() == b.value();
89}
90
91template<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
98namespace BASE_HASH_NAMESPACE {
99
100#if defined(COMPILER_GCC)
101template<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)
107template<typename T>
108inline 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.
118template<typename T>
119class 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_
190