2
\$\begingroup\$

Backstory

This is a buffer I wrote for use in multiple personal projects. It is designed to handle pretty much any data in pretty much any way. In particular I intend to use it in such instances as recursive-descent parsers, where it will be important to be able to 'undo' operations.

Undo

This 'undo' functionality is implemented alongside thread safety by maintaining references to a 'reference' object. Thus a buffer can be copied in a (mostly) shallow manner while maintaining the same underlying data. Removing from a copy of a buffer doesn't actually remove its 'head' node unless it is the last copy of a buffer to reference it.

Memory safety

The memory safety is achieved by re-using old nodes instead of freeing them if possible and not allowing data to be inserted unless there is an already allocated node available. This effectively implements a custom memory store.

Memory and Thread Safety

I had quite a bit of headache trying to get this to be both threadsafe and devoid of memory leaks. I believe I have finally achieved that. There were a lot of off-by-one errors that had to be corrected with respect to references and null pointers to ensure that everything gets cleaned up when appropriate and nothing gets cleaned up prematurely.

Your Task

The reason I am posting this here is because I intend to re-use this implementation a lot. As such I want to make sure it doesn't have any bugs later. While I don't expect subtle memory or thread-safety bugs to be easily detected, any stylistic changes that may be allowing such bugs to hide would be nice to detect early.

Therefore if there are any areas where a slight change of methodology could get more inherent safety, I would greatly appreciate it. I was surprised by how finicky this was, considering that Ada typically makes it harder to actually make surface-level mistakes.

If I had to point to one thing I'm not happy about it would be that each node is its own protected object. I would have thought it would be doable with only the reference list being protected and using its mutual exclusion to reference count the nodes. I just couldn't find a way to make that work.

Specification

with Ada.Finalization;

generic
    type Element is private;

    -- 0 capacity means use entire accessible memory pool
    Max_Capacity : Natural := 0;

    -- Total number of nodes to cache for re-use
    Max_Cache : Positive := 1;
package Shared_Buffers is
    type Shared_Buffer is new Ada.Finalization.Controlled with private;

    procedure Insert (Into : in out Shared_Buffer; Value : Element);
    procedure Remove (From : in out Shared_Buffer; Value : out Element);

    function Has_Data (What : Shared_Buffer) return Boolean;

    procedure Initialize (Object : in out Shared_Buffer);
    procedure Adjust (Object : in out Shared_Buffer);
    procedure Finalize (Object : in out Shared_Buffer);
private
    type Element_Node;
    type Element_Node_Access is access Element_Node;
    type Node_List is array (Positive range <>) of Element_Node_Access;

    protected type Element_Node is
        -- Reference counting features
        procedure Reference (Times : Positive := 1);
        procedure Ignore;
        procedure Clear;
        function Has_References return Boolean;
        function Get_References return Natural;

        -- Node features
        procedure Set (Value : Element);
        procedure Follow_With (Node : Element_Node_Access);
        function Get return Element;
        function Next return Element_Node_Access;
        entry Wait;
    private
        Data : Element;
        Following : Element_Node_Access := null;
        References : Natural := 1;
    end Element_Node;

    protected type Protected_Shared_Buffer is
        -- Reference counting features
        procedure Reference (From : Element_Node_Access);
        procedure Ignore;
        function Has_References return Boolean;

        -- Buffer features
        entry Insert (Value : Element);
        entry Get_Head (Node : out Element_Node_Access);
        procedure Remove (Node : in out Element_Node_Access);
        function Has_Head return Boolean;
    private
        Tail : Element_Node_Access := null;
        Head : Element_Node_Access := null;

        Cache : Node_List (1 .. Max_Cache) :=
            (1 => new Element_Node, others => null);
        Cached : Natural := 1;
        Count : Natural := 1;

        References : Natural := 1;
        Newborns : Natural := 1;
    end Protected_Shared_Buffer;

    type Protected_Shared_Buffer_Access is access Protected_Shared_Buffer;

    type Shared_Buffer is new Ada.Finalization.Controlled with
        record
            Reference : Protected_Shared_Buffer_Access;
            Self : Element_Node_Access;
            Tailed : Boolean;
        end record;
end Shared_Buffers;

Body

with Ada.Unchecked_Deallocation;

package body Shared_Buffers is
    procedure Free_Node is new Ada.Unchecked_Deallocation
        (Element_Node, Element_Node_Access);

    procedure Free_Protected_Shared_Buffer is new Ada.Unchecked_Deallocation
        (Protected_Shared_Buffer, Protected_Shared_Buffer_Access);

    protected body Element_Node is
        procedure Reference (Times : Positive := 1) is begin
            References := References + Times;
        end Reference;

        procedure Ignore is begin
            if References > 0 then
                References := References - 1;
            end if;
        end Ignore;

        procedure Clear is begin
            References := 0;
        end Clear;

        function Has_References return Boolean is (References > 0);
        function Get_References return Natural is (References);

        procedure Set (Value : Element) is begin
            Data := Value;
        end Set;

        procedure Follow_With (Node : Element_Node_Access) is begin
            Following := Node;
        end Follow_With;

        function Get return Element is (Data);

        function Next return Element_Node_Access is (Following);

        entry Wait when Following /= null is begin null; end Wait;
    end Element_Node;

    protected body Protected_Shared_Buffer is
        procedure Reference (From : Element_Node_Access) is
            Node : Element_Node_Access := From;
        begin
            References := References + 1;

            if From = null then
                Newborns := Newborns + 1;
            end if;

            while Node /= null loop
                Node.Reference;
                Node := Node.Next;
            end loop;
        end Reference;

        procedure Ignore is begin
            if References > 1 then
                References := References - 1;
            else
                References := 0;
                for I in Positive range 1 .. Cached loop
                    Free_Node (Cache (I));
                    Count := Count - 1;
                end loop;
            end if;
        end Ignore;

        function Has_References return Boolean is (References > 0);

        entry Insert (Value : Element) when Cached > 0 is
            Node : Element_Node_Access := Cache (Cached);
        begin
            Node.Clear;
            Node.Set (Value);

            if Tail = null then
                Node.Reference (Newborns);
                Head := Node;
            else
                Node.Reference (Tail.Get_References);
                Tail.Follow_With (Node);
            end if;

            Tail := Node;

            if Max_Capacity = 0 or Count < Max_Capacity then
                Cache (Cached) := new Element_Node;
                Count := Count + 1;
            else
                Cached := Cached - 1;
            end if;
        exception
            when Storage_Error =>
                Cached := Cached - 1;
        end Insert;

        entry Get_Head (Node : out Element_Node_Access) when Head /= null is
        begin
            Node := Head;
            Newborns := Newborns - 1;
        end Get_Head;

        procedure Remove (Node : in out Element_Node_Access) is begin
            Node.Ignore;

            if not Node.Has_References then
                if Cached = Max_Cache then
                    Free_Node (Node);
                    Count := Count - 1;
                else
                    Cached := Cached + 1;
                    Cache (Cached) := Node;
                end if;
            end if;
        end Remove;

        function Has_Head return Boolean is (Head /= null);
    end Protected_Shared_Buffer;

    procedure Insert (Into : in out Shared_Buffer; Value : Element) is
    begin
        Into.Reference.Insert (Value);
    end Insert;

    procedure Remove (From : in out Shared_Buffer; Value : out Element) is
        Next : Element_Node_Access;
    begin
        if From.Tailed then
            if From.Self /= null then
                From.Self.Wait;
                Next := From.Self.Next;

                From.Reference.Remove (From.Self);
                From.Self := Next;
            else
                From.Reference.Get_Head (From.Self);
            end if;
        end if;

        Value := From.Self.Get;
        Next := From.Self.Next;

        if Next /= null then
            From.Reference.Remove (From.Self);
            From.Self := Next;
            From.Tailed := False;
        else
            From.Tailed := True;
        end if;
    end Remove;

    function Has_Data (What : Shared_Buffer) return Boolean is
        (if What.Tailed then (
            if What.Self /= null then
                What.Self.Next /= null
            else
                What.Reference.Has_Head));

    procedure Initialize (Object : in out Shared_Buffer) is
    begin
        Object.Reference := new Protected_Shared_Buffer;

        Object.Self := null;
        Object.Tailed := True;
    end Initialize;

    procedure Adjust (Object : in out Shared_Buffer) is
    begin
        Object.Reference.Reference (Object.Self);
    end Adjust;

    procedure Finalize (Object : in out Shared_Buffer) is
        Removed : Element_Node_Access;
    begin
        if not Object.Tailed then
            while Object.Self /= null loop
                Removed := Object.Self;
                Object.Self := Object.Self.Next;
                Object.Reference.Remove (Removed);
            end loop;
        end if;

        Object.Reference.Ignore;
        if not Object.Reference.Has_References then
            Free_Protected_Shared_Buffer (Object.Reference);
        end if;
    end Finalize;
end Shared_Buffers;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.