libfdt: Add APIs around FdtNodeMut::delete_and_next_node()
Following APIs are added to iterate and filter FDT nodes:
- FdtNodeMut::delete_and_next_node()
- FdtNodeMut::next_node()
Just FYI, previously FdtNodeMut::*_next_subnode() were added for the
same purpose, but they couldn't be used for traveling the whole tree.
Borrow checker didn't like tree travesal algorithms for both BFS nor DFS
because they expect to keep multiple FdtNodeMut.
Bug: 317830919
Test: atest liblibfdt.integration_test
Change-Id: I230bee75ab15bd7349f7e03cf097f209a5690766
diff --git a/libs/libfdt/src/lib.rs b/libs/libfdt/src/lib.rs
index 7eb08b2..14f0f37 100644
--- a/libs/libfdt/src/lib.rs
+++ b/libs/libfdt/src/lib.rs
@@ -811,6 +811,41 @@
Ok(next_offset.map(|offset| Self { fdt: self.fdt, offset }))
}
+ fn next_node_offset(&self, depth: usize) -> Result<Option<(c_int, usize)>> {
+ let mut next_depth: c_int = depth.try_into().or(Err(FdtError::BadValue))?;
+ // SAFETY: Accesses (read-only) are constrained to the DT totalsize.
+ let ret = unsafe {
+ libfdt_bindgen::fdt_next_node(self.fdt.as_ptr(), self.offset, &mut next_depth)
+ };
+ let Ok(next_depth) = usize::try_from(next_depth) else {
+ return Ok(None);
+ };
+ Ok(fdt_err_or_option(ret)?.map(|offset| (offset, next_depth)))
+ }
+
+ /// Returns the next node
+ pub fn next_node(self, depth: usize) -> Result<Option<(Self, usize)>> {
+ Ok(self
+ .next_node_offset(depth)?
+ .map(|(offset, next_depth)| (FdtNodeMut { fdt: self.fdt, offset }, next_depth)))
+ }
+
+ /// Deletes this and returns the next node
+ pub fn delete_and_next_node(mut self, depth: usize) -> Result<Option<(Self, usize)>> {
+ // Skip all would-be-removed descendants.
+ let mut iter = self.next_node_offset(depth)?;
+ while let Some((descendant_offset, descendant_depth)) = iter {
+ if descendant_depth <= depth {
+ break;
+ }
+ let descendant = FdtNodeMut { fdt: self.fdt, offset: descendant_offset };
+ iter = descendant.next_node_offset(descendant_depth)?;
+ }
+ // SAFETY: This consumes self, so invalid node wouldn't be used any further
+ unsafe { self.nop_self()? };
+ Ok(iter.map(|(offset, next_depth)| (FdtNodeMut { fdt: self.fdt, offset }, next_depth)))
+ }
+
fn parent(&'a self) -> Result<FdtNode<'a>> {
// SAFETY: Accesses (read-only) are constrained to the DT totalsize.
let ret = unsafe { libfdt_bindgen::fdt_parent_offset(self.fdt.as_ptr(), self.offset) };
diff --git a/libs/libfdt/tests/api_test.rs b/libs/libfdt/tests/api_test.rs
index e68557f..e0c10b8 100644
--- a/libs/libfdt/tests/api_test.rs
+++ b/libs/libfdt/tests/api_test.rs
@@ -399,3 +399,39 @@
assert_eq!(expected_names, subnode_names);
}
+
+#[test]
+fn node_mut_delete_and_next_node() {
+ let mut data = fs::read(TEST_TREE_PHANDLE_PATH).unwrap();
+ let fdt = Fdt::from_mut_slice(&mut data).unwrap();
+
+ let expected_nodes = vec![
+ (Ok(cstr!("node_b")), 1),
+ (Ok(cstr!("node_c")), 1),
+ (Ok(cstr!("node_z")), 1),
+ (Ok(cstr!("node_za")), 2),
+ (Ok(cstr!("node_zb")), 2),
+ (Ok(cstr!("__symbols__")), 1),
+ ];
+
+ let mut expected_nodes_iter = expected_nodes.iter();
+ let mut iter = fdt.root_mut().unwrap().next_node(0).unwrap();
+ while let Some((node, depth)) = iter {
+ let node_name = node.as_node().name();
+ if node_name == Ok(cstr!("node_a")) || node_name == Ok(cstr!("node_zz")) {
+ iter = node.delete_and_next_node(depth).unwrap();
+ } else {
+ // Note: Checking name here is easier than collecting names and assert_eq!(),
+ // because we can't keep name references while iterating with FdtNodeMut.
+ let expected_node = expected_nodes_iter.next();
+ assert_eq!(expected_node, Some(&(node_name, depth)));
+ iter = node.next_node(depth).unwrap();
+ }
+ }
+ assert_eq!(None, expected_nodes_iter.next());
+
+ let root = fdt.root().unwrap();
+ let all_descendants: Vec<_> =
+ root.descendants().map(|(node, depth)| (node.name(), depth)).collect();
+ assert_eq!(expected_nodes, all_descendants);
+}