TBB concurrent_unordered_multiset 并发不安全修饰器clear / unsafe_erase / unsafe_extract / swap规格与源码解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文基于 TBBIntel oneAPI Threading Building Blocks随仓库内置于 third-party/tbb 子目录容器规格文档 unsafe_modifiers.rst 编写系统讲解concurrent_unordered_multiset中所有并发不安全修饰器的语义、前置条件与返回值约定并对照 源码实现 说明每个成员函数在底层链表上实际做了什么。读完后你将掌握如何安全地在单线程窗口内批量删除或抽离节点、透明键transparent key重载的 SFINAE 参与条件以及swap的noexcept判定逻辑。为什么这些成员函数被标记为不安全规格文档开篇给出整章的总前提All member functions in this section can only be performed serially. The behavior is undefined in case of concurrent execution of these member functions with other (either concurrently safe) methods.即本节的每个成员函数只能串行执行只要它与任何其他方法无论对方是否是并发安全方法并发运行行为即为未定义UB。这一设计与 STL 容器一致——std::unordered_multiset::erase、clear、extract同样不保证线程安全。在 TBB 的语境下该约束的实际含义是这些操作修改了底层分桶链表与原子大小计数器因此必须由用户自行保证调用期间没有并发访问典型做法是先完成并行阶段、在汇聚后的单线程阶段执行批量维护。从源码结构看不安全体现在实现上完全没有加锁例如 internal_erase 直接断言节点非空后解链并销毁节点internal_extract也直接改写桶内链表指针二者都不持有任何段级互斥量这正是文档要求串行调用的根本原因。clear()清空容器声明与语义继承自文档void clear();移除容器中的全部元素。源码中对应 concurrent_unordered_base::clear它是一个noexcept函数转发到internal_clear()。值得注意的一点是clear()出现在本不安全章节意味着即使并行迭代阶段刚结束若仍有线程在做并发安全方法如insert访问容器此时调用clear()同样构成未定义行为——清空操作不是原子屏障。unsafe_erase(pos)按迭代器删除单个元素文档给出两个按迭代器删除的重载iterator unsafe_erase( const_iterator pos ); iterator unsafe_erase( iterator pos );效果移除pos指向的元素迭代器失效所有指向被删元素的迭代器与引用失效返回值指向被删元素之后的迭代器即删除后接管遍历位置的迭代器可直接用于while (it ! end()) it unsafe_erase(it);这类循环前置条件Requirementspos必须有效、可解引用dereferenceable且指向*this中的元素。实现见 unsafe_erase 两个 pos 重载iterator unsafe_erase( const_iterator pos ) { return iterator(first_value_node(internal_erase(pos.get_node_ptr()))); } iterator unsafe_erase( iterator pos ) { return iterator(first_value_node(internal_erase(pos.get_node_ptr()))); }两个重载都委托给internal_erase并经过 first_value_node 过滤value_node_ptr first_value_node( node_ptr first_node ) const { while (first_node ! nullptr first_node-is_dummy()) { first_node first_node-next(); } return static_castvalue_node_ptr(first_node); }这里揭示了一个实现细节TBB 的分桶链表内部存在 dummy 占位节点下一个有效元素的返回值需要在跳过 dummy 节点后才交给用户。internal_erase本身L1157-L1163的流程是断言迭代器合法 → 先取出next()→ 解链并销毁节点→ 返回下一个节点。也就是说按迭代器删除是取出后继再销毁的顺序这保证了返回的迭代器一定指向仍然存活的节点或空即end()。unsafe_erase(key)按键删除返回删除个数size_type unsafe_erase( const key_type key );效果若容器中存在与key等价的元素则删除该元素multiset 语义下可能有多个等价元素迭代器失效所有指向被删元素的迭代器与引用失效返回值被删除元素的个数。由于这是 multiset同名元素可共存erase(key)会删除所有等价元素。源码中 unsafe_erase(key) 转发到internal_erase_by_keytemplate typename K size_type internal_erase_by_key( const K key ) { // TODO: consider reimplementation without equal_range - it is not effective to perform lookup over a bucket // for each unsafe_erase call auto eq_range equal_range(key); size_type erased_count 0; for (auto it eq_range.first; it ! eq_range.second;) { it unsafe_erase(it); erased_count; } return erased_count; }实现策略是先用equal_range(key)圈定所有等价元素的半开区间再循环调用按迭代器的unsafe_erase。源码注释中还保留了作者的 TODO当前做法在 multiset 场景下每次删除都要重新查找桶并不高效。这一内部实现细节解释了为什么按 key 删除的返回值是size_type计数而按迭代器删除返回迭代器——两者的循环驱动方式不同。透明键transparent key模板重载template typename K size_type unsafe_erase( const K key );与 key 等价的元素若存在则删除同样会使被删元素的迭代器与引用失效返回删除个数。该重载只有在满足全部三个条件时才参与重载决议限定名hasher::transparent_key_equal合法且表示一个类型即哈希函数承诺了透明比较能力std::is_convertibleK, iterator::value为falsestd::is_convertibleK, const_iterator::value为false。源码用 SFINAE 落实了这三条约束见 L515-L522template typename K typename std::enable_ifis_transparentK::value !std::is_convertibleK, const_iterator::value !std::is_convertibleK, iterator::value, size_type::type unsafe_erase( const K key ) { return internal_erase_by_key(key); }其中is_transparentK对应文档第一条hasher::transparent_key_equal检测后两个is_convertible检查则避免字符串字面量等可隐式转换为迭代器指针的类型被误匹配。实际效果是使用std::equal_tovoid这类透明比较器的哈希策略时可以传入与key_type不同类型但可比较的查询键例如用std::string_view查std::string键而无需临时构造键对象。unsafe_erase(first, last)按区间批量删除iterator unsafe_erase( const_iterator first, const_iterator last );效果移除半开区间[first, last)内所有元素返回值指向最后一个被删元素之后的迭代器前置条件[first, last)必须是*this中的一个合法子区间valid subrange。实现见 L504-L509iterator unsafe_erase( const_iterator first, const_iterator last ) { while(first ! last) { first unsafe_erase(first); } return iterator(first.get_node_ptr()); }它就是一个基于单元素unsafe_erase的线性推进循环——每次删除后返回的后继迭代器自然成为下一轮的first。由于删除返回的迭代器已经过first_value_node过滤 dummy 节点循环终止条件是可靠的前进过程当first追到last时返回last所在位置。这个写法与 STLunordered_multiset::erase(first, last)的返回约定完全对齐方便迁移已有代码。unsafe_extract把节点所有权移交给 node handle抽离extract与擦除erase的本质区别是元素不被销毁而是被封装进node_typenode handle可以稍后插入本容器或其他同型容器。文档提供三个重载。按迭代器抽离node_type unsafe_extract( iterator pos ); node_type unsafe_extract( const_iterator pos );将pos所指元素的所有权从容器转移到 node handle不会调用value_type的拷贝或移动构造零拷贝、零移动所有指向被抽离元素的迭代器失效但指向该元素的指针和引用仍然有效因为对象本身没有被破坏返回拥有该元素的 node handle前置条件pos有效、可解引用且指向*this中的元素。实现见 L524-L532node_type unsafe_extract( const_iterator pos ) { internal_extract(pos.get_node_ptr()); return d1::node_handle_accessor::constructnode_type(pos.get_node_ptr()); }关键在于内部函数 internal_extract// Unsafe method, which extracts the node from the list void internal_extract( value_node_ptr node_to_extract ) { const key_type key traits_type::get_key(node_to_extract-value()); sokey_type hash_key sokey_type(my_hash_compare(key)); node_ptr prev_node prepare_bucket(hash_key); for (node_ptr node prev_node-next(); node ! nullptr; prev_node node, node node-next()) { if (node node_to_extract) { unlink_node(prev_node, node, node_to_extract-next()); my_size.store(my_size.load(std::memory_order_relaxed) - 1, std::memory_order_relaxed); return; } __TBB_ASSERT(node-order_key() node_to_extract-order_key(), node, which is going to be extracted should be presented in the list); } }对照文档语义这里可以看到三层证据其一它只是把节点从链表中unlink_node摘除并原子递减my_size没有调用析构与指针和引用仍然有效的承诺吻合其二它依据节点自身键值重新哈希定位桶再线性查找与必须串行的前提一致无锁、无 CAS其三断言检查被抽离节点必须确实位于链表中呼应了文档对pos的 Requirements。随后node_handle_accessor::construct把这枚裸节点包装成node_type完成所有权转移——这解释了为什么文档强调不执行 value_type 的拷贝/移动构造对象只是换了个外壳。按键抽离node_type unsafe_extract( const key_type key ); template typename K node_type unsafe_extract( const K key );若存在与key等价的元素则转移该元素的所有权不执行value_type的拷贝/移动构造multiset 语义要点若存在多个等价元素转移其中哪一个是不确定的unspecified所有指向被抽离元素的迭代器失效指针与引用保持有效返回拥有该元素的 node handle若未找到等价元素返回空node handle可用empty()判断模板重载的参与条件与unsafe_erase的透明键重载完全相同transparent_key_equal合法且K不可转换为iterator/const_iterator。实现上两个按键重载先find再复用按迭代器抽离见 L534-L547node_type unsafe_extract( const key_type key ) { iterator item find(key); return item end() ? node_type() : unsafe_extract(item); }find返回桶内命中的第一个等价元素因此多个等价元素时抽哪一个不确定在实现层面就是取查找路径先命中的那个找不到时返回默认构造的node_type()与文档空 node handle的约定一一对应。抽离出的 node handle 可以与insert(node_type)配合完成跨容器搬迁先unsafe_extract摘走节点再在目标容器中insert(std::move(nh))全程不触碰value_type的构造/析构适合把大对象在多个容器间重新分配的场景。swap整体内容互换void swap( concurrent_unordered_multiset other ) noexcept(/*See below*/);交换*this与other的内容若std::allocator_traitsallocator_type::propagate_on_container_swap::value为true则连分配器一起交换否则不传播如果get_allocator() ! other.get_allocator()行为未定义文档给出的noexcept规格为noexcept(std::allocator_traitsallocator_type::is_always_equal::value std::is_nothrow_swappablehasher::value std::is_nothrow_swappablekey_equal::value文档原文的 noexcept 表达式在此处截断完整表达式以 源码头文件 的实际标注为准。源码中 swap 实现void swap( concurrent_unordered_base other ) noexcept(unordered_segment_table::is_noexcept_swap) { if (this ! other) { using pocs_type typename allocator_traits_type::propagate_on_container_swap; using is_always_equal typename allocator_traits_type::is_always_equal; internal_swap(other, tbb::detail::disjunctionpocs_type, is_always_equal()); } }三个实现事实可以佐证文档的语义第一自交换this other被短路跳过a.swap(a)是安全的空操作第二internal_swap以disjunctionpocs_type, is_always_equal作为标签分派参数——当分配器总是相等时即使分配器类型不承诺propagate_on_container_swap交换内容也是安全的这正是文档否则若分配器不相等则 UB条款在实现上的兜底判定第三整个方法标注为noexcept(unordered_segment_table::is_noexcept_swap)把 noexcept 与否的判定权委托给底层分段表的静态常量而分段表能否无抛出交换本质上取决于其内存分配器与策略对象hasher、key_equal是否满足 noexcept 可交换条件与文档 noexcept 表达式所列因子一致。swap也属于本节只能串行执行的范畴虽然它不修改单个元素的数据但它整体替换了两容器的内部结构若与任何并发访问同时进行同样触发未定义行为。与文档同章规格的关系与测试佐证该 RST 文件是concurrent_unordered_multiset完整规格的一部分同目录下还有 safe_modifiers.rst并发安全的增改方法、lookup.rst、iterators.rst 等章节。理解safe/unsafe两套修饰器的分工是正确使用该容器的前提safe 修饰器如并发insert任何时刻都可与彼此并行调用unsafe 修饰器本文主题必须串行执行且不得与任何方法并发。容器本身的类定义见 concurrent_unordered_set.hconcurrent_unordered_multiset继承自concurrent_unordered_base其 traits 的最后一项模板参数为true允许同键多值即 multimapping这正是按 key 删除/抽离返回计数或不确定命中对象这一 multiset 语义的类型学根源。仓库测试侧在 test/common/concurrent_associative_common.h 与 test/common/node_handling_support.h 中对unsafe_erase、unsafe_extract等接口做了通用用例覆盖可用于对照本文语义说明。实用要点小结使用窗口所有unsafe_*成员都应在无并发访问的单线程阶段调用典型是并行构建/迭代之后的维护阶段与文档总述一致任何与它们并发的调用无论并发方法本身是否安全都是未定义行为。迭代器协议unsafe_erase(pos)与unsafe_erase(first,last)返回删除点之后的迭代器是标准的 STL 式删除遍历协议返回值已经过滤内部 dummy 节点可直接续用。multiset 差异按键操作面对多个等价元素时unsafe_erase(key)删除全部等价元素并返回计数unsafe_extract(key)只转移其中一个具体哪个 unspecified抽离未命中时得到可用empty()判定的空 node handle。零拷贝抽离unsafe_extract不触发value_type的拷贝/移动构造被抽离元素的指针与引用保持有效可配合insert(node_type)做容器间节点搬迁。透明键重载template typename K版本仅在hasher::transparent_key_equal有效且K不可转换为iterator/const_iterator时参与重载决议源码中由enable_ifis_transparentK ...实现使string_view之类查询键可免构造使用。swap 的分配器契约内容互换始终执行分配器是否跟随交换取决于propagate_on_container_swap不传播时两容器分配器必须相等否则 UBswap的noexcept由分配器、哈希器与比较器的可交换性共同决定实现中委托给unordered_segment_table::is_noexcept_swap静态常量。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考