Creazione di una struttura dei dati ad albero (deve essere nativa) in Perl per rappresentare un albero di chiamate che si trova in un file esterno
https://stackoverflow.com/questions/4891453
-
28-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ecco un esempio del file.
powrup.asm POWER_UP
......EXTERNAL_RAM_ADDRESSING_CHECK powrup.asm:461
......EXRAM powrup.asm:490
......INRAM powrup.asm:540
......OUTPUT_TEST powrup.asm:573
............AD_READ douttst.asm:276
............AD_READ douttst.asm:366
......OUTPUT2_TEST powrup.asm:584
............AD_READ douttst2.asm:253
............AD_READ douttst2.asm:342
......OUTPUT3_TEST powrup.asm:599
............AD_READ douttst3.asm:307
............AD_READ douttst3.asm:398
......INPUT_TEST powrup.asm:614
......PROGRAM_PINS2_INPUT powrup.asm:629
......ARINC_TEST powrup.asm:633
............ARINC_LEVEL_TEST artest.asm:178
..................AD_READ arltst.asm:204
..................AD_READ arltst.asm:250
..................AD_READ arltst.asm:300
..................AD_READ arltst.asm:346
..................AD_READ arltst.asm:396
..................AD_READ arltst.asm:442
............ARINC_READ artest.asm:209
............ARINC_WORD_TXRX_TEST artest.asm:221
..................ARINC_OUT artxrx.asm:207
..................ARINC_READ artxrx.asm:221
............ARINC_READ artest.asm:251
............ARINC_WORD_TXRX_TEST artest.asm:263
..................ARINC_OUT artxrx.asm:207
..................ARINC_READ artxrx.asm:221
......PROGRAM_PINS2_INPUT powrup.asm:640
......PROGRAM_PIN_TEST powrup.asm:642
......PT_RCVR_BITE powrup.asm:645
............AD_READ10 ptbite.asm:225
..................AD_READ adread10.asm:141
............AD_READ10 ptbite.asm:308
..................AD_READ adread10.asm:141
............AD_READ10 ptbite.asm:384
..................AD_READ adread10.asm:141
............AD_READ10 ptbite.asm:467
..................AD_READ adread10.asm:141
............AD_READ10 ptbite.asm:542
..................AD_READ adread10.asm:141
............AD_READ10 ptbite.asm:622
..................AD_READ adread10.asm:141
......PROGRAM_PINS2_INPUT powrup.asm:653
......EXEC_INIT powrup.asm:663
Il ... rappresenta la profondità della chiamata. Il nome del file dopo la riga indica il nome del file e il numero di riga da cui è stato chiamato nel genitore. Posso analizzare il file. Quello che sto cercando di fare una volta analizzato il file viene inserito i dati in un albero n-ary. Sto facendo un'analisi dell'accoppiamento e dell'accoppiamento di controllo dei dati e ho già raccolto tutti i dati SET/USA per tutte le variabili nella build. Ora devo essere in grado di attraversare l'albero e in base alla profondità di capire se esistono situazioni di utilizzo prima di utilizzo o set ma non utilizzate. Pensavo che un attraversamento di alberi avrebbe avuto più senso.
Ecco un esempio dei dati raccolti:
$hash_DB{'alt_deviation_evaluation.asm->ALT_STATUS'} = [
'alt_deviation_evaluation.asm',
'ALT_STATUS',
'1.1',
1,
"",
"",
"135,188,202,242",
"130,144"
];
'alt_deviation_evaluation.asm->ALT_STATUS' is the file name and variable name.
'alt_deviation_evaluation.asm', File name
'ALT_STATUS', Variable name
'1.1', versions of file
1, indicates has been processed
"", not used (maybe in future)
"", not used (maybe in future)
"135,188,202,242", variable Set line numbers for this fileVariable
"130,144" Variable Use line number for this file/Variable
Ho anche un array con tutti i nomi delle variabili. Esempio abbreviato:
our @vars_list = (
'A429_TX_BUFFER_LENGTH',
'A429_TX_INPUT_BUFFER',
'A429_TX_INT_MASK',
'ABS_ALT_DIFF',
'ACTUAL_ALT',
'ADDRESS_FAIL',
'AD_CONV_FAIL',
'AD_CONV_SIGNAL',
'AD_DATA',
'AD_FAIL',
'AD_STATUS',
'AIR_MODE',
'AIR_MODE_COUNT',
'AIR_MODE_LAST',
'ALPHA_COR_SSM',
'ALPHA_EC_SSM',
'ALPHA_GRAD_SSM',
'ALPHA_LE_SSM',
'ALPHA_LG_SSM',
'ALPHA_MAX_MC_SSM'
};
Il mio più grande ostacolo è capire le strutture di dati e gli algoritmi adeguati per svolgere questo compito.
Ho pensato che una prima ricerca di profondità di un albero n-ary mi avrebbe dato quello che voglio.
Ecco la mia soluzione finale:
#!/usr/local/bin/perl
# !/usr/bin/perl
use Data::Dumper; #!!!
sub Create_Tree;
sub Treverse;
#for my $node (@TREE) {
# print_node($node[0], 1);
#}
#Main
our @TREE;
Create_Tree("call_tree.small_01.txt");
my $str = Dumper @TREE;
$str =~ s/^(\s+)/' 'x(length($1)>>2)/meg;
#print "\n\n=======================================\n$str"; #!!!
#print "\n\n=======================================\n" . (Dumper @TREE); #!!!
#print "Arr = @TREE, SZ = $#TREE\n\n";
Treverse(\@TREE,1);
sub Create_Tree
{
my ($call_tree) = @_;
my @stack;
my ($old_depth, $p_arr) = (0, \@TREE);
open(IN, "< $call_tree" ) or die "Can not open '$call_tree' for input.\n";
for (<IN>)
{
if (m/^(\s*)(\S+)\s*=>\s*(\S+):(\d+)/ or m/^(\s*)(\S+)()()/)
{
my ($depth, $callee_fn, $caller_fn, $ln, $diff) = ($1, $2, $3, $4, 0);
$depth = int(length($depth) / 6);
$diff = $depth - $old_depth;
if ($diff == 1)
{
push @stack, $p_arr;
$p_arr = \@{$$p_arr[$#{$p_arr}]{children}};
}
elsif ($diff < 0)
{
$p_arr = pop @stack while ++$diff <= 0;
}
elsif ($diff > 1)
{
die "Incorrectly formated call tree:\n $_\n";
}
push @$p_arr, {
caller => $caller_fn,
called_by => $callee_fn,
at_line => $ln
};
$old_depth = $depth;
}
}
close IN;
}
exit;
L'output sembra così:
......file1
............file1 101:A
..................XXX.AA 102:AA
........................XXX.AAA 103:AAA
........................XXX.AAB 104:AAB
..............................XXX.AABA 105:AABA
..................XXX.AB 106:AB
........................XXX.ABA 107:ABA
............file1 108:B
..................XXX.BA 109:BA
........................XXX.BAA 110:BAA
........................XXX.BAB 111:BAB
Da questo file call_tree.txt:
file1
A => file1:101
AA => XXX.AA:102
AAA => XXX.AAA:103
AAB => XXX.AAB:104
AABA => XXX.AABA:105
AB => XXX.AB:106
ABA => XXX.ABA:107
B => file1:108
BA => XXX.BA:109
BAA => XXX.BAA:110
BAB => XXX.BAB:111
Usando questa subroutine:
sub Treverse
{
my ($p_arr, $level) = @_;
for (my $ind=0; $ind<=$#{$p_arr}; $ind++)
{
print "." x ($level*6);
if ($$p_arr[$ind]{'caller'} ne "") {print "$$p_arr[$ind]{'caller'}" . " " x 4;}
if ($$p_arr[$ind]{'at_line'} ne "") {print "$$p_arr[$ind]{'at_line' }" . ":";}
if ($$p_arr[$ind]{'called_by'} ne "") {print "$$p_arr[$ind]{'called_by'}" . "\n";}
Treverse(\@{$$p_arr[$ind]{children}}, $level +1) if defined $$p_arr[$ind]{children};
}
}
# END of Treverse
Soluzione
Per le strutture di dati, uno dei maggiori poteri di Perl è la nidificazione arbitraria delle strutture. Pertanto, piuttosto che avere una singola variabile che contiene tutti i dati per tutte le note che puoi avere "subnodi" all'interno dei loro genitori.
Diciamo che hai avuto un hash per una voce:
%node1 = ( name => 'ALPHA_MAX_MC_SSM', file => 'arltst.asm', line => 42 );
Il codice sopra creerà un bel nodo semplicemente per archiviare i dati. Ma puoi effettivamente archiviare più dati all'interno di quello stesso. Un "nodo figlio":
%node2 = (
name => 'ACTUAL_ALT',
file => 'foo.asm',
line => 2001
);
$node1{children}[0] = \%node2;
Quindi hai un nodo figlio ('figli') nel primo nodo che è una matrice di tutti i suoi bambini. Puoi accedere alla data nel bambino direttamente come:
$node1{'children'}[0]{'name'};
Per capire questo e come funziona, è necessario leggere sui riferimenti perl e sui tipi di dati Perl. Ci vuole un po 'come un nuovo programmatore Perl per ottenere i concetti, ma una volta ottenuto lo puoi fare programmi rapidi incredibilmente potenti che si aggrappano a dati gerarchici complessi ed elaborarli.
Altri suggerimenti
Ecco come stampare la struttura che hai costruito usando la risposta di Wes.
Una volta elaborati i dati, finisci con qualcosa del genere:
my @nodes = (
{ name => 'ARINC_TEST', file => 'powrup.asm', line => 633,
children => [
{ name => 'ARINC_LEVEL_TEST', file => 'artest.asm', line => 178,
children => [
{ name => 'AD_READ', file => 'arltst.asm', line => 204 },
{ name => 'AD_READ', file => 'arltst.asm', line => 250 },
{ name => 'AD_READ', file => 'arltst.asm', line => 300 },
{ name => 'AD_READ', file => 'arltst.asm', line => 346 },
{ name => 'AD_READ', file => 'arltst.asm', line => 396 },
{ name => 'AD_READ', file => 'arltst.asm', line => 442 },
],
},
{ name => 'ARINC_READ', file => 'artest.asm', line => 209,
children => [],
},
{ name => 'ARINC_WORD_TXRX_TEST', file => 'artest.asm', line => 221,
children => [
{ name => 'ARINC_OUT', file => 'artxrx.asm', line => 207 },
{ name => 'ARINC_READ', file => 'artxrx.asm', line => 221 },
],
}
]
}
);
La struttura è ricorsiva e children punto chiave per ArrayRef di un altro hash. Per stampare questo, hai bisogno di codice ricorsivo:
for my $node (@nodes) {
print_node($node, 1);
}
sub print_node {
my ($node, $level) = @_;
# the node itself
print "." x ($level*6)
, $node->{name}, " " x 4
, $node->{file}, ":"
, $node->{line}, "\n";
# recurse for children
if(defined $node->{children}) {
for my $child (@{ $node->{children} }) {
print_node($child, $level + 1);
}
}
}
Per i dati di cui sopra, il codice output
......ARINC_TEST powrup.asm:633
............ARINC_LEVEL_TEST artest.asm:178
..................AD_READ arltst.asm:204
..................AD_READ arltst.asm:250
..................AD_READ arltst.asm:300
..................AD_READ arltst.asm:346
..................AD_READ arltst.asm:396
..................AD_READ arltst.asm:442
............ARINC_READ artest.asm:209
............ARINC_WORD_TXRX_TEST artest.asm:221
..................ARINC_OUT artxrx.asm:207
..................ARINC_READ artxrx.asm:221
