From 48cd2c3f351ff188bc85684b84a91b6e6d17d896 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 27 Sep 2018 12:24:54 -0700 Subject: Export of internal Abseil changes. -- 4eacae3ff1b14b1d309e8092185bc10e8a6203cf by Derek Mauro : Release SwissTable - a fast, efficient, cache-friendly hash table. https://www.youtube.com/watch?v=ncHmEUmJZf4 PiperOrigin-RevId: 214816527 -- df8c3dfab3cfb2f4365909a84d0683b193cfbb11 by Derek Mauro : Internal change PiperOrigin-RevId: 214785288 -- 1eabd5266bbcebc33eecc91e5309b751856a75c8 by Abseil Team : Internal change PiperOrigin-RevId: 214722931 -- 2ebbfac950f83146b46253038e7dd7dcde9f2951 by Derek Mauro : Internal change PiperOrigin-RevId: 214701684 GitOrigin-RevId: 4eacae3ff1b14b1d309e8092185bc10e8a6203cf Change-Id: I9ba64e395b22ad7863213d157b8019b082adc19d --- absl/container/internal/raw_hash_set.cc | 45 +++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) create mode 100644 absl/container/internal/raw_hash_set.cc (limited to 'absl/container/internal/raw_hash_set.cc') diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc new file mode 100644 index 00000000..10153129 --- /dev/null +++ b/absl/container/internal/raw_hash_set.cc @@ -0,0 +1,45 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/container/internal/raw_hash_set.h" + +#include + +#include "absl/base/config.h" + +namespace absl { +namespace container_internal { + +constexpr size_t Group::kWidth; + +// Returns "random" seed. +inline size_t RandomSeed() { +#if ABSL_HAVE_THREAD_LOCAL + static thread_local size_t counter = 0; + size_t value = ++counter; +#else // ABSL_HAVE_THREAD_LOCAL + static std::atomic counter; + size_t value = counter.fetch_add(1, std::memory_order_relaxed); +#endif // ABSL_HAVE_THREAD_LOCAL + return value ^ static_cast(reinterpret_cast(&counter)); +} + +bool ShouldInsertBackwards(size_t hash, ctrl_t* ctrl) { + // To avoid problems with weak hashes and single bit tests, we use % 13. + // TODO(kfm,sbenza): revisit after we do unconditional mixing + return (H1(hash, ctrl) ^ RandomSeed()) % 13 > 6; +} + +} // namespace container_internal +} // namespace absl -- cgit v1.2.3