private with Ada.Containers.Doubly_Linked_Lists;
private with Locking_Objects;
generic
type Element_Type is private;
with function "="( left, right : Element_Type ) return Boolean is <>;
package Mutable_Lists is
pragma Preelaborate;
-- A Cursor references a location in a list. List elements referenced by
-- cursors are locked and can only be examined via the open cursor
-- referencing them. Any threads attempting to reference a locked list
-- element will block until the element's cursor is closed. Note that while
-- a List is thread safe, a Cursor is not.
type Cursor is limited private;
-- Closes the cursor, unlocking the list element under examination.
procedure Close( position : in out Cursor );
-- Returns the element referenced by the cursor. An exception is raised on
-- error.
function Element( position : Cursor ) return Element_Type;
-- Returns True if the cursor is open, referencing an existing list element.
function Has_Element( position : Cursor ) return Boolean;
-- Modifies the cursor to point to the next element in the list, blocking if
-- the next element is already being examined.
procedure Next( position : in out Cursor );
-- A List is a thread-safe mutable list backed by doubly linked list.
--
-- Mutable lists may be modified during iteration, so it is possible for a
-- thread A to add to or remove elements from the list while a thread B is
-- iterating across the list. However, elements which are being examined by
-- a cursor or the Iterate procedure are locked to prevent other threads
-- from modifying or removing elements referenced by cursors.
--
-- Lists only support Append and Prepend additions.
--
-- While the atomic list operations provided in this package are thread
-- safe, there is no guarantee that the list will not be modified by a
-- different thread between calls. For example, the following may fail:
--
-- if list.Is_Empty then
-- list.Append( element );
-- end if;
-- Assert( not list.Is_Empty );
--
-- The list may be modified by other threads between the calls to Is_Empty
-- and Append.
type List is tagged limited private;
type A_List is access all List'Class;
-- Appends the element to the list.
procedure Append( this : access List; element : Element_Type );
-- Appends the element to the list unless it's already in the list. Inserted
-- will be returned as True if the append was performed.
procedure Append_No_Duplicate( this : access List;
element : Element_Type;
inserted : out Boolean );
-- Clears the list, blocking on elements that are being examined.
procedure Clear( this : access List );
-- Returns a cursor pointing to the element in the list if it is found. The
-- procedure will block if the element is being examined. If the element is
-- not found in the list, a null cursor will be returned.
procedure Find( this : access List; element : Element_Type; position : out Cursor );
-- Returns a cursor pointing to the first element in the list, blocking if
-- the first element is being examined.
procedure First( this : access List; position : out Cursor );
-- Returns True if the list has no elements.
function Is_Empty( this : access List ) return Boolean;
-- Iterates forward through the list, blocking on elements that are already
-- being examined. Any thread can still modify the list while one thread is
-- iterating over it, except for elements that are being examined.
procedure Iterate( this : access List;
examine : access procedure( element : Element_Type ) );
-- Iterates forward through the list with the option of an early exit. Set
-- quit to True in the examine procedure to abort iteration. See Iterate for
-- further details.
procedure Iterate_With_Quit( this : access List;
examine : access procedure( element : Element_Type;
quit : in out Boolean ) );
-- Returns the number of elements in the list.
function Length( this : access List ) return Natural;
-- Prepends an element to the list.
procedure Prepend( this : access List; element : Element_Type );
-- Removes the element pointed to by position, blocking if the element is
-- being examined. The cursor will be closed.
procedure Remove( this : access List; position : in out Cursor );
-- Deletes the list. If there are any open cursors, the deletion will fail
-- without modifying the list and an exception will be raised.
procedure Delete( this : in out A_List );
-- Raised when any kind of use error occurs while using a mutable list.
-- See the exception occurence's message for details.
Container_Error : exception;
private
use Locking_Objects;
type Node is limited
record
lock : A_Locking_Object := new Locking_Object;
element : Element_Type;
end record;
type A_Node is access all Node;
procedure Delete( n : in out A_Node );
package Node_Lists is new Ada.Containers.Doubly_Linked_Lists( A_Node, "=" );
type List is tagged limited
record
lock : A_Locking_Object := new Locking_Object;
refs : Natural := 0; -- open cursors referencing the list
contents : Node_Lists.List;
end record;
procedure Find_Next( this : access List;
crsr : in out Node_Lists.Cursor;
nextNode : out A_Node );
type Cursor is limited
record
list : access Mutable_Lists.List := null;
crsr : Node_Lists.Cursor;
node : A_Node := null;
end record;
end Mutable_Lists;