1*795d594fSAndroid Build Coastguard Worker /*
2*795d594fSAndroid Build Coastguard Worker * Copyright (C) 2014 The Android Open Source Project
3*795d594fSAndroid Build Coastguard Worker *
4*795d594fSAndroid Build Coastguard Worker * Licensed under the Apache License, Version 2.0 (the "License");
5*795d594fSAndroid Build Coastguard Worker * you may not use this file except in compliance with the License.
6*795d594fSAndroid Build Coastguard Worker * You may obtain a copy of the License at
7*795d594fSAndroid Build Coastguard Worker *
8*795d594fSAndroid Build Coastguard Worker * http://www.apache.org/licenses/LICENSE-2.0
9*795d594fSAndroid Build Coastguard Worker *
10*795d594fSAndroid Build Coastguard Worker * Unless required by applicable law or agreed to in writing, software
11*795d594fSAndroid Build Coastguard Worker * distributed under the License is distributed on an "AS IS" BASIS,
12*795d594fSAndroid Build Coastguard Worker * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13*795d594fSAndroid Build Coastguard Worker * See the License for the specific language governing permissions and
14*795d594fSAndroid Build Coastguard Worker * limitations under the License.
15*795d594fSAndroid Build Coastguard Worker */
16*795d594fSAndroid Build Coastguard Worker
17*795d594fSAndroid Build Coastguard Worker #ifndef ART_LIBARTBASE_BASE_HASH_SET_H_
18*795d594fSAndroid Build Coastguard Worker #define ART_LIBARTBASE_BASE_HASH_SET_H_
19*795d594fSAndroid Build Coastguard Worker
20*795d594fSAndroid Build Coastguard Worker #include <stdint.h>
21*795d594fSAndroid Build Coastguard Worker
22*795d594fSAndroid Build Coastguard Worker #include <functional>
23*795d594fSAndroid Build Coastguard Worker #include <iterator>
24*795d594fSAndroid Build Coastguard Worker #include <memory>
25*795d594fSAndroid Build Coastguard Worker #include <string>
26*795d594fSAndroid Build Coastguard Worker #include <type_traits>
27*795d594fSAndroid Build Coastguard Worker #include <utility>
28*795d594fSAndroid Build Coastguard Worker
29*795d594fSAndroid Build Coastguard Worker #include <android-base/logging.h>
30*795d594fSAndroid Build Coastguard Worker
31*795d594fSAndroid Build Coastguard Worker #include "base/data_hash.h"
32*795d594fSAndroid Build Coastguard Worker #include "bit_utils.h"
33*795d594fSAndroid Build Coastguard Worker #include "macros.h"
34*795d594fSAndroid Build Coastguard Worker
35*795d594fSAndroid Build Coastguard Worker namespace art {
36*795d594fSAndroid Build Coastguard Worker
37*795d594fSAndroid Build Coastguard Worker template <class Elem, class HashSetType>
38*795d594fSAndroid Build Coastguard Worker class HashSetIterator {
39*795d594fSAndroid Build Coastguard Worker public:
40*795d594fSAndroid Build Coastguard Worker using iterator_category = std::forward_iterator_tag;
41*795d594fSAndroid Build Coastguard Worker using value_type = Elem;
42*795d594fSAndroid Build Coastguard Worker using difference_type = std::ptrdiff_t;
43*795d594fSAndroid Build Coastguard Worker using pointer = Elem*;
44*795d594fSAndroid Build Coastguard Worker using reference = Elem&;
45*795d594fSAndroid Build Coastguard Worker
46*795d594fSAndroid Build Coastguard Worker HashSetIterator(const HashSetIterator&) = default;
47*795d594fSAndroid Build Coastguard Worker HashSetIterator(HashSetIterator&&) noexcept = default;
HashSetIterator(HashSetType * hash_set,size_t index)48*795d594fSAndroid Build Coastguard Worker HashSetIterator(HashSetType* hash_set, size_t index) : index_(index), hash_set_(hash_set) {}
49*795d594fSAndroid Build Coastguard Worker
50*795d594fSAndroid Build Coastguard Worker // Conversion from iterator to const_iterator.
51*795d594fSAndroid Build Coastguard Worker template <class OtherElem,
52*795d594fSAndroid Build Coastguard Worker class OtherHashSetType,
53*795d594fSAndroid Build Coastguard Worker typename = std::enable_if_t<
54*795d594fSAndroid Build Coastguard Worker std::is_same_v<Elem, const OtherElem> &&
55*795d594fSAndroid Build Coastguard Worker std::is_same_v<HashSetType, const OtherHashSetType>>>
HashSetIterator(const HashSetIterator<OtherElem,OtherHashSetType> & other)56*795d594fSAndroid Build Coastguard Worker HashSetIterator(const HashSetIterator<OtherElem, OtherHashSetType>& other)
57*795d594fSAndroid Build Coastguard Worker : index_(other.index_), hash_set_(other.hash_set_) {}
58*795d594fSAndroid Build Coastguard Worker
59*795d594fSAndroid Build Coastguard Worker HashSetIterator& operator=(const HashSetIterator&) = default;
60*795d594fSAndroid Build Coastguard Worker HashSetIterator& operator=(HashSetIterator&&) noexcept = default;
61*795d594fSAndroid Build Coastguard Worker
62*795d594fSAndroid Build Coastguard Worker bool operator==(const HashSetIterator& other) const {
63*795d594fSAndroid Build Coastguard Worker return hash_set_ == other.hash_set_ && this->index_ == other.index_;
64*795d594fSAndroid Build Coastguard Worker }
65*795d594fSAndroid Build Coastguard Worker
66*795d594fSAndroid Build Coastguard Worker bool operator!=(const HashSetIterator& other) const {
67*795d594fSAndroid Build Coastguard Worker return !(*this == other);
68*795d594fSAndroid Build Coastguard Worker }
69*795d594fSAndroid Build Coastguard Worker
70*795d594fSAndroid Build Coastguard Worker HashSetIterator operator++() { // Value after modification.
71*795d594fSAndroid Build Coastguard Worker this->index_ = hash_set_->NextNonEmptySlot(index_);
72*795d594fSAndroid Build Coastguard Worker return *this;
73*795d594fSAndroid Build Coastguard Worker }
74*795d594fSAndroid Build Coastguard Worker
75*795d594fSAndroid Build Coastguard Worker HashSetIterator operator++(int) {
76*795d594fSAndroid Build Coastguard Worker HashSetIterator temp = *this;
77*795d594fSAndroid Build Coastguard Worker ++*this;
78*795d594fSAndroid Build Coastguard Worker return temp;
79*795d594fSAndroid Build Coastguard Worker }
80*795d594fSAndroid Build Coastguard Worker
81*795d594fSAndroid Build Coastguard Worker Elem& operator*() const {
82*795d594fSAndroid Build Coastguard Worker DCHECK(!hash_set_->IsFreeSlot(this->index_));
83*795d594fSAndroid Build Coastguard Worker return hash_set_->ElementForIndex(this->index_);
84*795d594fSAndroid Build Coastguard Worker }
85*795d594fSAndroid Build Coastguard Worker
86*795d594fSAndroid Build Coastguard Worker Elem* operator->() const {
87*795d594fSAndroid Build Coastguard Worker return &**this;
88*795d594fSAndroid Build Coastguard Worker }
89*795d594fSAndroid Build Coastguard Worker
90*795d594fSAndroid Build Coastguard Worker private:
91*795d594fSAndroid Build Coastguard Worker size_t index_;
92*795d594fSAndroid Build Coastguard Worker HashSetType* hash_set_;
93*795d594fSAndroid Build Coastguard Worker
94*795d594fSAndroid Build Coastguard Worker template <class Elem1, class HashSetType1, class Elem2, class HashSetType2>
95*795d594fSAndroid Build Coastguard Worker friend bool operator==(const HashSetIterator<Elem1, HashSetType1>& lhs,
96*795d594fSAndroid Build Coastguard Worker const HashSetIterator<Elem2, HashSetType2>& rhs);
97*795d594fSAndroid Build Coastguard Worker template <class T, class EmptyFn, class HashFn, class Pred, class Alloc> friend class HashSet;
98*795d594fSAndroid Build Coastguard Worker template <class OtherElem, class OtherHashSetType> friend class HashSetIterator;
99*795d594fSAndroid Build Coastguard Worker };
100*795d594fSAndroid Build Coastguard Worker
101*795d594fSAndroid Build Coastguard Worker template <class Elem1, class HashSetType1, class Elem2, class HashSetType2>
102*795d594fSAndroid Build Coastguard Worker bool operator==(const HashSetIterator<Elem1, HashSetType1>& lhs,
103*795d594fSAndroid Build Coastguard Worker const HashSetIterator<Elem2, HashSetType2>& rhs) {
104*795d594fSAndroid Build Coastguard Worker static_assert(
105*795d594fSAndroid Build Coastguard Worker std::is_convertible_v<HashSetIterator<Elem1, HashSetType1>,
106*795d594fSAndroid Build Coastguard Worker HashSetIterator<Elem2, HashSetType2>> ||
107*795d594fSAndroid Build Coastguard Worker std::is_convertible_v<HashSetIterator<Elem2, HashSetType2>,
108*795d594fSAndroid Build Coastguard Worker HashSetIterator<Elem1, HashSetType1>>, "Bad iterator types.");
109*795d594fSAndroid Build Coastguard Worker DCHECK_EQ(lhs.hash_set_, rhs.hash_set_);
110*795d594fSAndroid Build Coastguard Worker return lhs.index_ == rhs.index_;
111*795d594fSAndroid Build Coastguard Worker }
112*795d594fSAndroid Build Coastguard Worker
113*795d594fSAndroid Build Coastguard Worker template <class Elem1, class HashSetType1, class Elem2, class HashSetType2>
114*795d594fSAndroid Build Coastguard Worker bool operator!=(const HashSetIterator<Elem1, HashSetType1>& lhs,
115*795d594fSAndroid Build Coastguard Worker const HashSetIterator<Elem2, HashSetType2>& rhs) {
116*795d594fSAndroid Build Coastguard Worker return !(lhs == rhs);
117*795d594fSAndroid Build Coastguard Worker }
118*795d594fSAndroid Build Coastguard Worker
119*795d594fSAndroid Build Coastguard Worker // Returns true if an item is empty.
120*795d594fSAndroid Build Coastguard Worker template <class T>
121*795d594fSAndroid Build Coastguard Worker class DefaultEmptyFn {
122*795d594fSAndroid Build Coastguard Worker public:
MakeEmpty(T & item)123*795d594fSAndroid Build Coastguard Worker void MakeEmpty(T& item) const {
124*795d594fSAndroid Build Coastguard Worker item = T();
125*795d594fSAndroid Build Coastguard Worker }
IsEmpty(const T & item)126*795d594fSAndroid Build Coastguard Worker bool IsEmpty(const T& item) const {
127*795d594fSAndroid Build Coastguard Worker return item == T();
128*795d594fSAndroid Build Coastguard Worker }
129*795d594fSAndroid Build Coastguard Worker };
130*795d594fSAndroid Build Coastguard Worker
131*795d594fSAndroid Build Coastguard Worker template <class T>
132*795d594fSAndroid Build Coastguard Worker class DefaultEmptyFn<T*> {
133*795d594fSAndroid Build Coastguard Worker public:
MakeEmpty(T * & item)134*795d594fSAndroid Build Coastguard Worker void MakeEmpty(T*& item) const {
135*795d594fSAndroid Build Coastguard Worker item = nullptr;
136*795d594fSAndroid Build Coastguard Worker }
IsEmpty(T * const & item)137*795d594fSAndroid Build Coastguard Worker bool IsEmpty(T* const& item) const {
138*795d594fSAndroid Build Coastguard Worker return item == nullptr;
139*795d594fSAndroid Build Coastguard Worker }
140*795d594fSAndroid Build Coastguard Worker };
141*795d594fSAndroid Build Coastguard Worker
142*795d594fSAndroid Build Coastguard Worker template <>
143*795d594fSAndroid Build Coastguard Worker class DefaultEmptyFn<std::string> {
144*795d594fSAndroid Build Coastguard Worker public:
MakeEmpty(std::string & item)145*795d594fSAndroid Build Coastguard Worker void MakeEmpty(std::string& item) const {
146*795d594fSAndroid Build Coastguard Worker item = std::string();
147*795d594fSAndroid Build Coastguard Worker }
IsEmpty(const std::string & item)148*795d594fSAndroid Build Coastguard Worker bool IsEmpty(const std::string& item) const {
149*795d594fSAndroid Build Coastguard Worker return item.empty();
150*795d594fSAndroid Build Coastguard Worker }
151*795d594fSAndroid Build Coastguard Worker };
152*795d594fSAndroid Build Coastguard Worker
153*795d594fSAndroid Build Coastguard Worker template <class T>
154*795d594fSAndroid Build Coastguard Worker using DefaultHashFn = std::conditional_t<std::is_same_v<T, std::string>, DataHash, std::hash<T>>;
155*795d594fSAndroid Build Coastguard Worker
156*795d594fSAndroid Build Coastguard Worker struct DefaultStringEquals {
157*795d594fSAndroid Build Coastguard Worker // Allow comparison with anything that can be compared to std::string,
158*795d594fSAndroid Build Coastguard Worker // for example std::string_view.
159*795d594fSAndroid Build Coastguard Worker template <typename T>
operatorDefaultStringEquals160*795d594fSAndroid Build Coastguard Worker bool operator()(const std::string& lhs, const T& rhs) const {
161*795d594fSAndroid Build Coastguard Worker return lhs == rhs;
162*795d594fSAndroid Build Coastguard Worker }
163*795d594fSAndroid Build Coastguard Worker };
164*795d594fSAndroid Build Coastguard Worker
165*795d594fSAndroid Build Coastguard Worker template <class T>
166*795d594fSAndroid Build Coastguard Worker using DefaultPred =
167*795d594fSAndroid Build Coastguard Worker std::conditional_t<std::is_same_v<T, std::string>, DefaultStringEquals, std::equal_to<T>>;
168*795d594fSAndroid Build Coastguard Worker
169*795d594fSAndroid Build Coastguard Worker // Low memory version of a hash set, uses less memory than std::unordered_multiset since elements
170*795d594fSAndroid Build Coastguard Worker // aren't boxed. Uses linear probing to resolve collisions.
171*795d594fSAndroid Build Coastguard Worker // EmptyFn needs to implement two functions MakeEmpty(T& item) and IsEmpty(const T& item).
172*795d594fSAndroid Build Coastguard Worker // TODO: We could get rid of this requirement by using a bitmap, though maybe this would be slower
173*795d594fSAndroid Build Coastguard Worker // and more complicated.
174*795d594fSAndroid Build Coastguard Worker template <class T,
175*795d594fSAndroid Build Coastguard Worker class EmptyFn = DefaultEmptyFn<T>,
176*795d594fSAndroid Build Coastguard Worker class HashFn = DefaultHashFn<T>,
177*795d594fSAndroid Build Coastguard Worker class Pred = DefaultPred<T>,
178*795d594fSAndroid Build Coastguard Worker class Alloc = std::allocator<T>>
179*795d594fSAndroid Build Coastguard Worker class HashSet {
180*795d594fSAndroid Build Coastguard Worker public:
181*795d594fSAndroid Build Coastguard Worker using value_type = T;
182*795d594fSAndroid Build Coastguard Worker using allocator_type = Alloc;
183*795d594fSAndroid Build Coastguard Worker using reference = T&;
184*795d594fSAndroid Build Coastguard Worker using const_reference = const T&;
185*795d594fSAndroid Build Coastguard Worker using pointer = T*;
186*795d594fSAndroid Build Coastguard Worker using const_pointer = const T*;
187*795d594fSAndroid Build Coastguard Worker using iterator = HashSetIterator<T, HashSet>;
188*795d594fSAndroid Build Coastguard Worker using const_iterator = HashSetIterator<const T, const HashSet>;
189*795d594fSAndroid Build Coastguard Worker using size_type = size_t;
190*795d594fSAndroid Build Coastguard Worker using difference_type = ptrdiff_t;
191*795d594fSAndroid Build Coastguard Worker
192*795d594fSAndroid Build Coastguard Worker static constexpr double kDefaultMinLoadFactor = 0.4;
193*795d594fSAndroid Build Coastguard Worker static constexpr double kDefaultMaxLoadFactor = 0.7;
194*795d594fSAndroid Build Coastguard Worker static constexpr size_t kMinBuckets = 1000;
195*795d594fSAndroid Build Coastguard Worker
196*795d594fSAndroid Build Coastguard Worker // If we don't own the data, this will create a new array which owns the data.
clear()197*795d594fSAndroid Build Coastguard Worker void clear() {
198*795d594fSAndroid Build Coastguard Worker DeallocateStorage();
199*795d594fSAndroid Build Coastguard Worker num_elements_ = 0;
200*795d594fSAndroid Build Coastguard Worker elements_until_expand_ = 0;
201*795d594fSAndroid Build Coastguard Worker }
202*795d594fSAndroid Build Coastguard Worker
HashSet()203*795d594fSAndroid Build Coastguard Worker HashSet() : HashSet(kDefaultMinLoadFactor, kDefaultMaxLoadFactor) {}
HashSet(const allocator_type & alloc)204*795d594fSAndroid Build Coastguard Worker explicit HashSet(const allocator_type& alloc) noexcept
205*795d594fSAndroid Build Coastguard Worker : HashSet(kDefaultMinLoadFactor, kDefaultMaxLoadFactor, alloc) {}
206*795d594fSAndroid Build Coastguard Worker
HashSet(double min_load_factor,double max_load_factor)207*795d594fSAndroid Build Coastguard Worker HashSet(double min_load_factor, double max_load_factor) noexcept
208*795d594fSAndroid Build Coastguard Worker : HashSet(min_load_factor, max_load_factor, allocator_type()) {}
HashSet(double min_load_factor,double max_load_factor,const allocator_type & alloc)209*795d594fSAndroid Build Coastguard Worker HashSet(double min_load_factor, double max_load_factor, const allocator_type& alloc) noexcept
210*795d594fSAndroid Build Coastguard Worker : HashSet(min_load_factor, max_load_factor, HashFn(), Pred(), alloc) {}
211*795d594fSAndroid Build Coastguard Worker
HashSet(const HashFn & hashfn,const Pred & pred)212*795d594fSAndroid Build Coastguard Worker HashSet(const HashFn& hashfn,
213*795d594fSAndroid Build Coastguard Worker const Pred& pred) noexcept
214*795d594fSAndroid Build Coastguard Worker : HashSet(kDefaultMinLoadFactor, kDefaultMaxLoadFactor, hashfn, pred) {}
HashSet(const HashFn & hashfn,const Pred & pred,const allocator_type & alloc)215*795d594fSAndroid Build Coastguard Worker HashSet(const HashFn& hashfn,
216*795d594fSAndroid Build Coastguard Worker const Pred& pred,
217*795d594fSAndroid Build Coastguard Worker const allocator_type& alloc) noexcept
218*795d594fSAndroid Build Coastguard Worker : HashSet(kDefaultMinLoadFactor, kDefaultMaxLoadFactor, hashfn, pred, alloc) {}
219*795d594fSAndroid Build Coastguard Worker
HashSet(double min_load_factor,double max_load_factor,const HashFn & hashfn,const Pred & pred)220*795d594fSAndroid Build Coastguard Worker HashSet(double min_load_factor,
221*795d594fSAndroid Build Coastguard Worker double max_load_factor,
222*795d594fSAndroid Build Coastguard Worker const HashFn& hashfn,
223*795d594fSAndroid Build Coastguard Worker const Pred& pred) noexcept
224*795d594fSAndroid Build Coastguard Worker : HashSet(min_load_factor, max_load_factor, hashfn, pred, allocator_type()) {}
HashSet(double min_load_factor,double max_load_factor,const HashFn & hashfn,const Pred & pred,const allocator_type & alloc)225*795d594fSAndroid Build Coastguard Worker HashSet(double min_load_factor,
226*795d594fSAndroid Build Coastguard Worker double max_load_factor,
227*795d594fSAndroid Build Coastguard Worker const HashFn& hashfn,
228*795d594fSAndroid Build Coastguard Worker const Pred& pred,
229*795d594fSAndroid Build Coastguard Worker const allocator_type& alloc) noexcept
230*795d594fSAndroid Build Coastguard Worker : allocfn_(alloc),
231*795d594fSAndroid Build Coastguard Worker hashfn_(hashfn),
232*795d594fSAndroid Build Coastguard Worker emptyfn_(),
233*795d594fSAndroid Build Coastguard Worker pred_(pred),
234*795d594fSAndroid Build Coastguard Worker num_elements_(0u),
235*795d594fSAndroid Build Coastguard Worker num_buckets_(0u),
236*795d594fSAndroid Build Coastguard Worker elements_until_expand_(0u),
237*795d594fSAndroid Build Coastguard Worker owns_data_(false),
238*795d594fSAndroid Build Coastguard Worker data_(nullptr),
239*795d594fSAndroid Build Coastguard Worker min_load_factor_(min_load_factor),
240*795d594fSAndroid Build Coastguard Worker max_load_factor_(max_load_factor) {
241*795d594fSAndroid Build Coastguard Worker DCHECK_GT(min_load_factor, 0.0);
242*795d594fSAndroid Build Coastguard Worker DCHECK_LT(max_load_factor, 1.0);
243*795d594fSAndroid Build Coastguard Worker }
244*795d594fSAndroid Build Coastguard Worker
HashSet(const HashSet & other)245*795d594fSAndroid Build Coastguard Worker HashSet(const HashSet& other)
246*795d594fSAndroid Build Coastguard Worker : allocfn_(other.allocfn_),
247*795d594fSAndroid Build Coastguard Worker hashfn_(other.hashfn_),
248*795d594fSAndroid Build Coastguard Worker emptyfn_(other.emptyfn_),
249*795d594fSAndroid Build Coastguard Worker pred_(other.pred_),
250*795d594fSAndroid Build Coastguard Worker num_elements_(other.num_elements_),
251*795d594fSAndroid Build Coastguard Worker num_buckets_(0),
252*795d594fSAndroid Build Coastguard Worker elements_until_expand_(other.elements_until_expand_),
253*795d594fSAndroid Build Coastguard Worker owns_data_(false),
254*795d594fSAndroid Build Coastguard Worker data_(nullptr),
255*795d594fSAndroid Build Coastguard Worker min_load_factor_(other.min_load_factor_),
256*795d594fSAndroid Build Coastguard Worker max_load_factor_(other.max_load_factor_) {
257*795d594fSAndroid Build Coastguard Worker AllocateStorage(other.NumBuckets());
258*795d594fSAndroid Build Coastguard Worker for (size_t i = 0; i < num_buckets_; ++i) {
259*795d594fSAndroid Build Coastguard Worker ElementForIndex(i) = other.data_[i];
260*795d594fSAndroid Build Coastguard Worker }
261*795d594fSAndroid Build Coastguard Worker }
262*795d594fSAndroid Build Coastguard Worker
263*795d594fSAndroid Build Coastguard Worker // noexcept required so that the move constructor is used instead of copy constructor.
264*795d594fSAndroid Build Coastguard Worker // b/27860101
HashSet(HashSet && other)265*795d594fSAndroid Build Coastguard Worker HashSet(HashSet&& other) noexcept
266*795d594fSAndroid Build Coastguard Worker : allocfn_(std::move(other.allocfn_)),
267*795d594fSAndroid Build Coastguard Worker hashfn_(std::move(other.hashfn_)),
268*795d594fSAndroid Build Coastguard Worker emptyfn_(std::move(other.emptyfn_)),
269*795d594fSAndroid Build Coastguard Worker pred_(std::move(other.pred_)),
270*795d594fSAndroid Build Coastguard Worker num_elements_(other.num_elements_),
271*795d594fSAndroid Build Coastguard Worker num_buckets_(other.num_buckets_),
272*795d594fSAndroid Build Coastguard Worker elements_until_expand_(other.elements_until_expand_),
273*795d594fSAndroid Build Coastguard Worker owns_data_(other.owns_data_),
274*795d594fSAndroid Build Coastguard Worker data_(other.data_),
275*795d594fSAndroid Build Coastguard Worker min_load_factor_(other.min_load_factor_),
276*795d594fSAndroid Build Coastguard Worker max_load_factor_(other.max_load_factor_) {
277*795d594fSAndroid Build Coastguard Worker other.num_elements_ = 0u;
278*795d594fSAndroid Build Coastguard Worker other.num_buckets_ = 0u;
279*795d594fSAndroid Build Coastguard Worker other.elements_until_expand_ = 0u;
280*795d594fSAndroid Build Coastguard Worker other.owns_data_ = false;
281*795d594fSAndroid Build Coastguard Worker other.data_ = nullptr;
282*795d594fSAndroid Build Coastguard Worker }
283*795d594fSAndroid Build Coastguard Worker
284*795d594fSAndroid Build Coastguard Worker // Construct with pre-existing buffer, usually stack-allocated,
285*795d594fSAndroid Build Coastguard Worker // to avoid malloc/free overhead for small HashSet<>s.
HashSet(value_type * buffer,size_t buffer_size)286*795d594fSAndroid Build Coastguard Worker HashSet(value_type* buffer, size_t buffer_size)
287*795d594fSAndroid Build Coastguard Worker : HashSet(kDefaultMinLoadFactor, kDefaultMaxLoadFactor, buffer, buffer_size) {}
HashSet(value_type * buffer,size_t buffer_size,const allocator_type & alloc)288*795d594fSAndroid Build Coastguard Worker HashSet(value_type* buffer, size_t buffer_size, const allocator_type& alloc)
289*795d594fSAndroid Build Coastguard Worker : HashSet(kDefaultMinLoadFactor, kDefaultMaxLoadFactor, buffer, buffer_size, alloc) {}
HashSet(double min_load_factor,double max_load_factor,value_type * buffer,size_t buffer_size)290*795d594fSAndroid Build Coastguard Worker HashSet(double min_load_factor, double max_load_factor, value_type* buffer, size_t buffer_size)
291*795d594fSAndroid Build Coastguard Worker : HashSet(min_load_factor, max_load_factor, buffer, buffer_size, allocator_type()) {}
HashSet(double min_load_factor,double max_load_factor,value_type * buffer,size_t buffer_size,const allocator_type & alloc)292*795d594fSAndroid Build Coastguard Worker HashSet(double min_load_factor,
293*795d594fSAndroid Build Coastguard Worker double max_load_factor,
294*795d594fSAndroid Build Coastguard Worker value_type* buffer,
295*795d594fSAndroid Build Coastguard Worker size_t buffer_size,
296*795d594fSAndroid Build Coastguard Worker const allocator_type& alloc)
297*795d594fSAndroid Build Coastguard Worker : HashSet(min_load_factor, max_load_factor, HashFn(), Pred(), buffer, buffer_size, alloc) {}
HashSet(double min_load_factor,double max_load_factor,const HashFn & hashfn,const Pred & pred,value_type * buffer,size_t buffer_size,const allocator_type & alloc)298*795d594fSAndroid Build Coastguard Worker HashSet(double min_load_factor,
299*795d594fSAndroid Build Coastguard Worker double max_load_factor,
300*795d594fSAndroid Build Coastguard Worker const HashFn& hashfn,
301*795d594fSAndroid Build Coastguard Worker const Pred& pred,
302*795d594fSAndroid Build Coastguard Worker value_type* buffer,
303*795d594fSAndroid Build Coastguard Worker size_t buffer_size,
304*795d594fSAndroid Build Coastguard Worker const allocator_type& alloc)
305*795d594fSAndroid Build Coastguard Worker : allocfn_(alloc),
306*795d594fSAndroid Build Coastguard Worker hashfn_(hashfn),
307*795d594fSAndroid Build Coastguard Worker pred_(pred),
308*795d594fSAndroid Build Coastguard Worker num_elements_(0u),
309*795d594fSAndroid Build Coastguard Worker num_buckets_(buffer_size),
310*795d594fSAndroid Build Coastguard Worker elements_until_expand_(buffer_size * max_load_factor),
311*795d594fSAndroid Build Coastguard Worker owns_data_(false),
312*795d594fSAndroid Build Coastguard Worker data_(buffer),
313*795d594fSAndroid Build Coastguard Worker min_load_factor_(min_load_factor),
314*795d594fSAndroid Build Coastguard Worker max_load_factor_(max_load_factor) {
315*795d594fSAndroid Build Coastguard Worker DCHECK_GT(min_load_factor, 0.0);
316*795d594fSAndroid Build Coastguard Worker DCHECK_LT(max_load_factor, 1.0);
317*795d594fSAndroid Build Coastguard Worker for (size_t i = 0; i != buffer_size; ++i) {
318*795d594fSAndroid Build Coastguard Worker emptyfn_.MakeEmpty(buffer[i]);
319*795d594fSAndroid Build Coastguard Worker }
320*795d594fSAndroid Build Coastguard Worker }
321*795d594fSAndroid Build Coastguard Worker
322*795d594fSAndroid Build Coastguard Worker // Construct from existing data.
323*795d594fSAndroid Build Coastguard Worker // Read from a block of memory, if make_copy_of_data is false, then data_ points to within the
324*795d594fSAndroid Build Coastguard Worker // passed in ptr_.
HashSet(const uint8_t * ptr,bool make_copy_of_data,size_t * read_count)325*795d594fSAndroid Build Coastguard Worker HashSet(const uint8_t* ptr, bool make_copy_of_data, size_t* read_count) noexcept {
326*795d594fSAndroid Build Coastguard Worker uint64_t temp;
327*795d594fSAndroid Build Coastguard Worker size_t offset = 0;
328*795d594fSAndroid Build Coastguard Worker offset = ReadFromBytes(ptr, offset, &temp);
329*795d594fSAndroid Build Coastguard Worker num_elements_ = static_cast<uint64_t>(temp);
330*795d594fSAndroid Build Coastguard Worker offset = ReadFromBytes(ptr, offset, &temp);
331*795d594fSAndroid Build Coastguard Worker num_buckets_ = static_cast<uint64_t>(temp);
332*795d594fSAndroid Build Coastguard Worker CHECK_LE(num_elements_, num_buckets_);
333*795d594fSAndroid Build Coastguard Worker offset = ReadFromBytes(ptr, offset, &temp);
334*795d594fSAndroid Build Coastguard Worker elements_until_expand_ = static_cast<uint64_t>(temp);
335*795d594fSAndroid Build Coastguard Worker offset = ReadFromBytes(ptr, offset, &min_load_factor_);
336*795d594fSAndroid Build Coastguard Worker offset = ReadFromBytes(ptr, offset, &max_load_factor_);
337*795d594fSAndroid Build Coastguard Worker if (!make_copy_of_data) {
338*795d594fSAndroid Build Coastguard Worker owns_data_ = false;
339*795d594fSAndroid Build Coastguard Worker data_ = const_cast<T*>(reinterpret_cast<const T*>(ptr + offset));
340*795d594fSAndroid Build Coastguard Worker offset += sizeof(*data_) * num_buckets_;
341*795d594fSAndroid Build Coastguard Worker } else {
342*795d594fSAndroid Build Coastguard Worker AllocateStorage(num_buckets_);
343*795d594fSAndroid Build Coastguard Worker // Write elements, not that this may not be safe for cross compilation if the elements are
344*795d594fSAndroid Build Coastguard Worker // pointer sized.
345*795d594fSAndroid Build Coastguard Worker for (size_t i = 0; i < num_buckets_; ++i) {
346*795d594fSAndroid Build Coastguard Worker offset = ReadFromBytes(ptr, offset, &data_[i]);
347*795d594fSAndroid Build Coastguard Worker }
348*795d594fSAndroid Build Coastguard Worker }
349*795d594fSAndroid Build Coastguard Worker // Caller responsible for aligning.
350*795d594fSAndroid Build Coastguard Worker *read_count = offset;
351*795d594fSAndroid Build Coastguard Worker }
352*795d594fSAndroid Build Coastguard Worker
353*795d594fSAndroid Build Coastguard Worker // Returns how large the table is after being written. If target is null, then no writing happens
354*795d594fSAndroid Build Coastguard Worker // but the size is still returned. Target must be 8 byte aligned.
WriteToMemory(uint8_t * ptr)355*795d594fSAndroid Build Coastguard Worker size_t WriteToMemory(uint8_t* ptr) const {
356*795d594fSAndroid Build Coastguard Worker size_t offset = 0;
357*795d594fSAndroid Build Coastguard Worker offset = WriteToBytes(ptr, offset, static_cast<uint64_t>(num_elements_));
358*795d594fSAndroid Build Coastguard Worker offset = WriteToBytes(ptr, offset, static_cast<uint64_t>(num_buckets_));
359*795d594fSAndroid Build Coastguard Worker offset = WriteToBytes(ptr, offset, static_cast<uint64_t>(elements_until_expand_));
360*795d594fSAndroid Build Coastguard Worker offset = WriteToBytes(ptr, offset, min_load_factor_);
361*795d594fSAndroid Build Coastguard Worker offset = WriteToBytes(ptr, offset, max_load_factor_);
362*795d594fSAndroid Build Coastguard Worker // Write elements, not that this may not be safe for cross compilation if the elements are
363*795d594fSAndroid Build Coastguard Worker // pointer sized.
364*795d594fSAndroid Build Coastguard Worker for (size_t i = 0; i < num_buckets_; ++i) {
365*795d594fSAndroid Build Coastguard Worker offset = WriteToBytes(ptr, offset, data_[i]);
366*795d594fSAndroid Build Coastguard Worker }
367*795d594fSAndroid Build Coastguard Worker // Caller responsible for aligning.
368*795d594fSAndroid Build Coastguard Worker return offset;
369*795d594fSAndroid Build Coastguard Worker }
370*795d594fSAndroid Build Coastguard Worker
~HashSet()371*795d594fSAndroid Build Coastguard Worker ~HashSet() {
372*795d594fSAndroid Build Coastguard Worker DeallocateStorage();
373*795d594fSAndroid Build Coastguard Worker }
374*795d594fSAndroid Build Coastguard Worker
375*795d594fSAndroid Build Coastguard Worker HashSet& operator=(HashSet&& other) noexcept {
376*795d594fSAndroid Build Coastguard Worker HashSet(std::move(other)).swap(*this); // NOLINT [runtime/explicit] [5]
377*795d594fSAndroid Build Coastguard Worker return *this;
378*795d594fSAndroid Build Coastguard Worker }
379*795d594fSAndroid Build Coastguard Worker
380*795d594fSAndroid Build Coastguard Worker HashSet& operator=(const HashSet& other) {
381*795d594fSAndroid Build Coastguard Worker HashSet(other).swap(*this); // NOLINT(runtime/explicit) - a case of lint gone mad.
382*795d594fSAndroid Build Coastguard Worker return *this;
383*795d594fSAndroid Build Coastguard Worker }
384*795d594fSAndroid Build Coastguard Worker
385*795d594fSAndroid Build Coastguard Worker // Lower case for c++11 for each.
begin()386*795d594fSAndroid Build Coastguard Worker iterator begin() {
387*795d594fSAndroid Build Coastguard Worker iterator ret(this, 0);
388*795d594fSAndroid Build Coastguard Worker if (num_buckets_ != 0 && IsFreeSlot(ret.index_)) {
389*795d594fSAndroid Build Coastguard Worker ++ret; // Skip all the empty slots.
390*795d594fSAndroid Build Coastguard Worker }
391*795d594fSAndroid Build Coastguard Worker return ret;
392*795d594fSAndroid Build Coastguard Worker }
393*795d594fSAndroid Build Coastguard Worker
394*795d594fSAndroid Build Coastguard Worker // Lower case for c++11 for each. const version.
begin()395*795d594fSAndroid Build Coastguard Worker const_iterator begin() const {
396*795d594fSAndroid Build Coastguard Worker const_iterator ret(this, 0);
397*795d594fSAndroid Build Coastguard Worker if (num_buckets_ != 0 && IsFreeSlot(ret.index_)) {
398*795d594fSAndroid Build Coastguard Worker ++ret; // Skip all the empty slots.
399*795d594fSAndroid Build Coastguard Worker }
400*795d594fSAndroid Build Coastguard Worker return ret;
401*795d594fSAndroid Build Coastguard Worker }
402*795d594fSAndroid Build Coastguard Worker
403*795d594fSAndroid Build Coastguard Worker // Lower case for c++11 for each.
end()404*795d594fSAndroid Build Coastguard Worker iterator end() {
405*795d594fSAndroid Build Coastguard Worker return iterator(this, NumBuckets());
406*795d594fSAndroid Build Coastguard Worker }
407*795d594fSAndroid Build Coastguard Worker
408*795d594fSAndroid Build Coastguard Worker // Lower case for c++11 for each. const version.
end()409*795d594fSAndroid Build Coastguard Worker const_iterator end() const {
410*795d594fSAndroid Build Coastguard Worker return const_iterator(this, NumBuckets());
411*795d594fSAndroid Build Coastguard Worker }
412*795d594fSAndroid Build Coastguard Worker
size()413*795d594fSAndroid Build Coastguard Worker size_t size() const {
414*795d594fSAndroid Build Coastguard Worker return num_elements_;
415*795d594fSAndroid Build Coastguard Worker }
416*795d594fSAndroid Build Coastguard Worker
empty()417*795d594fSAndroid Build Coastguard Worker bool empty() const {
418*795d594fSAndroid Build Coastguard Worker return size() == 0;
419*795d594fSAndroid Build Coastguard Worker }
420*795d594fSAndroid Build Coastguard Worker
421*795d594fSAndroid Build Coastguard Worker // Erase algorithm:
422*795d594fSAndroid Build Coastguard Worker // Make an empty slot where the iterator is pointing.
423*795d594fSAndroid Build Coastguard Worker // Scan forwards until we hit another empty slot.
424*795d594fSAndroid Build Coastguard Worker // If an element in between doesn't rehash to the range from the current empty slot to the
425*795d594fSAndroid Build Coastguard Worker // iterator. It must be before the empty slot, in that case we can move it to the empty slot
426*795d594fSAndroid Build Coastguard Worker // and set the empty slot to be the location we just moved from.
427*795d594fSAndroid Build Coastguard Worker // Relies on maintaining the invariant that there's no empty slots from the 'ideal' index of an
428*795d594fSAndroid Build Coastguard Worker // element to its actual location/index.
429*795d594fSAndroid Build Coastguard Worker // Note that since erase shuffles back elements, it may result in the same element being visited
430*795d594fSAndroid Build Coastguard Worker // twice during HashSet iteration. This happens when an element already visited during iteration
431*795d594fSAndroid Build Coastguard Worker // gets shuffled to the end of the bucket array.
erase(iterator it)432*795d594fSAndroid Build Coastguard Worker iterator erase(iterator it) {
433*795d594fSAndroid Build Coastguard Worker // empty_index is the index that will become empty.
434*795d594fSAndroid Build Coastguard Worker size_t empty_index = it.index_;
435*795d594fSAndroid Build Coastguard Worker DCHECK(!IsFreeSlot(empty_index));
436*795d594fSAndroid Build Coastguard Worker size_t next_index = empty_index;
437*795d594fSAndroid Build Coastguard Worker bool filled = false; // True if we filled the empty index.
438*795d594fSAndroid Build Coastguard Worker while (true) {
439*795d594fSAndroid Build Coastguard Worker next_index = NextIndex(next_index);
440*795d594fSAndroid Build Coastguard Worker T& next_element = ElementForIndex(next_index);
441*795d594fSAndroid Build Coastguard Worker // If the next element is empty, we are done. Make sure to clear the current empty index.
442*795d594fSAndroid Build Coastguard Worker if (emptyfn_.IsEmpty(next_element)) {
443*795d594fSAndroid Build Coastguard Worker emptyfn_.MakeEmpty(ElementForIndex(empty_index));
444*795d594fSAndroid Build Coastguard Worker break;
445*795d594fSAndroid Build Coastguard Worker }
446*795d594fSAndroid Build Coastguard Worker // Otherwise try to see if the next element can fill the current empty index.
447*795d594fSAndroid Build Coastguard Worker const size_t next_hash = hashfn_(next_element);
448*795d594fSAndroid Build Coastguard Worker // Calculate the ideal index, if it is within empty_index + 1 to next_index then there is
449*795d594fSAndroid Build Coastguard Worker // nothing we can do.
450*795d594fSAndroid Build Coastguard Worker size_t next_ideal_index = IndexForHash(next_hash);
451*795d594fSAndroid Build Coastguard Worker // Loop around if needed for our check.
452*795d594fSAndroid Build Coastguard Worker size_t unwrapped_next_index = next_index;
453*795d594fSAndroid Build Coastguard Worker if (unwrapped_next_index < empty_index) {
454*795d594fSAndroid Build Coastguard Worker unwrapped_next_index += NumBuckets();
455*795d594fSAndroid Build Coastguard Worker }
456*795d594fSAndroid Build Coastguard Worker // Loop around if needed for our check.
457*795d594fSAndroid Build Coastguard Worker size_t unwrapped_next_ideal_index = next_ideal_index;
458*795d594fSAndroid Build Coastguard Worker if (unwrapped_next_ideal_index < empty_index) {
459*795d594fSAndroid Build Coastguard Worker unwrapped_next_ideal_index += NumBuckets();
460*795d594fSAndroid Build Coastguard Worker }
461*795d594fSAndroid Build Coastguard Worker if (unwrapped_next_ideal_index <= empty_index ||
462*795d594fSAndroid Build Coastguard Worker unwrapped_next_ideal_index > unwrapped_next_index) {
463*795d594fSAndroid Build Coastguard Worker // If the target index isn't within our current range it must have been probed from before
464*795d594fSAndroid Build Coastguard Worker // the empty index.
465*795d594fSAndroid Build Coastguard Worker ElementForIndex(empty_index) = std::move(next_element);
466*795d594fSAndroid Build Coastguard Worker filled = true; // TODO: Optimize
467*795d594fSAndroid Build Coastguard Worker empty_index = next_index;
468*795d594fSAndroid Build Coastguard Worker }
469*795d594fSAndroid Build Coastguard Worker }
470*795d594fSAndroid Build Coastguard Worker --num_elements_;
471*795d594fSAndroid Build Coastguard Worker // If we didn't fill the slot then we need go to the next non free slot.
472*795d594fSAndroid Build Coastguard Worker if (!filled) {
473*795d594fSAndroid Build Coastguard Worker ++it;
474*795d594fSAndroid Build Coastguard Worker }
475*795d594fSAndroid Build Coastguard Worker return it;
476*795d594fSAndroid Build Coastguard Worker }
477*795d594fSAndroid Build Coastguard Worker
478*795d594fSAndroid Build Coastguard Worker // Find an element, returns end() if not found.
479*795d594fSAndroid Build Coastguard Worker // Allows custom key (K) types, example of when this is useful:
480*795d594fSAndroid Build Coastguard Worker // Set of Class* indexed by name, want to find a class with a name but can't allocate
481*795d594fSAndroid Build Coastguard Worker // a temporary Class object in the heap for performance solution.
482*795d594fSAndroid Build Coastguard Worker template <typename K>
find(const K & key)483*795d594fSAndroid Build Coastguard Worker iterator find(const K& key) {
484*795d594fSAndroid Build Coastguard Worker return FindWithHash(key, hashfn_(key));
485*795d594fSAndroid Build Coastguard Worker }
486*795d594fSAndroid Build Coastguard Worker
487*795d594fSAndroid Build Coastguard Worker template <typename K>
find(const K & key)488*795d594fSAndroid Build Coastguard Worker const_iterator find(const K& key) const {
489*795d594fSAndroid Build Coastguard Worker return FindWithHash(key, hashfn_(key));
490*795d594fSAndroid Build Coastguard Worker }
491*795d594fSAndroid Build Coastguard Worker
492*795d594fSAndroid Build Coastguard Worker template <typename K>
FindWithHash(const K & key,size_t hash)493*795d594fSAndroid Build Coastguard Worker iterator FindWithHash(const K& key, size_t hash) {
494*795d594fSAndroid Build Coastguard Worker return iterator(this, FindIndex(key, hash));
495*795d594fSAndroid Build Coastguard Worker }
496*795d594fSAndroid Build Coastguard Worker
497*795d594fSAndroid Build Coastguard Worker template <typename K>
FindWithHash(const K & key,size_t hash)498*795d594fSAndroid Build Coastguard Worker const_iterator FindWithHash(const K& key, size_t hash) const {
499*795d594fSAndroid Build Coastguard Worker return const_iterator(this, FindIndex(key, hash));
500*795d594fSAndroid Build Coastguard Worker }
501*795d594fSAndroid Build Coastguard Worker
502*795d594fSAndroid Build Coastguard Worker // Insert an element with hint.
503*795d594fSAndroid Build Coastguard Worker // Note: The hint is not very useful for a HashSet<> unless there are many hash conflicts
504*795d594fSAndroid Build Coastguard Worker // and in that case the use of HashSet<> itself should be reconsidered.
insert(const_iterator hint,const T & element)505*795d594fSAndroid Build Coastguard Worker std::pair<iterator, bool> insert([[maybe_unused]] const_iterator hint, const T& element) {
506*795d594fSAndroid Build Coastguard Worker return insert(element);
507*795d594fSAndroid Build Coastguard Worker }
insert(const_iterator hint,T && element)508*795d594fSAndroid Build Coastguard Worker std::pair<iterator, bool> insert([[maybe_unused]] const_iterator hint, T&& element) {
509*795d594fSAndroid Build Coastguard Worker return insert(std::move(element));
510*795d594fSAndroid Build Coastguard Worker }
511*795d594fSAndroid Build Coastguard Worker
512*795d594fSAndroid Build Coastguard Worker // Insert an element.
insert(const T & element)513*795d594fSAndroid Build Coastguard Worker std::pair<iterator, bool> insert(const T& element) {
514*795d594fSAndroid Build Coastguard Worker return InsertWithHash(element, hashfn_(element));
515*795d594fSAndroid Build Coastguard Worker }
insert(T && element)516*795d594fSAndroid Build Coastguard Worker std::pair<iterator, bool> insert(T&& element) {
517*795d594fSAndroid Build Coastguard Worker return InsertWithHash(std::move(element), hashfn_(element));
518*795d594fSAndroid Build Coastguard Worker }
519*795d594fSAndroid Build Coastguard Worker
520*795d594fSAndroid Build Coastguard Worker template <typename U, typename = std::enable_if_t<std::is_convertible_v<U, T>>>
InsertWithHash(U && element,size_t hash)521*795d594fSAndroid Build Coastguard Worker std::pair<iterator, bool> InsertWithHash(U&& element, size_t hash) {
522*795d594fSAndroid Build Coastguard Worker DCHECK_EQ(hash, hashfn_(element));
523*795d594fSAndroid Build Coastguard Worker if (num_elements_ >= elements_until_expand_) {
524*795d594fSAndroid Build Coastguard Worker Expand();
525*795d594fSAndroid Build Coastguard Worker DCHECK_LT(num_elements_, elements_until_expand_);
526*795d594fSAndroid Build Coastguard Worker }
527*795d594fSAndroid Build Coastguard Worker bool find_failed = false;
528*795d594fSAndroid Build Coastguard Worker auto find_fail_fn = [&](size_t index) ALWAYS_INLINE {
529*795d594fSAndroid Build Coastguard Worker find_failed = true;
530*795d594fSAndroid Build Coastguard Worker return index;
531*795d594fSAndroid Build Coastguard Worker };
532*795d594fSAndroid Build Coastguard Worker size_t index = FindIndexImpl(element, hash, find_fail_fn);
533*795d594fSAndroid Build Coastguard Worker if (find_failed) {
534*795d594fSAndroid Build Coastguard Worker data_[index] = std::forward<U>(element);
535*795d594fSAndroid Build Coastguard Worker ++num_elements_;
536*795d594fSAndroid Build Coastguard Worker }
537*795d594fSAndroid Build Coastguard Worker return std::make_pair(iterator(this, index), find_failed);
538*795d594fSAndroid Build Coastguard Worker }
539*795d594fSAndroid Build Coastguard Worker
540*795d594fSAndroid Build Coastguard Worker // Insert an element known not to be in the `HashSet<>`.
Put(const T & element)541*795d594fSAndroid Build Coastguard Worker void Put(const T& element) {
542*795d594fSAndroid Build Coastguard Worker return PutWithHash(element, hashfn_(element));
543*795d594fSAndroid Build Coastguard Worker }
Put(T && element)544*795d594fSAndroid Build Coastguard Worker void Put(T&& element) {
545*795d594fSAndroid Build Coastguard Worker return PutWithHash(std::move(element), hashfn_(element));
546*795d594fSAndroid Build Coastguard Worker }
547*795d594fSAndroid Build Coastguard Worker
548*795d594fSAndroid Build Coastguard Worker template <typename U, typename = std::enable_if_t<std::is_convertible_v<U, T>>>
PutWithHash(U && element,size_t hash)549*795d594fSAndroid Build Coastguard Worker void PutWithHash(U&& element, size_t hash) {
550*795d594fSAndroid Build Coastguard Worker DCHECK_EQ(hash, hashfn_(element));
551*795d594fSAndroid Build Coastguard Worker if (num_elements_ >= elements_until_expand_) {
552*795d594fSAndroid Build Coastguard Worker Expand();
553*795d594fSAndroid Build Coastguard Worker DCHECK_LT(num_elements_, elements_until_expand_);
554*795d594fSAndroid Build Coastguard Worker }
555*795d594fSAndroid Build Coastguard Worker auto find_fail_fn = [](size_t index) ALWAYS_INLINE { return index; };
556*795d594fSAndroid Build Coastguard Worker size_t index = FindIndexImpl</*kCanFind=*/ false>(element, hash, find_fail_fn);
557*795d594fSAndroid Build Coastguard Worker data_[index] = std::forward<U>(element);
558*795d594fSAndroid Build Coastguard Worker ++num_elements_;
559*795d594fSAndroid Build Coastguard Worker }
560*795d594fSAndroid Build Coastguard Worker
swap(HashSet & other)561*795d594fSAndroid Build Coastguard Worker void swap(HashSet& other) {
562*795d594fSAndroid Build Coastguard Worker // Use argument-dependent lookup with fall-back to std::swap() for function objects.
563*795d594fSAndroid Build Coastguard Worker using std::swap;
564*795d594fSAndroid Build Coastguard Worker swap(allocfn_, other.allocfn_);
565*795d594fSAndroid Build Coastguard Worker swap(hashfn_, other.hashfn_);
566*795d594fSAndroid Build Coastguard Worker swap(emptyfn_, other.emptyfn_);
567*795d594fSAndroid Build Coastguard Worker swap(pred_, other.pred_);
568*795d594fSAndroid Build Coastguard Worker std::swap(data_, other.data_);
569*795d594fSAndroid Build Coastguard Worker std::swap(num_buckets_, other.num_buckets_);
570*795d594fSAndroid Build Coastguard Worker std::swap(num_elements_, other.num_elements_);
571*795d594fSAndroid Build Coastguard Worker std::swap(elements_until_expand_, other.elements_until_expand_);
572*795d594fSAndroid Build Coastguard Worker std::swap(min_load_factor_, other.min_load_factor_);
573*795d594fSAndroid Build Coastguard Worker std::swap(max_load_factor_, other.max_load_factor_);
574*795d594fSAndroid Build Coastguard Worker std::swap(owns_data_, other.owns_data_);
575*795d594fSAndroid Build Coastguard Worker }
576*795d594fSAndroid Build Coastguard Worker
get_allocator()577*795d594fSAndroid Build Coastguard Worker allocator_type get_allocator() const {
578*795d594fSAndroid Build Coastguard Worker return allocfn_;
579*795d594fSAndroid Build Coastguard Worker }
580*795d594fSAndroid Build Coastguard Worker
ShrinkToMaximumLoad()581*795d594fSAndroid Build Coastguard Worker void ShrinkToMaximumLoad() {
582*795d594fSAndroid Build Coastguard Worker Resize(size() / max_load_factor_);
583*795d594fSAndroid Build Coastguard Worker }
584*795d594fSAndroid Build Coastguard Worker
585*795d594fSAndroid Build Coastguard Worker // Reserve enough room to insert until Size() == num_elements without requiring to grow the hash
586*795d594fSAndroid Build Coastguard Worker // set. No-op if the hash set is already large enough to do this.
reserve(size_t num_elements)587*795d594fSAndroid Build Coastguard Worker void reserve(size_t num_elements) {
588*795d594fSAndroid Build Coastguard Worker size_t num_buckets = num_elements / max_load_factor_;
589*795d594fSAndroid Build Coastguard Worker // Deal with rounding errors. Add one for rounding.
590*795d594fSAndroid Build Coastguard Worker while (static_cast<size_t>(num_buckets * max_load_factor_) <= num_elements + 1u) {
591*795d594fSAndroid Build Coastguard Worker ++num_buckets;
592*795d594fSAndroid Build Coastguard Worker }
593*795d594fSAndroid Build Coastguard Worker if (num_buckets > NumBuckets()) {
594*795d594fSAndroid Build Coastguard Worker Resize(num_buckets);
595*795d594fSAndroid Build Coastguard Worker }
596*795d594fSAndroid Build Coastguard Worker }
597*795d594fSAndroid Build Coastguard Worker
598*795d594fSAndroid Build Coastguard Worker // To distance that inserted elements were probed. Used for measuring how good hash functions
599*795d594fSAndroid Build Coastguard Worker // are.
TotalProbeDistance()600*795d594fSAndroid Build Coastguard Worker size_t TotalProbeDistance() const {
601*795d594fSAndroid Build Coastguard Worker size_t total = 0;
602*795d594fSAndroid Build Coastguard Worker for (size_t i = 0; i < NumBuckets(); ++i) {
603*795d594fSAndroid Build Coastguard Worker const T& element = ElementForIndex(i);
604*795d594fSAndroid Build Coastguard Worker if (!emptyfn_.IsEmpty(element)) {
605*795d594fSAndroid Build Coastguard Worker size_t ideal_location = IndexForHash(hashfn_(element));
606*795d594fSAndroid Build Coastguard Worker if (ideal_location > i) {
607*795d594fSAndroid Build Coastguard Worker total += i + NumBuckets() - ideal_location;
608*795d594fSAndroid Build Coastguard Worker } else {
609*795d594fSAndroid Build Coastguard Worker total += i - ideal_location;
610*795d594fSAndroid Build Coastguard Worker }
611*795d594fSAndroid Build Coastguard Worker }
612*795d594fSAndroid Build Coastguard Worker }
613*795d594fSAndroid Build Coastguard Worker return total;
614*795d594fSAndroid Build Coastguard Worker }
615*795d594fSAndroid Build Coastguard Worker
616*795d594fSAndroid Build Coastguard Worker // Calculate the current load factor and return it.
CalculateLoadFactor()617*795d594fSAndroid Build Coastguard Worker double CalculateLoadFactor() const {
618*795d594fSAndroid Build Coastguard Worker return static_cast<double>(size()) / static_cast<double>(NumBuckets());
619*795d594fSAndroid Build Coastguard Worker }
620*795d594fSAndroid Build Coastguard Worker
621*795d594fSAndroid Build Coastguard Worker // Make sure that everything reinserts in the right spot. Returns the number of errors.
Verify()622*795d594fSAndroid Build Coastguard Worker size_t Verify() NO_THREAD_SAFETY_ANALYSIS {
623*795d594fSAndroid Build Coastguard Worker size_t errors = 0;
624*795d594fSAndroid Build Coastguard Worker for (size_t i = 0; i < num_buckets_; ++i) {
625*795d594fSAndroid Build Coastguard Worker T& element = data_[i];
626*795d594fSAndroid Build Coastguard Worker if (!emptyfn_.IsEmpty(element)) {
627*795d594fSAndroid Build Coastguard Worker T temp;
628*795d594fSAndroid Build Coastguard Worker emptyfn_.MakeEmpty(temp);
629*795d594fSAndroid Build Coastguard Worker std::swap(temp, element);
630*795d594fSAndroid Build Coastguard Worker size_t first_slot = FirstAvailableSlot(IndexForHash(hashfn_(temp)));
631*795d594fSAndroid Build Coastguard Worker if (i != first_slot) {
632*795d594fSAndroid Build Coastguard Worker LOG(ERROR) << "Element " << i << " should be in slot " << first_slot;
633*795d594fSAndroid Build Coastguard Worker ++errors;
634*795d594fSAndroid Build Coastguard Worker }
635*795d594fSAndroid Build Coastguard Worker std::swap(temp, element);
636*795d594fSAndroid Build Coastguard Worker }
637*795d594fSAndroid Build Coastguard Worker }
638*795d594fSAndroid Build Coastguard Worker return errors;
639*795d594fSAndroid Build Coastguard Worker }
640*795d594fSAndroid Build Coastguard Worker
GetMinLoadFactor()641*795d594fSAndroid Build Coastguard Worker double GetMinLoadFactor() const {
642*795d594fSAndroid Build Coastguard Worker return min_load_factor_;
643*795d594fSAndroid Build Coastguard Worker }
644*795d594fSAndroid Build Coastguard Worker
GetMaxLoadFactor()645*795d594fSAndroid Build Coastguard Worker double GetMaxLoadFactor() const {
646*795d594fSAndroid Build Coastguard Worker return max_load_factor_;
647*795d594fSAndroid Build Coastguard Worker }
648*795d594fSAndroid Build Coastguard Worker
649*795d594fSAndroid Build Coastguard Worker // Change the load factor of the hash set. If the current load factor is greater than the max
650*795d594fSAndroid Build Coastguard Worker // specified, then we resize the hash table storage.
SetLoadFactor(double min_load_factor,double max_load_factor)651*795d594fSAndroid Build Coastguard Worker void SetLoadFactor(double min_load_factor, double max_load_factor) {
652*795d594fSAndroid Build Coastguard Worker DCHECK_LT(min_load_factor, max_load_factor);
653*795d594fSAndroid Build Coastguard Worker DCHECK_GT(min_load_factor, 0.0);
654*795d594fSAndroid Build Coastguard Worker DCHECK_LT(max_load_factor, 1.0);
655*795d594fSAndroid Build Coastguard Worker min_load_factor_ = min_load_factor;
656*795d594fSAndroid Build Coastguard Worker max_load_factor_ = max_load_factor;
657*795d594fSAndroid Build Coastguard Worker elements_until_expand_ = NumBuckets() * max_load_factor_;
658*795d594fSAndroid Build Coastguard Worker // If the current load factor isn't in the range, then resize to the mean of the minimum and
659*795d594fSAndroid Build Coastguard Worker // maximum load factor.
660*795d594fSAndroid Build Coastguard Worker const double load_factor = CalculateLoadFactor();
661*795d594fSAndroid Build Coastguard Worker if (load_factor > max_load_factor_) {
662*795d594fSAndroid Build Coastguard Worker Resize(size() / ((min_load_factor_ + max_load_factor_) * 0.5));
663*795d594fSAndroid Build Coastguard Worker }
664*795d594fSAndroid Build Coastguard Worker }
665*795d594fSAndroid Build Coastguard Worker
666*795d594fSAndroid Build Coastguard Worker // The hash set expands when Size() reaches ElementsUntilExpand().
ElementsUntilExpand()667*795d594fSAndroid Build Coastguard Worker size_t ElementsUntilExpand() const {
668*795d594fSAndroid Build Coastguard Worker return elements_until_expand_;
669*795d594fSAndroid Build Coastguard Worker }
670*795d594fSAndroid Build Coastguard Worker
NumBuckets()671*795d594fSAndroid Build Coastguard Worker size_t NumBuckets() const {
672*795d594fSAndroid Build Coastguard Worker return num_buckets_;
673*795d594fSAndroid Build Coastguard Worker }
674*795d594fSAndroid Build Coastguard Worker
675*795d594fSAndroid Build Coastguard Worker private:
ElementForIndex(size_t index)676*795d594fSAndroid Build Coastguard Worker T& ElementForIndex(size_t index) {
677*795d594fSAndroid Build Coastguard Worker DCHECK_LT(index, NumBuckets());
678*795d594fSAndroid Build Coastguard Worker DCHECK(data_ != nullptr);
679*795d594fSAndroid Build Coastguard Worker return data_[index];
680*795d594fSAndroid Build Coastguard Worker }
681*795d594fSAndroid Build Coastguard Worker
ElementForIndex(size_t index)682*795d594fSAndroid Build Coastguard Worker const T& ElementForIndex(size_t index) const {
683*795d594fSAndroid Build Coastguard Worker DCHECK_LT(index, NumBuckets());
684*795d594fSAndroid Build Coastguard Worker DCHECK(data_ != nullptr);
685*795d594fSAndroid Build Coastguard Worker return data_[index];
686*795d594fSAndroid Build Coastguard Worker }
687*795d594fSAndroid Build Coastguard Worker
IndexForHash(size_t hash)688*795d594fSAndroid Build Coastguard Worker size_t IndexForHash(size_t hash) const {
689*795d594fSAndroid Build Coastguard Worker // Protect against undefined behavior (division by zero).
690*795d594fSAndroid Build Coastguard Worker if (UNLIKELY(num_buckets_ == 0)) {
691*795d594fSAndroid Build Coastguard Worker return 0;
692*795d594fSAndroid Build Coastguard Worker }
693*795d594fSAndroid Build Coastguard Worker return hash % num_buckets_;
694*795d594fSAndroid Build Coastguard Worker }
695*795d594fSAndroid Build Coastguard Worker
NextIndex(size_t index)696*795d594fSAndroid Build Coastguard Worker size_t NextIndex(size_t index) const {
697*795d594fSAndroid Build Coastguard Worker if (UNLIKELY(++index >= num_buckets_)) {
698*795d594fSAndroid Build Coastguard Worker DCHECK_EQ(index, NumBuckets());
699*795d594fSAndroid Build Coastguard Worker return 0;
700*795d594fSAndroid Build Coastguard Worker }
701*795d594fSAndroid Build Coastguard Worker return index;
702*795d594fSAndroid Build Coastguard Worker }
703*795d594fSAndroid Build Coastguard Worker
704*795d594fSAndroid Build Coastguard Worker // Find the hash table slot for an element, or return NumBuckets() if not found.
705*795d594fSAndroid Build Coastguard Worker // This value for not found is important so that iterator(this, FindIndex(...)) == end().
706*795d594fSAndroid Build Coastguard Worker template <typename K>
707*795d594fSAndroid Build Coastguard Worker ALWAYS_INLINE
FindIndex(const K & element,size_t hash)708*795d594fSAndroid Build Coastguard Worker size_t FindIndex(const K& element, size_t hash) const {
709*795d594fSAndroid Build Coastguard Worker // Guard against failing to get an element for a non-existing index.
710*795d594fSAndroid Build Coastguard Worker if (UNLIKELY(NumBuckets() == 0)) {
711*795d594fSAndroid Build Coastguard Worker return 0;
712*795d594fSAndroid Build Coastguard Worker }
713*795d594fSAndroid Build Coastguard Worker auto fail_fn = [&]([[maybe_unused]] size_t index) ALWAYS_INLINE { return NumBuckets(); };
714*795d594fSAndroid Build Coastguard Worker return FindIndexImpl(element, hash, fail_fn);
715*795d594fSAndroid Build Coastguard Worker }
716*795d594fSAndroid Build Coastguard Worker
717*795d594fSAndroid Build Coastguard Worker // Find the hash table slot for an element, or return an empty slot index if not found.
718*795d594fSAndroid Build Coastguard Worker template <bool kCanFind = true, typename K, typename FailFn>
719*795d594fSAndroid Build Coastguard Worker ALWAYS_INLINE
FindIndexImpl(const K & element,size_t hash,FailFn fail_fn)720*795d594fSAndroid Build Coastguard Worker size_t FindIndexImpl(const K& element, size_t hash, FailFn fail_fn) const {
721*795d594fSAndroid Build Coastguard Worker DCHECK_NE(NumBuckets(), 0u);
722*795d594fSAndroid Build Coastguard Worker DCHECK_EQ(hashfn_(element), hash);
723*795d594fSAndroid Build Coastguard Worker size_t index = IndexForHash(hash);
724*795d594fSAndroid Build Coastguard Worker while (true) {
725*795d594fSAndroid Build Coastguard Worker const T& slot = ElementForIndex(index);
726*795d594fSAndroid Build Coastguard Worker if (emptyfn_.IsEmpty(slot)) {
727*795d594fSAndroid Build Coastguard Worker return fail_fn(index);
728*795d594fSAndroid Build Coastguard Worker }
729*795d594fSAndroid Build Coastguard Worker if (!kCanFind) {
730*795d594fSAndroid Build Coastguard Worker DCHECK(!pred_(slot, element));
731*795d594fSAndroid Build Coastguard Worker } else if (pred_(slot, element)) {
732*795d594fSAndroid Build Coastguard Worker return index;
733*795d594fSAndroid Build Coastguard Worker }
734*795d594fSAndroid Build Coastguard Worker index = NextIndex(index);
735*795d594fSAndroid Build Coastguard Worker }
736*795d594fSAndroid Build Coastguard Worker }
737*795d594fSAndroid Build Coastguard Worker
IsFreeSlot(size_t index)738*795d594fSAndroid Build Coastguard Worker bool IsFreeSlot(size_t index) const {
739*795d594fSAndroid Build Coastguard Worker return emptyfn_.IsEmpty(ElementForIndex(index));
740*795d594fSAndroid Build Coastguard Worker }
741*795d594fSAndroid Build Coastguard Worker
742*795d594fSAndroid Build Coastguard Worker // Allocate a number of buckets.
AllocateStorage(size_t num_buckets)743*795d594fSAndroid Build Coastguard Worker void AllocateStorage(size_t num_buckets) {
744*795d594fSAndroid Build Coastguard Worker num_buckets_ = num_buckets;
745*795d594fSAndroid Build Coastguard Worker data_ = allocfn_.allocate(num_buckets_);
746*795d594fSAndroid Build Coastguard Worker owns_data_ = true;
747*795d594fSAndroid Build Coastguard Worker for (size_t i = 0; i < num_buckets_; ++i) {
748*795d594fSAndroid Build Coastguard Worker std::allocator_traits<allocator_type>::construct(allocfn_, std::addressof(data_[i]));
749*795d594fSAndroid Build Coastguard Worker emptyfn_.MakeEmpty(data_[i]);
750*795d594fSAndroid Build Coastguard Worker }
751*795d594fSAndroid Build Coastguard Worker }
752*795d594fSAndroid Build Coastguard Worker
DeallocateStorage()753*795d594fSAndroid Build Coastguard Worker void DeallocateStorage() {
754*795d594fSAndroid Build Coastguard Worker if (owns_data_) {
755*795d594fSAndroid Build Coastguard Worker for (size_t i = 0; i < NumBuckets(); ++i) {
756*795d594fSAndroid Build Coastguard Worker std::allocator_traits<allocator_type>::destroy(allocfn_, std::addressof(data_[i]));
757*795d594fSAndroid Build Coastguard Worker }
758*795d594fSAndroid Build Coastguard Worker if (data_ != nullptr) {
759*795d594fSAndroid Build Coastguard Worker allocfn_.deallocate(data_, NumBuckets());
760*795d594fSAndroid Build Coastguard Worker }
761*795d594fSAndroid Build Coastguard Worker owns_data_ = false;
762*795d594fSAndroid Build Coastguard Worker }
763*795d594fSAndroid Build Coastguard Worker data_ = nullptr;
764*795d594fSAndroid Build Coastguard Worker num_buckets_ = 0;
765*795d594fSAndroid Build Coastguard Worker }
766*795d594fSAndroid Build Coastguard Worker
767*795d594fSAndroid Build Coastguard Worker // Expand the set based on the load factors.
Expand()768*795d594fSAndroid Build Coastguard Worker void Expand() {
769*795d594fSAndroid Build Coastguard Worker size_t min_index = static_cast<size_t>(size() / min_load_factor_);
770*795d594fSAndroid Build Coastguard Worker // Resize based on the minimum load factor.
771*795d594fSAndroid Build Coastguard Worker Resize(min_index);
772*795d594fSAndroid Build Coastguard Worker }
773*795d594fSAndroid Build Coastguard Worker
774*795d594fSAndroid Build Coastguard Worker // Expand / shrink the table to the new specified size.
Resize(size_t new_size)775*795d594fSAndroid Build Coastguard Worker void Resize(size_t new_size) {
776*795d594fSAndroid Build Coastguard Worker if (new_size < kMinBuckets) {
777*795d594fSAndroid Build Coastguard Worker new_size = kMinBuckets;
778*795d594fSAndroid Build Coastguard Worker }
779*795d594fSAndroid Build Coastguard Worker DCHECK_GE(new_size, size());
780*795d594fSAndroid Build Coastguard Worker T* const old_data = data_;
781*795d594fSAndroid Build Coastguard Worker size_t old_num_buckets = num_buckets_;
782*795d594fSAndroid Build Coastguard Worker // Reinsert all of the old elements.
783*795d594fSAndroid Build Coastguard Worker const bool owned_data = owns_data_;
784*795d594fSAndroid Build Coastguard Worker AllocateStorage(new_size);
785*795d594fSAndroid Build Coastguard Worker for (size_t i = 0; i < old_num_buckets; ++i) {
786*795d594fSAndroid Build Coastguard Worker T& element = old_data[i];
787*795d594fSAndroid Build Coastguard Worker if (!emptyfn_.IsEmpty(element)) {
788*795d594fSAndroid Build Coastguard Worker data_[FirstAvailableSlot(IndexForHash(hashfn_(element)))] = std::move(element);
789*795d594fSAndroid Build Coastguard Worker }
790*795d594fSAndroid Build Coastguard Worker if (owned_data) {
791*795d594fSAndroid Build Coastguard Worker std::allocator_traits<allocator_type>::destroy(allocfn_, std::addressof(element));
792*795d594fSAndroid Build Coastguard Worker }
793*795d594fSAndroid Build Coastguard Worker }
794*795d594fSAndroid Build Coastguard Worker if (owned_data) {
795*795d594fSAndroid Build Coastguard Worker allocfn_.deallocate(old_data, old_num_buckets);
796*795d594fSAndroid Build Coastguard Worker }
797*795d594fSAndroid Build Coastguard Worker
798*795d594fSAndroid Build Coastguard Worker // When we hit elements_until_expand_, we are at the max load factor and must expand again.
799*795d594fSAndroid Build Coastguard Worker elements_until_expand_ = NumBuckets() * max_load_factor_;
800*795d594fSAndroid Build Coastguard Worker }
801*795d594fSAndroid Build Coastguard Worker
FirstAvailableSlot(size_t index)802*795d594fSAndroid Build Coastguard Worker ALWAYS_INLINE size_t FirstAvailableSlot(size_t index) const {
803*795d594fSAndroid Build Coastguard Worker DCHECK_LT(index, NumBuckets()); // Don't try to get a slot out of range.
804*795d594fSAndroid Build Coastguard Worker size_t non_empty_count = 0;
805*795d594fSAndroid Build Coastguard Worker while (!emptyfn_.IsEmpty(data_[index])) {
806*795d594fSAndroid Build Coastguard Worker index = NextIndex(index);
807*795d594fSAndroid Build Coastguard Worker non_empty_count++;
808*795d594fSAndroid Build Coastguard Worker DCHECK_LE(non_empty_count, NumBuckets()); // Don't loop forever.
809*795d594fSAndroid Build Coastguard Worker }
810*795d594fSAndroid Build Coastguard Worker return index;
811*795d594fSAndroid Build Coastguard Worker }
812*795d594fSAndroid Build Coastguard Worker
NextNonEmptySlot(size_t index)813*795d594fSAndroid Build Coastguard Worker size_t NextNonEmptySlot(size_t index) const {
814*795d594fSAndroid Build Coastguard Worker const size_t num_buckets = NumBuckets();
815*795d594fSAndroid Build Coastguard Worker DCHECK_LT(index, num_buckets);
816*795d594fSAndroid Build Coastguard Worker do {
817*795d594fSAndroid Build Coastguard Worker ++index;
818*795d594fSAndroid Build Coastguard Worker } while (index < num_buckets && IsFreeSlot(index));
819*795d594fSAndroid Build Coastguard Worker return index;
820*795d594fSAndroid Build Coastguard Worker }
821*795d594fSAndroid Build Coastguard Worker
822*795d594fSAndroid Build Coastguard Worker // Return new offset.
823*795d594fSAndroid Build Coastguard Worker template <typename Elem>
WriteToBytes(uint8_t * ptr,size_t offset,Elem n)824*795d594fSAndroid Build Coastguard Worker static size_t WriteToBytes(uint8_t* ptr, size_t offset, Elem n) {
825*795d594fSAndroid Build Coastguard Worker DCHECK_ALIGNED(ptr + offset, sizeof(n));
826*795d594fSAndroid Build Coastguard Worker if (ptr != nullptr) {
827*795d594fSAndroid Build Coastguard Worker *reinterpret_cast<Elem*>(ptr + offset) = n;
828*795d594fSAndroid Build Coastguard Worker }
829*795d594fSAndroid Build Coastguard Worker return offset + sizeof(n);
830*795d594fSAndroid Build Coastguard Worker }
831*795d594fSAndroid Build Coastguard Worker
832*795d594fSAndroid Build Coastguard Worker template <typename Elem>
ReadFromBytes(const uint8_t * ptr,size_t offset,Elem * out)833*795d594fSAndroid Build Coastguard Worker static size_t ReadFromBytes(const uint8_t* ptr, size_t offset, Elem* out) {
834*795d594fSAndroid Build Coastguard Worker DCHECK(ptr != nullptr);
835*795d594fSAndroid Build Coastguard Worker DCHECK_ALIGNED(ptr + offset, sizeof(*out));
836*795d594fSAndroid Build Coastguard Worker *out = *reinterpret_cast<const Elem*>(ptr + offset);
837*795d594fSAndroid Build Coastguard Worker return offset + sizeof(*out);
838*795d594fSAndroid Build Coastguard Worker }
839*795d594fSAndroid Build Coastguard Worker
840*795d594fSAndroid Build Coastguard Worker Alloc allocfn_; // Allocator function.
841*795d594fSAndroid Build Coastguard Worker HashFn hashfn_; // Hashing function.
842*795d594fSAndroid Build Coastguard Worker EmptyFn emptyfn_; // IsEmpty/SetEmpty function.
843*795d594fSAndroid Build Coastguard Worker Pred pred_; // Equals function.
844*795d594fSAndroid Build Coastguard Worker size_t num_elements_; // Number of inserted elements.
845*795d594fSAndroid Build Coastguard Worker size_t num_buckets_; // Number of hash table buckets.
846*795d594fSAndroid Build Coastguard Worker size_t elements_until_expand_; // Maximum number of elements until we expand the table.
847*795d594fSAndroid Build Coastguard Worker bool owns_data_; // If we own data_ and are responsible for freeing it.
848*795d594fSAndroid Build Coastguard Worker T* data_; // Backing storage.
849*795d594fSAndroid Build Coastguard Worker double min_load_factor_;
850*795d594fSAndroid Build Coastguard Worker double max_load_factor_;
851*795d594fSAndroid Build Coastguard Worker
852*795d594fSAndroid Build Coastguard Worker template <class Elem, class HashSetType>
853*795d594fSAndroid Build Coastguard Worker friend class HashSetIterator;
854*795d594fSAndroid Build Coastguard Worker
855*795d594fSAndroid Build Coastguard Worker ART_FRIEND_TEST(InternTableTest, CrossHash);
856*795d594fSAndroid Build Coastguard Worker ART_FRIEND_TEST(HashSetTest, Preallocated);
857*795d594fSAndroid Build Coastguard Worker };
858*795d594fSAndroid Build Coastguard Worker
859*795d594fSAndroid Build Coastguard Worker template <class T, class EmptyFn, class HashFn, class Pred, class Alloc>
swap(HashSet<T,EmptyFn,HashFn,Pred,Alloc> & lhs,HashSet<T,EmptyFn,HashFn,Pred,Alloc> & rhs)860*795d594fSAndroid Build Coastguard Worker void swap(HashSet<T, EmptyFn, HashFn, Pred, Alloc>& lhs,
861*795d594fSAndroid Build Coastguard Worker HashSet<T, EmptyFn, HashFn, Pred, Alloc>& rhs) {
862*795d594fSAndroid Build Coastguard Worker lhs.swap(rhs);
863*795d594fSAndroid Build Coastguard Worker }
864*795d594fSAndroid Build Coastguard Worker
865*795d594fSAndroid Build Coastguard Worker } // namespace art
866*795d594fSAndroid Build Coastguard Worker
867*795d594fSAndroid Build Coastguard Worker #endif // ART_LIBARTBASE_BASE_HASH_SET_H_
868