libufdt: device tree overlay via unflattening FDT

The original version of libdtoverlay is slow in searching for
particular nodes and adding subnodes/properties due to the operations
on flattened device tree (FDT).

`libufdt` builds a real tree structure (named ufdt -- unflattned
device tree) from FDT. In the real tree, we can perform certain
operations (e.g., merge 2 subtrees, search for a node by path) in
almost optimal time complexity with acceptable additional memory usage.

With libufdt, we improve the merging of two dtb files from O(N^2) to
O(N), where N is the number of nodes in the tree.

Bug: 30800619
Test: run test scripts (see libufdt/tests/README)
Test: manually ported libufdt into a bootloader,
      checked it can merge a base dtb and a dtbo to generate a final dtb
      to boot the device
Change-Id: I6a282cc99129d5280ecbf40852723f83735fa523

1 files changed, 7 insertions, 0 deletions

diff --git a/tests/testdata/overlay_2_layers.add_dts b/tests/testdata/overlay_2_layers.add_dts
new file mode 100644
index 0000000..952a462
--- /dev/null
+++ b/tests/testdata/overlay_2_layers.add_dts
@@ -0,0 +1,7 @@
+&a {
+  g = "g";
+  d {
+    f = "f";
+  };
+};
+