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_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