| 2019 |
mateusz.vi |
1 |
Below is pseudo code for a non-recursive tree.
|
|
|
2 |
pdTree v1.01 uses this algorithm slighty modified to properly mimic
|
|
|
3 |
the display behavior of MS and PC DOS versions of tree, but the actual
|
|
|
4 |
directory tree traversal is the same.
|
|
|
5 |
|
|
|
6 |
It has the properties that there is no function level recursion,
|
|
|
7 |
hence the only stack usage is to pass parameters to 1 level deep functions.
|
|
|
8 |
It stores the handle/DTA for each subdirectory as it proceeds deeper into
|
|
|
9 |
the tree, so as it returns it can continue from where it left off, but
|
|
|
10 |
does not store the complete subdirectory listing of each subdirectory
|
|
|
11 |
along the way. This means a given directory can have as many subdirectories
|
|
|
12 |
as it wants, and this will handle them. However this comes at some cost
|
|
|
13 |
of speed, as each directory is scanned twice (once for count of subdirectories,
|
|
|
14 |
and once to display each subdirectory) and the start/stop of the second
|
|
|
15 |
scanning will probably not be using sequential reads.
|
|
|
16 |
[Note: this implementation is limited to 2^31 subdirectories in a given dir.]
|
|
|
17 |
This can handle as many subdirectories deep as their is memory to store the
|
|
|
18 |
subdirinfo structures. Each structure is potentially MAXPATH+1 + sizeof(long) +
|
|
|
19 |
sizeof(HANDLE). (A handle is probably sizeof(void ptr) or sizeof(DTA).)
|
|
|
20 |
The actual implementation has a depth limit defined by maximum path length,
|
|
|
21 |
which is about 260 for DOS.
|
|
|
22 |
This can handle any number of files in a directory. If files are displayed,
|
|
|
23 |
when each subdirectory is 1st entered (thus there is only a single additional
|
|
|
24 |
search of the directory for showing files) the directory is searched and all
|
|
|
25 |
files matching the search attribute criteria are shown.
|
|
|
26 |
Note: a faster approach would be to add all the subdirectories in a given
|
|
|
27 |
directory when we 1st process it, then pop the top one off, display it and
|
|
|
28 |
possibly its files, repeat [scan for its subdirectories, adding any we find].
|
|
|
29 |
However, this limits the recursion to how many subdirectory names can be
|
|
|
30 |
stored in memory (a directory with many subdirectories will take up a lot
|
|
|
31 |
of space reducing maximum depth). This is what the current FreeDOS tree
|
|
|
32 |
(v 3.2-3.6) does, except it has hard coded maximum subdirectory count and
|
|
|
33 |
maximum depth.
|
|
|
34 |
|
|
|
35 |
|
|
|
36 |
struct subdirinfo { string currentpath; long subdircnt; HANDLE findnexthnd; }
|
|
|
37 |
|
|
|
38 |
subdirinfo * newsubdirinfo(string currentpath)
|
|
|
39 |
{
|
|
|
40 |
subdirinfo *temp = new subdirinfo;
|
|
|
41 |
temp->currentpath = currentpath;
|
|
|
42 |
temp->subdircnt = getsubdircnt(currentpath);
|
|
|
43 |
temp->findnexthnd = NULL;
|
|
|
44 |
|
|
|
45 |
return temp;
|
|
|
46 |
}
|
|
|
47 |
|
|
|
48 |
nonrecurse(string initialpath, bool showfiles)
|
|
|
49 |
{
|
|
|
50 |
stack s = empty;
|
|
|
51 |
|
|
|
52 |
subdirinfo initialsdi = newsubdirinfo(initialpath);
|
|
|
53 |
s.push(initialsdi);
|
|
|
54 |
|
|
|
55 |
do
|
|
|
56 |
{
|
|
|
57 |
subdirinfo sdi = s.pop();
|
|
|
58 |
|
|
|
59 |
if (sdi.findnexthnd == NULL) // findfirst not called yet
|
|
|
60 |
{
|
|
|
61 |
// 1st time this subdirectory processed, so display its name & possibly files
|
|
|
62 |
showpath(sdi.currentpath);
|
|
|
63 |
if (showfiles) displayfiles(sdi.currentpath);
|
|
|
64 |
}
|
|
|
65 |
|
|
|
66 |
if (sdi.subdircnt > 0)
|
|
|
67 |
{
|
|
|
68 |
sdi.subdircnt--;
|
|
|
69 |
|
|
|
70 |
string newcurrentpath;
|
|
|
71 |
if (sdi.findnexthnd == NULL)
|
|
|
72 |
sdi.findnexthnd = findfirstsubdir(sdi.currentpath, newcurrentpath);
|
|
|
73 |
else
|
|
|
74 |
newcurrentpath = findnextsubdir(sdi.findnexthnd);
|
|
|
75 |
|
|
|
76 |
s.push(sdi);
|
|
|
77 |
|
|
|
78 |
subdirinfo sdi = newsubdirinfo(newcurrentpath);
|
|
|
79 |
s.push(sdi);
|
|
|
80 |
}
|
|
|
81 |
else
|
|
|
82 |
{
|
|
|
83 |
findclose(sdi.findnexthnd);
|
|
|
84 |
free sdi;
|
|
|
85 |
}
|
|
|
86 |
} while (! s.empty())
|
|
|
87 |
}
|
|
|
88 |
|