[SLOF] [PATCH slof] fdt: Avoid recursion when traversing tree

Segher Boessenkool segher at kernel.crashing.org
Fri Jul 17 10:54:56 AEST 2020

On Fri, Jul 17, 2020 at 10:45:58AM +1000, Alexey Kardashevskiy wrote:
> > You can code any of the tree walks without any recursion, using just
> > O(1) extra memory (just keep track of the previous node visited, for
> > example)
> for O(1) we need to keep a parent in the current node (which we do). I
> wonder now if SLOF does O(1) walks anywhere.

Before the FDT stuff the only (full) tree walks were done via the client
interface, and then all the traversion logic is done there.  In OF you
typically open a node by (partial) path name, unit addresses, etc.; you
are never interested in a whole (sub-)tree, as far as I can see.  Maybe
there is some case, but it then escapes me.


More information about the SLOF mailing list