mold 仓库中的 TBB 容器规范concurrent_unordered_multiset 迭代器的 ForwardIterator 契约与源码实现【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本篇聚焦 iterators.rst 这一 TBB 容器规范文档它规定了oneapi::tbb::concurrent_unordered_multiset的begin/cbegin/end/cend四个成员函数以及iterator/const_iterator的语义。结合仓库中 vendored 的 TBB 头文件源码本文完整还原这组迭代器的标准类型要求、返回语义以及底层solist_iterator如何跳过 dummy 节点实现安全遍历帮助读者理解并发哈希容器的迭代机制并能在多线程场景下正确使用。背景文档在 TBB 规范体系中的位置该文档是 concurrent_unordered_multiset.rst 规范页“Member functions”部分的一节与 construction_destruction_copying.rst、lookup.rst、bucket_interface.rst 等小节共同构成concurrent_unordered_multiset的完整规范。从父文档可以确认容器的核心定位concurrent_unordered_multiset表示一个无序元素序列支持并发的插入、查找和遍历但不支持并发删除且允许存储多个等价值multiset 语义key_type与value_type相同。元素按哈希函数的值组织进 buckets其中第一个 bucket 的第一个元素被内嵌在容器对象的my_head节点中——这一结构细节将直接影响迭代器的起点定义。mold 仓库将 TBB 完整 vendor 在third-party/tbb/下作为构建依赖链接器自身的多线程实现就构建在这套并发设施之上例如 gc-sections.cc 同时包含tbb/concurrent_unordered_map.h、tbb/concurrent_vector.h与tbb/parallel_for_each.h用于垃圾回收阶段的并发处理。理解 TBB 容器的迭代器规范等于理解 mold 链接管线中并发数据结构的遍历契约。迭代器类型与 ForwardIterator 要求原文档的核心断言只有一条但它是整节的灵魂类型concurrent_unordered_multiset::iterator和concurrent_unordered_multiset::const_iterator满足 ISO C 标准 [forward.iterators] 节对ForwardIterator的要求。这一要求在仓库源码中有直接的实现证据。真正的迭代器类型定义在 detail/_concurrent_unordered_base.h容器基类通过以下别名将其暴露出来约 L210-L213using iterator solist_iteratorself_type, value_type; using const_iterator solist_iteratorself_type, const value_type; using local_iterator iterator; using const_local_iterator const_iterator;注意两点iterator与const_iterator是同一个模板类solist_iterator在不同Value参数下的实例化——可变性与否只体现在解引用返回类型上底层遍历逻辑完全共享local_iteratorbucket 局部迭代器与全局迭代器是同一类型这在后文的 bucket 接口讨论中还会用到。solist_iterator的标准库类型成员detail/_concurrent_unordered_base.h逐条对应 ForwardIterator 的要求templatetypename Container, typename Value class solist_iterator { // ... public: using value_type Value; using difference_type typename Container::difference_type; using pointer value_type*; using reference value_type; using iterator_category std::forward_iterator_tag; // L74ForwardIterator 的类别证明iterator_category为std::forward_iterator_tag这是满足 [forward.iterators] 要求的类别下限容器侧的difference_type定义为std::ptrdiff_t基类 L208value_type为key_type对 multiset 即元素本身。ForwardIterator 要求的另外两个语义——自增值与自身可比较——同样有实现背书。等值比较直接比较底层节点指针约 L116-L119templatetypename Solist, typename T, typename U bool operator( const solist_iteratorSolist, T i, const solist_iteratorSolist, U j ) { return i.my_node_ptr j.my_node_ptr; }operator!为其否定。由于迭代器本质只是一个节点指针end()与begin()的比较、以及迭代器自身的拷贝/赋值都是平凡且廉价的。begin 与 cbegin指向“第一个元素”原文档给出的声明与语义iterator begin(); const_iterator begin() const; const_iterator cbegin() const;Returns: an iterator to the first element in the container.返回指向容器中第一个元素的迭代器实现位于容器基类detail/_concurrent_unordered_base.hiterator begin() noexcept { return iterator(first_value_node(my_head)); } const_iterator begin() const noexcept { return const_iterator(first_value_node(const_castnode_ptr(my_head))); } const_iterator cbegin() const noexcept { return const_iterator(first_value_node(const_castnode_ptr(my_head))); }三个事实值得拆解起点是my_head节点。构造时my_head(sokey_type(0))L250作为顺序键为 0 的头节点被嵌入容器对象内部并且my_segments[0]在初始化时指向它L1097-L1099 的注释明确写着 Atomically store the first bucket into my_head。因此begin()不经过任何指针追逐就能取到遍历入口空容器的my_head后继为空时first_value_node会直接落到nullptr上从而与end()相等。begin()与cbegin()都调用first_value_node(my_head)。该辅助函数L1149 起的作用是从给定节点开始跳过所有 dummy 节点返回第一个真实值节点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 /* first_node 转型为 value 节点 */; }dummy 节点是 TBB 并发哈希表内部的哨兵节点用于标记正在被 resize 的 bucket 边界。begin()必须跳过 dummy 节点才能保证“指向第一个元素”这一规范语义即使在并发 rehash 期间也成立。const 版本通过const_cast复用同一非 const 路径。这是实现层的技巧my_head的next指针是std::atomicnode_ptr其读取本身是线程安全的不需要区分 const 访问。end 与 cend指向“最后元素之后”原文档的声明与语义iterator end(); const_iterator end() const; const_iterator cend() const;Returns: an iterator to the element that follows the last element in the container.返回指向容器中最后一个元素之后位置的迭代器实现极为简洁detail/_concurrent_unordered_base.hiterator end() noexcept { return iterator(nullptr); } const_iterator end() const noexcept { return const_iterator(nullptr); }即end()是一个持有空指针的solist_iterator。这与单链表遍历的惯例一致整条链由my_head起、以nullptr收尾。default构造的solist_iterator即为此状态L76solist_iterator() : my_node_ptr(nullptr) {}因此默认构造的迭代器恰好等价于end()。遍历机制operator*、operator- 与自增要完整理解 ForwardIterator 契约还需看迭代器自身的三个核心操作detail/_concurrent_unordered_base.hreference operator*() const { return my_node_ptr-value(); } pointer operator-() const { return my_node_ptr-storage(); } solist_iterator operator() { auto next_node my_node_ptr-next(); while(next_node next_node-is_dummy()) { next_node next_node-next(); } my_node_ptr static_castnode_ptr(next_node); return *this; }几个要点解引用返回元素引用。节点类型value_nodeL164-L186内嵌value_type my_valuevalue()与storage()分别提供引用与指针访问对 multiset 而言value_type即Key本身。前置自增会跨过 dummy 节点。while(next_node next_node-is_dummy())循环说明即使遍历中途有并发操作在链上留下 dummy 哨兵迭代器也能透明地越过它们继续前进而不需要调用方感知 bucket 的重组过程。这解释了为何规范敢于声称迭代器在并发插入下遍历是安全的。后置自增返回旧值标准的tmp *this; *this; return tmp;模式L102-L106。从源码结构看遍历的可见性语义可以推断如下迭代器每一步只读取当前节点的next()一个 release 顺序的原子指针见list_node::my_nextL160因此并发insert追加的新元素“可能”不被正在进行的遍历看见——这与父文档“支持并发插入与遍历”的承诺一致不承诺看到插入只承诺不崩溃。规范文档本身未展开这一点这里仅作推断性说明。与 local_iterator 及桶接口的衔接由于local_iterator就是iteratorL212begin()/end()返回的迭代器可以直接与 bucket_interface.rst 描述的unsafe_begin(n)/unsafe_end(n)返回值混用比较。实现上L613-L639local_iterator unsafe_begin( size_type n ) { return local_iterator(first_value_node(get_bucket(n))); } // unsafe_end(n) 指向下一个 bucket 的起点最后一个 bucket 的 end 为 local_iterator(nullptr)unsafe_end(最后一个 bucket)返回的正是与end()相同的空指针迭代器二者可以统一参与std::distance等算法unsafe_bucket_size(n)在 L649 内部就是这么实现的。multiset 特有的equal_range也依赖同一套节点机制equal_range在匹配到键后继续沿链扫描直到遇到 dummy 哨兵或不等价的节点为止L1301 附近的allow_multimapping循环返回[first, last)区间。这正是“multiset 允许多个等价元素”语义在迭代器层面的落点。使用示例与并发注意事项基于上述语义一个典型用法如下示例代码非仓库文件#include oneapi/tbb/concurrent_unordered_set.h #include iostream int main() { oneapi::tbb::concurrent_unordered_multisetint m; // 单线程阶段填充insert 本身是并发安全的 m.insert(10); m.insert(20); m.insert(20); m.insert(30); // 只读遍历cbegin()/cend() 满足 ForwardIterator 要求 for (auto it m.cbegin(); it ! m.cend(); it) { std::cout *it ; } }实践中的三条注意事项均直接源于本文所述的实现不要持有迭代器跨越unsafe_erase/clear/swap这些属于“并发不安全修改器”被迭代节点的内存会被释放迭代器随即悬空遍历期间的并发插入不会使已持有的迭代器失效节点一经分配即不被移动但新插入的元素不保证被当前遍历看见迭代器比较是指针比较O(1)跨不同begin()取回的迭代器可以直接比较适合实现“从上次断点继续遍历”之类的模式。小结iterators.rst 篇幅虽短却钉死了concurrent_unordered_multiset迭代器的标准契约iterator/const_iterator满足 ISO CForwardIterator要求begin/cbegin指向第一个元素end/cend指向尾后位置。对照 detail/_concurrent_unordered_base.h 的实现可以看到该契约的支撑结构solist_iterator以std::forward_iterator_tag声明类别begin()从内嵌的my_head节点出发并经first_value_node跳过 dummy 哨兵end()即空指针迭代器自增与比较均为 O(1)。掌握这些细节后无论是阅读 TBB 容器规范还是在类似 mold 这样把 TBB 作为构建依赖的项目中排查并发遍历问题都有了一份可对照的规范与源码索引。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考