From 1d1ad2292bb5c7be26074e516b4cc70d9cc469f9 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 10 Feb 2021 08:52:54 -0800 Subject: Export of internal Abseil changes -- f9476c95cf7625d7b0fc4661f253b0aac4341044 by Abseil Team : Add a test to verify that the new checksum field in Hashtablez is calculated PiperOrigin-RevId: 356744293 -- ff8a3612463000e8c3d451e50367a3c65cb6cf21 by Abseil Team : Remove the implied support comment for port.h, attributes.h, and integral_types.h's C compatibility from the header documentations. Abseil-cpp is a C++ library; this brings port.h, attributes.h, and integral_types.h, into our stance for the rest of Abseil (aka, no assurance of C compatibility) There is no guarantee that future changes to port.h, attributes.h, and integral_types.h, and their dependencies, will remain compatible with C, even for macros and definitions that currently are. PiperOrigin-RevId: 356727505 -- be62292016381deee628dbb3f36cb6009bcc0282 by Abseil Team : internal change PiperOrigin-RevId: 356608125 -- 13b35f17171df3d6853ea7088797b3be611505fc by Evan Brown : Clarify the comments for CapacityToGrowth/GrowthToLowerboundCapacity methods to specify the intent that capacity should equal growth when `capacity+1 < kWidth`. Also add testing for this behavior. PiperOrigin-RevId: 356579041 GitOrigin-RevId: f9476c95cf7625d7b0fc4661f253b0aac4341044 Change-Id: Iadd094d109b4869998f2427319ef66d1cf1e8eff --- absl/container/internal/raw_hash_set.h | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) (limited to 'absl/container/internal/raw_hash_set.h') diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 74b2ef4c..80fc2cba 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -468,8 +468,16 @@ inline size_t NormalizeCapacity(size_t n) { return n ? ~size_t{} >> countl_zero(n) : 1; } -// We use 7/8th as maximum load factor. -// For 16-wide groups, that gives an average of two empty slots per group. +// General notes on capacity/growth methods below: +// - We use 7/8th as maximum load factor. For 16-wide groups, that gives an +// average of two empty slots per group. +// - For (capacity+1) >= Group::kWidth, growth is 7/8*capacity. +// - For (capacity+1) < Group::kWidth, growth == capacity. In this case, we +// never need to probe (the whole table fits in one group) so we don't need a +// load factor less than 1. + +// Given `capacity` of the table, returns the size (i.e. number of full slots) +// at which we should grow the capacity. inline size_t CapacityToGrowth(size_t capacity) { assert(IsValidCapacity(capacity)); // `capacity*7/8` @@ -480,7 +488,7 @@ inline size_t CapacityToGrowth(size_t capacity) { return capacity - capacity / 8; } // From desired "growth" to a lowerbound of the necessary capacity. -// Might not be a valid one and required NormalizeCapacity(). +// Might not be a valid one and requires NormalizeCapacity(). inline size_t GrowthToLowerboundCapacity(size_t growth) { // `growth*8/7` if (Group::kWidth == 8 && growth == 7) { -- cgit v1.2.3