Add HashSet::Reserve
Reserves enough room to insert n elements without expanding.
Motivation is to use this for cases where we know how many elements
will be inserted.
Change-Id: I3c51fc7f4601903411fc90b0f1bf270fe9a30919
diff --git a/runtime/base/hash_set.h b/runtime/base/hash_set.h
index 4819f06..95baa82 100644
--- a/runtime/base/hash_set.h
+++ b/runtime/base/hash_set.h
@@ -420,6 +420,19 @@
Resize(Size() / max_load_factor_);
}
+ // Reserve enough room to insert until Size() == num_elements without requiring to grow the hash
+ // set. No-op if the hash set is already large enough to do this.
+ void Reserve(size_t num_elements) {
+ size_t num_buckets = num_elements / max_load_factor_;
+ // Deal with rounding errors. Add one for rounding.
+ while (static_cast<size_t>(num_buckets * max_load_factor_) <= num_elements + 1u) {
+ ++num_buckets;
+ }
+ if (num_buckets > NumBuckets()) {
+ Resize(num_buckets);
+ }
+ }
+
// To distance that inserted elements were probed. Used for measuring how good hash functions
// are.
size_t TotalProbeDistance() const {
@@ -488,6 +501,15 @@
}
}
+ // The hash set expands when Size() reaches ElementsUntilExpand().
+ size_t ElementsUntilExpand() const {
+ return elements_until_expand_;
+ }
+
+ size_t NumBuckets() const {
+ return num_buckets_;
+ }
+
private:
T& ElementForIndex(size_t index) {
DCHECK_LT(index, NumBuckets());
@@ -543,10 +565,6 @@
return emptyfn_.IsEmpty(ElementForIndex(index));
}
- size_t NumBuckets() const {
- return num_buckets_;
- }
-
// Allocate a number of buckets.
void AllocateStorage(size_t num_buckets) {
num_buckets_ = num_buckets;
diff --git a/runtime/base/hash_set_test.cc b/runtime/base/hash_set_test.cc
index 743e98e..8254063 100644
--- a/runtime/base/hash_set_test.cc
+++ b/runtime/base/hash_set_test.cc
@@ -333,4 +333,25 @@
ASSERT_NE(hash_set.end(), hash_set.Find(std::forward_list<int>({1, 2, 3, 4})));
}
+TEST_F(HashSetTest, TestReserve) {
+ HashSet<std::string, IsEmptyFnString> hash_set;
+ std::vector<size_t> sizes = {1, 10, 25, 55, 128, 1024, 4096};
+ for (size_t size : sizes) {
+ hash_set.Reserve(size);
+ const size_t buckets_before = hash_set.NumBuckets();
+ // Check that we expanded enough.
+ CHECK_GE(hash_set.ElementsUntilExpand(), size);
+ // Try inserting elements until we are at our reserve size and ensure the hash set did not
+ // expand.
+ while (hash_set.Size() < size) {
+ hash_set.Insert(std::to_string(hash_set.Size()));
+ }
+ CHECK_EQ(hash_set.NumBuckets(), buckets_before);
+ }
+ // Check the behaviour for shrinking, it does not necessarily resize down.
+ constexpr size_t size = 100;
+ hash_set.Reserve(size);
+ CHECK_GE(hash_set.ElementsUntilExpand(), size);
+}
+
} // namespace art
