Unrolled linked lists for StateHEADmaster

1 files changed, 47 insertions, 28 deletions

diff --git a/src/kompsos-collector.adb b/src/kompsos-collector.adb
index 4654dc7..2c52160 100644
--- a/src/kompsos-collector.adb
+++ b/src/kompsos-collector.adb
@@ -55,6 +55,33 @@ package body Kompsos.Collector is
 
     --  Unification  --
 
+    Use_New_Node : Boolean := False;
+
+    function Append
+           (This  : in State;
+            Key   : in Variable;
+            Value : in Term)
+        return State is
+    begin
+        if Use_New_Node or else This.Ctrl.Actual = null or else
+            (This.Ctrl.Actual /= null and then This.Ctrl.Actual.Valid = Valid_Count'Last)
+        then
+            Use_New_Node := False;
+            return (Ctrl => (Ada.Finalization.Controlled with
+                Actual => new State_Component'(
+                    Counter => 1,
+                    Valid   => Valid_Count'First,
+                    Data    => (1 => (Key, Value), others => <>),
+                    Next    => This)));
+        else
+            return Result : constant State := This do
+                Result.Ctrl.Actual.Valid := Result.Ctrl.Actual.Valid + 1;
+                Result.Ctrl.Actual.Data (Result.Ctrl.Actual.Valid) := (Key, Value);
+            end return;
+        end if;
+    end Append;
+
+
     procedure Walk
            (This : in     State;
             Item : in out Term)
@@ -95,21 +122,11 @@ package body Kompsos.Collector is
 
         --  Unify Variable and other Terms by introducing a new substitution
         if Real_Left.Kind = Var_Term then
-            Extended := (Ctrl => (Ada.Finalization.Controlled with
-                Actual => new State_Component'(
-                    Counter => 1,
-                    Key     => Real_Left.Var,
-                    Value   => Real_Right,
-                    Next    => Potential)));
+            Extended := Append (Potential, Real_Left.Var, Real_Right);
             return True;
         end if;
         if Real_Right.Kind = Var_Term then
-            Extended := (Ctrl => (Ada.Finalization.Controlled with
-                Actual => new State_Component'(
-                    Counter => 1,
-                    Key     => Real_Right.Var,
-                    Value   => Real_Left,
-                    Next    => Potential)));
+            Extended := Append (Potential, Real_Right.Var, Real_Left);
             return True;
         end if;
 
@@ -205,7 +222,7 @@ package body Kompsos.Collector is
     end Reset;
 
 
-    function Raw_New_Book
+    function New_Book_Factory
            (Kind : in Node_Kind)
         return Book_Node_Access is
     begin
@@ -219,7 +236,7 @@ package body Kompsos.Collector is
         when Recurse_Node =>
             return new Book_Node'(Data => (Kind => Recurse_Node,  others => <>), others => <>);
         end case;
-    end Raw_New_Book;
+    end New_Book_Factory;
 
 
     function New_Book
@@ -228,9 +245,9 @@ package body Kompsos.Collector is
     begin
         pragma Assert (Ptr.Counter /= 0);
         if Ptr.Counter = 1 or Ptr = Relation.Graph.Actual then
-            return Raw_New_Book (Ptr.Kind);
+            return New_Book_Factory (Ptr.Kind);
         else
-            return Acc : constant Book_Node_Access := Raw_New_Book (Ptr.Kind) do
+            return Acc : constant Book_Node_Access := New_Book_Factory (Ptr.Kind) do
                 Loose_Books.Append ((1, Ptr, Acc));
             end return;
         end if;
@@ -414,12 +431,10 @@ package body Kompsos.Collector is
             if Book = null then
                 Book := New_Book (Ptr);
             end if;
-            if Ptr.Rec_Goal.Actual = null then
-                Book.Data.Rec_Cache := False;
-            elsif Book.Next1 = null then
+            if Book.Next1 = null then
                 Book.Next1 := Connect_Loose (Ptr.Rec_Goal.Actual);
             end if;
-            if Book.Data.Rec_Cache then
+            if Ptr.Rec_Goal.Actual /= null then
                 if Book.Next1 = null then
                     Book.Next1 := New_Book (Ptr.Rec_Goal.Actual);
                     Book.Next1.Cache := new Cache_Entry'(True, State_Vectors.Empty_Vector);
@@ -443,12 +458,8 @@ package body Kompsos.Collector is
                     return False;
                 else
                     Book.Data.Rec_Next := 1;
-                    Book.Data.Rec_Cache := False;
                 end if;
             end loop;
-            if Book.Data.Rec_Cache and Ptr.Rec_Goal.Actual.Counter = 1 then
-                Book.Next1.Cache.Data.Append ((1, new State'(Result)));
-            end if;
             Book.Data.Rec_Next := Book.Data.Rec_Next + 1;
             return True;
         end case;
@@ -468,6 +479,7 @@ package body Kompsos.Collector is
         elsif Ptr.Actual = null then
             if Index = 1 then
                 Result := Base;
+                Use_New_Node := True;
                 return True;
             else
                 return False;
@@ -483,17 +495,24 @@ package body Kompsos.Collector is
             if not Book.Cache.Keep and then Book.Cache.Data (Index).Used >= Ptr.Actual.Counter then
                 Free (Book.Cache.Data (Index).Data);
             end if;
+            Use_New_Node := True;
             return True;
         else
             return Found : constant Boolean :=
                 Do_Get_Next (Ptr.Actual, Book, Base, Index, Result)
             do
-                if Found and Ptr.Actual.Counter > 1 and Ptr.Actual /= Relation.Graph.Actual then
-                    if Book.Cache = null then
+                if Found then
+                    if Ptr.Actual.Counter > 1 and then
+                        Ptr.Actual /= Relation.Graph.Actual and then
+                        Book.Cache = null
+                    then
                         Book.Cache := new Cache_Entry'(False, State_Vectors.Empty_Vector);
                     end if;
-                    pragma Assert (Index = Book.Cache.Data.Last_Index + 1);
-                    Book.Cache.Data.Append ((1, new State'(Result)));
+                    if Book.Cache /= null then
+                        pragma Assert (Index = Book.Cache.Data.Last_Index + 1);
+                        Book.Cache.Data.Append ((1, new State'(Result)));
+                        Use_New_Node := True;
+                    end if;
                 end if;
             end return;
         end if;