hash_set.h revision 3552d96086c75523a76f399a13dd85d65eaa2d19
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> 21c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#include <memory> 22c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#include <stdint.h> 23c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#include <utility> 24c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 25d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier#include "bit_utils.h" 26c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#include "logging.h" 27c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 28c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartiernamespace art { 29c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 30c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier// Returns true if an item is empty. 31c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartiertemplate <class T> 32c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartierclass DefaultEmptyFn { 33c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier public: 34c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void MakeEmpty(T& item) const { 35c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier item = T(); 36c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 37c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool IsEmpty(const T& item) const { 38c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return item == T(); 39c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 40c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier}; 41c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 42c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartiertemplate <class T> 43c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartierclass DefaultEmptyFn<T*> { 44c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier public: 45c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void MakeEmpty(T*& item) const { 46c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier item = nullptr; 47c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 48c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool IsEmpty(const T*& item) const { 49c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return item == nullptr; 50c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 51c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier}; 52c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 53c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier// Low memory version of a hash set, uses less memory than std::unordered_set since elements aren't 5447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier// boxed. Uses linear probing to resolve collisions. 5547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier// EmptyFn needs to implement two functions MakeEmpty(T& item) and IsEmpty(const T& item). 5647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier// TODO: We could get rid of this requirement by using a bitmap, though maybe this would be slower 5747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier// and more complicated. 58c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartiertemplate <class T, class EmptyFn = DefaultEmptyFn<T>, class HashFn = std::hash<T>, 59c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier class Pred = std::equal_to<T>, class Alloc = std::allocator<T>> 60c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartierclass HashSet { 6147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <class Elem, class HashSetType> 6247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier class BaseIterator { 63c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier public: 6447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator(const BaseIterator&) = default; 6547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator(BaseIterator&&) = default; 6647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator(HashSetType* hash_set, size_t index) : index_(index), hash_set_(hash_set) { 67c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 6847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator& operator=(const BaseIterator&) = default; 6947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator& operator=(BaseIterator&&) = default; 7047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 7147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier bool operator==(const BaseIterator& other) const { 7247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return hash_set_ == other.hash_set_ && this->index_ == other.index_; 73c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 7447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 7547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier bool operator!=(const BaseIterator& other) const { 76c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return !(*this == other); 77c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 7847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 7947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator operator++() { // Value after modification. 8047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier this->index_ = this->NextNonEmptySlot(this->index_, hash_set_); 81c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return *this; 82c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 8347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 8447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier BaseIterator operator++(int) { 85c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Iterator temp = *this; 8647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier this->index_ = this->NextNonEmptySlot(this->index_, hash_set_); 87c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return temp; 88c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 8947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 9047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier Elem& operator*() const { 9147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier DCHECK(!hash_set_->IsFreeSlot(this->index_)); 9247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return hash_set_->ElementForIndex(this->index_); 93c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 9447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 9547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier Elem* operator->() const { 96c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return &**this; 97c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 9847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 99c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // TODO: Operator -- --(int) 100c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 101c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier private: 102c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t index_; 10347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier HashSetType* hash_set_; 104c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 10547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t NextNonEmptySlot(size_t index, const HashSet* hash_set) const { 10647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier const size_t num_buckets = hash_set->NumBuckets(); 107c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(index, num_buckets); 108c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier do { 109c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++index; 11047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } while (index < num_buckets && hash_set->IsFreeSlot(index)); 111c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return index; 112c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 113c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 114c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier friend class HashSet; 115c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier }; 116c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 11747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier public: 11847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier static constexpr double kDefaultMinLoadFactor = 0.5; 11947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier static constexpr double kDefaultMaxLoadFactor = 0.9; 12047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier static constexpr size_t kMinBuckets = 1000; 12147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 12247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier typedef BaseIterator<T, HashSet> Iterator; 12347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier typedef BaseIterator<const T, const HashSet> ConstIterator; 12447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 125d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // If we don't own the data, this will create a new array which owns the data. 126c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Clear() { 127c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DeallocateStorage(); 128c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier AllocateStorage(1); 129c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier num_elements_ = 0; 130c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier elements_until_expand_ = 0; 131c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 13247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 133d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier HashSet() : num_elements_(0), num_buckets_(0), owns_data_(false), data_(nullptr), 134c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier min_load_factor_(kDefaultMinLoadFactor), max_load_factor_(kDefaultMaxLoadFactor) { 135c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Clear(); 136c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 13747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 138d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier HashSet(const HashSet& other) : num_elements_(0), num_buckets_(0), owns_data_(false), 139d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier data_(nullptr) { 140c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier *this = other; 141c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 14247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 143d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier HashSet(HashSet&& other) : num_elements_(0), num_buckets_(0), owns_data_(false), 144d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier data_(nullptr) { 145c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier *this = std::move(other); 146c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 14747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 148d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Construct from existing data. 149d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Read from a block of memory, if make_copy_of_data is false, then data_ points to within the 150d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // passed in ptr_. 151d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier HashSet(const uint8_t* ptr, bool make_copy_of_data, size_t* read_count) { 152d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier uint64_t temp; 153d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier size_t offset = 0; 154d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &temp); 155d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier num_elements_ = static_cast<uint64_t>(temp); 156d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &temp); 157d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier num_buckets_ = static_cast<uint64_t>(temp); 158d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier CHECK_LE(num_elements_, num_buckets_); 159d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &temp); 160d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier elements_until_expand_ = static_cast<uint64_t>(temp); 161d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &min_load_factor_); 162d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &max_load_factor_); 163d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (!make_copy_of_data) { 164d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier owns_data_ = false; 165d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier data_ = const_cast<T*>(reinterpret_cast<const T*>(ptr + offset)); 166d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset += sizeof(*data_) * num_buckets_; 167d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } else { 168d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier AllocateStorage(num_buckets_); 169d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Write elements, not that this may not be safe for cross compilation if the elements are 170d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // pointer sized. 171d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 172d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = ReadFromBytes(ptr, offset, &data_[i]); 173d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 174d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 175d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Caller responsible for aligning. 176d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier *read_count = offset; 177d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 178d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier 179d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Returns how large the table is after being written. If target is null, then no writing happens 180d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // but the size is still returned. Target must be 8 byte aligned. 181d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier size_t WriteToMemory(uint8_t* ptr) { 182d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier size_t offset = 0; 183d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, static_cast<uint64_t>(num_elements_)); 184d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, static_cast<uint64_t>(num_buckets_)); 185d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, static_cast<uint64_t>(elements_until_expand_)); 186d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, min_load_factor_); 187d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, max_load_factor_); 188d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Write elements, not that this may not be safe for cross compilation if the elements are 189d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // pointer sized. 190d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 191d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier offset = WriteToBytes(ptr, offset, data_[i]); 192d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 193d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Caller responsible for aligning. 194d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier return offset; 195d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 196d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier 197c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ~HashSet() { 198c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DeallocateStorage(); 199c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 20047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 201c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier HashSet& operator=(HashSet&& other) { 202c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(data_, other.data_); 203c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(num_buckets_, other.num_buckets_); 204c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(num_elements_, other.num_elements_); 205c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(elements_until_expand_, other.elements_until_expand_); 206c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(min_load_factor_, other.min_load_factor_); 207c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(max_load_factor_, other.max_load_factor_); 208d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier std::swap(owns_data_, other.owns_data_); 209c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return *this; 210c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 21147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 212c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier HashSet& operator=(const HashSet& other) { 213c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DeallocateStorage(); 214c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier AllocateStorage(other.NumBuckets()); 215c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 216c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ElementForIndex(i) = other.data_[i]; 217c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 218c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier num_elements_ = other.num_elements_; 219c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier elements_until_expand_ = other.elements_until_expand_; 220c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier min_load_factor_ = other.min_load_factor_; 221c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier max_load_factor_ = other.max_load_factor_; 222c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return *this; 223c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 22447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 225c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Lower case for c++11 for each. 226c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Iterator begin() { 227c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Iterator ret(this, 0); 22847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier if (num_buckets_ != 0 && IsFreeSlot(ret.index_)) { 229c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++ret; // Skip all the empty slots. 230c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 231c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return ret; 232c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 23347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 234c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Lower case for c++11 for each. 235c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Iterator end() { 236c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return Iterator(this, NumBuckets()); 237c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 23847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 239c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool Empty() { 24047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return Size() == 0; 241c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 24247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 243c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Erase algorithm: 244c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Make an empty slot where the iterator is pointing. 245c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Scan fowards until we hit another empty slot. 246c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // If an element inbetween doesn't rehash to the range from the current empty slot to the 247c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // iterator. It must be before the empty slot, in that case we can move it to the empty slot 248c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // and set the empty slot to be the location we just moved from. 249c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Relies on maintaining the invariant that there's no empty slots from the 'ideal' index of an 250c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // element to its actual location/index. 251c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Iterator Erase(Iterator it) { 252c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // empty_index is the index that will become empty. 25347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t empty_index = it.index_; 254c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK(!IsFreeSlot(empty_index)); 255c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t next_index = empty_index; 256c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool filled = false; // True if we filled the empty index. 257c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier while (true) { 258c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier next_index = NextIndex(next_index); 259c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& next_element = ElementForIndex(next_index); 260c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // If the next element is empty, we are done. Make sure to clear the current empty index. 261c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (emptyfn_.IsEmpty(next_element)) { 262c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier emptyfn_.MakeEmpty(ElementForIndex(empty_index)); 263c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier break; 264c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 265c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Otherwise try to see if the next element can fill the current empty index. 266c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const size_t next_hash = hashfn_(next_element); 267c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Calculate the ideal index, if it is within empty_index + 1 to next_index then there is 268c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // nothing we can do. 269c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t next_ideal_index = IndexForHash(next_hash); 270c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Loop around if needed for our check. 271c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t unwrapped_next_index = next_index; 272c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (unwrapped_next_index < empty_index) { 273c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier unwrapped_next_index += NumBuckets(); 274c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 275c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Loop around if needed for our check. 276c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t unwrapped_next_ideal_index = next_ideal_index; 277c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (unwrapped_next_ideal_index < empty_index) { 278c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier unwrapped_next_ideal_index += NumBuckets(); 279c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 280c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (unwrapped_next_ideal_index <= empty_index || 281c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier unwrapped_next_ideal_index > unwrapped_next_index) { 282c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // If the target index isn't within our current range it must have been probed from before 283c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // the empty index. 284c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ElementForIndex(empty_index) = std::move(next_element); 285c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier filled = true; // TODO: Optimize 286c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier empty_index = next_index; 287c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 288c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 289c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier --num_elements_; 290c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // If we didn't fill the slot then we need go to the next non free slot. 291c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!filled) { 292c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++it; 293c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 294c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return it; 295c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 29647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 297c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Find an element, returns end() if not found. 29847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier // Allows custom key (K) types, example of when this is useful: 299c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Set of Class* sorted by name, want to find a class with a name but can't allocate a dummy 300c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // object in the heap for performance solution. 301c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier template <typename K> 302c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Iterator Find(const K& element) { 303c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return FindWithHash(element, hashfn_(element)); 304c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 30547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 30647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <typename K> 30747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier ConstIterator Find(const K& element) const { 30847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return FindWithHash(element, hashfn_(element)); 30947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 31047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 311c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier template <typename K> 312c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Iterator FindWithHash(const K& element, size_t hash) { 31347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return Iterator(this, FindIndex(element, hash)); 31447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 31547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 31647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <typename K> 31747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier ConstIterator FindWithHash(const K& element, size_t hash) const { 31847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return ConstIterator(this, FindIndex(element, hash)); 319c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 32047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 321c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Insert an element, allows duplicates. 322c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Insert(const T& element) { 323c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier InsertWithHash(element, hashfn_(element)); 324c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 32547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 326c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void InsertWithHash(const T& element, size_t hash) { 327c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_EQ(hash, hashfn_(element)); 328c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (num_elements_ >= elements_until_expand_) { 329c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Expand(); 330c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(num_elements_, elements_until_expand_); 331c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 332c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const size_t index = FirstAvailableSlot(IndexForHash(hash)); 333c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier data_[index] = element; 334c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++num_elements_; 335c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 33647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 337c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t Size() const { 338c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return num_elements_; 339c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 34047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 341c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void ShrinkToMaximumLoad() { 342c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Resize(Size() / max_load_factor_); 343c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 34447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 345c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // To distance that inserted elements were probed. Used for measuring how good hash functions 346c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // are. 347c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t TotalProbeDistance() const { 348c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t total = 0; 349c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < NumBuckets(); ++i) { 350c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const T& element = ElementForIndex(i); 351c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!emptyfn_.IsEmpty(element)) { 352c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t ideal_location = IndexForHash(hashfn_(element)); 353c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (ideal_location > i) { 354c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier total += i + NumBuckets() - ideal_location; 355c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } else { 356c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier total += i - ideal_location; 357c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 358c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 359c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 360c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return total; 361c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 36247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 363c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Calculate the current load factor and return it. 364c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier double CalculateLoadFactor() const { 365c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return static_cast<double>(Size()) / static_cast<double>(NumBuckets()); 366c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 36747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 368c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Make sure that everything reinserts in the right spot. Returns the number of errors. 369c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t Verify() { 370c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t errors = 0; 371c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 372c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& element = data_[i]; 373c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!emptyfn_.IsEmpty(element)) { 374c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T temp; 375c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier emptyfn_.MakeEmpty(temp); 376c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(temp, element); 377c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t first_slot = FirstAvailableSlot(IndexForHash(hashfn_(temp))); 378c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (i != first_slot) { 379c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier LOG(ERROR) << "Element " << i << " should be in slot " << first_slot; 380c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++errors; 381c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 382c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(temp, element); 383c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 384c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 385c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return errors; 386c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 387c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 388c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier private: 389c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& ElementForIndex(size_t index) { 390c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(index, NumBuckets()); 391c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK(data_ != nullptr); 392c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return data_[index]; 393c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 39447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 395c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const T& ElementForIndex(size_t index) const { 396c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(index, NumBuckets()); 397c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK(data_ != nullptr); 398c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return data_[index]; 399c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 40047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 401c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t IndexForHash(size_t hash) const { 402c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return hash % num_buckets_; 403c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 40447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 405c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t NextIndex(size_t index) const { 406c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (UNLIKELY(++index >= num_buckets_)) { 407c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_EQ(index, NumBuckets()); 408c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return 0; 409c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 410c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return index; 411c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 41247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 41347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier // Find the hash table slot for an element, or return NumBuckets() if not found. 41447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier // This value for not found is important so that Iterator(this, FindIndex(...)) == end(). 41547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <typename K> 41647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t FindIndex(const K& element, size_t hash) const { 41747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier DCHECK_EQ(hashfn_(element), hash); 41847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t index = IndexForHash(hash); 41947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier while (true) { 42047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier const T& slot = ElementForIndex(index); 42147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier if (emptyfn_.IsEmpty(slot)) { 42247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return NumBuckets(); 42347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 42447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier if (pred_(slot, element)) { 42547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return index; 42647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 42747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier index = NextIndex(index); 42847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 42947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 43047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 431c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool IsFreeSlot(size_t index) const { 432c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return emptyfn_.IsEmpty(ElementForIndex(index)); 433c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 43447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 435c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t NumBuckets() const { 436c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return num_buckets_; 437c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 43847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 439c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Allocate a number of buckets. 440c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void AllocateStorage(size_t num_buckets) { 441c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier num_buckets_ = num_buckets; 442c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier data_ = allocfn_.allocate(num_buckets_); 443d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier owns_data_ = true; 444c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 445c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier allocfn_.construct(allocfn_.address(data_[i])); 446c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier emptyfn_.MakeEmpty(data_[i]); 447c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 448c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 44947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 450c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void DeallocateStorage() { 451c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (num_buckets_ != 0) { 452d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (owns_data_) { 453d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier for (size_t i = 0; i < NumBuckets(); ++i) { 454d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier allocfn_.destroy(allocfn_.address(data_[i])); 455d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 456d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier allocfn_.deallocate(data_, NumBuckets()); 457d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier owns_data_ = false; 458c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 459c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier data_ = nullptr; 460c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier num_buckets_ = 0; 461c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 462c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 46347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 464c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Expand the set based on the load factors. 465c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Expand() { 466c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t min_index = static_cast<size_t>(Size() / min_load_factor_); 467c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (min_index < kMinBuckets) { 468c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier min_index = kMinBuckets; 469c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 470c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Resize based on the minimum load factor. 471c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Resize(min_index); 472c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 47347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 474c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Expand / shrink the table to the new specified size. 475c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Resize(size_t new_size) { 476c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_GE(new_size, Size()); 477d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier T* const old_data = data_; 478c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t old_num_buckets = num_buckets_; 479c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Reinsert all of the old elements. 480d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier const bool owned_data = owns_data_; 481c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier AllocateStorage(new_size); 482c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < old_num_buckets; ++i) { 483c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& element = old_data[i]; 484c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!emptyfn_.IsEmpty(element)) { 485c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier data_[FirstAvailableSlot(IndexForHash(hashfn_(element)))] = std::move(element); 486c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 487d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (owned_data) { 488d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier allocfn_.destroy(allocfn_.address(element)); 489d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 490d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 491d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (owned_data) { 492d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier allocfn_.deallocate(old_data, old_num_buckets); 493c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 4943552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin 4953552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin // When we hit elements_until_expand_, we are at the max load factor and must expand again. 4963552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin elements_until_expand_ = NumBuckets() * max_load_factor_; 497c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 49847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 499c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ALWAYS_INLINE size_t FirstAvailableSlot(size_t index) const { 5003552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin DCHECK_LT(index, NumBuckets()); // Don't try to get a slot out of range. 5013552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin size_t non_empty_count = 0; 502c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier while (!emptyfn_.IsEmpty(data_[index])) { 503c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier index = NextIndex(index); 5043552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin non_empty_count++; 5053552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin DCHECK_LE(non_empty_count, NumBuckets()); // Don't loop forever. 506c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 507c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return index; 508c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 509c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 510d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Return new offset. 511d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier template <typename Elem> 512d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier static size_t WriteToBytes(uint8_t* ptr, size_t offset, Elem n) { 513d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier DCHECK_ALIGNED(ptr + offset, sizeof(n)); 514d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (ptr != nullptr) { 515d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier *reinterpret_cast<Elem*>(ptr + offset) = n; 516d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 517d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier return offset + sizeof(n); 518d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 519d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier 520d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier template <typename Elem> 521d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier static size_t ReadFromBytes(const uint8_t* ptr, size_t offset, Elem* out) { 522d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier DCHECK(ptr != nullptr); 523d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier DCHECK_ALIGNED(ptr + offset, sizeof(*out)); 524d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier *out = *reinterpret_cast<const Elem*>(ptr + offset); 525d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier return offset + sizeof(*out); 526d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 527d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier 528c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Alloc allocfn_; // Allocator function. 529c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier HashFn hashfn_; // Hashing function. 530c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier EmptyFn emptyfn_; // IsEmpty/SetEmpty function. 531c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Pred pred_; // Equals function. 532c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t num_elements_; // Number of inserted elements. 533c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t num_buckets_; // Number of hash table buckets. 5343552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin size_t elements_until_expand_; // Maximum number of elements until we expand the table. 535d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier bool owns_data_; // If we own data_ and are responsible for freeing it. 536c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T* data_; // Backing storage. 537c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier double min_load_factor_; 538c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier double max_load_factor_; 539c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier}; 540c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 541c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier} // namespace art 542c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 543c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#endif // ART_RUNTIME_BASE_HASH_SET_H_ 544