hash_set.h revision 88b6b051cc1c92b40537941c68061fc0d3b46a9f
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 234e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // Lower case for c++11 for each. const version. 235e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin ConstIterator begin() const { 236e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin ConstIterator ret(this, 0); 237e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin if (num_buckets_ != 0 && IsFreeSlot(ret.index_)) { 238e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin ++ret; // Skip all the empty slots. 239e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin } 240e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return ret; 241e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin } 242e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin 243c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Lower case for c++11 for each. 244c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Iterator end() { 245c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return Iterator(this, NumBuckets()); 246c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 24747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 248e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // Lower case for c++11 for each. const version. 249e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin ConstIterator end() const { 250e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return ConstIterator(this, NumBuckets()); 251e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin } 252e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin 253c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool Empty() { 25447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return Size() == 0; 255c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 25647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 257c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Erase algorithm: 258c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Make an empty slot where the iterator is pointing. 259e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // Scan forwards until we hit another empty slot. 260e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // If an element in between doesn't rehash to the range from the current empty slot to the 261c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // iterator. It must be before the empty slot, in that case we can move it to the empty slot 262c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // and set the empty slot to be the location we just moved from. 263c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Relies on maintaining the invariant that there's no empty slots from the 'ideal' index of an 264c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // element to its actual location/index. 265c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Iterator Erase(Iterator it) { 266c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // empty_index is the index that will become empty. 26747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t empty_index = it.index_; 268c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK(!IsFreeSlot(empty_index)); 269c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t next_index = empty_index; 270c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool filled = false; // True if we filled the empty index. 271c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier while (true) { 272c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier next_index = NextIndex(next_index); 273c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& next_element = ElementForIndex(next_index); 274c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // If the next element is empty, we are done. Make sure to clear the current empty index. 275c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (emptyfn_.IsEmpty(next_element)) { 276c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier emptyfn_.MakeEmpty(ElementForIndex(empty_index)); 277c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier break; 278c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 279c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Otherwise try to see if the next element can fill the current empty index. 280c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const size_t next_hash = hashfn_(next_element); 281c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Calculate the ideal index, if it is within empty_index + 1 to next_index then there is 282c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // nothing we can do. 283c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t next_ideal_index = IndexForHash(next_hash); 284c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Loop around if needed for our check. 285c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t unwrapped_next_index = next_index; 286c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (unwrapped_next_index < empty_index) { 287c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier unwrapped_next_index += NumBuckets(); 288c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 289c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Loop around if needed for our check. 290c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t unwrapped_next_ideal_index = next_ideal_index; 291c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (unwrapped_next_ideal_index < empty_index) { 292c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier unwrapped_next_ideal_index += NumBuckets(); 293c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 294c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (unwrapped_next_ideal_index <= empty_index || 295c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier unwrapped_next_ideal_index > unwrapped_next_index) { 296c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // If the target index isn't within our current range it must have been probed from before 297c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // the empty index. 298c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ElementForIndex(empty_index) = std::move(next_element); 299c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier filled = true; // TODO: Optimize 300c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier empty_index = next_index; 301c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 302c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 303c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier --num_elements_; 304c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // If we didn't fill the slot then we need go to the next non free slot. 305c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!filled) { 306c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++it; 307c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 308c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return it; 309c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 31047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 311c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Find an element, returns end() if not found. 31247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier // Allows custom key (K) types, example of when this is useful: 313c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Set of Class* sorted by name, want to find a class with a name but can't allocate a dummy 314c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // object in the heap for performance solution. 315c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier template <typename K> 316e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin Iterator Find(const K& key) { 317e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return FindWithHash(key, hashfn_(key)); 318c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 31947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 32047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <typename K> 321e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin ConstIterator Find(const K& key) const { 322e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return FindWithHash(key, hashfn_(key)); 32347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 32447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 325c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier template <typename K> 326e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin Iterator FindWithHash(const K& key, size_t hash) { 327e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return Iterator(this, FindIndex(key, hash)); 32847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 32947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 33047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <typename K> 331e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin ConstIterator FindWithHash(const K& key, size_t hash) const { 332e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return ConstIterator(this, FindIndex(key, hash)); 333c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 33447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 335c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Insert an element, allows duplicates. 336c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Insert(const T& element) { 337c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier InsertWithHash(element, hashfn_(element)); 338c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 33947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 340c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void InsertWithHash(const T& element, size_t hash) { 341c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_EQ(hash, hashfn_(element)); 342c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (num_elements_ >= elements_until_expand_) { 343c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Expand(); 344c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(num_elements_, elements_until_expand_); 345c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 346c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const size_t index = FirstAvailableSlot(IndexForHash(hash)); 347c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier data_[index] = element; 348c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++num_elements_; 349c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 35047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 351c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t Size() const { 352c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return num_elements_; 353c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 35447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 355c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void ShrinkToMaximumLoad() { 356c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Resize(Size() / max_load_factor_); 357c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 35847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 359c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // To distance that inserted elements were probed. Used for measuring how good hash functions 360c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // are. 361c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t TotalProbeDistance() const { 362c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t total = 0; 363c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < NumBuckets(); ++i) { 364c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const T& element = ElementForIndex(i); 365c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!emptyfn_.IsEmpty(element)) { 366c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t ideal_location = IndexForHash(hashfn_(element)); 367c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (ideal_location > i) { 368c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier total += i + NumBuckets() - ideal_location; 369c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } else { 370c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier total += i - ideal_location; 371c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 372c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 373c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 374c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return total; 375c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 37647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 377c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Calculate the current load factor and return it. 378c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier double CalculateLoadFactor() const { 379c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return static_cast<double>(Size()) / static_cast<double>(NumBuckets()); 380c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 38147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 382c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Make sure that everything reinserts in the right spot. Returns the number of errors. 383c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t Verify() { 384c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t errors = 0; 385c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 386c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& element = data_[i]; 387c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!emptyfn_.IsEmpty(element)) { 388c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T temp; 389c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier emptyfn_.MakeEmpty(temp); 390c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(temp, element); 391c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t first_slot = FirstAvailableSlot(IndexForHash(hashfn_(temp))); 392c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (i != first_slot) { 393c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier LOG(ERROR) << "Element " << i << " should be in slot " << first_slot; 394c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ++errors; 395c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 396c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier std::swap(temp, element); 397c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 398c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 399c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return errors; 400c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 401c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 402c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier private: 403c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& ElementForIndex(size_t index) { 404c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(index, NumBuckets()); 405c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK(data_ != nullptr); 406c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return data_[index]; 407c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 40847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 409c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier const T& ElementForIndex(size_t index) const { 410c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_LT(index, NumBuckets()); 411c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK(data_ != nullptr); 412c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return data_[index]; 413c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 41447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 415c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t IndexForHash(size_t hash) const { 416e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // Protect against undefined behavior (division by zero). 417e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin if (UNLIKELY(num_buckets_ == 0)) { 418e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return 0; 419e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin } 420c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return hash % num_buckets_; 421c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 42247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 423c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t NextIndex(size_t index) const { 424c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (UNLIKELY(++index >= num_buckets_)) { 425c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_EQ(index, NumBuckets()); 426c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return 0; 427c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 428c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return index; 429c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 43047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 43147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier // Find the hash table slot for an element, or return NumBuckets() if not found. 43247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier // This value for not found is important so that Iterator(this, FindIndex(...)) == end(). 43347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier template <typename K> 43447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t FindIndex(const K& element, size_t hash) const { 435e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin // Guard against failing to get an element for a non-existing index. 436e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin if (UNLIKELY(NumBuckets() == 0)) { 437e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin return 0; 438e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7Igor Murashkin } 43947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier DCHECK_EQ(hashfn_(element), hash); 44047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier size_t index = IndexForHash(hash); 44147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier while (true) { 44247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier const T& slot = ElementForIndex(index); 44347f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier if (emptyfn_.IsEmpty(slot)) { 44447f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return NumBuckets(); 44547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 44647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier if (pred_(slot, element)) { 44747f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier return index; 44847f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 44947f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier index = NextIndex(index); 45047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 45147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier } 45247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 453c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier bool IsFreeSlot(size_t index) const { 454c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return emptyfn_.IsEmpty(ElementForIndex(index)); 455c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 45647f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 457c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t NumBuckets() const { 458c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return num_buckets_; 459c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 46047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 461c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Allocate a number of buckets. 462c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void AllocateStorage(size_t num_buckets) { 463c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier num_buckets_ = num_buckets; 464c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier data_ = allocfn_.allocate(num_buckets_); 465d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier owns_data_ = true; 466c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < num_buckets_; ++i) { 467c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier allocfn_.construct(allocfn_.address(data_[i])); 468c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier emptyfn_.MakeEmpty(data_[i]); 469c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 470c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 47147f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 472c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void DeallocateStorage() { 47388b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier if (owns_data_) { 47488b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier for (size_t i = 0; i < NumBuckets(); ++i) { 47588b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier allocfn_.destroy(allocfn_.address(data_[i])); 47688b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier } 47788b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier if (data_ != nullptr) { 478d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier allocfn_.deallocate(data_, NumBuckets()); 479c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 48088b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier owns_data_ = false; 481c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 48288b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier data_ = nullptr; 48388b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier num_buckets_ = 0; 484c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 48547f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 486c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Expand the set based on the load factors. 487c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Expand() { 488c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t min_index = static_cast<size_t>(Size() / min_load_factor_); 489c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Resize based on the minimum load factor. 490c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Resize(min_index); 491c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 49247f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 493c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Expand / shrink the table to the new specified size. 494c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier void Resize(size_t new_size) { 49588b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier if (new_size < kMinBuckets) { 49688b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier new_size = kMinBuckets; 49788b6b051cc1c92b40537941c68061fc0d3b46a9fMathieu Chartier } 498c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier DCHECK_GE(new_size, Size()); 499d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier T* const old_data = data_; 500c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t old_num_buckets = num_buckets_; 501c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier // Reinsert all of the old elements. 502d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier const bool owned_data = owns_data_; 503c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier AllocateStorage(new_size); 504c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier for (size_t i = 0; i < old_num_buckets; ++i) { 505c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T& element = old_data[i]; 506c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier if (!emptyfn_.IsEmpty(element)) { 507c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier data_[FirstAvailableSlot(IndexForHash(hashfn_(element)))] = std::move(element); 508c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 509d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (owned_data) { 510d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier allocfn_.destroy(allocfn_.address(element)); 511d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 512d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 513d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (owned_data) { 514d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier allocfn_.deallocate(old_data, old_num_buckets); 515c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 5163552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin 5173552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin // When we hit elements_until_expand_, we are at the max load factor and must expand again. 5183552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin elements_until_expand_ = NumBuckets() * max_load_factor_; 519c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 52047f867a0ae34d743f6159c2261e5b11e39693e15Mathieu Chartier 521c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier ALWAYS_INLINE size_t FirstAvailableSlot(size_t index) const { 5223552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin DCHECK_LT(index, NumBuckets()); // Don't try to get a slot out of range. 5233552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin size_t non_empty_count = 0; 524c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier while (!emptyfn_.IsEmpty(data_[index])) { 525c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier index = NextIndex(index); 5263552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin non_empty_count++; 5273552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin DCHECK_LE(non_empty_count, NumBuckets()); // Don't loop forever. 528c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 529c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier return index; 530c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier } 531c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 532d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier // Return new offset. 533d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier template <typename Elem> 534d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier static size_t WriteToBytes(uint8_t* ptr, size_t offset, Elem n) { 535d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier DCHECK_ALIGNED(ptr + offset, sizeof(n)); 536d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier if (ptr != nullptr) { 537d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier *reinterpret_cast<Elem*>(ptr + offset) = n; 538d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 539d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier return offset + sizeof(n); 540d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 541d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier 542d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier template <typename Elem> 543d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier static size_t ReadFromBytes(const uint8_t* ptr, size_t offset, Elem* out) { 544d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier DCHECK(ptr != nullptr); 545d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier DCHECK_ALIGNED(ptr + offset, sizeof(*out)); 546d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier *out = *reinterpret_cast<const Elem*>(ptr + offset); 547d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier return offset + sizeof(*out); 548d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier } 549d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier 550c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Alloc allocfn_; // Allocator function. 551c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier HashFn hashfn_; // Hashing function. 552c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier EmptyFn emptyfn_; // IsEmpty/SetEmpty function. 553c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier Pred pred_; // Equals function. 554c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t num_elements_; // Number of inserted elements. 555c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier size_t num_buckets_; // Number of hash table buckets. 5563552d96086c75523a76f399a13dd85d65eaa2d19Igor Murashkin size_t elements_until_expand_; // Maximum number of elements until we expand the table. 557d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier bool owns_data_; // If we own data_ and are responsible for freeing it. 558c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier T* data_; // Backing storage. 559c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier double min_load_factor_; 560c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier double max_load_factor_; 561c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier}; 562c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 563c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier} // namespace art 564c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier 565c2e20629c7dfdb0f679fa30c14b41fe68588697fMathieu Chartier#endif // ART_RUNTIME_BASE_HASH_SET_H_ 566