Passage through the first directory: is this possible with O (log n) memory?

Question

I am trying to create an iterator that crawls the width of all files and folders inside a specific folder. I already did this with a depth transition that returns, for example:

\A \A\1 \A\1\x \A\1\y \A\2 \B \B\1 

and etc.

Now I'm trying to create a program that will instead return the results in width: (or level by level)

 \A \B \A\1 \A\2 \B\1 \A\1\x \A\1\y 

for the same hierarchy. However, I came across a stumbling block: if I want this to happen in the correct order (and, in particular, not in the reverse order), I cannot find a way to complete this action without ultimately requiring O (n) memory, where n is the number of files / folders on the disk, because it seems to me that in the end I will need to save the entire hierarchy of disks in memory at some point, while for DFS I can completely ignore all the records that I listed previously at the same level in the hierarchy.

So my question is: is there a more than linear way to use memory to move around a folder?

Answer 1

If your platform supports the concept of inode number , you can save one number for each directory by specifying the largest inode number you visited for that particular directory. If you access inodes in numerical order, tracking one record will be good enough to find out where the next record is.

This is a small gain, since you still need to maintain an inode number for each individual directory in the system, but you will not need to worry about the contents of the directories.

Of course, bearing in mind that any bypass mechanism is subject to terrible conditions of the race, you will need to have some level of confidence that the file system is at rest or your code is resistant to directories / files that are deleted, created, moved, etc., while your code is already running.