mold 内嵌 TBB：concurrent_unordered_multiset 的构造、析构与复制语义深度解析

mold 内嵌 TBBconcurrent_unordered_multiset 的构造、析构与复制语义深度解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文聚焦 mold 仓库 third-party 目录中随附的 Intel oneAPI TBB 规范文档construction_destruction_copying.rst系统讲解concurrent_unordered_multiset容器从空构造、序列构造、拷贝/移动到析构与赋值运算符的完整生命周期 API。读完本文你既能掌握规范中每个构造函数与赋值运算符的签名、参数约束与并发安全边界也能对照 vendored TBB 的模板源码concurrent_unordered_set.h与内部基类_concurrent_unordered_base.h理解这些语义背后的无锁实现细节分片段表、split-ordered 链表、分配器传播规则以及 noexcept 规格的推导方式。需要说明的前提mold 是 ELF 链接器TBB 以第三方依赖形式 vendored 在 third-party/tbb 子树中。本文所有规范依据均出自 construction_destruction_copying.rst所有实现依据均可在该子树的include/oneapi/tbb头文件与test目录中找到对应物。一、容器定位multiset 在 TBB 无序容器家族中的角色concurrent_unordered_multiset的规范位于 concurrent_unordered_multiset_cls 目录同目录还包含 bucket 接口、查找、观察器、并行迭代等章节。其类模板声明在 concurrent_unordered_set.htemplate typename Key, typename Hash std::hashKey, typename KeyEqual std::equal_toKey, typename Allocator tbb::tbb_allocatorKey class concurrent_unordered_multiset : public concurrent_unordered_baseconcurrent_unordered_set_traitsKey, Hash, KeyEqual, Allocator, true从源码结构看TBB 的四种无序容器set/multiset/map/multimap共用同一个内部基类concurrent_unordered_baseTraits差异被压缩进 traits 的一个布尔量allow_multimappingconcurrent_unordered_set.h#L28-L39multiset 传trueset 传false。这直接决定了重复键的插入行为——基类在search_after中只有当allow_multimapping为false时才把找到等键节点视为插入失败_concurrent_unordered_base.h#L1022-L1039。因此本文讨论的构造语义对 set 同样成立但 multiset 允许等键元素共存于同一桶内。multiset 类体本身非常薄除merge与operator(std::initializer_list)外其余成员全部继承自基类// concurrent_unordered_set.h L208-L219 using base_type::base_type; // 继承基类全部构造函数 concurrent_unordered_multiset() default; concurrent_unordered_multiset( const concurrent_unordered_multiset ) default; concurrent_unordered_multiset( const concurrent_unordered_multiset other, const allocator_type alloc ) : base_type(other, alloc) {} concurrent_unordered_multiset( concurrent_unordered_multiset ) default; concurrent_unordered_multiset( concurrent_unordered_multiset other, const allocator_type alloc ) : base_type(std::move(other), alloc) {} // Required to respect the rule of 5 concurrent_unordered_multiset operator( const concurrent_unordered_multiset ) default; concurrent_unordered_multiset operator( concurrent_unordered_multiset ) default;源码注释明确写出 default 成员是为了遵守规则五rule of 5并支撑隐式推导指南。下面按规范文档的小节顺序逐一展开。二、空容器构造函数规范给出两组空容器构造见 construction_destruction_copying.rst#L9-L41concurrent_unordered_multiset(); explicit concurrent_unordered_multiset( const allocator_type alloc );构造一个空容器初始桶数由实现定义unspecified提供alloc时用它分配内存。explicit concurrent_unordered_multiset( size_type bucket_count, const hasher hash hasher(), const key_equal equal key_equal(), const allocator_type alloc allocator_type() ); concurrent_unordered_multiset( size_type bucket_count, const allocator_type alloc ); concurrent_unordered_multiset( size_type bucket_count, const hasher hash, const allocator_type alloc );构造一个拥有bucket_count个桶的空容器可选提供哈希函数、等值谓词与分配器。实现定义的默认桶数在源码中是有确切值的。基类主构造函数_concurrent_unordered_base.h#L244-L262explicit concurrent_unordered_base( size_type bucket_count, const hasher hash hasher(), const key_equal equal key_equal(), const allocator_type alloc allocator_type() ) : my_size(0), my_bucket_count(round_up_to_power_of_two(bucket_count)), my_max_load_factor(float(initial_max_load_factor)), my_hash_compare(hash, equal), my_head(sokey_type(0)), my_segments(alloc) {} concurrent_unordered_base() : concurrent_unordered_base(initial_bucket_count) {}对应的实现常量L787-L788static constexpr size_type initial_bucket_count 8; static constexpr float initial_max_load_factor 4; // TODO: consider 1?即不传参数时初始桶数为 8、初始最大负载因子为 4.0。这里有两个值得注意的实现细节桶数会被上取整到 2 的幂。round_up_to_power_of_twoL235-L237先对bucket_count做log2(x*2-1)再左移一位例如传 100 会得到 128 个桶。这与桶下标用hash % bucket_count计算prepare_bucketL1082-L1085相配合保证取模运算可退化为位与。桶并不在构造时实体分配。my_segments是内嵌段表embedded segment table桶 0 直接指向容器内嵌的头节点my_head见init_bucket中my_segments[0].compare_exchange_strong(disabled, my_head)L1095-L1119其余桶的虚节点dummy node在首次访问时按需插入链表。因此空构造 指定大 bucket_count的开销非常小内存占用随实际插入量惰性增长。另一个结构性事实my_head(sokey_type(0))表明头节点的 order key 是 0而普通节点 order key 的最低位恒为 1split_order_key_regularL1445-L1453is_dummy()正是靠这个最低位区分空桶虚节点与真实元素节点L142-L145——这是理解拷贝/移动为何要逐节点复制的前提。三、从元素序列构造规范给出三组迭代器构造、三组初始化列表构造construction_destruction_copying.rst#L42-L101template typename InputIterator concurrent_unordered_multiset( InputIterator first, InputIterator last, size_type bucket_count /*implementation-defined*/, const hasher hash hasher(), const key_equal equal key_equal(), const allocator_type alloc allocator_type() ); template typename InputIterator concurrent_unordered_multiset( InputIterator first, InputIterator last, size_type bucket_count, const allocator_type alloc ); template typename InputIterator concurrent_unordered_multiset( InputIterator first, InputIterator last, size_type bucket_count, const hasher hash, const allocator_type alloc );构造包含半开区间[first, last)中元素的容器。要求InputIterator必须满足 ISO C 标准 [input.iterators] 一节对 InputIterator 的要求。concurrent_unordered_multiset( std::initializer_listvalue_type init, size_type bucket_count /*implementation-defined*/, const hasher hash hasher(), const key_equal equal key_equal(), const allocator_type alloc allocator_type() ); // 等价于 concurrent_unordered_multiset(init.begin(), init.end(), bucket_count, hash, equal, alloc) concurrent_unordered_multiset( std::initializer_listvalue_type init, size_type bucket_count, const allocator_type alloc ); // 等价于 concurrent_unordered_multiset(init.begin(), init.end(), bucket_count, alloc) concurrent_unordered_multiset( std::initializer_listvalue_type init, size_type bucket_count, const hasher hash, const allocator_type alloc ); // 等价于 concurrent_unordered_multiset(init.begin(), init.end(), bucket_count, hash, alloc)源码中迭代器构造的实现_concurrent_unordered_base.h#L264-L281就是先按bucket_count完成基础构造再循环inserttemplate typename InputIterator concurrent_unordered_base( InputIterator first, InputIterator last, size_type bucket_count initial_bucket_count, const hasher hash hasher(), const key_equal equal key_equal(), const allocator_type alloc allocator_type() ) : concurrent_unordered_base(bucket_count, hash, equal, alloc) { insert(first, last); }其中insert(first, last)是逐个insert(*first)L433-L438每次插入走完整的internal_insert无锁路径L986-L1017计算 order key、经search_after定位、用try_insert的 CAS 循环挂接插入成功后my_size.fetch_add(1)并按需把桶数翻倍adjust_table_sizeL1041-L1047。对 multiset 而言重复键会各自成为独立节点被插入对 set 则重复键会创建节点后在发现已存在时销毁该节点internal_insert_value中的destroy_node(insert_result.remaining_node)L952-L970。初始化列表构造则是纯委托concurrent_unordered_base( std::initializer_listvalue_type init, size_type bucket_count initial_bucket_count, const hasher hash hasher(), const key_equal equal key_equal(), const allocator_type alloc allocator_type() ) : concurrent_unordered_base(init.begin(), init.end(), bucket_count, hash, equal, alloc) {}与规范等价于……的表述逐字对应L336-L348。C17 类模板参数推导上述构造在 C17 下支持 CTAD拷贝/移动构造含带 allocator 的版本提供隐式生成的推导指南头文件另外给出了显式推导指南规范见 deduction_guides.rst实现见 concurrent_unordered_set.h#L247 起。关键约束是推导指南仅当迭代器满足 InputIterator 要求、allocator 满足 Allocator 要求、且Hash/KeyEqual不满足 Allocator 要求时才参与重载决议——这一组enable_if条件is_input_iterator_v/is_allocator_v/!std::is_integral_vHash用于消除第三个参数是 allocator 还是哈希函数的二义性。规范给出的示例#include oneapi/tbb/concurrent_unordered_set.h #include vector #include functional struct CustomHasher {...}; int main() { std::vectorint v; // Deduces s1 as concurrent_unordered_multisetint oneapi::tbb::concurrent_unordered_multiset s1(v.begin(), v.end()); // Deduces s2 as concurrent_unordered_multisetint, CustomHasher; oneapi::tbb::concurrent_unordered_multiset s2(v.begin(), v.end(), CustomHasher{}); }四、拷贝构造逐节点复制 split-ordered 链表规范construction_destruction_copying.rst#L103-L118concurrent_unordered_multiset( const concurrent_unordered_multiset other ); concurrent_unordered_multiset( const concurrent_unordered_multiset other, const allocator_type alloc );构造other的拷贝。未提供 allocator 时调用std::allocator_traitsallocator_type::select_on_container_copy_construction(other.get_allocator())获得。与other并发操作时行为未定义。multiset 头文件中这两个构造要么是 default继承基类要么显式委托base_type(other, alloc)concurrent_unordered_set.h#L213-L214。基类的拷贝构造_concurrent_unordered_base.h#L283-L311分三步以 relaxed 序快照other的my_size、my_bucket_count、my_max_load_factor、哈希比较器与头节点 order key并拷贝/带 allocator 拷贝my_segments段表internal_copy(other)遍历other.my_head.next()开始的整条split-ordered 链表真实节点用create_node(order_key, value)复制值虚节点用create_dummy_node(order_key)复制桶锚点并同步写回my_segments[reverse_bits(order_key)]异常安全try_call(...).on_exception([] { clear(); })复制中途抛异常时清理已建节点。void internal_copy( const concurrent_unordered_base other ) { node_ptr last_node my_head; my_segments[0].store(my_head, std::memory_order_relaxed); for (node_ptr node other.my_head.next(); node ! nullptr; node node-next()) { node_ptr new_node; if (!node-is_dummy()) { new_node create_node(node-order_key(), static_castvalue_node_ptr(node)-value()); } else { new_node create_dummy_node(node-order_key()); my_segments[reverse_bits(node-order_key())].store(new_node, std::memory_order_relaxed); } last_node-set_next(new_node); last_node new_node; } }L1321-L1339从源码结构看这份实现把顺序一致作为不变量整体迁移order key即反向哈希随节点一起复制段表与链表的相对关系不变因此拷贝出的容器可以直接并发使用而不需要重新哈希。代价是连尚未被任何元素占用的桶虚节点也一并复制——这也是拷贝构造比迭代 insert重建更忠实于other桶布局的原因。五、移动构造偷换链表头 vs. 逐节点搬移规范construction_destruction_copying.rst#L120-L136concurrent_unordered_multiset( concurrent_unordered_multiset other ); concurrent_unordered_multiset( concurrent_unordered_multiset other, const allocator_type alloc );以移动语义构造other被留在有效但未指定的状态未提供 allocator 时由std::move(other.get_allocator())获得与other并发操作时行为未定义。基类移动构造L313-L334先把my_size、my_bucket_count、负载因子、哈希比较器、my_segments从other搬走再进入move_contentvoid move_content( concurrent_unordered_base other ) { // NOTE: allocators should be equal my_head.set_next(other.my_head.next()); other.my_head.set_next(nullptr); my_segments[0].store(my_head, std::memory_order_relaxed); other.my_bucket_count.store(initial_bucket_count, std::memory_order_relaxed); other.my_max_load_factor initial_max_load_factor; other.my_size.store(0, std::memory_order_relaxed); }L1362-L1371这里印证了valid but unspecified的规范措辞move_content直接把other的头节点 next 指针摘走并置空然后把other的桶数/负载因子/size 重置为初始值8 桶、4.0、0 元素——other确实回到与默认构造几乎一致的可复用状态。若两侧 allocator 恒等is_always_equal如std::allocator/tbb_allocator走上述 O(1) 的指针交接。若 allocator 可能不等则委托internal_move_construct_with_allocatorL1373-L1391分配器相等仍走move_content不相等则逐节点create_node(order_key, std::move(value))重新构造到alloc中internal_moveL1341-L1360并以try_call/on_exception(clear)提供异常安全。六、析构函数销毁元素并归还存储规范construction_destruction_copying.rst#L138-L148~concurrent_unordered_multiset();销毁容器调用被存元素的析构函数并释放所占用的存储。与*this并发操作时行为未定义。基类析构L350-L352一行委托给internal_clear后者与clear()共用同一段逻辑L900-L915void internal_clear() { node_ptr next my_head.next(); node_ptr curr next; my_head.set_next(nullptr); while (curr ! nullptr) { next curr-next(); destroy_node(curr); curr next; } my_size.store(0, std::memory_order_relaxed); my_segments.clear(); }destroy_nodeL917-L938按节点类型分派虚节点用 rebind 出的node_allocator_type销毁并释放真实节点先对storage()内的值调用析构value_node_allocator_traits::destroy再销毁节点对象本身并释放内存。my_segments.clear()释放段表中各虚节点段。这解释了规范调用元素析构 释放存储这句话在实现层的两个动作边界值的析构与节点/段内存的释放是独立步骤。七、赋值运算符规范给出三个赋值construction_destruction_copying.rst#L150-L201。拷贝赋值concurrent_unordered_multiset operator( const concurrent_unordered_multiset other );以other的元素拷贝替换*this的全部元素当propagate_on_container_copy_assignment::value为 true 时拷贝赋值 allocator与*this、other并发操作时行为未定义返回*this的引用。基类实现L354-L365concurrent_unordered_base operator( const concurrent_unordered_base other ) { if (this ! other) { clear(); my_size.store(other.my_size.load(std::memory_order_relaxed), std::memory_order_relaxed); my_bucket_count.store(other.my_bucket_count.load(std::memory_order_relaxed), std::memory_order_relaxed); my_max_load_factor other.my_max_load_factor; my_hash_compare other.my_hash_compare; my_segments other.my_segments; internal_copy(other); } return *this; }注意其先clear()再逐字段快照再internal_copy的次序先腾空自身再从other完整重建链表与段表因此*this原有的桶布局被整体替换为other的布局。移动赋值concurrent_unordered_multiset operator( concurrent_unordered_multiset other ) noexcept(/*See below*/);以移动语义替换全部元素other留在有效但未指定状态当propagate_on_container_move_assignment::value为 true 时移动赋值 allocator并发操作时行为未定义返回*this。noexcept 规格规范原文noexcept(std::allocator_traitsallocator_type::is_always_equal::value std::is_nothrow_move_assignablehasher::value std::is_nothrow_move_assignablekey_equal::value)源码中的对应物是段表类型上的静态常量L805-L810移动赋值的 noexcept 参数即取unordered_segment_table::is_noexcept_assignmentstatic constexpr bool is_noexcept_assignment std::is_nothrow_move_assignablehasher::value std::is_nothrow_move_assignablekey_equal::value segment_allocator_traits::is_always_equal::value;两者在 allocator 语义上一致分配器恒等 hasher/key_equal 可无抛出移动赋值差别仅在 is_always_equal 具体取自哪个 rebind 后的分配器 traits——对tbb_allocator与std::allocator这类无状态分配器结论相同。赋值本体L367-L381先clear()再搬走 size/桶数/负载因子/哈希比较器/段表最后按disjunctionpropagate_on_container_move_assignment, is_always_equal选择move_contentO(1) 换头或internal_move逐节点移动构造L1395-L1408。初始化列表赋值concurrent_unordered_multiset operator( std::initializer_listvalue_type init );以init的元素替换*this的全部元素与*this并发操作时行为未定义返回*this。该成员在 multiset 类体中显式重写并转发基类concurrent_unordered_set.h#L221-L224基类实现是最直白的两步L383-L387concurrent_unordered_base operator( std::initializer_listvalue_type init ) { clear(); insert(init); return *this; }八、并发安全边界与unsafe约定规范在拷贝构造、移动构造、析构和三个赋值运算符上反复标注与容器并发操作时行为未定义。这不是措辞上的谨慎而是有实现的对应基类中所有需要稳定视图的遍历internal_copy、internal_move、move_content、internal_clear都不带 CAS 保护直接沿next()指针走。删除/摘取 API 在规范中被归入 unsafe_modifiers 与 safe_modifiers 两章基类里也命名呼应unsafe_erase/unsafe_extractL496-L547内部用__TBB_ASSERT校验摘除操作在单线程前提下前后指针关系稳定unlink_nodeL1249-L1256。由此可得实践边界并发安全默认/指定桶数/迭代器/初始化列表构造构造过程只做插入插入路径本身无锁、析构单线程销毁整个容器是常规用法、以及对无其他线程接触的容器做拷贝/移动/赋值未定义行为在operator、拷贝/移动构造、clear/析构进行中另一线程并发修改同一对象若需在容器被并发读写期间获取快照应改用迭代 插入到新建容器的自行复制策略——这与insert的并发安全性质一致。九、验证路径规范与实现如何对账TBB 子树自带两层次的测试可以佐证本文所述语义test/conformance/conformance_concurrent_unordered_set.cpp标准符合性测试按 STL 容器模型逐项校验构造、赋值、观察器等行为是规范文档与实现之间最直接的桥梁test/tbb/test_concurrent_unordered_set.cpp功能/压力测试覆盖插入查找、桶接口、拷贝移动等路径。规范文档目录 concurrent_unordered_multiset_cls 下的兄弟章节bucket 接口、查找、观察器、hash 策略、swap、并行迭代等与本文构成完整 API 面需要时可以顺藤摸瓜。十、实践要点小结默认桶数并非任意规范写 unspecifiedvendored 实现为 8initial_bucket_count且任何bucket_count参数都会经round_up_to_power_of_two上取整到 2 的幂最大负载因子初始为 4.0——预知规模时传偏大的bucket_count可减少运行期 CAS 翻倍。桶是惰性的构造只建立段表骨架桶虚节点随插入按需创建空构造 大桶数几乎零成本但bucket_count增大后桶数只能增不能减rehash仅在目标更大时生效L670-L676。移动是最廉价的转移方式无状态分配器下移动构造/移动赋值是 O(1) 的头指针交接源对象回到有效但未指定的初始桶状态只有 allocator 不恒等时才退化为逐节点搬移。拷贝是忠实重建order key 与段表一并复制无需重新散列因此拷贝构造/赋值保留桶布局但要求操作期间无并发修改。异常安全靠 clear 兜底拷贝构造与带分配器的移动构造都用try_call().on_exception([]{ clear(); })包裹逐节点复制中途失败不会泄漏节点。C17 下可用 CTAD迭代器/初始化列表构造有显式推导指南Hash/KeyEqual参数不得满足 Allocator 要求否则参与决议会被enable_if剔除。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考