1c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier/* 2c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * Copyright (C) 2014 The Android Open Source Project 3c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * 4c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * Licensed under the Apache License, Version 2.0 (the "License"); 5c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * you may not use this file except in compliance with the License. 6c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * You may obtain a copy of the License at 7c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * 8c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * http://www.apache.org/licenses/LICENSE-2.0 9c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * 10c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * Unless required by applicable law or agreed to in writing, software 11c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * distributed under the License is distributed on an "AS IS" BASIS, 12c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * See the License for the specific language governing permissions and 14c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier * limitations under the License. 15c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier */ 16c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 17c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#ifndef ART_RUNTIME_BASE_HASH_SET_H_ 18c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#define ART_RUNTIME_BASE_HASH_SET_H_ 19c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 20c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#include <functional> 211f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko#include <iterator> 22c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#include <memory> 23c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#include <stdint.h> 24c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#include <utility> 25c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 26d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier#include "bit_utils.h" 27c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#include "logging.h" 28c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 29c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartiernamespace art { 30c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 31c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier// Returns true if an item is empty. 32c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartiertemplate <class T> 33c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartierclass DefaultEmptyFn { 34c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier public: 35c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void MakeEmpty(T& item) const { 36c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier item = T(); 37c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 38c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool IsEmpty(const T& item) const { 39c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return item == T(); 40c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 41c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier}; 42c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 43c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartiertemplate <class T> 44c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartierclass DefaultEmptyFn<T*> { 45c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier public: 46c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void MakeEmpty(T*& item) const { 47c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier item = nullptr; 48c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 491f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko bool IsEmpty(T* const& item) const { 50c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return item == nullptr; 51c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 52c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier}; 53c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 54c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier// Low memory version of a hash set, uses less memory than std::unordered_set since elements aren't 5547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier// boxed. Uses linear probing to resolve collisions. 5647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier// EmptyFn needs to implement two functions MakeEmpty(T& item) and IsEmpty(const T& item). 5747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier// TODO: We could get rid of this requirement by using a bitmap, though maybe this would be slower 5847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier// and more complicated. 59c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartiertemplate <class T, class EmptyFn = DefaultEmptyFn<T>, class HashFn = std::hash<T>, 60c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier class Pred = std::equal_to<T>, class Alloc = std::allocator<T>> 61c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartierclass HashSet { 6247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <class Elem, class HashSetType> 631f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko class BaseIterator : std::iterator<std::forward_iterator_tag, Elem> { 64c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier public: 6547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator(const BaseIterator&) = default; 6647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator(BaseIterator&&) = default; 6747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator(HashSetType* hash_set, size_t index) : index_(index), hash_set_(hash_set) { 68c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 6947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator& operator=(const BaseIterator&) = default; 7047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator& operator=(BaseIterator&&) = default; 7147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 7247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier bool operator==(const BaseIterator& other) const { 7347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return hash_set_ == other.hash_set_ && this->index_ == other.index_; 74c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 7547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 7647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier bool operator!=(const BaseIterator& other) const { 77c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return !(*this == other); 78c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 7947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 8047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator operator++() { // Value after modification. 8147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier this->index_ = this->NextNonEmptySlot(this->index_, hash_set_); 82c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return *this; 83c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 8447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 8547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator operator++(int) { 861f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko BaseIterator temp = *this; 8747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier this->index_ = this->NextNonEmptySlot(this->index_, hash_set_); 88c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return temp; 89c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 9047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 9147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier Elem& operator*() const { 9247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier DCHECK(!hash_set_->IsFreeSlot(this->index_)); 9347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return hash_set_->ElementForIndex(this->index_); 94c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 9547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 9647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier Elem* operator->() const { 97c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return &**this; 98c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 9947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 1001f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko // TODO: Operator -- --(int) (and use std::bidirectional_iterator_tag) 101c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 102c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier private: 103c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t index_; 10447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier HashSetType* hash_set_; 105c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 10647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t NextNonEmptySlot(size_t index, const HashSet* hash_set) const { 10747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier const size_t num_buckets = hash_set->NumBuckets(); 108c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(index, num_buckets); 109c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier do { 110c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++index; 11147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } while (index < num_buckets && hash_set->IsFreeSlot(index)); 112c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return index; 113c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 114c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 115c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier friend class HashSet; 116c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier }; 117c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 11847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier public: 1191f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using value_type = T; 1201f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using allocator_type = Alloc; 1211f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using reference = T&; 1221f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using const_reference = const T&; 1231f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using pointer = T*; 1241f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using const_pointer = const T*; 1251f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using iterator = BaseIterator<T, HashSet>; 1261f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using const_iterator = BaseIterator<const T, const HashSet>; 1271f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using size_type = size_t; 1281f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using difference_type = ptrdiff_t; 1291f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko 13032cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier static constexpr double kDefaultMinLoadFactor = 0.4; 13132cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier static constexpr double kDefaultMaxLoadFactor = 0.7; 13247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier static constexpr size_t kMinBuckets = 1000; 13347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 134d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // If we don't own the data, this will create a new array which owns the data. 135c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Clear() { 136c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DeallocateStorage(); 137c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier num_elements_ = 0; 138c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier elements_until_expand_ = 0; 139c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 14047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 14132cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier HashSet() : HashSet(kDefaultMinLoadFactor, kDefaultMaxLoadFactor) {} 14232cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier 1435ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier HashSet(double min_load_factor, double max_load_factor) noexcept 1441f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko : num_elements_(0u), 1451f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko num_buckets_(0u), 1461f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko elements_until_expand_(0u), 1471f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko owns_data_(false), 1481f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko data_(nullptr), 14932cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier min_load_factor_(min_load_factor), 15032cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier max_load_factor_(max_load_factor) { 15132cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier DCHECK_GT(min_load_factor, 0.0); 15232cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier DCHECK_LT(max_load_factor, 1.0); 1531f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko } 1541f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko 1555ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier explicit HashSet(const allocator_type& alloc) noexcept 1561f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko : allocfn_(alloc), 1571f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko hashfn_(), 1581f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko emptyfn_(), 1591f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko pred_(), 1601f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko num_elements_(0u), 1611f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko num_buckets_(0u), 1621f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko elements_until_expand_(0u), 1631f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko owns_data_(false), 1641f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko data_(nullptr), 1651f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko min_load_factor_(kDefaultMinLoadFactor), 1661f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko max_load_factor_(kDefaultMaxLoadFactor) { 1671f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko } 1681f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko 1695ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier HashSet(const HashSet& other) noexcept 1701f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko : allocfn_(other.allocfn_), 1711f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko hashfn_(other.hashfn_), 1721f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko emptyfn_(other.emptyfn_), 1731f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko pred_(other.pred_), 1741f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko num_elements_(other.num_elements_), 1751f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko num_buckets_(0), 1761f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko elements_until_expand_(other.elements_until_expand_), 1771f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko owns_data_(false), 1781f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko data_(nullptr), 1791f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko min_load_factor_(other.min_load_factor_), 1801f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko max_load_factor_(other.max_load_factor_) { 1811f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko AllocateStorage(other.NumBuckets()); 1821f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko for (size_t i = 0; i < num_buckets_; ++i) { 1831f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko ElementForIndex(i) = other.data_[i]; 1841f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko } 185c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 18647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 1875ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier // noexcept required so that the move constructor is used instead of copy constructor. 1885ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier // b/27860101 1895ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier HashSet(HashSet&& other) noexcept 1901f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko : allocfn_(std::move(other.allocfn_)), 1911f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko hashfn_(std::move(other.hashfn_)), 1921f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko emptyfn_(std::move(other.emptyfn_)), 1931f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko pred_(std::move(other.pred_)), 1941f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko num_elements_(other.num_elements_), 1951f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko num_buckets_(other.num_buckets_), 1961f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko elements_until_expand_(other.elements_until_expand_), 1971f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko owns_data_(other.owns_data_), 1981f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko data_(other.data_), 1991f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko min_load_factor_(other.min_load_factor_), 2001f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko max_load_factor_(other.max_load_factor_) { 2011f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko other.num_elements_ = 0u; 2021f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko other.num_buckets_ = 0u; 2031f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko other.elements_until_expand_ = 0u; 2041f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko other.owns_data_ = false; 2051f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko other.data_ = nullptr; 206c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 20747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 208d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Construct from existing data. 209d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Read from a block of memory, if make_copy_of_data is false, then data_ points to within the 210d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // passed in ptr_. 2115ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier HashSet(const uint8_t* ptr, bool make_copy_of_data, size_t* read_count) noexcept { 212d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier uint64_t temp; 213d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier size_t offset = 0; 214d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &temp); 215d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier num_elements_ = static_cast<uint64_t>(temp); 216d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &temp); 217d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier num_buckets_ = static_cast<uint64_t>(temp); 218d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier CHECK_LE(num_elements_, num_buckets_); 219d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &temp); 220d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier elements_until_expand_ = static_cast<uint64_t>(temp); 221d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &min_load_factor_); 222d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &max_load_factor_); 223d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (!make_copy_of_data) { 224d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier owns_data_ = false; 225d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier data_ = const_cast<T*>(reinterpret_cast<const T*>(ptr + offset)); 226d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset += sizeof(*data_) * num_buckets_; 227d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } else { 228d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier AllocateStorage(num_buckets_); 229d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Write elements, not that this may not be safe for cross compilation if the elements are 230d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // pointer sized. 231d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 232d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &data_[i]); 233d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 234d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 235d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Caller responsible for aligning. 236d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier *read_count = offset; 237d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 238d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier 239d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Returns how large the table is after being written. If target is null, then no writing happens 240d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // but the size is still returned. Target must be 8 byte aligned. 241208a5cb383dd9dcd3461f89b74af5df67dc8d794Mathieu Chartier size_t WriteToMemory(uint8_t* ptr) const { 242d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier size_t offset = 0; 243d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, static_cast<uint64_t>(num_elements_)); 244d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, static_cast<uint64_t>(num_buckets_)); 245d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, static_cast<uint64_t>(elements_until_expand_)); 246d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, min_load_factor_); 247d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, max_load_factor_); 248d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Write elements, not that this may not be safe for cross compilation if the elements are 249d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // pointer sized. 250d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 251d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, data_[i]); 252d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 253d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Caller responsible for aligning. 254d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier return offset; 255d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 256d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier 257c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ~HashSet() { 258c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DeallocateStorage(); 259c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 26047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 2615ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier HashSet& operator=(HashSet&& other) noexcept { 2621f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko HashSet(std::move(other)).swap(*this); 263c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return *this; 264c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 26547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 2665ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier HashSet& operator=(const HashSet& other) noexcept { 2671f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko HashSet(other).swap(*this); // NOLINT(runtime/explicit) - a case of lint gone mad. 268c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return *this; 269c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 27047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 271c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Lower case for c++11 for each. 2721f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko iterator begin() { 2731f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko iterator ret(this, 0); 27447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier if (num_buckets_ != 0 && IsFreeSlot(ret.index_)) { 275c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++ret; // Skip all the empty slots. 276c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 277c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return ret; 278c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 27947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 280e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // Lower case for c++11 for each. const version. 2811f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko const_iterator begin() const { 2821f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko const_iterator ret(this, 0); 283e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin if (num_buckets_ != 0 && IsFreeSlot(ret.index_)) { 284e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin ++ret; // Skip all the empty slots. 285e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin } 286e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return ret; 287e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin } 288e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin 289c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Lower case for c++11 for each. 2901f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko iterator end() { 2911f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko return iterator(this, NumBuckets()); 292c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 29347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 294e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // Lower case for c++11 for each. const version. 2951f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko const_iterator end() const { 2961f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko return const_iterator(this, NumBuckets()); 297e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin } 298e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin 299c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool Empty() { 30047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return Size() == 0; 301c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 30247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 3035ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier // Return true if the hash set has ownership of the underlying data. 3045ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier bool OwnsData() const { 3055ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier return owns_data_; 3065ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier } 3075ef868c8332db11bb90284887a7f676f5dbef373Mathieu Chartier 308c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Erase algorithm: 309c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Make an empty slot where the iterator is pointing. 310e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // Scan forwards until we hit another empty slot. 311e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // If an element in between doesn't rehash to the range from the current empty slot to the 312c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // iterator. It must be before the empty slot, in that case we can move it to the empty slot 313c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // and set the empty slot to be the location we just moved from. 314c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Relies on maintaining the invariant that there's no empty slots from the 'ideal' index of an 315c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // element to its actual location/index. 3161f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko iterator Erase(iterator it) { 317c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // empty_index is the index that will become empty. 31847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t empty_index = it.index_; 319c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK(!IsFreeSlot(empty_index)); 320c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t next_index = empty_index; 321c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool filled = false; // True if we filled the empty index. 322c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier while (true) { 323c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier next_index = NextIndex(next_index); 324c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& next_element = ElementForIndex(next_index); 325c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // If the next element is empty, we are done. Make sure to clear the current empty index. 326c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (emptyfn_.IsEmpty(next_element)) { 327c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier emptyfn_.MakeEmpty(ElementForIndex(empty_index)); 328c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier break; 329c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 330c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Otherwise try to see if the next element can fill the current empty index. 331c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const size_t next_hash = hashfn_(next_element); 332c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Calculate the ideal index, if it is within empty_index + 1 to next_index then there is 333c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // nothing we can do. 334c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t next_ideal_index = IndexForHash(next_hash); 335c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Loop around if needed for our check. 336c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t unwrapped_next_index = next_index; 337c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (unwrapped_next_index < empty_index) { 338c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier unwrapped_next_index += NumBuckets(); 339c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 340c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Loop around if needed for our check. 341c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t unwrapped_next_ideal_index = next_ideal_index; 342c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (unwrapped_next_ideal_index < empty_index) { 343c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier unwrapped_next_ideal_index += NumBuckets(); 344c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 345c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (unwrapped_next_ideal_index <= empty_index || 346c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier unwrapped_next_ideal_index > unwrapped_next_index) { 347c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // If the target index isn't within our current range it must have been probed from before 348c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // the empty index. 349c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ElementForIndex(empty_index) = std::move(next_element); 350c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier filled = true; // TODO: Optimize 351c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier empty_index = next_index; 352c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 353c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 354c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier --num_elements_; 355c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // If we didn't fill the slot then we need go to the next non free slot. 356c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!filled) { 357c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++it; 358c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 359c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return it; 360c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 36147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 362c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Find an element, returns end() if not found. 36347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier // Allows custom key (K) types, example of when this is useful: 364c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Set of Class* sorted by name, want to find a class with a name but can't allocate a dummy 365c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // object in the heap for performance solution. 366c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier template <typename K> 3671f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko iterator Find(const K& key) { 368e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return FindWithHash(key, hashfn_(key)); 369c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 37047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 37147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <typename K> 3721f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko const_iterator Find(const K& key) const { 373e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return FindWithHash(key, hashfn_(key)); 37447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 37547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 376c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier template <typename K> 3771f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko iterator FindWithHash(const K& key, size_t hash) { 3781f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko return iterator(this, FindIndex(key, hash)); 37947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 38047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 38147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <typename K> 3821f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko const_iterator FindWithHash(const K& key, size_t hash) const { 3831f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko return const_iterator(this, FindIndex(key, hash)); 384c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 38547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 386c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Insert an element, allows duplicates. 387c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Insert(const T& element) { 388c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier InsertWithHash(element, hashfn_(element)); 389c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 39047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 391c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void InsertWithHash(const T& element, size_t hash) { 392c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_EQ(hash, hashfn_(element)); 393c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (num_elements_ >= elements_until_expand_) { 394c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Expand(); 395c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(num_elements_, elements_until_expand_); 396c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 397c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const size_t index = FirstAvailableSlot(IndexForHash(hash)); 398c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier data_[index] = element; 399c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++num_elements_; 400c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 40147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 402c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t Size() const { 403c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return num_elements_; 404c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 40547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 4061f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko void swap(HashSet& other) { 4071f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko // Use argument-dependent lookup with fall-back to std::swap() for function objects. 4081f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko using std::swap; 4091f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko swap(allocfn_, other.allocfn_); 4101f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko swap(hashfn_, other.hashfn_); 4111f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko swap(emptyfn_, other.emptyfn_); 4121f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko swap(pred_, other.pred_); 4131f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko std::swap(data_, other.data_); 4141f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko std::swap(num_buckets_, other.num_buckets_); 4151f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko std::swap(num_elements_, other.num_elements_); 4161f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko std::swap(elements_until_expand_, other.elements_until_expand_); 4171f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko std::swap(min_load_factor_, other.min_load_factor_); 4181f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko std::swap(max_load_factor_, other.max_load_factor_); 4191f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko std::swap(owns_data_, other.owns_data_); 4201f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko } 4211f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko 4221f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko allocator_type get_allocator() const { 4231f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko return allocfn_; 4241f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko } 4251f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko 426c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void ShrinkToMaximumLoad() { 427c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Resize(Size() / max_load_factor_); 428c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 42947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 430c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier // Reserve enough room to insert until Size() == num_elements without requiring to grow the hash 431c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier // set. No-op if the hash set is already large enough to do this. 432c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier void Reserve(size_t num_elements) { 433c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier size_t num_buckets = num_elements / max_load_factor_; 434c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier // Deal with rounding errors. Add one for rounding. 435c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier while (static_cast<size_t>(num_buckets * max_load_factor_) <= num_elements + 1u) { 436c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier ++num_buckets; 437c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier } 438c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier if (num_buckets > NumBuckets()) { 439c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier Resize(num_buckets); 440c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier } 441c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier } 442c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier 443c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // To distance that inserted elements were probed. Used for measuring how good hash functions 444c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // are. 445c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t TotalProbeDistance() const { 446c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t total = 0; 447c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < NumBuckets(); ++i) { 448c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const T& element = ElementForIndex(i); 449c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!emptyfn_.IsEmpty(element)) { 450c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t ideal_location = IndexForHash(hashfn_(element)); 451c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (ideal_location > i) { 452c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier total += i + NumBuckets() - ideal_location; 453c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } else { 454c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier total += i - ideal_location; 455c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 456c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 457c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 458c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return total; 459c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 46047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 461c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Calculate the current load factor and return it. 462c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier double CalculateLoadFactor() const { 463c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return static_cast<double>(Size()) / static_cast<double>(NumBuckets()); 464c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 46547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 466c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Make sure that everything reinserts in the right spot. Returns the number of errors. 467208a5cb383dd9dcd3461f89b74af5df67dc8d794Mathieu Chartier size_t Verify() NO_THREAD_SAFETY_ANALYSIS { 468c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t errors = 0; 469c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 470c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& element = data_[i]; 471c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!emptyfn_.IsEmpty(element)) { 472c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T temp; 473c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier emptyfn_.MakeEmpty(temp); 474c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(temp, element); 475c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t first_slot = FirstAvailableSlot(IndexForHash(hashfn_(temp))); 476c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (i != first_slot) { 477c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier LOG(ERROR) << "Element " << i << " should be in slot " << first_slot; 478c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++errors; 479c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 480c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(temp, element); 481c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 482c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 483c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return errors; 484c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 485c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 48632cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier double GetMinLoadFactor() const { 48732cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier return min_load_factor_; 48832cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier } 48932cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier 49032cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier double GetMaxLoadFactor() const { 49132cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier return max_load_factor_; 49232cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier } 49332cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier 49432cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier // Change the load factor of the hash set. If the current load factor is greater than the max 49532cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier // specified, then we resize the hash table storage. 49632cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier void SetLoadFactor(double min_load_factor, double max_load_factor) { 49732cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier DCHECK_LT(min_load_factor, max_load_factor); 49832cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier DCHECK_GT(min_load_factor, 0.0); 49932cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier DCHECK_LT(max_load_factor, 1.0); 50032cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier min_load_factor_ = min_load_factor; 50132cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier max_load_factor_ = max_load_factor; 50232cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier elements_until_expand_ = NumBuckets() * max_load_factor_; 50332cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier // If the current load factor isn't in the range, then resize to the mean of the minimum and 50432cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier // maximum load factor. 50532cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier const double load_factor = CalculateLoadFactor(); 50632cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier if (load_factor > max_load_factor_) { 50732cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier Resize(Size() / ((min_load_factor_ + max_load_factor_) * 0.5)); 50832cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier } 50932cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier } 51032cc9ee0cdffecb0ec8d80a7fd55d7dccae3a7eeMathieu Chartier 511c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier // The hash set expands when Size() reaches ElementsUntilExpand(). 512c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier size_t ElementsUntilExpand() const { 513c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier return elements_until_expand_; 514c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier } 515c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier 516c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier size_t NumBuckets() const { 517c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier return num_buckets_; 518c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier } 519c482d383593ad5202c9a4d7c2042cdc27d4c7c50Mathieu Chartier 520c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier private: 521c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& ElementForIndex(size_t index) { 522c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(index, NumBuckets()); 523c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK(data_ != nullptr); 524c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return data_[index]; 525c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 52647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 527c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const T& ElementForIndex(size_t index) const { 528c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(index, NumBuckets()); 529c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK(data_ != nullptr); 530c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return data_[index]; 531c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 53247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 533c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t IndexForHash(size_t hash) const { 534e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // Protect against undefined behavior (division by zero). 535e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin if (UNLIKELY(num_buckets_ == 0)) { 536e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return 0; 537e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin } 538c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return hash % num_buckets_; 539c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 54047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 541c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t NextIndex(size_t index) const { 542c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (UNLIKELY(++index >= num_buckets_)) { 543c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_EQ(index, NumBuckets()); 544c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return 0; 545c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 546c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return index; 547c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 54847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 54947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier // Find the hash table slot for an element, or return NumBuckets() if not found. 5501f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko // This value for not found is important so that iterator(this, FindIndex(...)) == end(). 55147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <typename K> 55247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t FindIndex(const K& element, size_t hash) const { 553e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // Guard against failing to get an element for a non-existing index. 554e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin if (UNLIKELY(NumBuckets() == 0)) { 555e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return 0; 556e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin } 55747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier DCHECK_EQ(hashfn_(element), hash); 55847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t index = IndexForHash(hash); 55947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier while (true) { 56047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier const T& slot = ElementForIndex(index); 56147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier if (emptyfn_.IsEmpty(slot)) { 56247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return NumBuckets(); 56347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 56447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier if (pred_(slot, element)) { 56547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return index; 56647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 56747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier index = NextIndex(index); 56847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 56947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 57047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 571c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool IsFreeSlot(size_t index) const { 572c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return emptyfn_.IsEmpty(ElementForIndex(index)); 573c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 57447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 575c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Allocate a number of buckets. 576c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void AllocateStorage(size_t num_buckets) { 577c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier num_buckets_ = num_buckets; 578c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier data_ = allocfn_.allocate(num_buckets_); 579d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier owns_data_ = true; 580c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 581c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier allocfn_.construct(allocfn_.address(data_[i])); 582c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier emptyfn_.MakeEmpty(data_[i]); 583c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 584c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 58547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 586c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void DeallocateStorage() { 58788b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier if (owns_data_) { 58888b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier for (size_t i = 0; i < NumBuckets(); ++i) { 58988b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier allocfn_.destroy(allocfn_.address(data_[i])); 59088b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier } 59188b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier if (data_ != nullptr) { 592d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier allocfn_.deallocate(data_, NumBuckets()); 593c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 59488b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier owns_data_ = false; 595c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 59688b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier data_ = nullptr; 59788b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier num_buckets_ = 0; 598c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 59947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 600c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Expand the set based on the load factors. 601c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Expand() { 602c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t min_index = static_cast<size_t>(Size() / min_load_factor_); 603c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Resize based on the minimum load factor. 604c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Resize(min_index); 605c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 60647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 607c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Expand / shrink the table to the new specified size. 608c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Resize(size_t new_size) { 60988b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier if (new_size < kMinBuckets) { 61088b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier new_size = kMinBuckets; 61188b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier } 612c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_GE(new_size, Size()); 613d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier T* const old_data = data_; 614c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t old_num_buckets = num_buckets_; 615c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Reinsert all of the old elements. 616d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier const bool owned_data = owns_data_; 617c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier AllocateStorage(new_size); 618c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < old_num_buckets; ++i) { 619c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& element = old_data[i]; 620c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!emptyfn_.IsEmpty(element)) { 621c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier data_[FirstAvailableSlot(IndexForHash(hashfn_(element)))] = std::move(element); 622c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 623d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (owned_data) { 624d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier allocfn_.destroy(allocfn_.address(element)); 625d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 626d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 627d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (owned_data) { 628d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier allocfn_.deallocate(old_data, old_num_buckets); 629c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 6303552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin 6313552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin // When we hit elements_until_expand_, we are at the max load factor and must expand again. 6323552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin elements_until_expand_ = NumBuckets() * max_load_factor_; 633c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 63447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 635c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ALWAYS_INLINE size_t FirstAvailableSlot(size_t index) const { 6363552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin DCHECK_LT(index, NumBuckets()); // Don't try to get a slot out of range. 6373552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin size_t non_empty_count = 0; 638c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier while (!emptyfn_.IsEmpty(data_[index])) { 639c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier index = NextIndex(index); 6403552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin non_empty_count++; 6413552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin DCHECK_LE(non_empty_count, NumBuckets()); // Don't loop forever. 642c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 643c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return index; 644c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 645c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 646d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Return new offset. 647d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier template <typename Elem> 648d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier static size_t WriteToBytes(uint8_t* ptr, size_t offset, Elem n) { 649d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier DCHECK_ALIGNED(ptr + offset, sizeof(n)); 650d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (ptr != nullptr) { 651d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier *reinterpret_cast<Elem*>(ptr + offset) = n; 652d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 653d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier return offset + sizeof(n); 654d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 655d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier 656d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier template <typename Elem> 657d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier static size_t ReadFromBytes(const uint8_t* ptr, size_t offset, Elem* out) { 658d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier DCHECK(ptr != nullptr); 659d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier DCHECK_ALIGNED(ptr + offset, sizeof(*out)); 660d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier *out = *reinterpret_cast<const Elem*>(ptr + offset); 661d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier return offset + sizeof(*out); 662d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 663d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier 664c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Alloc allocfn_; // Allocator function. 665c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier HashFn hashfn_; // Hashing function. 666c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier EmptyFn emptyfn_; // IsEmpty/SetEmpty function. 667c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Pred pred_; // Equals function. 668c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t num_elements_; // Number of inserted elements. 669c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t num_buckets_; // Number of hash table buckets. 6703552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin size_t elements_until_expand_; // Maximum number of elements until we expand the table. 671d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier bool owns_data_; // If we own data_ and are responsible for freeing it. 672c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T* data_; // Backing storage. 673c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier double min_load_factor_; 674c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier double max_load_factor_; 675c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier}; 676c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 6771f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Markotemplate <class T, class EmptyFn, class HashFn, class Pred, class Alloc> 6781f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Markovoid swap(HashSet<T, EmptyFn, HashFn, Pred, Alloc>& lhs, 6791f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko HashSet<T, EmptyFn, HashFn, Pred, Alloc>& rhs) { 6801f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko lhs.swap(rhs); 6811f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko} 6821f49764f7d62b2f80ce3418234a5036a59b2b762Vladimir Marko 683c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier} // namespace art 684c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 685c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#endif // ART_RUNTIME_BASE_HASH_SET_H_ 686