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