lock_free_address_hash_set.cc 2.1 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
  1. // Copyright 2018 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "base/sampling_heap_profiler/lock_free_address_hash_set.h"
  5. #include <limits>
  6. #include "base/bits.h"
  7. #include "base/containers/contains.h"
  8. namespace base {
  9. LockFreeAddressHashSet::LockFreeAddressHashSet(size_t buckets_count)
  10. : buckets_(buckets_count), bucket_mask_(buckets_count - 1) {
  11. DCHECK(bits::IsPowerOfTwo(buckets_count));
  12. DCHECK_LE(bucket_mask_, std::numeric_limits<uint32_t>::max());
  13. }
  14. LockFreeAddressHashSet::~LockFreeAddressHashSet() {
  15. for (std::atomic<Node*>& bucket : buckets_) {
  16. Node* node = bucket.load(std::memory_order_relaxed);
  17. while (node) {
  18. Node* next = node->next;
  19. delete node;
  20. node = next;
  21. }
  22. }
  23. }
  24. void LockFreeAddressHashSet::Insert(void* key) {
  25. DCHECK_NE(key, nullptr);
  26. CHECK(!Contains(key));
  27. ++size_;
  28. // Note: There's no need to use std::atomic_compare_exchange here,
  29. // as we do not support concurrent inserts, so values cannot change midair.
  30. std::atomic<Node*>& bucket = buckets_[Hash(key) & bucket_mask_];
  31. Node* node = bucket.load(std::memory_order_relaxed);
  32. // First iterate over the bucket nodes and try to reuse an empty one if found.
  33. for (; node != nullptr; node = node->next) {
  34. if (node->key.load(std::memory_order_relaxed) == nullptr) {
  35. node->key.store(key, std::memory_order_relaxed);
  36. return;
  37. }
  38. }
  39. // There are no empty nodes to reuse left in the bucket.
  40. // Create a new node first...
  41. Node* new_node = new Node(key, bucket.load(std::memory_order_relaxed));
  42. // ... and then publish the new chain.
  43. bucket.store(new_node, std::memory_order_release);
  44. }
  45. void LockFreeAddressHashSet::Copy(const LockFreeAddressHashSet& other) {
  46. DCHECK_EQ(0u, size());
  47. for (const std::atomic<Node*>& bucket : other.buckets_) {
  48. for (Node* node = bucket.load(std::memory_order_relaxed); node;
  49. node = node->next) {
  50. void* key = node->key.load(std::memory_order_relaxed);
  51. if (key)
  52. Insert(key);
  53. }
  54. }
  55. }
  56. } // namespace base