blob: 3ebf182d56a97a82f8d8c3fdf7041719e717f2df [file] [log] [blame]
// 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.
#include <stddef.h>
#include <algorithm>
#include <unordered_set>
#include <vector>
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 {
UniquifyRef() = default;
// Initialize with a pointer to a value.
explicit UniquifyRef(const T* v) : value_(v) { FillHashValue(); }
// Initialize with an array + index.
UniquifyRef(const std::vector<T>* v, size_t i) : vect_(v), index_(i) {
// 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)
: 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_; }
void FillHashValue() {
std::hash<T> h;
hash_val_ = h(value());
// When non-null, points to the object.
const T* value_ = nullptr;
// When value is null these are used.
const std::vector<T>* vect_ = nullptr;
size_t index_ = static_cast<size_t>(-1);
size_t hash_val_ = 0;
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 std {
template <typename T>
struct hash<internal::UniquifyRef<T>> {
std::size_t operator()(const internal::UniquifyRef<T>& v) const {
return v.hash_val();
} // namespace std
// 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 {
using Vector = std::vector<T>;
using iterator = typename Vector::iterator;
using const_iterator = typename Vector::const_iterator;
const Vector& vector() const { return vector_; }
size_t size() const { return vector_.size(); }
bool empty() const { return vector_.empty(); }
void 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.
set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val()));
return true;
bool push_back(T&& t) {
Ref ref(&t);
if (set_.find(ref) != set_.end())
return false; // Already have this one.
auto ref_hash_val = ref.hash_val(); // Save across moving t.
vector_.push_back(std::move(t)); // Invalidates |ref|.
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)
// 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();
using Ref = internal::UniquifyRef<T>;
using HashSet = std::unordered_set<Ref>;
HashSet set_;
Vector vector_;