Baum wird jetzt aufgebaut

4 files changed, 226 insertions, 75 deletions

diff --git a/gpggraph.lpi b/gpggraph.lpi
index 2cce007..48c32fe 100644
--- a/gpggraph.lpi
+++ b/gpggraph.lpi
@@ -30,11 +30,15 @@
         <FormatVersion Value="1"/>
       </local>
     </RunParams>
-    <Units Count="1">
+    <Units Count="2">
       <Unit0>
         <Filename Value="gpggraph.lpr"/>
         <IsPartOfProject Value="True"/>
       </Unit0>
+      <Unit1>
+        <Filename Value="graphunit.pas"/>
+        <IsPartOfProject Value="True"/>
+      </Unit1>
     </Units>
   </ProjectOptions>
   <CompilerOptions>
diff --git a/gpggraph.lpr b/gpggraph.lpr
index e2a0ba7..25e622e 100644
--- a/gpggraph.lpr
+++ b/gpggraph.lpr
@@ -3,38 +3,81 @@ program gpggraph;
 {$R *.res}
 
 uses
-  mystringlistunit;
+  mystringlistunit, classes, sysutils, graphunit;
+
+const
+  gpgCommand = 'gpg --no-auto-check-trustdb --fast-list-mode --fixed-list-mode';
 
 var
-  lKeys,kKeys: tMyStringList;
+  lKeys,kKeys:   tMyStringList;
+  baum:          tList;
+  wurzel,spitze: int64;
+  i:             longint;
+  cK:            tKnoten;
 
 begin
   lKeys:=tMyStringList.create;
   kKeys:=tMyStringList.create;
 
-  lKeys.loadFromPipe('gpg --list-keys --no-auto-check-trustdb --fast-list-mode --fixed-list-mode');
+  lKeys.loadFromPipe(gpgCommand+' --list-keys');
   lKeys.grep('^pub');
-  lKeys.replace('^\S+\s+[^ /]+/([0-9A-F]{8}) .*$','$1');
-  kKeys.loadFromPipe('gpg --homedir /var/cache/kernelKeys/.gnupg --list-keys --no-auto-check-trustdb --fast-list-mode --fixed-list-mode');
+  lKeys.replace('^\S+\s+[^ /]+/([0-9A-F]{8}) .*$','0x$1');
+  kKeys.loadFromPipe(gpgCommand+' --list-keys --homedir /var/cache/kernelKeys/.gnupg');
   kKeys.grep('^pub');
-  kKeys.replace('^\S+\s+[^ /]+/([0-9A-F]{8}) .*$','$1');
-
-//  kSigs.loadFromPipe('gpg --homedir /var/cache/kernelKeys/.gnupg --list-sigs --no-auto-check-trustdb --fast-list-mode --fixed-list-mode');
-//  kSigs.grep('^(pub|sig)');
+  kKeys.replace('^\S+\s+[^ /]+/([0-9A-F]{8}) .*$','0x$1');
 
   lKeys.sort;
   kKeys.sort;
   lKeys.uniq('-');
   kKeys.uniq('-');
 
-  writeln(lKeys.count,' ',length(lKeys.text));
-  writeln(kKeys.count,' ',length(kKeys.text));
+  writeln(inttostr(lKeys.count)+' lokale Schlüssel');
+  writeln(inttostr(kKeys.count)+' Kernel-Schlüssel');
+
+  lKeys.append(kKeys);
+  kKeys.clear;
 
-  kKeys.append(lKeys);
+  lKeys.sort;
+  lKeys.uniq('d');
+
+  lKeys.grep('^0x(CAFAA3E1|00411886|76E21CBB|65D0FD58)$',true);
+
+  kKeys.loadFromPipe(gpgCommand+' --list-keys '+lKeys.text);
+  kKeys.grep('^pub');
+  kKeys.grep('expired|revoked',true);
+  kKeys.replace('^\S+\s+[^ /]+/([0-9A-F]{8}) .*$','$1');
   kKeys.sort;
-  kKeys.uniq('d');
 
+  wurzel:=strtoint('$'+kKeys[0]);
+
+  writeln('folgende Kernelschlüssel sind auch lokal vorhanden:');
   write(kKeys.text);
+  writeln('davon nehme ich jetzt '+kKeys[0]);
+
+  kKeys.clear;
+  kKeys.loadFromPipe(gpgCommand+' --list-sigs');// --homedir /var/cache/kernelKeys/.gnupg');
+  kKeys.grep('^(pub|sig)');
+
+  kKeys.replace('^pub .*/([0-9A-F]{8}) .*$','pub $1');
+  kKeys.replace('^sig .* ([0-9A-F]{8}) .*$','sig $1');
+  kKeys.uniq('-');
+
+  baum:=tList.create;
+  i:=0;
+  while i<kKeys.count do begin
+    if leftStr(kKeys[i],4)='pub ' then begin
+      cK:=findeKnoten(baum,strtoint('$'+rightStr(kKeys[i],8)));
+      inc(i);
+      while (i<kKeys.count) and (leftStr(kKeys[i],4)='sig ') do begin
+        cK.addSig(baum,strtoint('$'+rightStr(kKeys[i],8)));
+        inc(i);
+      end;
+    end
+    else
+      inc(i);
+  end;
+
+  spitze:=strtoint('$00411886'); // Torvalds key
 
   lKeys.free;
   kKeys.free;
diff --git a/gpggraph.lps b/gpggraph.lps
index 01bb158..2095e71 100644
--- a/gpggraph.lps
+++ b/gpggraph.lps
@@ -3,30 +3,30 @@
   <ProjectSession>
     <Version Value="9"/>
     <BuildModes Active="Default"/>
-    <Units Count="4">
+    <Units Count="5">
       <Unit0>
         <Filename Value="gpggraph.lpr"/>
         <IsPartOfProject Value="True"/>
         <IsVisibleTab Value="True"/>
-        <TopLine Value="2"/>
-        <CursorPos X="8" Y="37"/>
-        <UsageCount Value="21"/>
+        <TopLine Value="43"/>
+        <CursorPos X="25" Y="80"/>
+        <UsageCount Value="27"/>
         <Loaded Value="True"/>
       </Unit0>
       <Unit1>
         <Filename Value="../units/mystringlistunit.pas"/>
-        <EditorIndex Value="1"/>
-        <TopLine Value="222"/>
-        <CursorPos X="16" Y="262"/>
-        <UsageCount Value="11"/>
+        <EditorIndex Value="2"/>
+        <TopLine Value="171"/>
+        <CursorPos X="12" Y="199"/>
+        <UsageCount Value="13"/>
         <Loaded Value="True"/>
       </Unit1>
       <Unit2>
         <Filename Value="../units/fileunit.pas"/>
-        <EditorIndex Value="2"/>
+        <EditorIndex Value="3"/>
         <TopLine Value="154"/>
         <CursorPos X="28" Y="172"/>
-        <UsageCount Value="11"/>
+        <UsageCount Value="13"/>
         <Loaded Value="True"/>
       </Unit2>
       <Unit3>
@@ -34,126 +34,140 @@
         <EditorIndex Value="-1"/>
         <TopLine Value="751"/>
         <CursorPos X="15" Y="770"/>
-        <UsageCount Value="10"/>
+        <UsageCount Value="9"/>
       </Unit3>
+      <Unit4>
+        <Filename Value="graphunit.pas"/>
+        <IsPartOfProject Value="True"/>
+        <EditorIndex Value="1"/>
+        <TopLine Value="50"/>
+        <CursorPos X="21" Y="79"/>
+        <FoldState Value=" T3Q052O"/>
+        <UsageCount Value="22"/>
+        <Loaded Value="True"/>
+      </Unit4>
     </Units>
-    <JumpHistory Count="29" HistoryIndex="28">
+    <JumpHistory Count="30" HistoryIndex="29">
       <Position1>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="14" Column="19"/>
+        <Caret Line="33" Column="21" TopLine="2"/>
       </Position1>
       <Position2>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="13" Column="6"/>
+        <Filename Value="../units/mystringlistunit.pas"/>
+        <Caret Line="235" Column="8" TopLine="219"/>
       </Position2>
       <Position3>
         <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="22" Column="25" TopLine="7"/>
+        <Caret Line="31" Column="19" TopLine="7"/>
       </Position3>
       <Position4>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="120" Column="24" TopLine="94"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="37" Column="8" TopLine="2"/>
       </Position4>
       <Position5>
-        <Filename Value="../units/fileunit.pas"/>
-        <Caret Line="30" Column="26" TopLine="8"/>
+        <Filename Value="../units/mystringlistunit.pas"/>
+        <Caret Line="23" Column="27" TopLine="3"/>
       </Position5>
       <Position6>
-        <Filename Value="../units/fileunit.pas"/>
-        <Caret Line="157" Column="18" TopLine="136"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="40" Column="66" TopLine="3"/>
       </Position6>
       <Position7>
-        <Filename Value="../units/fileunit.pas"/>
-        <Caret Line="169" Column="18" TopLine="136"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="6" Column="19"/>
       </Position7>
       <Position8>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="123" Column="9" TopLine="94"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="21" Column="22" TopLine="4"/>
       </Position8>
       <Position9>
         <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="120" Column="26" TopLine="100"/>
+        <Caret Line="28" Column="32" TopLine="8"/>
       </Position9>
       <Position10>
         <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="113" Column="25" TopLine="93"/>
+        <Caret Line="29" Column="23" TopLine="8"/>
       </Position10>
       <Position11>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="23" Column="15" TopLine="3"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="49" Column="10" TopLine="13"/>
       </Position11>
       <Position12>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="15" Column="19"/>
+        <Caret Line="19" Column="21"/>
       </Position12>
       <Position13>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="28" Column="19" TopLine="8"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="6" Column="30"/>
       </Position13>
       <Position14>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="30" Column="66" TopLine="8"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="70" Column="22" TopLine="49"/>
       </Position14>
       <Position15>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="20" Column="16"/>
+        <Caret Line="22" Column="24" TopLine="13"/>
       </Position15>
       <Position16>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="16" Column="9"/>
+        <Caret Line="19" Column="21"/>
       </Position16>
       <Position17>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="29" Column="23" TopLine="8"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="13"/>
       </Position17>
       <Position18>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="225" Column="37" TopLine="191"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="121" Column="55" TopLine="93"/>
       </Position18>
       <Position19>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="223" Column="21" TopLine="203"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="68" TopLine="34"/>
       </Position19>
       <Position20>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="30" Column="40"/>
+        <Caret Line="11" Column="11"/>
       </Position20>
       <Position21>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="30" Column="22" TopLine="10"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="24"/>
       </Position21>
       <Position22>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="249" Column="39" TopLine="230"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="76" Column="58" TopLine="38"/>
       </Position22>
       <Position23>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="229" Column="38" TopLine="209"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="25" Column="16"/>
       </Position23>
       <Position24>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="31" Column="28" TopLine="21"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="87" Column="26" TopLine="25"/>
       </Position24>
       <Position25>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="35"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="15" Column="34" TopLine="4"/>
       </Position25>
       <Position26>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="239" TopLine="221"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="6" Column="40"/>
       </Position26>
       <Position27>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="33" Column="21" TopLine="2"/>
+        <Caret Line="72" Column="22" TopLine="44"/>
       </Position27>
       <Position28>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="235" Column="8" TopLine="219"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="20" Column="58"/>
       </Position28>
       <Position29>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="31" Column="19" TopLine="7"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="56" Column="20" TopLine="38"/>
       </Position29>
+      <Position30>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="76" Column="25" TopLine="50"/>
+      </Position30>
     </JumpHistory>
   </ProjectSession>
 </CONFIG>
diff --git a/graphunit.pas b/graphunit.pas
new file mode 100644
index 0000000..ca8c58d
--- /dev/null
+++ b/graphunit.pas
@@ -0,0 +1,90 @@
+unit graphunit;
+
+{$mode objfpc}{$H+}
+
+interface
+
+uses
+  Classes, SysUtils;
+
+type
+  tKnoten = class
+    id:   int64;
+    sigs: tList;
+    constructor create(i: int64);
+    destructor destroy; override;
+    procedure addSig(var bm: tList; i: int64);
+  end;
+
+function findeKnoten(var bm: tList; id: int64): tKnoten; overload;
+function findeKnoten(var bm: tList; kn: tKnoten): tKnoten; overload;
+
+implementation
+
+uses
+  lowlevelunit;
+
+constructor tKnoten.create(i: int64);
+begin
+  inherited create;
+  id:=i;
+  sigs:=tList.create;
+end;
+
+destructor tKnoten.destroy;
+begin
+  sigs.free;
+end;
+
+procedure tKnoten.addSig(var bm: tList; i: int64);
+begin
+  findeKnoten(sigs,findeKnoten(bm,i));
+end;
+
+function findeKnoten(var bm: tList; id: int64): tKnoten; overload;
+var
+  kn: tKnoten;
+begin
+  kn:=tKnoten.create(id);
+  result:=findeKnoten(bm,kn);
+  if result<>kn then
+    kn.free;
+end;
+
+function findeKnoten(var bm: tList; kn: tKnoten): tKnoten; overload;
+var
+  mi,ma,i: longint;
+begin
+  mi:=0;
+  ma:=bm.count-1;
+  while mi<=ma do begin
+    i:=(mi+ma) div 2;
+    if tKnoten(bm[i]).id<kn.id then begin
+      mi:=i+1;
+      continue;
+    end;
+    if tKnoten(bm[i]).id>kn.id then begin
+      ma:=i-1;
+      continue;
+    end;
+    if tKnoten(bm[i]).id=kn.id then begin
+      result:=tKnoten(bm[i]);
+      exit;
+    end;
+  end;
+  if (mi>=0) and (mi<bm.count) and (tKnoten(bm[mi]).id=kn.id) then begin
+    result:=tKnoten(bm[mi]);
+    exit;
+  end;
+  if (ma>=0) and (ma<bm.count) and (tKnoten(bm[ma]).id=kn.id) then begin
+    result:=tKnoten(bm[ma]);
+    exit;
+  end;
+  if mi<>ma+1 then
+    fehler('Bisektionsfehler: mi<>ma+1!');
+  result:=kn;
+  bm.insert(mi,kn);
+end;
+
+end.
+