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