外部存储的红黑树集合F´ Fw/DataStructures 中 ExternalRedBlackTreeSet 完整技术指南【免费下载链接】fprimeF´ - A flight software and embedded systems framework项目地址: https://gitcode.com/GitHub_Trending/fpr/fprimeExternalRedBlackTreeSet是 F´F Prime飞行软件与嵌入式系统框架Fw/DataStructures数据结构库中基于红黑树实现、采用外部后备存储的集合Set类模板。本文以官方 SDD 文档Fw/DataStructures/docs/ExternalRedBlackTreeSet.md为骨架结合仓库头文件与单元测试系统讲解它的模板参数、继承体系、五个构造函数、全部成员函数、静态存储布局函数以及底层RedBlackTreeSetOrMapImpl的红黑树不变量与重平衡原理帮助你理解如何在零堆分配、容量受限的嵌入式场景中直接使用该容器。1. 定位F´ DataStructures 库中的外部存储集合在 F´ 框架中Fw/DataStructures提供了一组基础数据结构所有定义位于命名空间Fw下。该库区分两个核心概念见 sdd.mdsize大小数据结构当前存储的元素个数capacity容量数据结构最多可存储的元素个数。对于定长数组size 与 capacity 相同对于集合这类容器size 介于 0 与 capacity 之间。所有容器都属于顺序数据结构sequential data structures不支持多线程直接并发访问如需多线程使用官方建议将其作为 active/queued 组件的成员借助组件队列来串行化访问。集合Set家族在Fw/DataStructures中一共有四个实现类模板类模板底层结构存储方式ArraySet数组内部存储ExternalArraySet数组外部存储RedBlackTreeSet红黑树内部存储ExternalRedBlackTreeSet红黑树外部存储类图如下外部存储意味着树节点所用的内存由调用方提供可以是一段静态分配的缓冲区或字节数组容器自身不持有、不动态申请内存。这正是嵌入式/飞行软件场景的核心诉求零堆分配、容量静态可控、运行时可预测。2. 模板参数与基类2.1. 模板参数ExternalRedBlackTreeSet只有一个模板参数对应文档第 1 节KindNamePurposetypenameT集合中元素的类型与内部存储版本RedBlackTreeSetT, C容量C作为编译期模板参数见 RedBlackTreeSet.md不同ExternalRedBlackTreeSetT的容量是运行时通过构造函数或setStorage传入的灵活性更高代价是需要调用方自行管理后备内存。2.2. 基类ExternalRedBlackTreeSetT公开继承自抽象基类SetBaseT而SetBaseT又继承自SizedContainer表示具有 capacity 与 size 的通用容器。SetBase定义了集合的抽象接口SetBase.hppvirtual ConstIterator begin() const 0; virtual ConstIterator end() const 0; virtual Success find(const T element) const 0; virtual Success insert(const T element) 0; virtual Success remove(const T element) 0;此外SetBase还提供非虚的copyDataFrom(const SetBaseT set)用于把另一个集合的数据复制到当前集合先clear()再取min(set.getSize(), getCapacity())个元素逐一insert并断言插入成功。值得注意的继承细节SetBase的拷贝构造函数与拷贝赋值运算符被声明为 delete私有理由是避免在基类中使用虚的用户自定义运算符因此拷贝语义完全由派生类自己定义实现——ExternalRedBlackTreeSet正是这样做的见第 5 节。3. 公开类型与私有成员3.1. 公开类型对应文档第 3 节NameDefinitionConstIterator集合的常量迭代器实现对集合的只读遍历Entry树节点中存储的条目类型即SetOrMapImplEntryT, Nil其中Nil是一个空类型Nil.md仅作为占位符当SetOrMapImplEntry用作集合条目时其值部分没有意义就用Nil填充。Entry实际承载了元素keyOrElement与值/占位valueOrNil两部分见 SetOrMapImplEntry.md。关于迭代器类型需要以源码为准做一个澄清原 SDD 文档第 3 节将ConstIterator描述为MapConstIteratorT的别名但 ExternalRedBlackTreeSet.hpp 中实际定义为using ConstIterator SetConstIteratorT;这与基类SetBase中的定义一致SetBase.hpp。SetConstIterator提供operator、operator!、operator、isInRange()、operator*、operator-等操作且其operator*返回元素引用、对越界访问会触发断言失败详见 SetConstIterator.md。该迭代器基于实现类型数组、红黑树等提供不同的构造方式对使用者屏蔽底层差异。3.2. 私有成员变量对应文档第 4 节NameTypePurposeDefault Valuem_implRedBlackTreeSetOrMapImplT, Nil集合的底层实现C 默认初始化 {}组合关系ExternalRedBlackTreeSet本身不存储任何树节点所有逻辑都委托给成员m_impl。RedBlackTreeSetOrMapImplKE, VN是一个可同时用于 set 与 map 的红黑树实现模板RedBlackTreeSetOrMapImpl.hpp其内部由两个外部容器构成Nodes ExternalArrayNode存放树节点数组FreeNodes ExternalStackIndex空闲节点索引栈用于节点的分配与回收。当ExternalRedBlackTreeSet以外部存储接入时实际就是为这两个内部容器提供后备内存。4. 公开构造与析构函数对应文档第 5 节4.1. 零参数构造函数ExternalRedBlackTreeSet()所有成员按默认值初始化。此时容器没有绑定任何后备存储capacity 为 0size 为 0不能执行插入操作insert会因无空闲节点而返回失败。示例ExternalRedBlackTreeSetU32 set;4.2. 提供类型化后备存储的构造函数原文档给出的签名是ExternalRedBlackTreeSet(Entry* entries, FwSizeType capacity)但以当前仓库源码为准实际签名ExternalRedBlackTreeSet.hpp为ExternalRedBlackTreeSet(Node* nodes, //! 树节点数组至少 capacity 个元素 Index* freeNodes, //! 空闲节点索引数组至少 capacity 个元素 FwSizeType capacity)这是因为底层红黑树实现需要两块后备内存一块存放Node结构含父子指针、颜色与条目一块存放Index即FwSizeType类型的空闲节点栈。构造函数体调用setStorage(nodes, freeNodes, capacity)完成绑定。示例using Set ExternalRedBlackTreeSetU32; using Impl Fw::RedBlackTreeSetOrMapImplU32, Fw::Nil; constexpr FwSizeType capacity 10; Impl::Node nodes[capacity]; Impl::Index freeNodes[capacity]; Set set(nodes, freeNodes, capacity);这一用法与单元测试Fw/DataStructures/test/ut/ExternalRedBlackTreeSetTest.cpp中TypedStorageConstructor用例完全一致测试通过友元测试器ExternalRedBlackTreeSetTester取出m_impl验证nodes与freeNodes两块内存确实被底层m_nodes与m_freeNodes使用。4.3. 提供非类型化字节数组后备存储的构造函数ExternalRedBlackTreeSet(ByteArray data, FwSizeType capacity)这是嵌入式场景最常用的方式把一整块字节缓冲区按一定布局切成节点区 空闲栈区。前提条件data必须按照getByteArrayAlignment()返回的对齐要求对齐data必须包含至少getByteArraySize(capacity)个字节。构造函数体内调用setStorage(data, capacity)底层会把缓冲区切分为对齐的两段详见第 7 节。示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 10; constexpr U8 alignment Set::getByteArrayAlignment(); constexpr FwSizeType byteArraySize Set::getByteArraySize(capacity); alignas(alignment) U8 bytes[byteArraySize]; ExternalRedBlackTreeSetU32 set(ByteArray(bytes[0], sizeof bytes), capacity);4.4. 拷贝构造函数ExternalRedBlackTreeSet(const ExternalRedBlackTreeSetT set)直接执行*this set。由于后备存储外部数组指针随m_impl一起被复制拷贝后的集合与原集合共享同一块后备存储——两个对象操作的是同一棵树。使用时务必注意这一点避免双写同一缓冲区造成语义混乱。示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 3; Set::Entry entries[capacity]; // 使用带后备存储的构造函数 Set m1(entries, capacity); // 插入元素 const auto status m1.insert(42); ASSERT_EQ(status, Success::SUCCESS); // 调用拷贝构造函数 Set m2(m1); ASSERT_EQ(m2.getSize(), 1);4.5. 析构函数~ExternalRedBlackTreeSet() override定义为 default。析构时不释放外部后备存储——那块内存由调用方负责生命周期管理这正是外部存储设计的题中之义。5. 公开成员函数详解对应文档第 6 节除静态函数外ExternalRedBlackTreeSet的所有成员函数都是对m_impl的薄封装逐一说明如下。5.1. operator拷贝赋值ExternalRedBlackTreeSetT operator(const ExternalRedBlackTreeSetT set)实现逻辑与源码一致ExternalRedBlackTreeSet.hpp若set ! this则执行m_impl set.m_impl连同后备存储指针一起复制返回*this。示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 3; Set::Entry entries[capacity]; Set m1(entries, capacity); const auto status m1.insert(42); ASSERT_EQ(status, Success::SUCCESS); // 默认构造的集合 Set m2; ASSERT_EQ(m2.getSize(), 0); // 拷贝赋值 m2 m1; ASSERT_EQ(m2.getSize(), 1);5.2. begin / endConstIterator begin() const ConstIterator end() const分别返回m_impl.begin()与m_impl.end()。红黑树版本的begin()会从根节点出发沿左子树一直下行找到最左节点中序遍历的第一个节点end()则把迭代器内部节点索引置为哨兵值Node::NONE。begin 示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 10; Set::Entry entries[capacity]; Set set(entries, capacity); const auto status set.insert(42); ASSERT_EQ(status, Fw::Success::SUCCESS); auto it set.begin(); ASSERT_EQ(*it, 42);end 示例遍历到终点auto iter set.begin(); ASSERT_NE(iter, set.end()); // 非空集合时 begin 不等于 end iter; // 自增越过唯一元素 ASSERT_EQ(iter, set.end()); // 此时到达 end红黑树迭代器的自增逻辑increment值得关注若当前节点有右孩子则跳到右子树的最左节点否则沿父指针上溯直到经过一个左孩子或到达根。这是标准的二叉树中序遍历实现见 RedBlackTreeSetOrMapImpl.hpp 中ConstIterator::increment。5.3. clearvoid clear() override调用m_impl.clear()。底层实现把根置为NONE清空空闲栈然后把所有节点索引按逆序压回空闲栈capacity - i - 1。清空后集合 size 为 0但 capacity 与后备存储保持不变可继续复用。示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 10; Set::Entry entries[capacity]; Set set(entries, capacity); const auto status set.insert(42); ASSERT_EQ(set.getSize(), 1); set.clear(); ASSERT_EQ(set.getSize(), 0);5.4. findSuccess find(const T element) const override实现为Nil nil {}; return m_impl.find(element, nil);——用一个局部Nil占位接收值输出。底层find沿树进行二叉搜索比较keyOrElement entryKey、、三分支命中返回Success::SUCCESS否则返回FAILURE。由于红黑树保证树高为O(log n)查找最坏情况下需要O(log n)步。示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 10; Set::Entry entries[capacity]; Set set(entries, capacity); auto status set.find(42); ASSERT_EQ(status, Success::FAILURE); // 尚未插入 status set.insert(42); ASSERT_EQ(status, Success::SUCCESS); status set.find(42); ASSERT_EQ(status, Success::SUCCESS); // 插入后可找到5.5. getCapacity / getSizeFwSizeType getCapacity() const override // 返回 m_impl.getCapacity() FwSizeType getSize() const override // 返回 m_impl.getSize()底层getCapacity()返回节点数组大小即后备存储容量getSize()则计算capacity - freeNodesSize即已被占用的节点数也就是树中实际元素数并断言freeNodesSize capacity。示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 10; Set::Entry entries[capacity]; Set set(entries, capacity); ASSERT_EQ(set.getCapacity(), capacity); // 容量等于后备数组大小 auto size set.getSize(); ASSERT_EQ(size, 0); // 初始为空 const auto status set.insert(42); ASSERT_EQ(status, Success::SUCCESS); size set.getSize(); ASSERT_EQ(size, 1); // 插入后 size 为 15.6. insertSuccess insert(const T element) override实现为return m_impl.insert(element, Nil())即把值部分填Nil。底层insert的语义RedBlackTreeSetOrMapImpl.hpp先findNode(element, node, direction)查找若元素已存在则返回SUCCESS集合元素唯一不重复插入若不存在则从空闲栈pop一个节点设置元素后调用insertNode将其挂入树中并按红黑树规则重平衡若空闲栈为空容量已满返回FAILURE。示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 10; Set::Entry entries[capacity]; Set set(entries, capacity); auto size set.getSize(); ASSERT_EQ(size, 0); const auto status set.insert(42); ASSERT_EQ(status, Success::SUCCESS); size set.getSize(); ASSERT_EQ(size, 1);5.7. removeSuccess remove(const T element) override实现为Nil nil {}; return m_impl.remove(element, nil);。底层remove先查找节点命中后把节点从树中摘除、将 freed 节点索引压回空闲栈返回SUCCESS元素不存在则返回FAILURE。删除是红黑树最复杂的操作底层removeNode会对删除黑色节点导致黑高度失衡的多种兄弟/侄子形态分别进行旋转与重着色详见第 8 节。示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 10; Set::Entry entries[capacity]; Set set(entries, capacity); const auto status set.insert(42); ASSERT_EQ(status, Success::SUCCESS); // 元素不存在删除失败 status set.remove(0); ASSERT_EQ(status, Success::FAILURE); // 元素存在删除成功 status set.remove(42); ASSERT_EQ(status, Success::SUCCESS); ASSERT_EQ(set.getSize(), 0);提示原文档示例在remove后直接断言缓存的size变量删除前后均为旧值这是文档示例中的笔误实际使用时应像上文一样在删除后重新调用set.getSize()获取最新大小。单元测试ExternalRedBlackTreeSetTest.cpp中的Remove用例则是在remove之后调用set.getSize()验证。5.8. setStorage类型化数据void setStorage(Node* nodes, Index* freeNodes, FwSizeType capacity)直接转发给m_impl.setStorage(nodes, freeNodes, capacity)。底层实现会依次绑定m_nodes节点数组与m_freeNodes空闲栈然后调用clear()把整棵树初始化为空。调用后集合容量立即生效可以在任意时刻为同一个集合对象更换或重新绑定后备存储。示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 10; Set set; // 先零参构造 Set::Entry entries[capacity]; set.setStorage(entries, capacity); // 稍后绑定存储5.9. setStorage非类型化数据void setStorage(ByteArray data, FwSizeType capacity)把单个字节缓冲区按对齐要求切分为两块后备内存调用m_impl.setStorage(data, capacity)调用clear()。底层RedBlackTreeSetOrMapImpl::setStorage(ByteArray, ...)的切分逻辑RedBlackTreeSetOrMapImpl.hpp为节点区大小 Nodes::getByteArraySize(capacity)计算大于等于节点区大小、且对齐到FreeNodes::getByteArrayAlignment()的偏移freeNodesOffset用断言保证freeNodesOffset FreeNodes::getByteArraySize(capacity) data.size即缓冲区足够大把data.bytes[freeNodesOffset .. freeNodesOffset freeNodesSize)作为空闲栈的字节存储。示例using Set ExternalRedBlackTreeSetU32; constexpr FwSizeType capacity 10; constexpr U8 alignment Set::getByteArrayAlignment(); constexpr FwSizeType byteArraySize Set::getByteArraySize(capacity); alignas(alignment) U8 bytes[byteArraySize]; Set set; // 先零参构造 set.setStorage(ByteArray(bytes[0], sizeof bytes), capacity); // 再绑定字节存储单元测试UntypedStorageConstructor用例还验证了绑定字节存储后底层m_nodes的元素指针恰好等于reinterpret_castImpl::Node*(bytes)证明节点区确实从缓冲区起始位置开始。6. 公开静态函数对应文档第 7 节这两个静态函数用于预先计算非类型化后备存储的布局是外部存储容器正确用法的关键工具。6.1. getByteArrayAlignmentstatic constexpr U8 getByteArrayAlignment()返回RedBlackTreeSetOrMapImplT, Nil::getByteArrayAlignment()底层实现为ExternalArrayEntry::getByteArrayAlignment()。即字节缓冲区所需的对齐要求等于Entry树条目类型的对齐要求。6.2. getByteArraySizestatic constexpr FwSizeType getByteArraySize(FwSizeType capacity)返回RedBlackTreeSetOrMapImplT, Nil::getByteArraySize(capacity)底层计算公式为Nodes::getByteArraySize(capacity) FreeNodes::getByteArrayAlignment() FreeNodes::getByteArraySize(capacity)即节点区字节数 空闲栈对齐字节数 空闲栈字节数。由于两者都是constexpr你可以在编译期就得到缓冲区大小并用alignas静态数组声明内存如第 4.3 节示例所示完全避免堆分配。7. 源码级纵深底层红黑树如何工作ExternalRedBlackTreeSet的本质是一个外壳真正承载算法的是RedBlackTreeSetOrMapImplT, Nil。理解它的实现才算真正掌握这个容器RedBlackTreeSetOrMapImpl.hpp。7.1. 节点结构Node包含四个字段m_parent、m_left、m_right均为Index即FwSizeType用常量NONE std::numeric_limitsIndex::max()表示无节点、m_colorColor::BLACK或Color::RED以及条目m_entry。所有节点存放在ExternalArrayNode中通过索引互相链接不使用指针——这使整棵树可以被放到任意对齐的字节缓冲区中序列化/搬移都很方便。7.2. 红黑树不变量注释中明确了红黑树的两个合法性条件红孩子不变量red child invariant不存在红节点有红孩子的情况黑高度不变量black height invariant对叶扩展树 T把每个缺失的孩子替换为黑色叶节点而言从任一节点到叶节点的每条路径经过的黑色节点数相同。满足这两条不变量后树是平衡的find操作为O(log n)。7.3. 插入与重平衡insertNode先把新节点染红再向上检查父为黑无违例结束父为红且祖父存在根据叔父uncle颜色分两条路径——叔父为黑通过旋转rotateSubtree换色修复源码注释中用K1..K4的键序K1 K2 K3 K4图示了之字形zig-zag与直线形zig-zig两种旋转形态叔父为红把父、叔、祖父换色将红孩子违例向上推到祖父循环继续。7.4. 删除与重平衡removeNode结合removeBlackLeafNode处理最棘手的删除黑叶节点导致黑高度失衡问题。重平衡循环根据**兄弟sibling、近侄closeNephew、远侄distantNephew**的颜色组合执行多次旋转与重着色源码中附有大量 ASCII 树形图逐阶段说明黑高度的变化。这些实现细节从单元测试Fw/DataStructures/test/ut/RedBlackTreeSetOrMapImplTest.cpp及test/ut/STest/下基于 STest 规则/场景的测试得到系统性验证。7.5. 查找与定位findNode维护parent/child/direction三个游标沿树下行命中返回SUCCESS未命中时node返回应插入位置的父节点direction返回应插入的方向左/右。insert与remove都复用它保证插入/删除定位与查找使用同一套比较逻辑、、。8. 外部存储 vs 内部存储如何选择Fw/DataStructures同时提供红黑树集合的两个版本维度ExternalRedBlackTreeSetTRedBlackTreeSetT, C存储位置外部调用方提供 Node 数组 Index 数组或字节缓冲区内部类内嵌Entry[C]成员容量来源运行时构造函数/setStorage参数编译期模板参数C静态断言C 0堆分配无无内存布局控制完全由调用方决定可放静态区、共享内存等随对象实例所在存储位置从源码结构看RedBlackTreeSet.md 第 4 节内部存储版本RedBlackTreeSetT, C的组合方式是成员m_extSet一个ExternalRedBlackTreeSetT 成员m_entriesEntry[C]数组构造函数用ExternalRedBlackTreeSetT(m_entries, C)初始化。也就是说内部存储版本只是外部存储版本的一个便捷封装——ExternalRedBlackTreeSet才是红黑树集合的真正核心实现。因此实际选型建议需要把集合放进全局静态内存、共享内存或特定对齐的 DMA 缓冲区或希望容器对象与数据内存分离例如容器作为组件成员、数据内存单独静态分配时用ExternalRedBlackTreeSet希望最简用法、把容量固化在类型里编译期可检查、可优化时用RedBlackTreeSetT, C元素数量规模很小且对查找性能不敏感时可以退而选择数组实现ArraySet/ExternalArraySet它们占用更少内存且遍历更缓存友好。9. 测试与验证仓库为ExternalRedBlackTreeSet提供了完整的单元测试位于Fw/DataStructures/test/ut/ExternalRedBlackTreeSetTest.cpp覆盖ZeroArgConstructor零参构造后getCapacity() 0、getSize() 0TypedStorageConstructor节点数组与空闲栈数组被底层正确引用UntypedStorageConstructor字节缓冲区被切分为节点区与空闲栈区且对齐正确CopyConstructor、CopyAssignment拷贝后 size 正确Insert、Remove、Find、Clear等操作语义此外通过 STest 规则/场景框架test/ut/STest/目录对底层RedBlackTreeSetOrMapImpl进行随机化压力测试验证红黑树不变量在大量随机插入/删除后始终成立。单元测试中还用到友元测试器friend class ExternalRedBlackTreeSetTester得以直接访问私有成员m_impl断言内部状态——这是 F´ 测试基础设施STest配合友元类进行白盒验证的典型模式。10. 小结ExternalRedBlackTreeSetT是 F´ 框架为嵌入式飞行软件准备的零堆分配、容量外部可控的红黑树集合接口层继承SetBaseT提供insert/remove/find/clear/begin/end/getSize/getCapacity等标准集合操作元素唯一最坏O(log n)查找存储层所有树节点放入调用方提供的后备内存类型化双数组或对齐字节缓冲区并通过getByteArrayAlignment/getByteArraySize在编译期计算布局算法层底层RedBlackTreeSetOrMapImpl以索引链接 红黑节点着色实现完整插入/删除重平衡配套 STest 随机测试保障不变量。无论是作为RedBlackTreeSetT, C的内部引擎还是直接用于需要精确控制内存布局的组件场景它都是 F´ 数据容器家族中平衡性能、确定性、内存可控三要素的代表实现。相关参考组件文档目录、头文件实现、底层实现、单元测试。【免费下载链接】fprimeF´ - A flight software and embedded systems framework项目地址: https://gitcode.com/GitHub_Trending/fpr/fprime创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考