summaryrefslogtreecommitdiff
path: root/absl/container/internal/raw_hash_set.cc
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2018-09-27 12:24:54 -0700
committerGravatar Derek Mauro <dmauro@google.com>2018-09-27 15:28:12 -0400
commit48cd2c3f351ff188bc85684b84a91b6e6d17d896 (patch)
tree6f92b0cbb0f8282b7df1cd567cb66406fbbb6f80 /absl/container/internal/raw_hash_set.cc
parente291c279e458761e77a69b09b129d3d1e81f1e80 (diff)
Export of internal Abseil changes.
-- 4eacae3ff1b14b1d309e8092185bc10e8a6203cf by Derek Mauro <dmauro@google.com>: Release SwissTable - a fast, efficient, cache-friendly hash table. https://www.youtube.com/watch?v=ncHmEUmJZf4 PiperOrigin-RevId: 214816527 -- df8c3dfab3cfb2f4365909a84d0683b193cfbb11 by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 214785288 -- 1eabd5266bbcebc33eecc91e5309b751856a75c8 by Abseil Team <absl-team@google.com>: Internal change PiperOrigin-RevId: 214722931 -- 2ebbfac950f83146b46253038e7dd7dcde9f2951 by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 214701684 GitOrigin-RevId: 4eacae3ff1b14b1d309e8092185bc10e8a6203cf Change-Id: I9ba64e395b22ad7863213d157b8019b082adc19d
Diffstat (limited to 'absl/container/internal/raw_hash_set.cc')
-rw-r--r--absl/container/internal/raw_hash_set.cc45
1 files changed, 45 insertions, 0 deletions
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 <cstddef>
+
+#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<size_t> counter;
+ size_t value = counter.fetch_add(1, std::memory_order_relaxed);
+#endif // ABSL_HAVE_THREAD_LOCAL
+ return value ^ static_cast<size_t>(reinterpret_cast<uintptr_t>(&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