ЭЛЕКТРОННАЯ БИБЛИОТЕКА КОАПП |
Сборники Художественной, Технической, Справочной, Английской, Нормативной, Исторической, и др. литературы. |
5.16. Program: dutreeThe dutree program, shown in Example 5.3, turns the output of du. % du pcb into sorted, indented output:
The arguments you give dutree are passed through to du. That way you could call dutree in any of these ways, or maybe more if your du supports other options. % dutree % dutree /usr % dutree -a % dutree -a /bin The
The This program is inherently recursive because the filesystem is recursive. However, its data structure is not recursive; at least, not the way a circular linked list is. Each value is an array of further keys to process. The recursion resides in the processing, not in the storage. Example 5.3: dutree#!/usr/bin/perl -w # dutree - print sorted indented rendition of du output use strict; my %Dirsize; my %Kids; getdots(my $topdir = input()); output($topdir); # run du, read in input, save sizes and kids # return last directory (file?) read sub input { my($size, $name, $parent); @ARGV = ("du @ARGV |"); # prep the arguments while (<>) { # magic open is our friend ($size, $name) = split; $Dirsize{$name} = $size; ($parent = $name) =~ s#/[^/]+$##; # dirname push @{ $Kids{$parent} }, $name unless eof; } return $name; } # figure out how much is taken up in each directory # that isn't stored in subdirectories. add a new # fake kid called "." containing that much. sub getdots { my $root = $_[0]; my($size, $cursize); $size = $cursize = $Dirsize{$root}; if ($Kids{$root}) { for my $kid (@{ $Kids{$root} }) { $cursize -= $Dirsize{$kid}; getdots($kid); } } if ($size != $cursize) { my $dot = "$root/."; $Dirsize{$dot} = $cursize; push @{ $Kids{$root} }, $dot; } } # recursively output everything, # passing padding and number width in as well # on recursive calls sub output { my($root, $prefix, $width) = (shift, shift || '', shift || 0); my $path; ($path = $root) =~ s#.*/##; # basename my $size = $Dirsize{$root}; my $line = sprintf("%${width}d %s", $size, $path); print $prefix, $line, "\n"; for ($prefix .= $line) { # build up more output s/\d /| /; s/[^|]/ /g; } if ($Kids{$root}) { # not a bachelor node my @Kids = @{ $Kids{$root} }; @Kids = sort { $Dirsize{$b} <=> $Dirsize{$a} } @Kids; $Dirsize{$Kids[0]} =~ /(\d+)/; my $width = length $1; for my $kid (@Kids) { output($kid, $prefix, $width) } } } Before Perl supported hashes of arrays directly, Herculean efforts were required to emulate these higher order constructs. Some folks used repeated calls to Example 5.4 is a version of dutree from those days of Perl arcana. Because we didn't have proper array references, we had to usurp the Perl symbol table itself. This program created variables on the fly with bizarre names. Can you find which hash this program is using? The When you assign something like If that isn't interesting enough, consider how the Example 5.4: dutree-orig#!/usr/bin/perl # dutree_orig: the old version pre-perl5 (early 90s) @lines = `du @ARGV`; chop(@lines); &input($top = pop @lines); &output($top); exit; sub input { local($root, *kid, $him) = @_[0,0]; while (@lines && &childof($root, $lines[$#lines])) { &input($him = pop(@lines)); push(@kid, $him); } if (@kid) { local($mysize) = ($root =~ /^(\d+)/); for (@kid) { $mysize -= (/^(\d+)/)[0]; } push(@kid, "$mysize .") if $size != $mysize; } @kid = &sizesort(*kid); } sub output { local($root, *kid, $prefix) = @_[0,0,1]; local($size, $path) = split(' ', $root); $path =~ s!.*/!!; $line = sprintf("%${width}d %s", $size, $path); print $prefix, $line, "\n"; $prefix .= $line; $prefix =~ s/\d /| /; $prefix =~ s/[^|]/ /g; local($width) = $kid[0] =~ /(\d+)/ && length("$1"); for (@kid) { &output($_, $prefix); }; } sub sizesort { local(*list, @index) = shift; sub bynum { $index[$b] <=> $index[$a]; } for (@list) { push(@index, /(\d+)/); } @list[sort bynum 0..$#list]; } sub childof { local(@pair) = @_; for (@pair) { s/^\d+\s+//g; s/$/\//; } index($pair[1], $pair[0]) >= 0; } The answer to the question posed above, "Which hash is the old dutree using?" is |