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 5 #include "base/sampling_heap_profiler/lock_free_address_hash_set.h" 6 7 #include <limits> 8 9 #include "base/bits.h" 10 11 namespace base { 12 LockFreeAddressHashSet(size_t buckets_count)13LockFreeAddressHashSet::LockFreeAddressHashSet(size_t buckets_count) 14 : buckets_(buckets_count), bucket_mask_(buckets_count - 1) { 15 DCHECK(bits::IsPowerOfTwo(buckets_count)); 16 DCHECK(bucket_mask_ <= std::numeric_limits<uint32_t>::max()); 17 } 18 ~LockFreeAddressHashSet()19LockFreeAddressHashSet::~LockFreeAddressHashSet() { 20 for (subtle::AtomicWord bucket : buckets_) { 21 Node* node = reinterpret_cast<Node*>(bucket); 22 while (node) { 23 Node* next = reinterpret_cast<Node*>(node->next); 24 delete node; 25 node = next; 26 } 27 } 28 } 29 Insert(void * key)30void LockFreeAddressHashSet::Insert(void* key) { 31 // TODO(alph): Replace with DCHECK. 32 CHECK(key != nullptr); 33 CHECK(!Contains(key)); 34 subtle::NoBarrier_AtomicIncrement(&size_, 1); 35 uint32_t h = Hash(key); 36 subtle::AtomicWord* bucket_ptr = &buckets_[h & bucket_mask_]; 37 Node* node = reinterpret_cast<Node*>(subtle::NoBarrier_Load(bucket_ptr)); 38 // First iterate over the bucket nodes and try to reuse an empty one if found. 39 for (; node != nullptr; node = next_node(node)) { 40 if (subtle::NoBarrier_CompareAndSwap( 41 &node->key, 0, reinterpret_cast<subtle::AtomicWord>(key)) == 0) { 42 return; 43 } 44 } 45 DCHECK(node == nullptr); 46 // There are no empty nodes to reuse in the bucket. 47 // Create a new node and prepend it to the list. 48 Node* new_node = new Node(key); 49 subtle::AtomicWord current_head = subtle::NoBarrier_Load(bucket_ptr); 50 subtle::AtomicWord expected_head; 51 do { 52 subtle::NoBarrier_Store(&new_node->next, current_head); 53 expected_head = current_head; 54 current_head = subtle::Release_CompareAndSwap( 55 bucket_ptr, current_head, 56 reinterpret_cast<subtle::AtomicWord>(new_node)); 57 } while (current_head != expected_head); 58 } 59 Copy(const LockFreeAddressHashSet & other)60void LockFreeAddressHashSet::Copy(const LockFreeAddressHashSet& other) { 61 DCHECK_EQ(0u, size()); 62 for (subtle::AtomicWord bucket : other.buckets_) { 63 for (Node* node = reinterpret_cast<Node*>(bucket); node; 64 node = next_node(node)) { 65 subtle::AtomicWord k = subtle::NoBarrier_Load(&node->key); 66 if (k) 67 Insert(reinterpret_cast<void*>(k)); 68 } 69 } 70 } 71 72 } // namespace base 73