SIMPLE COMPONENTS
version 3.7
by Dmitry A. Kazakov
(mailbox@dmitry-kazakov.de)

This library is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

As a special exception, if other files instantiate generics from this unit, or you link this unit with other files to produce an executable, this unit does not by itself cause the resulting executable to be covered by the GNU General Public License. This exception does not however invalidate any other reasons why the executable file might be covered by the GNU Public License.

The current version provides implementations of smart pointers, directed graphs, sets, maps, stacks, tables, string editing, unbounded arrays, expression analyzers, lock-free data structures, synchronization primitives (events, race condition free pulse events, arrays of events, reentrant mutexes, deadlock-free arrays of mutexes), pseudo-random non-repeating numbers, symmetric encoding and decoding, IEEE 754 representations support. It grew out of needs and does not pretend to be universal. Tables management and strings editing are described in separate documents see Tables and Strings edit. The library is kept conform to both Ada 95 and Ada 2005 language standards.

Quick reference

Chebyshev series
Cryptography
Blackboards (lock-free)
Graphs (directed, weighted, acyclic, trees)
Doubly-linked webs and lists
Events (plain, pulse, array of)
FIFO (lock-free)
IEEE 754
Mutexes
Objects and handles to
Parsers
Persistent objects and handles to
Persistent storage and handles to
Pools
Sets and maps
Stacks
Strings editing
Tables (maps of strings)
Unbounded arrays

See also changes log.

1. Objects and handles (smart pointers)

The objects and handles are designed to provide automatic garbage collection. The objects are created explicitly, but never explicitly destroyed. An application program usually should not directly access objects, using object handles (smart pointers) instead. As long as at least one handle to an object exists the object will not be destroyed. When the last handle disappears the object is automatically destroyed. The presented implementation is oriented on large and rather complex objects. Usually it has little sense to have pointers to small objects, having no identity. For such objects by-value semantics is often safer, easier to understand and more efficient. For this reason an object-oriented approach was chosen. The object type is considered a descendant of a limited controlled type which can be extended as necessary. Same handle type can be used for the whole class of descendant types. The proxy operations can be defined on handles which implementations may dispatch according to the actual type of the pointed object.

A specialization of objects is provided to support object's persistence. Such objects can be stored in an external persistent storage and then restored from there. The persistent storage interface itself is an object. This allows implementation of object serving as proxies of external objects permanently resident in an external storage.

1.1. Objects

The package Object provides the base type Entity for all objects:

type Entity is new
   Ada.Finalization.Limited_Controlled with
record
   Use_Count : Natural := 0;
end record;
type Entity_Ptr is access all Entity'Class;

It is a limited controlled type. The following operations are defined on it:

procedure Decrement_Count (Object : in out Entity);

This procedure decreases object's reference count. It should never be used explicitly, except than in implementations of handles to objects.

function Equal
         (  Left  : Entity;
            Right : Entity'Class;
            Flag  : Boolean := False
         )  return Boolean;
function Less
         (  Left  : Entity;
            Right : Entity'Class;
            Flag  : Boolean := False
         )  return Boolean;

These functions are used to compare objects. The meaning of comparison is usually defined by the nature of the objects. However the main reason why comparison is defined, is to support ordered sets of objects, so any order is suitable. Thus the implementations of Equal and Less use storage addresses to get Entity objects ordered. They should be overridden if a more meaningful order of objects exists. Note that Ada does not fully support multiple dispatch. Therefore the operations are declared asymmetric. The second parameter is class-wide. If the operation is overridden, an implementation should dispatch on the second parameter to emulate true multiple dispatch. The parameter Flag indicates whether the function is called recursively. The following code fragment illustrates how to do it:

The idea is that a given overriding is responsible for implementation of Less if and only if Left :> Right, i.e. when Left is in the class of Right. The dispatching mechanism warranties that Left is in the type class, so if Right is of the same type or else does not belong to the type class, then Left :> Right. Otherwise, Right is used to re-dispatch and Flag is set to indicate that no more dispatch may happen. Observe, that if Left and Right are siblings and therefore neither of Left :> Right and Left <: Right is true, then Flag will stop the recursion.

If the implementation casts Right down to a known type, as it usually would do in other cases, then in the case of siblings, this would cause propagation of Constraint_Error out of Less or Equal. If this behavior is undesirable, another way to deal with comparison of siblings is to find the most specific common ancestor of both. In that case the code of Less might look as follows:

procedure Finalize (This : in out Entity);

This procedure is called upon object finalization. It raises Program_Error if the destroyed object is still in use. Note that any derived type shall call this procedure from its implementation of Finalize when it overrides Finalize.

procedure Increment_Count (Object : in out Entity);

This procedure increases object's reference count. It should never be used explicitly, except than in implementations of handles to objects.

procedure Initialize (Object : in out Entity);

This procedure is called upon object initialization. Any derived type shall call it from its implementation of.

procedure Release (Ptr : in out Entity_Ptr);

The object pointed by Ptr is deleted if its use count in 1. Otherwise the use count is decremented. Ptr becomes null if the object it points to is deleted. The procedure does nothing if Ptr is already null. It can be used for implementation of the smart pointers to Entity and its descendants.

1.1.1. Tasking

The package provides several implementations of Object:

• Task-safe implementation allows use of Decrement_Count, Increment_Count and Release from concurrent tasks. This makes handles to objects task-safe. Note that this by no means makes the objects themselves task-safe. It is up to the implementation of the derived type to ensure safety of its operations.
• Unsafe implementation can be found in the subdirectory single-task. The source files there replace files with the corresponding names in the parent directory. The project files for GNAT Ada allow choice of the implementation per project scenario variable "Tasking".
• Tracing implementation is intended for use with GNAT Ada. The corresponding files provide run-time tracing of reference counts. The implementation is located in the subdirectory gnat-debug. Upon an error the source locations of the object creation, of the reference count changes, where the error was detected are dumped onto the standard output, supplied by the stack traceback at the location  When the project is compiled manually, -bargs -E switches must be used with gnatmake.

1.2. Handles to objects

The generic child package Object.Handle defines the type Handle used to access objects of a given type:

generic
   type Object_Type (<>) is abstract new Entity with private;
   type Object_Type_Ptr is access Object_Type'Class;
package Object.Handle is
   type Handle is new Ada.Finalization.Controlled with private;

The package has two generic parameters:

• Object_Type is a type derived from Entity.
• Object_Type_Ptr is an access type to class-wide objects of Object_Type.

Handles can be assigned to copy a reference to the object. If a handle object is not initialized it is invalid. An invalid handle cannot be used to access objects, but it can be used in some comparisons, it can be copied and assigned. The constant Null_Handle defined in the package is a predefined invalid handle. The following operations are defined on a Handle:

procedure Finalize (Reference : in out Handle);

The destructor destroys the referenced object (if any) in case when the handle was the last one pointing the object.

procedure Invalidate (Reference : in out Handle);

This procedure detaches handle from the object (if any) it points to. The result handle cannot be used to access any object. The referenced object is destroyed if it was the last handle.

function Is_Valid (Reference : Handle) return Boolean;

function Ptr (Reference : Handle) return Object_Type_Ptr;

function Ref (Thing : Object_Type_Ptr) return Handle;

This function is used to get a handle from a pointer to an object.

procedure Set (Reference : in out Handle; Thing : Object_Type_Ptr);

This procedure resets the handle Reference to a possibly another object. In the course of this operation the previously pointed object may be destroyed if Reference was the last handle pointing to it. It is safe when Thing is the object Reference already points to. When Thing is null, this procedure is equivalent to Invalidate.

function "<" (Left, Right : Handle) return Boolean;
function "<="(Left, Right : Handle) return Boolean;
function ">="(Left, Right : Handle) return Boolean;
function ">" (Left, Right : Handle) return Boolean;
function "=" (Left, Right : Handle) return Boolean;
function "="
        (  Left  : Handle;
           Right : access Object_Type'Class
        )  return Boolean;
function "="
        (  Left  : access Object_Type'Class;
           Right : Handle
        )  return Boolean;

Valid handles are comparable. The result of comparison is one of the objects they point to. Implementations of the comparisons use Less and Equal defined on Object_Type. If one of arguments is invalid Contraint_Error is propagated for all functions except "=". For equality (and thus inequality) it is legal to compare with an invalid handle. The result of such comparison is true if and only if both handles are invalid. One of parameters in equality is allowed to be a pointer to an object.

1.3. An example of use

The usage of objects and handles is illustrated by the following simplified example of an implementation of dynamic strings: 

An instance of My_String keeps the string body. But a user should rather use handles to My_String, provided by the child package:

This package defines the type My_Safe_String which can be used with less care about memory allocation and deallocation. A handle can be copied using the standard assignment. A new string object can be created from a string. The value it points to can be accessed using the function Value, etc. It is a good practice to provide Create returning a handle instead of a direct use of Ref on an existing object, because it prevents referring stack-allocated objects which could get out of scope before handles to them. Object.Finalize would notice that and raise Program_Error. An implementation of My_Safe_String might look like follows.

1.4. Bounded arrays of objects

The package Object.Handle.Generic_Bounded_Array defines the type Bounded_Array. An instance of Bounded_Array is a fixed size array of references to objects. It is same as an array of handles to objects but more efficient.

generic
   type Index_Type is (<>);
   type Handle_Type is new Handle with private;
package Object.Handle.Generic_Bounded_Array is ...

Here Index_Type is the type used to index the array elements. Handle_Type is any descendant of Handle including itself. The type Bounded_Array is defined in the package as:

type Bounded_Array (First, Last : Index_Type) is
   new Ada.Finalization.Controlled with private;

The discriminants First and Last define the index range. The following operations are defined on Bounded_Array:

procedure Adjust (Container : in out Bounded_Array);

The assignment makes a copy of the array.

function Append
         (  Container : Bounded_Array;
            Element   : Object_Type_Ptr := null;
            Count     : Natural         := 1
         )  return Bounded_Array;
function Append
         (  Container : Bounded_Array;
            Element   : Handle_Type;
            Count     : Natural := 1
         )  return Bounded_Array;

These functions add Element Count times to the end of Container. The result will have the lower bound Container.First. Constraint_Error is propagated when the upper bound cannot be represented in Index_Type.

function Delete
         (  Container : Bounded_Array;
            From      : Index_Type;
            Count     : Natural := 1
         )  return Bounded_Array;

This function deletes Count elements from Container starting with the element From. When Count exceeds the number of elements in the array, the available elements are removed. The lower bound of the result is Container.First, except the case when all elements are removed. For an empty result, the lower bound is Index_Type'Succ (Index_Type'First). Constraint_Error is propagated when the result should be empty, but Index_Type has less than two values. It is also propagated when From is not in Container.

procedure Finalize (Container : in out Bounded_Array);

The destructor may delete some objects referenced by the array.

procedure Fill
          (  Container : in out Bounded_Array;
             From      : Index_Type;
             To        : Index_Type;
             Element   : Object_Type_Ptr := null
          );
procedure Fill
          (  Container : in out Bounded_Array;
             From      : Index_Type;
             To        : Index_Type;
             Element   : Handle_Type
          );

These procedures are used to put in / replace a range of array elements. The range From..To is filled with Element. Nothing happens if From > To. Otherwise Constraint_Error is propagated when From..To is not in Container.First..Constainer.Last.

function Get
         (  Container : Bounded_Array;
            Index     : Index_Type
         )  return Object_Type_Ptr;

This function returns either a pointer to an object or null.

function Get
         (  Container : Bounded_Array;
            From      : Index_Type;
            To        : Index_Type
         )  return Bounded_Array;

This function returns a slice of Container. The lower index of the slice is From, the upper index is To. Constraint_Error is propagated when From..To is not empty and does not belong to the range First..Last of Container.

function Prepend
         (  Container : Bounded_Array;
            Element   : Object_Type_Ptr := null;
            Count     : Natural         := 1
         )  return Bounded_Array;
function Prepend
         (  Container : Bounded_Array;
            Element   : Handle_Type;
            Count     : Natural := 1
         )  return Bounded_Array;

These functions add Element Count times in front of Container. The result will have the upper bound Container.Last. Constraint_Error is propagated when the upper bound cannot be represented in Index_Type.

procedure Put
          (  Container : in out Bounded_Array;
             Index     : Index_Type;
             Element   : Object_Type_Ptr
          );
procedure Put
          (  Container : in out Bounded_Array;
             Index     : Index_Type;
             Element   : Handle_Type
          );

These procedures are used to put in / replace an array element using its index. Constraint_Error is propagated when Index is illegal.

procedure Put
          (  Container : in out Bounded_Array;
             From      : Index_Type;
             To        : Index_Type;
             Elements  : Bounded_Array
          );

This procedures replaces the slice From..To of Container with Elements. Container and Elements can be the same object. Else if Elements is shorter than the slice, the rightmost elements of the slice are replaced with invalid handles. When Elements is longer, then its rightmost elements are ignored. The operation is void when From..To is empty. Constraint_Error is propagated when From..To is not empty and does not belong to the range First..Last of Container.

function Ref
         (  Container : Bounded_Array;
            Index     : Index_Type
         )  return Handle_Type;

function "&" (Left, Right : Bounded_Array) return Bounded_Array;

This function returns a concatenation of two arrays. If Right is empty, the result Left, else if Left is empty, the result is Right. Otherwise, the lower bound of the result is Index_Type'First.

Empty : constant Bounded_Array;

Empty array constant.

1.5. Unbounded arrays of objects

The package Object.Handle.Generic_Unbounded_Array defines the type Unbounded_Array. An instance of Unbounded_Array is an unbounded array of references to objects. The package has same functionality as an instance of Generic_Unbounded_Array with Handle as Object_Type, but it is more efficient.

generic
   type Index_Type is (<>);
   type Handle_Type is new Handle with private;
   Minimal_Size : Positive := 64;
   Increment    : Natural  := 50;
package Object.Handle.Generic_Unbounded_Array is ...

Here:

• Index_Type is the type used to index the array elements;
• Handle_Type is the type of handles to the elements. It is any descendant of Handle or the Handle itself;
• Minimal_Size is the minimal number of elements by which the array vector is enlarged. When the first element is put into the array, this will be the initial vector size.
• Increment controls further vector enlargements. The vector is enlarged by n*Increment/100, where n is the current vector size. If the evaluated increment of the vector size is less than Minimal_Size elements, then the latter is used instead.

The type is declared as:

type Unbounded_Array is new Ada.Finalization.Controlled with private;

The following operations are defined on Unbounded_Array:

procedure Adjust (Container : in out Unbounded_Array);

procedure Erase (Container : in out Unbounded_Array);

This procedure removes all elements from Container making it empty. The objects referenced only by Container will be deleted.

procedure Finalize (Container : in out Unbounded_Array);

The destructor may delete some objects referenced by the array.

function First
         (  Container : Unbounded_Array;
         )  return Index_Type;

This function returns the current lower bound of the array. Constraint_Error is propagated when the array is empty.

function Get
         (  Container : Unbounded_Array;
            Index     : Index_Type
         )  return Object_Type_Ptr;

This function returns either a pointer to an object or null.

function Last
         (  Container : Unbounded_Array;
         )  return Index_Type;

This function returns the current upper bound of the array. Constraint_Error is propagated when the array is empty.

procedure Put
          (  Container : in out Unbounded_Array;
             Index     : Index_Type;
             Element   : Object_Type_Ptr
          );
procedure Put
          (  Container : in out Unbounded_Array;
             Index     : Index_Type;
             Element   : Handle_Type
          );

These procedures are used to put in / replace an array element using its index. The array is automatically expanded as necessary. It never happens if Element is null or an invalid handle.

function Ref
         (  Container : Unbounded_Array;
            Index     : Index_Type
         )  return Handle_Type;

1.6. Unbounded sets of objects

The package Object.Handle.Generic_Set defines the type Set. An instance of Generic_Set is a set of references to objects. The package has same functionality as an instance of Generic_Set with Handle as Object_Type, but it is more efficient. It has the following generic parameters:

generic
   Minimal_Size : Positive := 64;
   Increment    : Natural  := 50;
package Object.Handle.Generic_Set is ...

Here:

• Minimal_Size is the minimal number of elements by which set is enlarged. When the first element is put into the array, this will be the initial vector size.
• Increment controls further vector enlargements. The vector is enlarged by n*Increment/100, where n is the current vector size. If the evaluated increment of the vector size is less than Minimal_Size elements, then the latter is used instead.

The type Set is declared as:

type Set is new Ada.Finalization.Controlled with private;

The following operations are defined on Set:

procedure Add (Container : in out Set; Item  : Handle);
procedure Add (Container : in out Set; Item  : Object_Type_Ptr);
procedure Add (Container : in out Set; Items : Set);

These procedures are used to add an object to a set or all items of one set to another. The parameter Item can be either a handle or a pointer to the object. Nothing happens if an item is already in the set or pointer is an invalid handle or null.

procedure Adjust (Container : in out Set);

The assignment does not make a copy of the Container. It just increments an internal use count of the set body. A set will be physicaly copied only when a destructive operation is applied to it.

function Create return Set;

This function returns an empty set.

procedure Erase (Container : in out Set);

This procedure removes all objects from the set. The objects referenced only by Container will be deleted.

procedure Finalize (Container : in out Set);

The destructor may delete some objects referenced by Container.

function Find (Container : Set; Item : Handle)
   return Integer;
function Find (Container : Set; Item : Object_Type_Ptr)
   return Integer;

This function is used to Item in the set Container. The result is either a positive index of the found item or a negated index of the place where the item should be if it were in the set.

function Get (Container : Set; Index : Positive)
   return Object_Type_Ptr;

This function is used to get an item of the set Container using a positive index. The result is a pointer to the object. It is valid as long as the object is in the set. See also Ref which represents a safer way of accessing the set items. Constraint_Error is propagated if Index is wrong.

function Get_Size (Container : Set) return Natural;

This function returns the number of items in the set.

function Is_Empty (Container : Set) return Boolean;

True is returned if Container is empty.

function Is_In (Container : Set; Item : Handle)
   return Boolean;
function Is_In (Container : Set; Item : Object_Type_Ptr)
   return Boolean;

True is returned if Item is in Container. Item can be either a pointer to an object or a handle to it. The result is always false when Item is invalid or null.

function Ref (Container : Set; Index : Positive) return Handle;

This function is used to get an item of the set Container using a positive index. The result is a handle to the object. Constraint_Error is propagated if Index is wrong.

procedure Remove (Container : in out Set; Index : Positive);
procedure Remove (Container : in out Set; Item  : Handle);
procedure Remove (Container : in out Set; Item  : Object_Type_Ptr);
procedure Remove (Container : in out Set; Items : Set);

These procedures are used to remove items from the set Container. An item can be removed either by its index, or explicitly by a pointer or handle to it, or else by specifying a set of items to be removed. If a particular item is not in the set, then nothing happens. Also nothing happens if a handle is illegal or pointer is null. Constraint_Error is propagated when item index is wrong.

function "and" (Left, Right : Set) return Set;
function "or"  (Left, Right : Set) return Set;
function "xor" (Left, Right : Set) return Set;

These functions are conventional set operations - intersection, union, difference. Difference is defined as a set which items are only in one of the sets Left and Right.

function "=" (Left, Right : Set) return Boolean;

True is returned if both sets contain same items.

1.7. Universal sets of objects

The packages Object.Handle.Generic_Handle_Set resembles Object.Handle.Generic_Set, but it is more universal. It allows to specify a user-defined types both for the object handles and for the weak references to objects (usually pointers). It has the following generic parameters:

generic
   type Handle_Type is new Handle with private;
   type Object_Ptr_Type is private;
   Null_Object_Ptr : Object_Ptr_Type;
   with function Ptr (Object : Handle_Type) return Object_Ptr_Type is <>;
   with function Ref (Object : Object_Ptr_Type) return Handle_Type is <>;
   with function To_Object_Ptr (Object : Object_Ptr_Type) return Object_Type_Ptr is <>;
   with function "<" (Left, Right : Object_Ptr_Type) return Boolean is <>;
   with function "=" (Left, Right : Object_Ptr_Type) return Boolean is <>;
   Minimal_Size : Positive := 64;
   Increment    : Natural  := 50;
package Object.Handle.Generic_Handle_Set is ...

Here:

• Handle_Type is a type derived from Handle to be used as an object handle (strong reference);
• Object_Ptr_Type is a type used to reference objects (weak reference). Usually it is a record type containing a pointer to Object_Type'Class;
• Null_Object_Ptr is a value never be put in the set. Usually it has the object pointer set to null;
• Ptr is a function that converts a handle to the object to a reference. It is analogous to the function Ptr of the parent package;
• Ref is a function that converts a reference to the object to a handle to. It is similar to the function Ref of the parent package;
• To_Object_Ptr is a function that gets Object_Type_Ptr from an object reference;
• "<" and "=" are comparisons defined on object references;
• Minimal_Size is the minimal number of elements by which set is enlarged. When the first element is put into the array, this will be the initial vector size.
• Increment controls further vector enlargements. The vector is enlarged by n*Increment/100, where n is the current vector size. If the evaluated increment of the vector size is less than Minimal_Size elements, then the latter is used instead.

In other aspects both packages are identical. The interface subprograms described below are similar in both. The Handle should be read Handle_Type when Object.Handle.Generic_Handle_Set is considered.

The type Set is declared as:

type Set is new Ada.Finalization.Controlled with private;

The following operations are defined on Set:

procedure Add (Container : in out Set; Item  : Handle_Type);
procedure Add (Container : in out Set; Item  : Object_Ptr_Type);
procedure Add (Container : in out Set; Items : Set);

These procedures are used to add an object to a set or all items of one set to another. The parameter Item can be either a handle or a pointer to the object. Nothing happens if an item is already in the set or pointer is an invalid handle or null.

procedure Adjust (Container : in out Set);

The assignment does not make a copy of the Container. It just increments an internal use count of the set body. A set will be physicaly copied only when a destructive operation is applied to it.

function Create return Set;

This function returns an empty set.

procedure Erase (Container : in out Set);

This procedure removes all objects from the set. The objects referenced only by Container will be deleted.

procedure Finalize (Container : in out Set);

The destructor may delete some objects referenced by Container.

function Find (Container : Set; Item : Handle_Type)
   return Integer;
function Find (Container : Set; Item : Object_Ptr_Type)
   return Integer;

This function is used to Item in the set Container. The result is either a positive index of the found item or a negated index of the place where the item should be if it were in the set.

function Get (Container : Set; Index : Positive)
   return Object_Ptr_Type;

This function is used to get an item of the set Container using a positive index. The result is a pointer to the object. It is valid as long as the object is in the set. See also Ref which represents a safer way of accessing the set items. Constraint_Error is propagated if Index is wrong.

function Get_Size (Container : Set) return Natural;

This function returns the number of items in the set.

function Is_Empty (Container : Set) return Boolean;

True is returned if Container is empty.

function Is_In (Container : Set; Item : Handle_Type)
   return Boolean;
function Is_In (Container : Set; Item : Object_Ptr_Type)
   return Boolean;

True is returned if Item is in Container. Item can be either a pointer to an object or a handle to it. The result is always false when Item is invalid or null.

function Ref (Container : Set; Index : Positive) return Handle_Type;

This function is used to get an item of the set Container using a positive index. The result is a handle to the object. Constraint_Error is propagated if Index is wrong.

procedure Remove (Container : in out Set; Index : Positive);
procedure Remove (Container : in out Set; Item  : Handle_Type);
procedure Remove (Container : in out Set; Item  : Object_Ptr_Type);
procedure Remove (Container : in out Set; Items : Set);

These procedures are used to remove items from the set Container. An item can be removed either by its index, or explicitly by a pointer or handle to it, or else by specifying a set of items to be removed. If a particular item is not in the set, then nothing happens. Also nothing happens if a handle is illegal or pointer is null. Constraint_Error is propagated when item index is wrong.

function "and" (Left, Right : Set) return Set;
function "or"  (Left, Right : Set) return Set;
function "xor" (Left, Right : Set) return Set;

These functions are conventional set operations - intersection, union, difference. Difference is defined as a set which items are only in one of the sets Left and Right.

function "=" (Left, Right : Set) return Boolean;

True is returned if both sets contain same items.

2. Persistency

2.1. Persistent objects

A persistent object is one stored in an external storage, independent on the application, that originally created it. A persistent object can be restored from the external storage in a fully functional state in the same or other application. The provided implementation of persistent objects was designed with the following goals in mind:

• Portability across different platforms in the sense that an object can be stored on one platform and successfully restored on another;
• Independency on the nature of the external storage;
• Support for dependent objects;
• Garbage collection within the application;
• A possibility to implement garbage collection within the external storage;
• Automatic synchronization with the persistent storage upon finalization.

Like other objects, persistent ones are normally accessed through handles.

2.1.1. Types

The package Object.Archived defines the type Deposit serving as the abstract base type for all persistent objects:

type Deposit is abstract new Entity with private;
type Deposit_Ptr is access Deposit'Class;

• Override the procedure Store which will be used to get a string description of the object;
• Define a procedure with the profile of Restore which will create the object from its string description;
• Register the restore procedure as a new class. This could be done once during elaboration of the package deriving the type from Deposit;
• Override Get_Class to return the object class for which Restore was registered;
• Optionally, override Get_Referents if the object may depend on other objects which thus have to be stored/restored together with it:
• If it overrides Finalize, then it shall call Close from there before the object becomes impossible to store.

Objects may depend on other objects, but these dependencies may not be circular. Store and Restore provide forth and back string conversions. String was chosen instead of Stream_Element_Array to make it portable across different systems.

Storing an object:

1. Get_Referents is called. Each object it refers is archived first. The order of the objects in the list is important and has to be preserved;
2. Get_Class is called and its result is archived;
3. Store is called and its result is finally archived.

Restoring an object:

1. A list of objects the archived object depends on is built, the objects are restored as necessary;
2. The object's class string is obtained;
3. Restore is finally called with these parameters. The class is used to select an appropriate Restore. This is equivalent to dispatching according to the class. The list of available classes and their Restore procedures is formed by calls to Register.

The type Backward_Link is used when it is necessary to monitor deletion of an object.

type Backward_Link is abstract new Entity with private;
type Backward_Link_Ptr is access Backward_Link'Class;

Reference counting is used to prevent deletion of a Deposit object, when it is in use. Such objects are referenced through handles. These are direct links to the object, also known as strong references. But sometimes it is necessary to break the dependency of one object from another to delete the latter. For this the former object may get a notification about a desire to delete a referent. Upon this notification it can invalidate the handle to the referent and so allow the collector to delete it. A notification object is derived from Backward_Link, which represent a backward link from a referred object to a dependent one. Each Deposit object maintains a list of its backward links, also called weak references. Typically an external storage connection object tracks all persistent objects which are in the memory at the moment. Usually it has an index of such memory resident objects. A record of this index has a handle to a specialized descendant of Backward_Link. So when an object is no more in use and so the last handle to it disappears, the object is automatically destroyed. In the course of this operation the storage connection object becomes a notification via call to Destroyed. At this point the object being destroyed can be stored and then removed from the external storage index of memory resident objects.

type Deposit_Container is abstract
   new Ada.Finalization.Controlled with private;

The type Deposit_Container is an abstract specialized container for Deposit objects. The container operates as a container of handles. That is when an object is put into it, then the object will not be deleted until it is in. Physically a reference to the object is placed into the container. Deposit_Container objects are used upon object storing and restoring to keep the list of things the object depends on. Deposit_Container is not limited so it can be copied when necessary. The child packages Object.Archived.Sets and Object.Archived.Lists provide unordered (set) and ordered (list) implementations of Deposit_Container.

2.1.2. Operations on objects

procedure Close (Object : in out Deposit'Class);

This class-wide procedure is called before finalization of a persistent object. It cleans the list of backward links. So it plays the role of a class-wide destructor. Finalize should always call it. For example, if the derived type is a descendant of Deposit overriding Finalize, then the implementation should look like:

procedure Finalize (Object : in out Derived) is
begin
   Close (Object);
   ... -- finalization of Derived
   Finalize (Deposit (Object));
end Finalize;

It is safe to call it multiple times, though it is essential to call it before any vital object data get finalized. So Finalization of a type derived from Derived may call Close as well. Note that in Ada Finalize is called prior finalization of any object's components. So it is safe to use them. However, keep in mind that task components (if any) are though not yet finalized, but completed before Finalize, thus neither Store nor Get_Referents may communicate with task components of the object.

procedure Create
          (  Source  : String;
             Pointer : in out Integer;
             Class   : String;
             List    : Deposit_Container'Class;
             Object  : out Deposit_Ptr
          );

This procedure calls Restore for Class simulating a dispatching call. Name_Error is propagated if Class is not a registered object class. The string Source contains object description to be restored starting from the character Source (Pointer). Pointer  is advanced to the first object following from the used ones. The parameter Object accepts a pointer to the newly created object.

procedure Delete (Object : in out Deposit'Class);

This procedure is used when Object is being deleted. On each item in the Object's obituary notices delivery list, Delete is called. This has the effect that some references to Object may disappear and so the object will be collected. Note that a call to Delete does not guaranty Object's deletion, because some references to it, may still be present. It is safe to add new backward links to the Object's notification list from Delete, because the items are appended at the end of the delivery list. This also means that they will receive a Deleted callback in the course of the same notification. Though Object's deletion is not guaranteed it might happen. So to prevent undefined behavior a caller should hold a handle to Object when it calls to Delete.

procedure Finalize (Object : in out Deposit);

Upon finalization backward links list is cleaned. All interested parties receive a notification via call to Destroyed. A derived type implementation have to call Finalize as well as Close.

procedure Free (Object : in out Deposit_Ptr);

This procedure is used to delete manually created objects. It is never called for existing objects, only for improperly constructed ones from an implementation of Restore.

function Get_Class (Object : Deposit) return String is abstract;

This function returns the class of Object. The class is a string uniquely describing the object's type. It is analogous to external type tag representation. Though, different types of objects may share same class if necessary.

procedure Get_Referents
          (  Object    : Deposit;
             Container : in out Deposit_Container'Class
          );

This procedure adds objects referenced from Object to Container objects. Only immediately viewed objects are stored there. No deep search has to be made to detect all objects. Objects shall not depend recursively. The default implementation does nothing, which behavior corresponds to an independent object. An implementation may raise Use_Error on a wrong object. See also notes about Close.

function Is_Modified (Object : Deposit)
   return Boolean is abstract;

This function is used to check if Object's state was changed. Persistent objects serving as proxies to a persistent storage will require synchronization if this function returns true. An implementation of a mutable object would normally have a Boolean flag to be set by any destructive operation or new object creation.

procedure Reset_Modified (Object : in out Deposit) is abstract;

This procedure is used to reset Object's state modification flag. It is called immediately after synchronization the object with the persistent storage.

type Restore is access procedure
     (  Source  : String;
        Pointer : in out Integer;
        Class   : String;
        List    : Deposit_Container'Class;
        Object  : out Deposit_Ptr
     );

This procedure creates a new object from its string representation. It parses Source starting from Source (Pointer). Pointer is then advanced to the first character following the object's description in the string. The procedure has to be dispatching depending on the object's class, which is impossible in Ada. For this reason it is defined as an access to procedure type. Each object class has to define such a function and register it (see Register_Class). The parameter Class contains the actual object class according to which dispatch to an implementation of Restore was made. The parameter List contains the references to the objects the restored object depends on. The order of the objects in the list is same as one returned in Get_Referents. The result is a newly allocated object pointed by the Object parameter. An implementation may raise the following exceptions to indicate errors:

procedure Store
          (  Destination : in out String;
             Pointer     : in out Integer;
             Object      : Deposit
          )  is abstract;

An implementation places string describing Object is into Destination starting from the position specified by Pointer. Pointer is then advanced to the next position following the output. Layout_Error is propagated when Pointer not in Source'First..Source'Last + 1 or there is no room for output. Use_Error can be raised when Object is wrong. See also notes about Close.

2.1.3. Operations on backward links to objects

procedure Attach
          (  Link   : Backward_Link_Ptr;
             Object : Deposit_Ptr
          );

This procedure places Link at the end of Object's delivery list. If it is already in another list then it is removed from there first. Nothing happens if Object is null.

procedure Deleted
          (  Link  : in out Backward_Link;
             Temps : in out Deposit_Container'Class
          )  is abstract;

This procedure is used when an object is requested to be deleted. Normally Deleted is called as a result of object deletion request via call to Delete. The parameter Temps is the list of temporal objects the implementation might create. For example, some objects might be created to be notified within the course of the operation performed by the caller. Note that the caller should hold a handle to Link, to allow the callee to undertake actions which would otherwise lead to Link deletion. Note also that object's finalization does not cause a call to Delete it calls Destroyed instead.

procedure Destroyed (Link : in out Backward_Link) is abstract;

This procedure is used when an object is finally destroyed, but is still fully operable. Thus an implementation of Destroyed may safely access the object referred by Link. It may for example synchronize the object with the external storage or remove the object from the index cache etc. The caller should hold a handle to Link.

procedure Detach (Link : in out Backward_Link);

This procedure removes Link from object's delivery list, if any.

procedure Finalize (Link : in out Backward_Link);

This procedure should be called by a derived type if overridden. Link is removed for object's delivery list if any.

function Self (Link : Backward_Link) return Backward_Link_Ptr;

This function returns a pointer to the link object (to Link itself). Constraint_Error is propagated when Link is not bound to any object.

function This (Link : Backward_Link) return Deposit_Ptr;

This function returns a pointer to the target of Link. Constraint_Error is propagated when Link is not bound to any object.

The package Backward_Link_Handles provides handles to Backward_Link objects.

The child package Backward_Link_Handles.Sets provides sets of handles to Backward_Link object.

2.1.4. Operations on containers

procedure Add
          (  Container : in out Deposit_Container;
             Object    : Deposit_Ptr;
             Backward  : Boolean := False
          )  is abstract;

This procedure puts a reference to Object into Container. The implementation should ensure that Object will not be destroyed until it is in. The parameter Backward, when true indicates a backward link. Backward links are used when the dependent object associated with the container can survive deletion of Object. It is an optional parameter which may be ignored by some implementations. When it is supported, then marking an Object as a backward link should override the effect of any placing the same object as a direct link (with Backward = false). Nothing happens if Object is null.

procedure Erase (Container : in out Deposit_Container) is abstract;

This procedure removes all objects from Container.

function Get
         (  Container : Deposit_Container;
            Index     : Positive
         )  return Deposit_Ptr is abstract;

This function is used to enumerate the objects in a container Objects indices start with 1. Contraint_Error is propagated when Index is wrong.

function Get_Size (Container : Deposit_Container)
   return Natural is abstract;

This function returns the number of objects in Container, i.e. the largest possible index allowed in Get. 0 is returned when the container is empty. Note that the objects in a container need not to be all different. This depends on the container implementation.

function Is_Backward
         (  Container : Deposit_Container;
            Object    : Deposit_Ptr
         )  return Boolean is abstract;

The result of this function is true if a backward link is used for Object in Container. Constraint_Error is propagated when Object is not in Container. Use_Error is propagated when the container implementation does not distinguish direct and backward links.

function Is_Empty (Container : Deposit_Container'Class)
   return Boolean;

This function returns true if Container is empty. It is class-wide.

function Is_In
         (  Container : Deposit_Container;
            Object    : Deposit_Ptr
         )  return Boolean is abstract;

This function returns true if Object is in Container. Note that null cannot be in any container.

2.1.5. Registering classes of objects

function Is_Registered (Class : String) return Boolean;

This function returns true if there is a class of objects registered under the name Class.

procedure Register_Class
          (  Class       : String;
             Constructor : Restore
          );

This procedure is used to register each new class of objects. It is analogous to creating a dispatching table. It is necessary to register a class to make Restore functions working. Nothing happens if the class is already registered and has same constructor. Name_Error is propagated when class is registered with a different constructor.

2.1.6. Sets of persistent objects

The package Object.Archived.Sets provides an implementation of Deposit_Container. The type Deposit_Set is derived there:

type Deposit_Set is new Deposit_Container with private;

Sets do not distinguish multiple insertion of an object. they also ignore the Backward parameter of Add. So Is_Backward will raise Use_Error. Additionally to the predefined operations, Deposit_Set provides standard set-operations:

procedure Remove
          (  Container : in out Deposit_Set;
             Object    : Deposit_Ptr
          );

This procedure removes Object from Container. Nothing happens if it is null or not in.

function "and" (Left, Right : Deposit_Set) return Deposit_Set;
function "or"  (Left, Right : Deposit_Set) return Deposit_Set;
function "xor" (Left, Right : Deposit_Set) return Deposit_Set;

These functions are conventional set operations - intersection, union, difference. Difference is defined as a set which items are only in one of the sets Left and Right.

function "=" (Left, Right : Deposit_Set) return Boolean;

true is returned if both sets contain same items.

2.1.7. Lists of persistent objects

The package Object.Archived.Lists provides an implementation of Deposit_Container. The type Deposit_List is derived there as:

type Deposit_List is new Deposit_Container with private;

All objects in the list are enumerated from 1. The same object can occupy several places in the list. In the external storage Deposit_List can be stored as a set of objects, where objects do not repeat, followed by a list of values identifying the objects in the set. Additionally to the predefined operations, Deposit_List provides:

function Get_Total (Container : Deposit_List) return Natural;

This function returns the number of distinct objects in Container. This value is less or equal to the one returned by Get_Size.

function Is_First
         (  Container : Deposit_List;
            Index     : Positive
         )  return Boolean;

This function returns true if Index is the least index of the object it specifies. I.e. the least index of the object returned by Get (Container, Index). Constraint_Error is propagated if Index is wrong.

2.1.8. Referent objects enumeration

The package Object.Archived.Iterators provides an abstract iterator of references:

type References_Iterator
     (  Referents : access Deposit_Container'Class
     )  is new Ada.Finalization.Limited_Controlled with private;

The type References_Iterator can be used directly or be extended. It provides the following operations:

procedure Enumerate
          (  Iterator : in out References_Iterator'Class;
             Object   : Deposit'Class
          );

This class-wide procedure is called to enumerate references of Object. This same procedure is used for both starting the process and continuing it for each found reference. Enumerate calls Get_Referents for Object and places all found objects which Object depends on into Iterator.Referents.all. A found object is placed only once which is detected by looking into Iterator.Referents.all. The object itself is not put there. After completion the caller may inspect Iterator.Referents.all for any found objects.

procedure On_Each
          (  Iterator : in out References_Iterator;
             Referent : Deposit_Ptr
          );

This procedure can be overridden. It is called by Enumerate each time a new object is found. It may raise an exception to stop the iteration process. This exception will then propagate out of Enumerate.

2.2. Handles to persistent objects

Persistent objects are subject of garbage collection. The recommended way to access them is through handles, which prevents premature destruction of objects in use. Handles can be aggregated into other objects to express object dependencies. Note that circular dependencies shall be avoided. The best way to do it is to design object in a way that would exclude any possibility of circular dependencies. If that is not possible, then Is_Dependent should be used to check dependencies at run time. The generic package Object.Archived.Handle defines the type Handle used to reference persistent object. It is derived from Handle obtained by an instantiation of Object.Handle:

generic
   type Object_Type is abstract new Deposit with private;
   type Object_Ptr_Type is access Object_Type'Class;
package Handles is new Object.Handle (Deposit, Deposit_Ptr);
   type Handle is new Handles.Handle with null record;

The formal parameters of the package are:

• Object_Type is a descendant of Deposit. It can be different from Deposit when it is necessary to narrow the class of persistent objects;
• Object_Ptr_Type is a class-wide pointer to Object_Type. Note that Object_Ptr_Type should use the same storage pool as Deposit_Ptr, because the implementation requires conversions between them. Unfortunately there is no formal way to express this requirement in Ada. Hopefully the compiler would refuse infeasible Object.Archived.Handle instantiations.

There is a ready-to use instantiation of Object.Archived.Handle with Deposit and Deposit_Ptr as the actual parameters: Deposit_Handles.

The package Object.Archived.Handle defines the following operations on Handle:

procedure Add
          (  Container : in out Deposit_Container;
             Object    : Handle;
             Backward  : Boolean := False
          )  is abstract;

This procedure puts Object into Container. The parameter Backward, when true indicates a backward link. Backward links are used when the dependent object associated with the container can survive deletion of Object. Constraint_Error is propagated when Object is an invalid handle.

procedure Delete (Object : in out Handle);

This procedure requests deletion of the object pointed by the handle Object. As the result of the operation Object becomes an invalid handle. The object itself is deleted if possible. Nothing happens if Object is not a valid handle.

function Get_Class (Object : Handle) return String;

This function returns the class of Object. The class is a string uniquely describing the object's type. It is analogous to an external type tag representation. Though, different types of objects may have same class if necessary.

procedure Get_References
          (  Object    : Handle;
             Container : in out Deposit_Container'Class
          );

This procedure adds to Container references to all objects the object specified by the handle Object depends on. No objects added if Object is an invalid handle.

procedure Invalidate (Object : in out Handle);

This procedure detaches handle from the object (if any) it points to. The result handle cannot be used to access any object. The referenced object is destroyed if it was the last handle.

function Is_Backward
         (  Container : Deposit_Container'Class;
            Object    : Handle
         )  return Boolean;

This function returns true if a backward link used for Object in Container. Contstraint_Error is propagated when Object is not in Container or invalid handle. Use_Error does when Container does not distinguish direct and backward links.

function Is_Dependent
         (  Dependant : Handle;
            Referent  : Handle
         )  return Boolean;
function Is_Dependent
         (  Dependant : Handle;
            Referents : Deposit_Container'Class
         )  return Boolean;

These functions check whether Dependant refers to Referent or, when the second parameter is a container, then whether Dependant refers to any of the objects from that container. The result is false if Dependant, Referent is invalid or Referents is empty.

function Is_In
         (  Container : Deposit_Container'Class;
            Object    : Handle
         )  return Boolean;

This function returns true if Object is in Container. When Object is an invalid handle, the result false.

function Is_Valid (Object : Handle) return Boolean;

This function checks whether a handle points to any object, i.e. is valid.

function Ptr (Object : Handle) return Deposit_Ptr;

This function is used to get a pointer to the object the handle Object points to. The pointer of to the object shall be used no longer the handle it was get from exists. A safe way to do it is to avoid declarations of any variables of the type Deposit_Ptr.

function Ref (Thing : Object_Type_Ptr) return Handle;

This function is used to get a handle from a pointer to an persistent object.

function Ref
         (  Container : Deposit_Container'Class;
            Index     : Positive
         )  return Handle;

This function can be used to enumerate the objects in a container. Objects are enumerated from 1. The result is a valid handle to an object in Container. Contraint_Error is propagated when Index is wrong. Note that objects may repeat in containers of some types.

function References (Object : Handle) return Deposit_Set;

This function is used to query all objects its argument depends on. The result is a set of objects. It is empty if Object is an invalid handle.

procedure Set (Object : in out Handle; Thing : Object_Type_Ptr);

This procedure resets the handle Object to a possibly another object. In the course of this operation the previously pointed object may be destroyed if Object was the last handle pointing to it. It is safe when Thing is the object already pointed by the handle. When Thing is null, this procedure is equivalent to Invalidate.

The package Deposit_Handles provides an instantiation of Object.Archived.Handle:

package Deposit_Handles is
   new Object.Archived.Handle (Deposit, Deposit_Ptr);

2.3. Persistent directories

There is no need to have dedicated objects to serve as persistent directories as any object could become a directory. Nevertheless the package Persistent.Directory provides objects which can be used as directories. They have no any functionality except an ability to persist. The package declares:

procedure Create
          (  Storage   : in out Storage_Handle;
             Directory : out Deposit_Handle;
             Name      : String;
             Parent    : Deposit_Handle := Root_Directory
          );

This procedure creates a new directory with the name Name and Parent as the parent directory. The result is a handle Directory to the object. The parameter Storage is a handle Storage_Handle to the persistent storage object where the directory has to be created.

function Is_Directory (Object : Deposit_Handle) return Boolean;

This function returns true if Object is a valid handle to a directory object.

Directory_Class : constant String := "Directory";

Is the class name of the directory objects.

2.4. Persistent storage implementation example

This paragraph describes a simplified example of persistent storage. It provides an implementation of a persistent storage based on direct access file. As an example of persistent objects serve nodes of binary trees.

2.4.1. Persistent storage implementation

The implementation uses a direct access file to store objects. Each object is stored in one file record. The record number serves as the object key. Observe that the implementation is independent from any implementation of concrete persistent object types (derived from Deposit). This example serves illustrative purpose. For abstract persistent storage interface see Persistent, Persistent.Handle. For persistent storage implementations see Persistent.Handle.Factory.

Here we declare the type File_Storage as a limited controlled type. The procedures Initialize / Finalize are overridden to provide construction / destruction. Upon construction the file is opened. Upon destruction it is closed. The procedure Clean_Up is provided to delete the file. The function Store will be used to store an object. It returns the object key, which identifies the object there. The key has the type Key also declared in this package. It is the number of the record reserved for the object in the file. When the object is already persistent in the file, its key is returned, so it is safe to call Store multiple times. The function Restore is the operation opposite to Store. It takes the object key and returns a handle to the object. Restore is also safe to call multiple times. So when the object referenced by a key, is already memory resident, a handle to it is returned instead of creating a new memory resident copy. The type Handle from the package Deposit_Handles is used to reference persistent objects. Deposit_Handles.Handle is "renamed" to Deposit_Handle for convenience. The objects themselves are never referenced directly but through handles only.

A File_Storage object encapsulates the file and an index of all memory resident objects from that file. The index consists of Index_Records. One record is allocated per memory resident object. Index_Record is derived from Backward_Link to monitor what happens with the object. It also contains the object's key in the file. Two operations of Backward_Link need to be implemented: Deleted and Destroyed. The implementation of Deleted is called upon a request of object deletion. It does nothing in our case. Destroyed is called when the object is about to be finalized. In our case we store that object into the file. A more advanced implementation would check if the object was modified. It could also check if the object was requested for deletion and is no more referenced from other objects, in which case it can be removed from the persistent storage as well. But that would be too complex for a small illustrative example.

To reference Index_Record we will use handles provided by Record_Handles, an instantiation of Object.Handle. A handle to Index_Record is "renamed" to Record_Handle. Then we declare two maps: one to map objects to index records, another to map keys to the records. For this the package Generic_Map is instantiated once as Object_Maps and once as Key_Maps. Both use Record_Handle to reference Index_Record. So when the index record is deleted it is enough to remove it from the both maps and the object Index_Record will be automatically collected. Note also that Object_Map uses Deposit_Ptr, a pointer to the persistent object rather than a handle to it. It is important to allow object deletion. Otherwise an object would be never deleted as long as Index_Record referring it exists, i.e. up to File_Storage finalization. It would a thinkable, but too crude implementation. Generic_Map requires map keys be comparable, so the implementation declares "<" on Deposit_Ptr.

The type File_Record describes one record in the file. The field References is the list of the keys of all the objects referred by the object. Count is the length of the list. The field Descriptor is a string describing the object. The length of the string is the field Length.

The implementation of "<" uses Less defined on objects to order them. Clean_Up opens the file in Out_File mode and immediately closes it. This erases the file.

The procedure Write is defined to store an object under the specified key. It calls to Get_Referents to obtain the list of the objects the stored object needs. Then for each such object it calls Store to ensure the object persistency in the file. The keys returned by Store are placed into the References array. After that Write starts to form the field Description. It places the object class there (Get_Class) followed by a colon. Then object's Store is called to query the object description and to add it to Description. The completed object record is then written into the file.

The implementation of Initialize just opens the file for input / output and initializes the field Last_ID. Finalize goes through the index of memory resident objects (the key to object map). For each record of the index it calls Write to store the corresponding object and then removes the references to the index record from both maps. This in turn deletes the record itself. Note how This is used to get the object. The procedure Bind is defined to create an index record. It calls to Attach to bind Index_Record with the object and places handles to Index_Record in each of the maps. Ref is used to obtain them

The implementation of Store first looks into the index to check if it is already there. If yes it returns the key of the object. Otherwise it generates a new key by incrementing the field Last_ID and calls Bind to create a new index record.

The procedure Restore checks the index if an object with the specified key was already created. If yes it returns a handle to the object. This is used to get an object pointer from Index_Record. When the key identifies an unknown object, Restore reads its record from the file. The key is the record number. Restore goes through the array References and for each key calls itself to ensure this object to be restored too. The returned handle to that object is placed in a Deposit_List container. The container together with Descriptor's prefix (up to the first colon) as object's class name and the rest of it as the object's description, are passed to Create. That creates the object. A handle to it is then returned after Bind is called to place the object into the storage index.

The implementation of Deleted does nothing. Destroyed writes the object into the file and then removes it from the index.

2.4.2. Persistent objects implementation

Let's take binary tree node as an example of persistent object. A node may have up to two successors or none. Predecessor - successor relation is naturally mapped to dependant - referent.

The public part of the package declares the function Create_Node and the procedure Print. Create_Node creates a new node and returns a handle to it. All nodes are referenced using Handle of Deposit_Handles. Each node is identified by an integer number. The next two parameters of Create_Node are the handles to the left and right successors. They are defaulted to an invalid handle for which the function Nothing is also declared. It plays role of a constant invalid handle. The procedure Print is used for control.  It prints the tree rooted in the node specified by the parameter Root.

The private part is straightforward. It declares the type Node as a descendant of Deposit. The operations Get_Class, Get_Referents, Is_Modified, Reset_Modified, Restore and Store are overridden to provide implementations.

The implementation of Get_Referents places handles to the node successors into a Deposit_Container. The left successor is placed first. Is_Modified and Reset_Modified are void for sake of simplicity. So a node is always written into the persistent storage even if it is not changed.

The implementation of Restore first gets description of node dependencies from the source string. It is two characters. The first one is either '<' if there is a left successor or '-' otherwise. The second is '>' if there is a right successor or else '-'. After that it gets the node identifier (plain integer number). Then a new node object is allocated. Note that the target access type should be Deposit_Ptr to ensure right storage pool selection.

The procedure Store is reverse to Restore. Also the package defines a new class of persistent objects named Node. For this it calls Register_Class once upon elaboration with the class name and a pointer to Restore as parameters.

2.4.3. Test program

The test program is shown below. It consists of two sessions. In the first session an object is stored. In the second one it is restored.

The test program first calls Clean_Up to delete any existing storage file. Then it declares DB, a File_Storage object. After that a tree is created and Root becomes a handle to the tree root node. The tree is printed and then its root node is stored into DB. There result of the operation is the external key of the root node. This key can be used to restore the object. Note that the whole tree is stored because the any node depends on its child nodes. What Store does depends on the implementation. In our case physical file writing happens either upon finalization of the storage object (DB) or upon finalization of the persistent object (Root). Both objects are go out of scope at end closing the first session. The second session uses Restore and the external key to bring the root node back from the storage. Again, all the objects it depends on are restored as well. Finally, the restored tree is printed.

2.4.4. Test programs that use a predefined persistent storage

The test program that uses an ODBC data base as a persistent storage is shown below:

Then it declares DB, a Storage_Handle. The handle is initialized using the function Open defined in Test_ODBC_Session.adb. It prompts for connection parameters and then calls Persistent.ODBC.Create. After that a tree is created and Root becomes a handle to the tree root node. The tree is printed and then its root node is stored into DB as "The three". For this it calls Put. Note that the whole tree is stored because the any node depends on its child nodes. The second session uses Get and the name "The three" to bring the root node back from the storage. Again, all the objects it depends on are restored as well. Finally, the restored tree is printed. Carefully observe that the package Test_Persistent_Tree needed no modifications to be able to work with a different type of storage.

A the test program for APQ data base can be found in the file test_APQ_persistence.adb.

2.5. Abstract persistent storage

The package Persistent provides an abstract persistent storage communication object. The corresponding persistent storage can be implemented on the basis of a plain file, data base etc. Objects in the storage are identified by their names. Additionally anonymous objects can be created and deleted as required by the named ones. If an object depends on some other objects, then when stored into the storage, the referred objects are stored as well. If they do not already persist there, these objects will be anonymous. Anonymous persistent objects are subject of garbage collection. The way of collection is determined by the implementation.

The objects can be named. The object names are UTF-8 encoded strings. An  implementation can internally provide other encoding when the persistent storage natively supports Unicode different to UTF-8. Named objects are deleted only on explicit request or when they loose names becoming anonymous. Named objects build a hierarchy, where one named object can be a descendant of another. This hierarchy is a forest. The parent objects serve as folders for their children. It is not specified which nature parent objects should have. Objects of any kind can serve as parents. Also the parent-child relation does not impose any additional dependency between the objects. It is a relation solely between the names of.

The procedure Delete can be applied to a handle to the object in order to request its deletion. If the object cannot be deleted immediately it becomes anonymous for later collection. Persistent storage interfaces are itself objects and are a subject of garbage collection as well. When a named parent object becomes anonymous all its descendants do as well.

The package defines the abstract type Storage_Object which describes the interface of a persistent storage communication object. It is derived from Entity, so persistent storage interface objects are subject of garbage collection:

type Storage_Object is abstract new Object.Entity with private;
type Storage_Object_Ptr is access Storage_Object'Class;
for Storage_Object_Ptr'Storage_Pool
   use Object.Entity_Ptr'Storage_Pool;

It is strongly recommended not to directly use derivatives of Storage_Object. For this purpose serve handles to the objects.

The subtype Deposit_Handle is provided for convenience in referring persistent objects. It "renames" the handle type of the package Deposit_Handles:

subtype Deposit_Handle is Deposit_Handles.Handle;

The root-level objects have no parent. When a subprogram requires a parent specification the constant Root_Directory is used:

Root_Directory : constant Deposit_Handle;

The package instantiates Generic_Set to obtain sets of object names.

package Catalogue is
   new Generic_Set
       (  Object_Type  => Unbounded_String,
          Null_Element => Null_Unbounded_String
       );

The following operations are defined on Storage_Object:

function Get
         (  Storage : access Storage_Object;
            Name    : String;
            Parent  : Deposit_Handle := Root_Directory
         )  return Deposit_Handle is abstract;

This function returns a handle to a persistent object by its name and a handle to the parent object. The root-level objects have no parents, in which case Parent is an invalid handle. An implementation should first check if the the persistent object already has a memory-resident counterpart. Otherwise it should create one from the persistent storage.

function Get_Class
         (  Storage : access Storage_Object;
            Name    : String;
            Parent  : Deposit_Handle := Root_Directory
         )  return String is abstract;

This function returns the class of a persistent object by its name and a handle to the parent object.

function Get_Creation_Time
         (  Storage : access Storage_Object;
            Name    : String;
            Parent  : Deposit_Handle := Root_Directory
         )  return Time is abstract;

This function returns the creation time of a persistent object by its name and a handle to the parent object.

function Get_List
         (  Storage     : access Storage_Object;
            Prefix      : String := "";
            Suffix      : String := "";
            Equivalence : Unicode_Mapping_Function := null;
            Parent      : Deposit_Handle := Root_Directory
         )  return Catalogue.Set is abstract;

This function returns a complete list of all named objects persistent in Storage which have parent object specified by the parameter Parent. The list does not include anonymous persistent objects, which have neither parents nor names. Only names starting with Prefix and ending with Suffix are returned. When names are compared two characters are considered same if their corresponding values returned by Equivalence are same. When Equivalence is null, it is assumed an identity mapping. For case insensitive mappings see Strings_Edit.UTF8.Mapping.To_Lowercase. Prefix and Suffix may not overlap when matched. The list is a set of object names.

function Get_Name
         (  Storage : access Storage_Object;
            Object  : Deposit_Handle
         )  return String is abstract;

This function returns the object's name in Storage. The object is specified by its handle. Note that object names are relative to their parents, so only a pair name - parent does identify the object.

function Get_Parent
         (  Storage : access Storage_Object;
            Object  : Deposit_Handle
         )  return Deposit_Handle is abstract;

This function returns the object's parent in Storage. The object is specified by its handle.

function Is_Descendant
         (  Storage : access Storage_Object;
            Object  : Deposit_Handle;
            Parent  : Deposit_Handle
         )  return Boolean is abstract;

This function checks if Object is a direct or indirect descendant of Parent. The result is false if Object is invalid, or else specifies an anonymous or non-persisting in Storage object. Otherwise the result is true when Parent is invalid (i.e. identifies root-level objects) and false when Parent does not persist in Storage. Data_Error is propagated on error in Storage.

function Is_In
         (  Storage : access Storage_Object;
            Name    : String;
            Parent  : Deposit_Handle := Root_Directory
         )  return Boolean is abstract;
function Is_In
         (  Storage : access Storage_Object;
            Object  : Deposit_Handle
         )  return Boolean is abstract;

These functions check whether an object persists in Storage. The object can be identified either by its name and parent or by a handle to it. When Object is not a valid handle the result is false.

function Is_Named
         (  Storage : access Storage_Object;
            Object  : Deposit_Handle
         )  return Boolean is abstract;

These functions check whether Object persists and named in Storage. When Object is not a valid handle the result is false.

procedure Put
          (  Storage : in out Storage_Object;
             Object  : in out Deposit_Handle;
             Name    : String;
             Parent  : Deposit_Handle := Root_Directory
          )  is abstract;
procedure Put
          (  Storage : in out Storage_Object;
             Object  : in out Deposit_Handle
          )  is abstract;

These procedures are used to store Object in Storage. The parameters Name and Parent specify the object's name and parent in Storage. When omitted the object is stored as anonymous. Anonymous persistent objects are collected when not used, but not before their memory-resident counterpart vanishes. When Object already persists in Storage and Name and Parent are specified, then they are checked to be same. If this check fails, or Name is empty or illegal, or else conflicts with the name of another object Name_Error is propagated. When name is not specified, no check is made. 

procedure Rename
          (  Storage    : in out Storage_Object;
             Old_Name   : String;
             Old_Parent : Deposit_Handle := Root_Directory
             New_Name   : String;
             New_Parent : Deposit_Handle := Root_Directory
          )  is abstract;
procedure Rename
          (  Storage    : in out Storage_Object;
             Object     : in out Deposit_Handle;
             New_Name   : String;
             New_Parent : Deposit_Handle := Root_Directory
          )  is abstract;

These procedures change the name of the object specified by either its old name and parent (the parameters Old_Name, Old_Parent) or by a handle to it (the parameter Object). When renamed object was anonymous before renaming it becomes a named one. When Object is an invalid handle or does not refer to a persistent object then Constraint_Error is propagated. End_Error is propagated when Old_Name does not refer any persistent object. No object can become a parent of itself, so a check shall be made whether New_Parent specifies the object or any of its descendant. If yes, Name_Error is propagated.

procedure Unname
          (  Storage : in out Storage_Object;
             Name    : String;
             Parent  : Deposit_Handle := Root_Directory
          )  is abstract;
procedure Unname
          (  Storage : in out Storage_Object;
             Object  : in out Deposit_Handle
          )  is abstract;

These procedures make object anonymous. The object can be specified either by its name and parent or by a handle to it. Unnamed objects are automatically deleted when no more in use. Nothing happens if the object is already unnamed. Nothing also happens if Object is an invalid handle, not a handle to a persistent object or does not exist. Note that anonymous objects are not deleted as long as they have memory-resident counterparts. Observe the difference between Unname and Delete (Object.Archived.Delete) called on an object handle. Delete requests object deletion from both memory and persistent storage. Unname does it for persistent storage only. Both may have no immediate effect if the object is still in use. Note that when a parent object becomes anonymous so all its descendants do.

2.6. Handles to persistent storage

A persistent storage interface is itself an object, which can be referenced by another object. Usually it is a persistent object which memory-resident counterpart of is a proxy to the data in the persistent storage. For example, for a large data structure it might be very inefficient to load it all into the memory. In this case in the memory one would create a small proxy object, which will query the persistent storage for parts of the object's data as necessary. Such proxy object will require a reference to its persistent storage. This also would prevent the persistent storage interface object from premature destruction. This is why it is strongly recommended to use handles to persistent storage interface objects.

The package Persistent.Handle provides the type Storage_Handle, which serves as a handle to an abstract persistent storage interface object. It is guarantied that a persistent storage interface object will not be destroyed as long at least one handle refers to it.

type Storage_Handle is private;

The following operations are defined on Storage_Handle:

function Get
         (  Storage : Storage_Handle;
            Name    : String / Wide_String;
            Parent  : Deposit_Handle := Root_Directory
         )  return Deposit_Handle;

This function searches for the specified object by its name and parent. The name is an UTF-8 encoded string or else a wide string. If the object is already available a handle to it is returned. Otherwise it first is restored from the persistent storage.

function Get_Class
         (  Storage : access Storage_Handle;
            Name    : String / Wide_String;
            Parent  : Deposit_Handle := Root_Directory
         )  return String;

These functions return the class of a persistent object by its name and parent. The name can be specified either an UTF-8 encoded string or as a wide string.

function Get_Creation_Time
         (  Storage : access Storage_Handle;
            Name    : String / Wide_String;
            Parent  : Deposit_Handle := Root_Directory
         )  return Time;

These functions return the creation time of a persistent object by its name and parent. The name can be specified either an UTF-8 encoded string or as a wide string.

function Get_List
         (  Storage     : Storage_Handle;
            Prefix      : String := "";
            Suffix      : String := "";
            Equivalence : Unicode_Mapping_Function := null;
            Parent      : Deposit_Handle := Root_Directory
         )  return Catalogue.Set;
function Get_List
         (  Storage     : Storage_Handle;
            Prefix      : Wide_String;
            Suffix      : Wide_String;
            Equivalence : Unicode_Mapping_Function := null;
            Parent      : Deposit_Handle := Root_Directory
         )  return Catalogue.Set;

These functions return a list of all immediate children of Parent persistent in Storage. Only names starting with Prefix and ending with Suffix are eligible. When names are compared two characters are considered same if their corresponding values according to Equivalence are same. When Equivalence is null, it is assumed an identity mapping. For case insensitive mappings see Strings_Edit.UTF8.Mapping.To_Lowercase. Observe that Prefix may not overlap Suffix when matched. So if Prefix="AB" and Suffix="BC", then "ABC" does not fit, but "ABBC" does. The result of the function is a set of object names. Prefix and Suffix are either UTF-8 encoded or wide strings.

function Get_Name
         (  Storage : Storage_Handle;
            Object  : Deposit_Handle
         )  return String;

This function returns the object's name in Storage. The object is specified by its handle. The result is an UTF-8 encoded string. Note that the object names are relative to the object's parent.

function Get_Parent
         (  Storage : Storage_Handle;
            Object  : Deposit_Handle
         )  return Deposit_Handle;

This function returns the object's parent in Storage. The object is specified by its handle.

procedure Invalidate (Storage : in out Storage_Handle);

This procedure makes handle pointing to nothing. If it was the last reference to the persistent storage interface object, the latter is destroyed.

function Is_Descendant
         (  Storage : Storage_Handle;
            Object  : Deposit_Handle;
            Parent  : Deposit_Handle
         )  return Boolean;

This function checks if Object is a direct or indirect descendant of Parent. The result is false if Object is invalid, or else specifies an anonymous or non-persisting in Storage object. Otherwise the result is true when Parent is invalid (i.e. identifies root-level objects) and false when Parent does not persist in Storage. Data_Error is propagated on error in Storage.

function Is_In
         (  Storage : Storage_Handle;
            Name    : String / Wide_String;
            Parent  : Deposit_Handle := Root_Directory
         )  return Boolean;
function Is_In
         (  Storage : Storage_Handle;
            Object  : Deposit_Handle
         )  return Boolean;

These functions check whether an object persists in Storage. The object can be identified either by its name and parent or by a handle to it. When Object is not a valid handle the result is false. The name can be specified either an UTF-8 encoded string or as a wide string.

function Is_Named
         (  Storage : Storage_Handle;
            Object  : Deposit_Handle
         )  return Boolean;

These functions check whether Object persists and named in Storage. When Object is not a valid handle the result is false.

function Is_Valid (Storage : Storage_ Handle) return Boolean;

function Ptr (Storage : Storage_ Handle) return Storage_Object_Ptr;

procedure Put
          (  Storage : in out Storage_Handle;
             Object  : in out Deposit_Handle;
             Name    : String;
             Parent  : Deposit_Handle := Root_Directory
          );
procedure Put
          (  Storage : in out Storage_Handle;
             Object  : in out Deposit_Handle;
             Name    : Wide_String;
             Parent  : Deposit_Handle := Root_Directory
          );
procedure Put
          (  Storage : Storage_Handle;
             Object  : in out Deposit_Handle
          );

These procedures are used to store Object in Storage. The parameters Name and Parent specify the object name there. It can be specified either an UTF-8 encoded string or as a wide string. When the name is omitted the object is stored anonymous. Anonymous persistent objects are collected when no more used. It is safe to put an anonymous object into Storage and then reference it in another persistent object. When Object already persists in Storage and Name is specified, then it is checked that it is same. If this check fails, Name is empty, illegal, or conflicts with the name of another object Name_Error is propagated.

function Ref (Storage : Storage_Object_Ptr) return Storage_Handle;

This function obtains a handle to the persistent storage interface object. Having a handle to the object prevents object's premature destruction.

procedure Rename
          (  Storage    : in out Storage_Handle;
             Old_Name   : String;
             Old_Parent : Deposit_Handle := Root_Directory;
             New_Name   : String;
             New_Parent : Deposit_Handle := Root_Directory
          );
procedure Rename
          (  Storage    : in out Storage_Handle;
             Object     : in out Deposit_Handle;
             New_Name   : String;
             New_Parent : Deposit_Handle := Root_Directory;
          );
procedure Rename
          (  Storage    : in out Storage_Handle;
             Old_Name   : Wide_String;
             Old_Parent : Deposit_Handle := Root_Directory;
             New_Name   : Wide_String;
             New_Parent : Deposit_Handle := Root_Directory
          );
procedure Rename
          (  Storage    : in out Storage_Handle;
             Object     : in out Deposit_Handle;
             New_Name   : Wide_String;
             New_Parent : Deposit_Handle := Root_Directory
          );

These procedures change the name of the object specified either by its old name and parent (the parameter Old_Name, Old_Parent) or by a handle to it. The names can be specified either an UTF-8 encoded string or as a wide string. When the renamed object was anonymous before renaming it becomes a named one.

procedure Set (Storage : in out Storage_Handle; Object : Storage_Object_Ptr);

This procedure resets the handle Storage to a possibly another object. In the course of this operation the previously pointed object may be destroyed if Storage was the last handle pointing to it. It is safe when Object is the object already pointed by the handle. When Object is null, this procedure is equivalent to Invalidate.

procedure Unname
          (  Storage : in out Storage_Handle;
             Name    : String / Wide_String;
             Parent  : Deposit_Handle := Root_Directory
          );
procedure Unname
          (  Storage : in out Storage_Handle;
             Object  : in out Deposit_Handle
          );

These procedures make an object anonymous. The object can be specified either by its name and parent object or by a handle to it. The name is either an UTF-8 encoded string or a wide string. Unnamed objects are automatically deleted when no more in use. Nothing happens if the object is already unnamed. Nothing also happens if Object is an invalid handle, not a handle to a persistent object or does not exist. Note that anonymous objects are not deleted before objects pointed by either Object or Storage destroyed. There is a difference between Unname and Delete called on an object handle. Delete requests object deletion from both memory and persistent storage. Unname does it for persistent storage only. Both may have no immediate effect if the object is still in use. When an object becomes anonymous so do all its descendants.

2.7. Persistent storage factory

The package Persistent.Handle.Factory provides a factory of persistent storage objects.

function Create_APQ
         (  Server_Type    : Database_Type;
            Data_Base_Name : String;
            User_Name      : String;
            Password       : String;
            Host_Name      : String  := "localhost";
            Port_Number    : Natural := 0;
            Erase          : Boolean := False
         )  return Storage_Handle;

This function creates an APQ persistent storage interface object and returns a handle to it. The object is responsible for interacting with a data base via APQ bindings. A connection is established to the server specified by the parameter Host_Name. The parameter Server_Type identifies the data base engine. It can be Engine_PostgreSQL, Engine_MySQL etc, one of the supported by APQ engines. The enumeration type Database_Type is defined in the package APQ delivered with the APQ distribution. User_Name and Password identify the data base user. Data_Base_Name is the name of a data base managed by the server. Port_Number specifies the TCP/IP port listened by the server. When specified as 0, a reasonable default is used. The parameter Erase when true erases the data base contents by dropping all the tables used for storing persistent objects. If the data base contains any additional tables, they remain untouched.

function Create_ODBC
         (  Server_Name : String;
            User_Name   : String;
            Password    : String;
            Erase       : Boolean := False
         )  return Storage_Handle;
function Create_ODBC
         (  Server_Name : Wide_String;
            User_Name   : Wide_String;
            Password    : Wide_String;
            Erase       : Boolean := False
         )  return Storage_Handle;

This function creates a connection to an ODBC data base, i.e. any data base that has an ODBC driver and returns a valid handle to the persistent storage interface object to communicate the data base. The parameter Server_Name specifies the data server name. It denotes both the data base and the server (driver). The parameters User_Name and Password specify the user and the password to access the data base. All names here are UTF-8 encoded or wide strings.When the parameter Erase is set to true, all used tables are erased upon establishing the connection. One can use it if there is a possibility that the data base contains some corrupted or undesired data. So the data base would initially contain no persistent objects.

2.8. Persistent storage implementations

Simple components provide ready-to-use persistent storage implementations. The package Persistent.Handle.Factory supports run-time selection of the most suitable implementation. That might be undesirable, because the implementations rely on third party products such as GNADE and APQ. So Persistent.Handle.Factory needs all of them installed. Alternatively, if it is known that only a particular implementation will be actually used, one can do it directly without the factory. This will remove any dependency on other implementations. This section describes presently available implementations.

2.8.1. ODBC data bases

The package Persistent.ODBC provides an implementation of abstract persistent storage based on Open Database Connectivity (ODBC) interface to data bases. ODBC is provided for a great variety of platforms and data bases. The package declares the following subroutines:

function Create
         (  Server_Name : String;
            User_Name   : String;
            Password    : String;
            Erase       : Boolean := False
         )  return Storage_Handle;

This function creates a connection to an ODBC data base, i.e. any data base that has an ODBC driver and returns a valid handle to the persistent storage interface object to communicate the data base. The parameter Server_Name specifies the data server name. It denotes both the data base and the server (driver). The parameters User_Name and Password specify the user and the password to access the data base. All these parameters are UTF-8 encoded strings. When the parameter Erase is set to true, all used tables are erased upon establishing the connection. One can use it if there is a possibility that the data base contains some corrupted or undesired data. So the data base would initially contain no persistent objects.

procedure Disable_Tracing
          (  Storage : in out Storage_Handle
          );

This procedure disables tracing of SQL requests. Constraint_Error is propagated when Storage is not a handle to ODBC persistent storage.

procedure Enable_Tracing
          (  Storage : in out Storage_Handle;
             Name    : String
          );

This procedure starts tracing SQL requests using trace file Name. Constraint_Error is propagated when Storage is not a handle to ODBC persistent storage. Data_Error is propagated on any other error.

function Is_ODBC (Storage : Storage_Handle) return Boolean;

This function returns true if Storage is a valid handle to an ODBC persistent storage interface object.

function Serializable (Storage : Storage_Handle) return Boolean;

This function returns true if the ODBC driver communicated through Storage supports serializable transactions. Constraint_Error is propagated when Storage is not a valid handle to an ODBC persistent storage interface object.

function Unicode (Storage : Storage_Handle) return Boolean;

This function returns true if the ODBC driver communicated through Storage natively supports Unicode. Constraint_Error is propagated when Storage is not a valid handle to an ODBC persistent storage interface object.

Implementation notes. The implementation uses a minimal set of SQL features to support a greater number of data bases. Therefore almost everything, from generating unique keys to ON DELETE CASCADE is implemented without the data base engine. The most suitable types are selected according to the results of SQLGetTypeInfo. As the result the performance might be not optimal.

The minimal requirements for an ODBC driver:

The implementation tries to serialize data base transactions if the ODBC driver support it. In any case the manual-commit mode is used to provide atomic data base changes. The data base structure consists of three tables:

Table objects:

Tables backward_links and direct_links:

The software was tested with:

• MS Access (Office 2000 edition);
• MySQL 4.1 (see MySQL home page);
• PostgreSQL 8.2 (see PostgreSQL home page)

Some words of warning:

• The ODBC driver provided for MS Excel does not fulfill the requirements above and therefore cannot be used with Persistent.ODBC;
• MyODBC 3.51 for Linux seems to be corrupt (at least SQLGetData). Windows version works well;
• There should be something wrong with Unicode support in many ODBC drivers under Linux. The issue requires further investigation.

Installation notes. The implementation is based on GNADE 1.5.3a (GNat Ada Database Environment). The GNADE project is distributed under modified GNU Public License. To compile the package Persistent.Handle.Factory you will need a GNADE distribution, at least its part related to ODBC bindings. If you do not use Persistent.Handle.Factory, you need not compile it. For ODBC driver installation refer your data base documentation.

2.8.2. APQ-interfaced data bases

The package Persistent.APQ provides an implementation of abstract persistent storage based on Ada95 Database Binding to PostgreSQL/MySQL by Warren W. Gay VE3WWG (APQ). APQ supports a number of data bases accessed via a unified interface. The package Persistent.APQ provides the following subroutines:

function Create
         (  Server_Type    : Database_Type;
            Data_Base_Name : String;
            User_Name      : String;
            Password       : String;
            Host_Name      : String  := "localhost";
            Port_Number    : Natural := 0;
            Erase          : Boolean := False
         )  return Storage_Handle;

This function creates an APQ persistent storage interface object and returns a handle to it. The object is responsible for interacting with a data base via APQ bindings. A connection is established to the server specified by the parameter Host_Name. The parameter Server_Type identifies the data base engine. It can be Engine_PostgreSQL, Engine_MySQL etc, one of the supported by APQ engines. The enumeration type Database_Type is defined in the package APQ delivered with the APQ distribution. User_Name and Password identify the data base user. Data_Base_Name is the name of a data base managed by the server. Port_Number specifies the TCP/IP port listened by the server. When specified as 0, a reasonable default is used. The parameter Erase when true erases the data base contents by dropping all the tables used for storing persistent objects. If the data base contains any additional tables, they remain untouched.

procedure Disable_Tracing
          (  Storage : in out Storage_Handle
          );

This procedure disables tracing of SQL requests. Constraint_Error is propagated when Storage is not a handle to APQ persistent storage.

procedure Enable_Tracing
          (  Storage : in out Storage_Handle;
             Name    : String
          );

This procedure starts tracing SQL requests using trace file Name. Constraint_Error is propagated when Storage is not a handle to APQ persistent storage. Data_Error is propagated on any other error.

function Is_APQ (Storage : Storage_Handle) return Boolean;

This function returns true if Storage is a valid handle to an APQ persistent storage interface object.

Implementation notes. The data base structure consists of three tables:

Table objects:

Tables backward_links and direct_links:

The software was tested with:

• MySQL 4.1 (see MySQL home page);
• PostgreSQL 8.2 (see PostgreSQL home page)

It was not tested under Linux because APQ 2.1 was targeted to 3.x versions of MySQL.

Installation notes. The implementation is based on APQ 2.1. It can be found here. The APQ project is distributed under modified GNU Public License 2 and Ada Community Licenses. To compile the package Persistent.Handle.Factory you will need an APQ distribution. If you do not use Persistent.Handle.Factory, you need not to compile it. You might need to modify the sources in order to be able to work with the recent versions of GNAT compiler, PostgreSQL or MySQL.

2.9. Implementation of a new persistent storage

This chapter describes the internal packages used to ease implementation of a persistent storage backed by a data base.

2.9.1. Data bases

Usually persistent storage is implemented on the basis of an external data base engine. In that data base persistent objects are represented by records or other data structures identified by keys. The packages Persistent.Data_Bank, Persistent.Data_Bank.Index and Persistent.Data_Bank.Indexed are provided for interfacing such data bases. The package Persistent.Data_Bank is the parent package providing basic types. The package Persistent.Data_Bank.Index defines a storage index object to be used at run-time by the storage object. The package Persistent.Data_Bank.Indexed provides a specialized abstract storage which implements the abstract storage operation used the interface defined in Persistent.Data_Bank. That is used to derive a concrete implementation of persistent storage object, that will override the remaining abstract operations.

2.9.2. Storages with keys

The package Persistent.Data_Bank defines abstract interface of the storage objects which identify stored objects using a key. It derives the abstract base type Data_Bank_Object from Storage_Object:

type Data_Bank_Object is abstract
   new Storage_Object with private;

The keys are provided by implementations by deriving from the abstract base type Persistent_Key:

type Persistent_Key is abstract
   new Ada.Finalization.Controlled with null record;
type Persistent_Key_Ptr is access Persistent_Key'Class;

The arrays of keys are to be implemented by deriving from the abstract base type Persistent_Key_Array:

type Persistent_Key_Array is abstract
   new Ada.Finalization.Limited_Controlled with null record;

In order to support data base transactions a special access policy is imposed on Storage_Objects. The type Access_Mutex is used to represent transactions:

type Access_Mutex (Storage : access Data_Bank_Object'Class) is
   abstract new Ada.Finalization.Limited_Controlled with private;

This type is used as the base for storage specific objects that represent atomic actions on storage, such as data base transactions. Two concrete types are derived from it. Read_Mutex is used for
viewing storage content without modification. Write_Mutex is used for full access.

type Read_Mutex is new Access_Mutex with private;
type Write_Mutex is new Access_Mutex with private;

An operation that requires access to Storage_Object that might require data base communication should do it as follows:

declare
   Transaction : Write_Mutex (DB'Access);
begin
   -- Do something with DB
   Commit (Transaction);
end;

When Commit is not called on Transaction, because of exception propagation for instance, then Roll_Back will be in the course of Transaction finalization.

type Sharing_Type is (Fully, Read_Only, Read_Write);

Operations defined on mutexes:

procedure Commit (Mutex : in out Access_Mutex);

This procedure is basically one call:

Commit (Mutex.Storage.all);

Commit can be called only once. Multiple commits cause Use_Error propagation. Any other exception indicates a data base error.

procedure Finalize (Mutex : in out Access_Mutex);

The destructor calls Roll_Back if no Commit was called before. This ensures data base consistency upon transaction errors.

Operations defined on keys. Normally an implementation of a persistent storage would provide a derived key type. That should override the following abstract operations:

function Image
         (  Storage : Data_Bank_Object'Class;
            Key     : Persistent_Key
         )  return String is abstract;

This function returns a string unambiguously identifying Key in Storage. Constraint_Error is propagated when Key cannot be used for Storage.

function Null_Key return Persistent_Key is abstract;

This function returns a value that serves as an illegal key which can never indicate an object.

function Value
         (  Storage : Data_Bank_Object;
            Key     : String
         )  return Persistent_Key'Class is abstract;

This function converts string to a key. Data_Error is propagated when Key does not identify a valid key for Storage. The implementation should not check for any objects existing under the key.

function "<" (Left, Right : Persistent_Key)
   return Boolean is abstract;
function "=" (Left, Right : Persistent_Key)
   return Boolean is abstract;

Persistent keys are comparable to provide ordered containers.

Operations defined on arrays of keys. The following abstract operations shall be overridden by an implementation:

function Get
         (  Container : Persistent_Key_Array;
            Index     : Integer
         )  return Persistent_Key'Class is abstract;

This function returns a key by its index. Contraint_Error is propagated when index is wrong.

procedure Put
          (  Container : in out Persistent_Key_Array;
             Index     : Integer;
             Key       : Persistent_Key'Class
          )  is abstract;

This procedure places Key at the position in the array Container specified by Index. The array is expanded as necessary. When an implementation chooses a dense representation of the array it is allowed to fill unspecified array elements with Null_Key, which can be returned by Get without raising Constraint_Error.

Operations defined to handle transactions. Data_Bank_Object declares abstract operations on persistent storage supporting transaction framework:

function Get_Access_Mode (Storage : Data_Bank_Object)
   return Sharing_Type is abstract;

This function returns present sharing mode to Storage.

procedure Commit (Storage : in out Data_Bank_Object) is abstract;

This abstract procedure is called at the end of each transaction: an atomic modification of the persistent storage. There should be no difference between Roll_Back and Commit if the transaction was initiated by Seize_Read. Normally, Commit is never called directly, but only through Commit of a mutex object.

procedure Roll_Back (Storage : in out Data_Bank_Object) is abstract;

This procedure is called when a transaction fails, due to an exception. It is always called from an exception handler which re-raises the exception. For this reason it is not recommended to raise any exceptions in Roll_Back. There is no difference between Roll_Back and Commit if the transaction was initiated by Seize_Read. For a transaction initiated by Seize_Write an implementation should discard any changes made.

procedure Seize_Read
          (  Storage : in out Data_Bank_Object
          )  is abstract;

This procedure is called to initiate a read-only transaction with Storage. Only one transaction can be active at a time. The transaction is finished by either a call to Commit or to Roll_Back. For a read-only transaction there should be no sufficient difference between Commit and Roll_Back. 

procedure Seize_Write
          (  Storage : in out Data_Bank_Object
          )  is abstract;

This procedure is called to initiate a read/write transaction with Storage. Only one transaction can be active at a time. The transaction is finished by either a call to Commit or to Roll_Back.

Operations defined in terms of keys. It is recommended to check active transaction in implementations of abstract operations and to raise Use_Error. Though it is not mandatory. Carefully observe that object key is a class-wide parameter. An implementation would usually check if the key's specific type is one supported by the data base. If it is not then End_Error should be used to indicate an absent object, except when otherwise is explicitly specified.

The following operations should be implemented:

procedure Delete
          (  Storage : in out Data_Bank_Object;
             Key     : Persistent_Key'Class
          )  is abstract;

This procedure deletes an object by its key. An implementation may proceed from the assumption that all dependent objects are already deleted and no object refers to the deleted one. It can be called only within a transaction following a call Seize_Write.

function Find
         (  Storage : access Data_Bank_Object;
            Name    : Wide_String;
            Parent  : Persistent_Key'Class
         )  return Persistent_Key'Class is abstract;

This procedure is used to determine the object's key by the object's name and the key of its immediate parent. It is allowed only within a transaction initiated either by Seize_Read or Seize_Write. 

function Get
         (  Storage : access Data_Bank_Object;
            Key     : Persistent_Key'Class
         )  return Deposit_Handle is abstract;

This procedure restores a persistent object by its key. An implementation shall check if the object for the specified key is already memory-resident. It is allowed to call only within a transaction initiated either by Seize_Read or Seize_Write. 

procedure Get_Children
          (  Storage  : in out Data_Bank_Object;
             Key      : Persistent_Key'Class;
             Children : in out Persistent_Key_Array'Class;
             Pointer  : in out Integer
          )  is abstract;

Implementation adds the keys of the immediate children of the object specified by Key into the array Children. The first item is placed at Pointer. Then Pointer is advanced. Get_Children is allowed to call only within a transaction initiated either by Seize_Read or Seize_Write. An implementation need not to check that, but if it does then Use_Error should indicate failed check.

function Get_Class
         (  Storage    : in out Data_Bank_Object;
            Key        : Persistent_Key'Class;
         )  return String is abstract;

Implementation returns the object's class. The function is allowed only within a transaction initiated either by Seize_Read or Seize_Write. 

function Get_Creation_Time
         (  Storage    : in out Data_Bank_Object;
            Key        : Persistent_Key'Class;
         )  return Time is abstract;

Implementation returns the object's creation time. The function is allowed only within a transaction initiated either by Seize_Read or Seize_Write. 

procedure Get_Data
          (  Storage    : in out Data_Bank_Object;
             Key        : Persistent_Key'Class;
             Class      : out Unbounded_String;
             Data       : out Unbounded_String;
             Parameters : out Unbounded_String
          )  is abstract;

Implementation returns the object's description stored in Storage under Key. The description is used to restore the object. The output parameters are the object's class and data as they were generated by Object.Archived.Store and internally used Parameters, which describe the dependency list of the object being restored. The procedure is allowed only within a transaction initiated either by Seize_Read or Seize_Write. 

function Get_Dependant
         (  Storage : access Data_Bank_Object;
            Key     : Persistent_Key'Class;
            No      : Positive
         )  return Persistent_Key'Class is abstract;

This function is used to enumerate objects having backward links to the object specified by Key. That are ones which have specified the object in the list of backward links (the parameter Backward_Links of Store and Update). All dependants are enumerated starting from 1. The parameter No specifies the number of a dependant to get. An implementation is allowed to use a cache, so the caller should not undertake any actions which may lead to updating the dependency list of the object. The function is allowed only within a transaction initiated either by Seize_Read or Seize_Write. 

function Get_Name
         (  Storage : access Data_Bank_Object;
            Key     : Persistent_Key'Class;
            Parent  : access Persistent_Key'Class
         )  return String is abstract;

Implementation returns the object's name stored in Storage under Key. The result is UTF-8 encoded. When the object has a parent, then the implementation sets Parent to the key of. Otherwise it sets Null_Key there. The function is allowed only within a transaction initiated either by either by Seize_Read or Seize_Write. 

procedure Get_References
          (  Storage    : in out Data_Bank_Object;
             Key        : Persistent_Key'Class;
             References : in out Persistent_Key_Array'Class;
             Pointer    : in out Integer
          )  is abstract;

Implementation adds the keys of the immediate the objects referenced by the object specified by Key into the array References. The first item is placed at Pointer. Then Pointer is advanced. An implementation need not to go after the references of the references. The procedure Get_References is allowed to call only within a transaction initiated either by Seize_Read or Seize_Write. An implementation need not to check that, but if it does then Use_Error should indicate failed check.

function Has_Dependants
         (  Storage : access Data_Bank_Object;
            Key     : Persistent_Key'Class
         )  return Boolean is abstract;

An anonymous object that has no dependants can be deleted, but not before its memory-resident counterpart disappears. It counts only direct links to the object. When key does not specify any object, the result is false. This function is allowed only within a transaction initiated either by either by Seize_Read or Seize_Write. 

function Is_In
         (  Storage : access Data_Bank_Object;
            Key     : Persistent_Key'Class
         )  return Boolean is abstract;

This function checks whether Key specify an object persistent in Storage. It is allowed only within a transaction initiated either by either by Seize_Read or Seize_Write. 

procedure Put
          (  Storage : in out Data_Bank_Object;
             Key     : Persistent_Key'Class;
             Object  : Deposit'Class
          )  is abstract;

This procedure updates a persistent object by its key. Usually it calls Update for this purpose. It is within a transaction initiated by Seize_Write. 

procedure Rename
          (  Storage : in out Data_Bank_Object;
             Key     : Persistent_Key'Class;
             Name    : Wide_String;
             Parent  : Persistent_Key'Class
          )  is abstract;

This procedure changes the name of the object specified by Key to Name. The object's parent is specified by the parameter Parent. It is specified as Null_Key for a root-level object. When the renamed object was anonymous before renaming it becomes a named one. I.e. it will not deleted when no more in use. An implementation can proceed from the assumption that the caller has already checked for illegal and conflicting names. This procedure is allowed only within a transaction initiated by Seize_Write.

function Store
         (  Storage        : access Data_Bank_Object;
            Name           : String;
            Parent         : Persistent_Key'Class;
            Class          : String;
            Data           : String;
            Parameters     : String;
            Direct_Links   : Deposit_Set;
            Backward_Links : Deposit_Set
         )  return Persistent_Key'Class is abstract;
function Store
         (  Storage        : access Data_Bank_Object;
            Class          : String;
            Data           : String;
            Parameters     : String;
            Direct_Links   : Deposit_Set;
            Backward_Links : Deposit_Set
         )  return Persistent_Key'Class is abstract;

These functions are used to write a persistent object. They are called internally. The parameters Name and Parent specify the name of the object in the storage and its parent. The name should be an unique UTF-8 encoded name. When not specified, the object is anonymous. The parameter Data contains a string unambiguously describing the object of the class specified by the parameter Class. It is normally obtained using Object.Archived.Store. Parameters is used to store additional information about links. The parameters Direct_Links and Backward_Links define the set of objects in Storage the object depends on. Objects mentioned in the set Backward_Links are those which can be deleted without deletion of the object itself. The union of Direct_Links and Backward_Links specifies only directly visible dependencies, it is nCocsure. An implementation usually stores Class and Data under the name Name and corrects a persistent dependency table according to Direct_Links and Backward_Links. Note that initially written object is not referenced. Store is allowed only within a transaction by Seize_Write. 

procedure Unname
          (  Storage : in out Data_Bank_Object;
             Key     : Persistent_Key'Class
          )  is abstract;

This procedure makes the object specified by Key anonymous. The object object should be automatically deleted when no more in use, but not before it has a memory-resident counterpart. An implementation can proceed from the assumption that the caller already checked for object existence. The procedure is allowed only within a transaction by Seize_Write. 

procedure Update
          (  Storage        : in out Data_Bank_Object;
             Key            : Persistent_Key'Class;
             Class          : String;
             Data           : String;
             Parameters     : String;
             Direct_Links   : Deposit_Set;
             Backward_Links : Deposit_Set
          )  is abstract;

This procedure is used to update a modified persistent object. It is called internally. The parameter Data contains a string unambiguously describing the object of the class specified by the parameter Class. Parameters is used internally to store additional information about links. It is normally obtained using Object.Archived.Store. The parameters Direct_Links and Backward_Links are same as in Store. An implementation would normally update Class and Data in the object's record and correct persistent dependency table. Update is allowed only within a transaction by Seize_Write. 

2.9.3. Storage index

The child generic package Persistent.Data_Bank.Index implements an index of persistent objects:

generic
   type Data_Bank is abstract new Data_Bank_Object with private;
   type Key is new Persistent_Key with private;
package Persistent.Data_Bank.Index is
   type Catalogue (Storage : access Data_Bank'Class) is
      new Ada.Finalization.Limited_Controlled with private;
   type Catalogue_Ptr is access all Catalogue;
   ...

Persistent objects having memory-resident counterparts are said to be bound. For each bound object the storage index of the Catalogue type contains a record. When an object is requested from the persistent storage it is first searched in the index. The index also contains information about object's keys and names. Additionally the index registers a notification object to catch bound objects destruction. Upon destruction of a bound object index checks if the object was anonymous and no more referenced in the persistent storage, if so the object is deleted from the storage. If the memory-resident object was modified it is synchronized with the storage.

The package has two generic parameters:

• Data_Bank is a descendant of Data_Bank_Object for which index should be used;
• Key is a descendant of Persistent_Key, a concrete type of keys used with Data_Bank_Object.

2.9.4. Indexed storage

The child generic package Persistent.Data_Bank.Indexed implements persistent storage interface using the operations defined in Persistent.Data_Bank:

generic
   type Data_Bank is abstract new Data_Bank_Object with private;
   type Key is new Persistent_Key with private;
package Persistent.Data_Bank.Indexed is ...

The generic parameters:

• Data_Bank is a descendant of Data_Bank_Object. It can be Data_Bank_Object itself;
• Key is a descendant of Persistent_Key, a concrete type of keys used with Data_Bank_Object.

The package provides the abstract type Indexed_Storage_Object which can be used as the base type for a concrete implementation of a data base interface:

type Indexed_Storage_Object is abstract new Data_Bank with private;

The derived type shall implement the following remaining operations:

• Commit to confirm a transaction with data base;
• Delete to delete an object by key;
• Find to find an object by name;
• Get_Children to get object's immediate children;
• Get_Class to get the object's class;
• Get_Creation_Time to get the object's creation time;
• Get_Data to get object's description string;
• Get_Dependant to enumerate dependants with backward links;
• Get_List to get the list of all persistent objects;
• Get_Name to get the object's name and parent;
• Get_References to get the objects immediately referenced by an object;
• Has_Dependants to check if an object can be deleted;
• Is_In to check if the object in the storage, by key;
• Put to store an object by key;
• Rename to set or change the object name;
• Roll_Back to discard changes made by a transaction;
• Seize_Read to initiate a read-only transaction;
• Seize_Write to initiate a read/write transaction;
• Store to create a new persistent object;
• Unname to remove object's name;
• Update to modify a persistent object.

Tasking. The implementation provided by default is task-safe. The operations on  Indexed_Storage_Object can be called from concurrent tasks. An unsafe implementation is provided in the subdirectory single-task. The implementation choice in GNAT Ada projects is controlled by the variable "Tasking." When compiled manually or with a compiler other than GNAT, the corresponding implementation must be chosen manually.

2.9.5. Proxy objects

Persistent objects that are not fully represented by their memory-resident counterparts require a reference to the storage they persist in. This is necessary at least to prevent persistent storage interface object from being prematurely destroyed. Further the operation Object.Archived.Restore does not contain a parameter referencing the storage. Special objects of the type Self_Reference defined in the child package Persistent.Data_Bank.Reference serve this purpose. An object may put a Self_Reference in its dependency list (see Object.Archived.Get_Referents) by calling the procedure Add from this package. If it does so then in its Restore it will find a Self_Reference again. The fields of that object denote the persistent storage and the object's key there.

type Self_Reference is new Deposit with record
   Storage : Storage_Handle;
   Key     : Persistent_Key_Ptr;
end record;

The following operations are defined on Self_Reference:

procedure Add
          (  List    : in out Deposit_Container'Class;
             Storage : Storage_Handle;
             Key     : Persistent_Key'Class
          );

This procedure adds to List a reference to Storage. Key is the Storage key of the object that requires a reference to Storage. The reference is placed at the list end. Other operations are implementations of the interface defined in Object.Archived.

The following sample code illustrates using Self_Reference objects. A user-defined persistent object is Proxy_Object. It contains a handle to the storage where it persists and implements some of its operations through communication to the storage. For example, it can be a large array of data stored there. When a piece of data is requested Proxy_Object routes the request to the storage and returns the result. Additionally Proxy_Object contains its key in the storage. Proxy_Object should call Add from its Get_Referents to add reference to the storage in its dependency list. Then upon restore it will find a Self_Reference object in the list passed to its Restore:

type Proxy_Object is new Deposit with record
   Storage : Storage_Handle; -- The storage used
   Key     : Storage_Key;    -- The storage key of the object
   ... 
end record;

procedure Get_Referents
          (  Object : Proxy_Object;
             List   : in out Deposit_Container'Class
          )  is
begin
   Add
   (  List,
      Object.Storage,
      Object.Key
   );
   ... -- adding other dependencies if any
end Get_Referents;

procedure Restore
          (  Source  : String;
             Pointer : in out Integer;
             Class   : String;
             List    : Deposit_Container'Class;
             Object  : out Deposit_Ptr
          )  is
   Object    : Deposit_Ptr := new Proxy_Object;
   Proxy     : Proxy_Object renames Proxy_Object (Result.all);
   Reference : Self_Reference'Class renames
                  Self_Reference'Class (Get (List, 1).all);
begin
   Proxy.Storage := Reference.Storage;
   Proxy.Key     := Storage_Key (Reference.Key.all);
   ... -- restoring the rest of Proxy_Object as necessary
end Restore;

2.10. Visual browsing of a persistent storage

The package Gtk.Persistent_Storage_Browser provides GTK+ widgets for visual browsing of persistent storages. It is a part of the GtkAda contribution software.

3. Sets and Maps

Note that only objects of non-limited type can be used in sets and maps. To have sets of limited objects use pointers or handles as elements. For sets of handles also see Object.Handle.Generic_Set. For maps of strings see Tables.

3.1. Sets

The package Generic_Set defines the type Set. An instance of the type is a set of items. One can add to and remove from items of the set. Items of the set can be accessed using the positive index. They are ordered, so the set implementation may use binary search. There is a null item, which is never included into the set and is used to mark free memory slots. The package is generic and has the following generic parameters:

generic
   type Object_Type is private;
   Null_Element : Object_Type;
   Minimal_Size : Positive := 64;
   Increment    : Natural  := 50;
   with function "<" (Left, Right : Object_Type) return Boolean is <>;
   with function "=" (Left, Right : Object_Type) return Boolean is <>;
package Generic_Set is
   type Set is new Ada.Finalization.Controlled with private;
   ...

Here:

• Object_Type is the type of set items;
• Null_Element is a value of Object_Type used as a null item;
• Minimal_Size is the minimal number of items by which the internal buffer of the set is enlarged. When the first item is put into the set, this will be the initial buffer size.
• Increment controls further buffer enlargements. The buffer is enlarged by n*Increment/100, where n is the current buffer size. If the evaluated increment of the buffer is less than Minimal_Size items, then the later is used instead. For instance, if the set size should grow linearly by m items per increment, then Minimal_Size=m, Increment=0. If the set should grow exponentially, for instance, by doubling its size per increment, then Increment should be 100, while Minimal_Size could be the initial non-empty set size.
• "<" and "=" are used to order items in the set.

Sets can be assigned. Assignment makes no deep copy, which is delayed until the time moment when the original and a copy become different. Items in the set are ordered so that lesser items have lesser indices, when indexed. The first item in the set has index 1.

The following operations are defined on Set:

procedure Add (Container : in out Set; Item  : Object_Type);
procedure Add (Container : in out Set; Items : Set);

These procedures are used to add an item to a set or all items of one set to another. Nothing happens if the item is already in the set or is a Null_Element. Note that items are compared using the provided operations "<" and "=". It is possible that these operations treat different items as same. Only one item from such equivalence class may be in a set. To control which one will be inserted use Insert and Replace.

function Create return Set;

This function returns an empty set.

procedure Erase (Container : in out Set);

This procedure removes all items from the set.

function Find (Container : Set; Item : Object_Type)
   return Integer;

This function is used to find an item in the set Container. The result is either a positive index of the found item or a negated index of the place where the item should be if it were in the set.

function Get (Container : Set; Index : Positive)
   return Object_Type;

function Get_Size (Container : Set) return Natural;

This function returns the number of items in the set.

procedure Insert (Container : in out Set; Item : in out Object_Type);

This procedure inserts an item into a set. Nothing happens if the item is Null_Element. When Container already has an element equivalent to Item, then Item will not replace it. Instead of that the element from Container will be returned through Item. So upon completion Item always has the value of the element in Container.

procedure Insert (Container : in out Set; Item : Object_Type; Inserted : out Boolean);

This procedure inserts an item into a set. Item is inserted only if it is not Null_Element and is not already in Container. When inserted Inserted is set to true. Otherwise it is to false..

function Is_Empty (Container : Set) return Boolean;

True is returned if Container is empty.

function Is_In (Container : Set; Item : Object_Type)
   return Boolean;

True is returned if Item is in Container.

procedure Remove (Container : in out Set; Item  : Object_Type);
procedure Remove (Container : in out Set; Items : Set);

These procedures are used to remove items from the set Container. An item can be removed either explicitly, or by specifying a set of items to be removed. If a particular item is not in the set, then nothing happens.

procedure Remove
          (  Container : in out Set;
             Item      : Object_Type;
             Removed   : out Boolean);

This procedure is a variant of the procedure Remove with the third parameter set to true when Item was in the set before its removal. Otherwise it is set to false.

procedure Remove (Container : in out Set; Index : Positive);

This procedures removes an item from the set Container by its positive index. Constraint_Error is propagated when item index is wrong.

procedure Replace (Container : in out Set; Item : Object_Type);
procedure Replace (Container : in out Set; Items : Set);

function "and" (Left, Right : Set) return Set;
function "or"  (Left, Right : Set) return Set;
function "xor" (Left, Right : Set) return Set;

These functions are conventional set operations - intersection, union, difference. Difference is defined as a set which items are only in one of the sets Left and Right.

function "=" (Left, Right : Set) return Boolean;

True is returned if both sets contain same items.

3.2. Maps

The package Generic_Map defines the type Map which represents an associative array. One can add to and remove from items of the map. Each item has an unique key associated with it. In other word a map is a function which for a given key yields an item. Items of the map can be also accessed using the positive index. Items in the map are ordered according to their keys, so the map implementation may use binary search. Reference counting is used for the objects of the type Map, which means that assigning Map objects is relatively cheap. The package is generic and has the following generic parameters:

generic
   type Key_Type is private;
   type Object_Type is private;
   Minimal_Size : Positive := 64;
   Increment    : Natural  := 50;
   with function "<" (Left, Right : Key_Type) return Boolean is <>;
   with function "=" (Left, Right : Key_Type) return Boolean is <>;
package Generic_Map is
   type Map is new Ada.Finalization.Controlled with private;
   ...

Here:

• Key_Type is the type of the association keys;
• Object_Type is the type of map items;
• Minimal_Size is the minimal number of items by which the internal buffer of the map is enlarged. When the first item is put into the map, this will be the initial buffer size.
• Increment controls further buffer enlargements. The buffer is enlarged by n*Increment/100, where n is the current buffer size. If the evaluated increment of the buffer is less than Minimal_Size items, then the later is used instead.
• "<" and "=" are used to order keys of the items in the map.

Both Key_Type and Object_Type can be controlled. The implementation warranties that when an item or key is no more used in the map it is erased by assigning it a value created by the default constructor (if any). This behavior ensures that items and keys removed from the map will be always finalized upon the operation. For example, when Object_Type is controlled, then Finalize will be called upon an item of Object_Type even if the item is not replaced but removed from a map. This happens through assigning some other object of Object_Type to the removed item. So when item is a Handle, then the reference count of an object it refers will be decreased as expected. On assignment no deep copy of a map is made. Deep copy is postponed till the time moment when the original and a copy become different. Items in the map are ordered according to their keys, so that items with lesser keys have lesser indices, when indexed. The first item in the map has index 1.

The following operations are defined on the type Map:

procedure Add
          (  Container : in out Map;
             Key       : Key_Type;
             Item      : Object_Type
          );

This procedure adds a new item (Item) to the map Container. Constraint_Error propagates if Container already contains an item with the key equal to Key.

procedure Add (Container : in out Map; Items : Map);

This procedure adds all items of Items to Container. If Container already has an item with the key equal to an item from Items, then that item from Items is ignored.

function Create return Map;

This function returns an empty map.

procedure Erase (Container : in out Map);

This procedure removes all items from Container.

function Find (Container : Map; Key : Key_Type) return Integer;

This function is used to find an item in the map Container. The result is either a positive index of the found item or a negated index of the place where the item should be if it were in the map.

function Get (Container : Map; Key : Key_Type) return Object_Type;

This returns an item of the map Container by its key. Constraint_Error is propagated if there is no item with the key equal to Key.

function Get (Container : Map; Index : Positive) return Object_Type;

This function is used to get an item of the map Container using positive index. Constraint_Error is propagated if Index is wrong. Note that item index may change when items are added or removed.

function Get_Key (Container : Map; Index : Positive) return Key_Type;

function Get_Size (Container : Map) return Natural;

This function returns the number of items in the map.

function Is_Empty (Container : Map) return Boolean;

True is returned if Container is empty.

function Is_In (Container : Map; Key : Key_Type)
   return Boolean;

True is returned if Container has an item for Key.

procedure Remove (Container : in out Map; Item  : Key_Type);
procedure Remove (Container : in out Map; Items : Set);

These procedures are used to remove items from the map Container. An item can be removed either by its key, or by specifying a map of items to be removed. If a particular item is not in the map, then nothing happens.

procedure Remove (Container : in out Map; Index : Positive);

This procedures removes an items from the map Container by its positive index. Constraint_Error is propagated when item index is wrong.

procedure Replace
          (  Container : in out Map;
             Key       : Key_Type;
             Item      : Object_Type
          );
procedure Replace
          (  Container : in out Map;
             Items     : Map
          );

procedure Replace
          (  Container : in out Map;
             Index     : Positive;
             Item      : Object_Type
          );

4. Unbounded arrays

The package Generic_Unbounded_Array defines the type Unbounded_Array. An instance of the type is a dynamically expanded vector of elements. The implementation keeps vector contiguous, so it might be very inefficient to put complex data structures into the array. In many cases it is better to put pointers to elements there. See also the package Generic_Unbounded_Ptr_Array which instantiates Generic_Unbounded_Array for this purpose. The type wraps the component Vector which is a pointer to an array of elements. One can use Vector to access array elements and query its present bounds, which are rather arbitrary. The unused  elements of the array vector are padded using a distinguished null-element value The package Generic_Unbounded_Array is generic and has the following generic parameters:

generic
   type Index_Type is (<>);
   type Object_Type is private;
   type Object_Array_Type is
      array (Index_Type range <>) of Object_Type;
   Null_Element : Object_Type;
   Minimal_Size : Positive := 64;
   Increment    : Natural  := 50;
package Generic_Unbounded_Array is ...

Here:

• Index_Type is the type used to index the array elements;
• Object_Type is the type of array elements;
• Object_Array_Type is an array type built on Index_Type and Object_Type. This is the type of the array's vector;
• Null_Element is a value of Object_Type used as a null element;
• Minimal_Size is the minimal number of elements by which the array vector is enlarged. When the first element is put into the array, this will be the initial vector size.
• Increment governs further vector enlargements. The vector is enlarged by n*Increment/100, where n is the current vector size. If the evaluated increment of the vector is less than Minimal_Size elements, then the latter is used instead.

The type Unbounded_Array is declared as follows:

type Object_Array_Ptr is access Object_Array_Type;
type Unbounded_Array is
   new Ada.Finalization.Limited_Controlled with
record
   Vector : Object_Array_Ptr := null;
end record;

Array elements can be accessed through indexing the component Vector. Note that single what can be said about the length of the vector is that it is big enough to keep all elements put into the array. The unused elements in the vector are padded using the value Null_Element. The implementation is very straightforward. It does not implement any optimization of assignments, like the implementation of Generic_Set does. This choice was intentionally made to mimic arrays as close as possible. If reference counting is needed a wrapper type could be built around Unbounded_Array. The following operations are defined on Unbounded_Array:

procedure Erase (Container : in out Unbounded_Array);

This procedure removes all elements from Container making it empty.

procedure Finalize (Container : in out Unbounded_Array);

The destructor frees the memory allocated for the array vector.

function Fetch
         (  Container : Unbounded_Array;
            Index     : Index_Type
         )  return Object_Type;

This function returns a container element or Null_Element if Index is out of vector range.

function Get
         (  Container : Unbounded_Array;
            Index     : Index_Type
         )  return Object_Type;

This function is an equivalent to Container.Vector (Index). Constraint_Error is propagated if Index is out of vector range.

procedure Put
          (  Container : in out Unbounded_Array;
             Index     : Index_Type;
             Element   : Object_Type
          );

5. Unbounded arrays of pointers

The package Generic_Unbounded_Ptr_Array defines the type Unbounded_Ptr_Array. An instance of Unbounded_Ptr_Array is a dynamically expanded vector of pointers to elements. Upon destruction objects pointed by array elements are destroyed. Same happens when an element is replaced. The package has the following generic parameters:

generic
   type Index_Type is (<>);
   type Object_Type (<>) is limited private;
   type Object_Ptr_Type is access Object_Type;
   type Object_Ptr_Array_Type is
      array (Index_Type range <>) of Object_Ptr_Type;
   Minimal_Size : Positive := 64;
   Increment    : Natural  := 50;
package Generic_Unbounded_Ptr_Array is ...

Here:

• Index_Type is the type used to index the array elements;
• Object_Type is the type of array elements;
• Object_Ptr_Type is an access type for Object_Type;
• Object_Array_Ptr_Type is an array type built on Index_Type and Object_Ptr_Type. This is the type of the array's vector;
• Minimal_Size is the minimal number of elements by which the array vector is enlarged. When the first element is put into the array, this will be the initial vector size.
• Increment governs further vector enlargements. The vector is enlarged by n*Increment/100, where n is the current vector size. If the evaluated increment of the vector is less than Minimal_Size elements, then the latter is used instead.

The type Unbounded_Ptr_Array is declared through an instantiation of the package Generic_Unbounded_Array. Array elements can be accessed through indexing the component Vector which are pointers to the elements. Note that single what can be said about the length of the vector is that it is big enough to keep all elements put into the array. The unused elements in the vector are padded using null. The following operations are defined on Unbounded_Ptr_Array:

procedure Erase (Container : in out Unbounded_Array);

This procedure removes all elements from Container making it empty.

procedure Finalize (Container : in out Unbounded_Ptr_Array);

The destructor frees the memory allocated for the array vector and all elements it refers to.

function Get
         (  Container : Unbounded_Ptr_Array;
            Index     : Index_Type
         )  return Object_Ptr_Type;

This function is an equivalent to Container.Vector (Index) with the exception that null is returned when Index is out of vector range.

procedure Put
          (  Container : in out Unbounded_Ptr_Array;
             Index     : Index_Type;
             Element   : Object_Ptr_Type
          );

This procedure is used to put in / replace an array element using its index. If the replaced array element is not null then the object it points to is destroyed. Note that the object pointed by Element is not copied. Thus it is not a responsibility of the caller to destroy the object. It will be automatically destroyed upon array destruction or replacing the element in the array. The array vector is expanded as necessary. Unused elements are padded with null.

The implementation of Generic_Segmented_Stack provides an illustration of use Generic_Unbounded_Ptr_Array. A segmented stack consists of segments of same size. The list of segments is viewed as an abstract array used to instantiate Generic_Stack. The array index is split into the high-order index indicating a segment and the low-order one specifying the element in the segment. The list of segments is implemented as an Unbounded_Ptr_Array indexed by the high-order index. Observe that once allocated a segment gets referenced in Unbounded_Ptr_Array, so there is no need to explicitly deallocate segments, Unbounded_Ptr_Array willl do it. So the implementation of Generic_Segmented_Stack can be as straightforward as:

• Declaration of the type of segments as a fixed sized array of stack elements;
• Instantiation of Generic_Unbounded_Ptr_Array using the segment type;
• Instantiation of Generic_Stack based on that unbounded array.

6. Stacks

Stack, also LIFO Stack (Last in First Out), is a container in which the only accessible element is the last one.

6.1. Stacks based on abstract arrays

The package Generic_Stack defines the type Stack which provides a generic stack. The stack is built upon an array type which might be a Unbounded_Array, Unbounded_Ptr_Array, array of handles or some other type (like Unbounded_String). The package has the following generic parameters:

generic
   type Index_Type is (<>);
   type Object_Type (<>) is limited private;
   type Array_Type is limited private;
   Null_Element : Object_Type;
   with function Get
                 (  Container : Array_Type;
                    Index     : Index_Type
                 )  return Object_Type is <>;
   with procedure Put
                  (  Container : in out Array_Type;
                     Index     : Index_Type;
                     Element   : Object_Type
                  )  is <>;
package Generic_Stack is
   type Stack is new Ada.Finalization.Limited_Controlled with private;

Here the formal parameters are:

• Index_Type is the type used to index the array elements;
• Object_Type is the type of array / stack elements;
• Array_Type is a private limited type implementing an array indexed by Index_Type and containing Object_Ptr_Type;
• Null_Element is a value of Object_Type used as a null element. The items removed from the stack are always padded with Null_Element. This warranties that for a stack built on Unbounded_Ptr_Array the popped items will be indeed destroyed. Observe that for this reason a function Pop is not provided, because there is no safe way to return a popped object without copying it;
• Get is the function used to get an array element by its index. It is never called for elements which were not previously put using the procedure Put. Thus any range checks can be omitted;
• Put is the procedure used to store array elements. When it is called for some array new index, for which it was not called before, then the index value is the next following the last new index. In other words the array grows by one element at time. The stack can have a limited size. If so then Put is allowed to raise an exception when the value of the parameter Index is out of limit.

The following operations are defined on Stack:

procedure Erase (Container : in out Stack);

This procedure pops all items from the stack Container.

function Get (Container : Stack; Index : Index_Type)
   return Object_Type;

This function returns the stack item with the index specified by the parameter Index. The item item on the stack top has the index returned by Mark, so that

Top (Container) = Get (Container, Mark (Container))

Constraint_Error is propagated if Index points out of stack.

function Is_Empty (Container : Stack) return Boolean;

This function returns true if Container is empty.

function Mark (Container : Stack) return Index_Type;

The value returned by this function can be used in the procedure Release to pop all the items pushed in between. When the type Index_Type is an integer type, then the difference between two values returned by Mark is the number of stack items.

procedure Pop (Container : in out Stack; Count : Natural := 1);

This procedure pops Count items from the top of Container. If the stack does not contain enough items, it is emptied.

procedure Push (Container : in out Stack; Item : Object_Type);

This procedure pushes Item onto Container.

procedure Put
          (  Container : in out Stack;
             Index     : Index_Type;
             Element   : Object_Type
          );

This procedure replaces the stack item specified by the parameter Index with Element. The index is same as described in Get. Constraint_Error is propagated if Index points out of stack.

procedure Release (Container : in out Stack; Mark : Index_Type);

This procedure is used to pop all items pushed since a call to the function Mark which result was the value of the parameter Mark. Nothing happens if the stack was already popped below Mark.

function Top (Container : Stack) return Object_Type;

This function returns the topmost stack item. Constraint_Error is propagated if Container is empty.

6.2. Segmented stacks

The package Generic_Segmented_Stack instantiates Generic_Stack so that the stack will use a list of segments of same size. The number of stack segments is unlimited. New segments are allocated as necessary. The package is generic:

generic
   type Index_Type is (<>);
   type Object_Type is private;
   Null_Element : Object_Type;
   Segment_Size : Positive := 128;
   Minimal_Size : Positive := 64;
   Increment    : Natural  := 50;
package Generic_Segmented_Stack is
   ...
   package Segmented_Stack is new Generic_Stack ...

Here the formal parameters are:

• Index_Type is the type used to index the stack elements. It can be used to mark and release the stack;
• Object_Type is the type of the stack elements;
• Null_Element is a value of Object_Type used as a null element. The items removed from the stack are always padded with Null_Element;
• Segment_Size is the size of a stack segment in slots;
• Minimal_Size of the segment slots array. This parameter and the next one control allocation of the array segment slots;
• Increment. When there is no free space the stack is enlarged by allocation a new segment. A reference to the segment is placed in an array of the segment slots. That array is enlarged by allocating Size * Increment / 100 new slots. Here Size is the current number of slots. The allocated amount of slots cannot be less than the parameter Minimal_Size specifies. So it will be the initial size after the first segment gets allocated.

The package can be used as follows:

package Float_Stack is
   new Generic_Segmented_Stack (Integer, Float, 0.0);
use Float_Stack.Segmented_Stack;
...
LIFO : Stack;

7. Pools

User-defined storage pools can be used for objects which creation / destruction policy allows a more efficient memory management strategy than the standard heap offers, but yet not enough strict to allocate them on the system stack.

7.1. Stack pool

The package Stack_Storage provides an implementation of a user-defined pool organized as a stack. The package the type Pool derived form System.Storage_Pools.Root_Storage_Pool:

type Pool
     (  Initial_Size : Storage_Count;
        Items_Number : Positive
     )  is new Root_Storage_Pool with private;

A stack pool consists of contiguous segments allocated dynamically as necessary. The discriminants control the stack segments allocation policy. Initial_Size determines the initial default size of a newly allocated segment. If this size is less than the size of the object being allocated the default size is set to the object size multiplied to Items_Number. This value will then used as the default size for all further segments. The segments allocated earlier having lesser size will be freed when possible. Otherwise, they remain allocated until pool destruction. Upon stack pool destruction, all the stack segments are deallocated. No checks made whether some objects remain allocated on the stack. Note also that no checks made whether objects allocation / deallocation order is indeed LIFO (last in, first out). Deallocation of an object frees the memory of all objects allocated after it. The stack pool is not task-safe. If that is required it has to be protected from a concurrent access.

7.2. Mark and release pool for controlled objects

The generic child package Stack_Storage.Mark_And_Release provides an implementation of a mark and release pool for limited controlled objects:

generic
   Stack : in out Pool'Class;
package Stack_Storage.Mark_And_Release is ...

The generic parameter Stack is a descendant of Pool, a stack pool. The package defines:

type Pool_Object is
   new Ada.Finalization.Limited_Controlled with private;

This is the base type for all objects to be allocated on Stack. The pool objects should be allocated only in the pool (using an allocator new). If they are destroyed explicitly using Unchecked_Deallocation, then it should happen LIFO and never under the last pool mark. The type Pool_Object has the following operations:

procedure Finalize (Object : in out Pool_Object);

The destructor has to be called by all descendants of Pool_Object. Storage_Error is propagated if Object is not the last allocated object in the pool.

procedure Initialize (Object : in out Pool_Object);

type Pool_Object_Ptr is access Pool_Object'Class;
for Pool_Object_Ptr'Storage_Pool use Stack;

This is the access type, which can be used as the target for an allocator of a Pool_Object descendant. If other access type used as the target, then it has to be specific to the pool Stack.

type Pool_Mark is
   new Ada.Finalization.Limited_Controlled with private;

Objects of Pool_Mark are used as snap-shots of the pool state. When such a pool mark object is created it remembers the pool state. Upon its destruction it finalizes all the objects allocated in the pool since its construction and reclaims the storage occupied by the objects. If some pool objects have to be destroyed explicitly, then that shall be ones created after the last pool mark creation only. The following operations are defined on Pool_Mark:

procedure Finalize (Snap : in out Pool_Mark);

The destructor removes all objects remaining in the pool since construction of Snap. Storage_Error is propagated on object finalization errors.

procedure Initialize (Snap : in out Pool_Mark);

The constructor remembers the pool state.

The following short code sample illustrates use of mark and release pool:

declare
   Snap : Pool_Mark;  -- Mark the pool state
   Ptr  : Pool_Object_Ptr;
begin
   ...
   Ptr := new Derived_Pool_Object;         -- Allocate
   ...
   Ptr := new Another_Derived_Pool_Object; -- Allocate
   ...
end;                  -- Release all allocated objects

8. Doubly-linked networks

The generic package Generic_Doubly_Linked_Web provides double-linked networks of items:

generic
   type List_Identification_Type is (<>);
   type List_Item_Type (<>) is limited private;
   Pool : in out Root_Storage_Pool'Class;
package Generic_Doubly_Linked_Web is ...

The items can be of any type as specifies the formal parameter List_Item_Type. This includes limited and unconstrained types. They are not required to be tagged. So protected objects or tasks can be items. The items are never copied when inserted into, moved along or removed from a list. All operations on the network lists and their items are referential. Insertion and removal are O(1). An item of the network may participate several lists of different types. The set of distinct list types is determined by the formal parameter List_Identification_Type, which is a discrete type. For each value of this type each item has a pair of pointers (links). So the number of values of List_Identification_Type is the number of lists an item can be simultaneously situated in. For a standard doubly-linked list where an item can be in only one list, the parameter List_Identification_Type could be, for example:

   type List_Identification is (The_List);

For multiple lists as illustrated on the figure below, it could be:

   type List_Identification is (Blue, Green, Red);

The figure shows 5 items forming a network of 4 lists of 3 different types. For instance, the item B is in the blue list A-B-C-D, green list B-C-D and red list B-C-D-E.

The items are allocated in the storage pool specified by the formal parameter Pool. The service data (links) associated with an item are allocated in Pool.

The package provides the access type Node for referencing the items and the access type Web to reference the head items of lists. Note that each list is circular, so any of its items can be considered as a head. All list operations are defined in terms of Node and Web. Naturally, Web and Node are freely convertible to each other:

type Node is access List_Item_Type;
type Web is new Node;

A distinct type was chosen to separate pointers to items from ones to lists. This was important for aliasing prevention. For example if Node were used in Delete, then the following would be legal:

Delete (Messages, List_Head, List_Head);

So the operation Delete could finalize the item referenced by the third parameter, and thus set List_Head to null. At the same time it would set the second parameter to point to the next item in the list, setting List_Head to some not null value. The result would depend on the compiler and the program were erroneous. This manifests an aliasing problem, which cannot occur because in Delete the second parameter has the type Web, making it impossible to mistakenly alias it to another type.

The representation clause

for Node'Size use Integer_Address'Size;

is used to prevent the compiler from making "fat" pointers out of Node and Web. This should actually be Address'Size, but that would be illegal because Address'Size is not a static expression in Ada. The type Integer_Address should have same size as Address on almost all architectures. If it is not, change it to an explicit number. Remember that the size is specified in bits.

A list item is created by using the allocator new. The obtained pointer is passed to Append (Prepend) or Insert as appropriate. The procedure Append is used for creating a new list. The list is specified by a pointer to its head. So it can be created like:

   Head : Web; -- Empty list
begin
   Append (Messages, Head, new Object);

Now Head points to the newly allocated item in the list. Subsequent items can be created as:

   Append (Messages, Head, new Object);

The first parameter of all list operations is the type of the list. If there were several types of lists, we could place the same item into different lists. For example:

type Signal is
   new abstract Ada.Finalization.Limited_Controlled with private;
type Signal_List is (Alarm, Log);
type Some_Ptr is access Any; -- The default storage pool
package Signal_Lists is
   new Generic_Doubly_Linked_Web
       (  Signal_List,
          Signal'Class,
          Some_Ptr'Storage_Pool
       );
...
Message := new Error_Message; -- Derived from Signal
Append (Alarm, Notifications_List, Message);
Append (Log,   System_Trace_List,  Message);

Both Append or Insert are intended for placing newly allocated items or items removed from their lists before. To move an item from one list to another of the same type they take an additional parameter Source to specify the head of the list, the element is removed from. These procedures are equivalent to a call to Remove with a subsequent Append or Insert as required. The difference between  Append and Insert is that for Append the list head is specified and thus the list can be empty. For Insert the list head is not identified and the list cannot be empty. The design of these operations was chosen to prevent, when possible, dangling pointers and garbage. For this reason all operations that remove an item from a list refer to the list head. When appropriately used, the rest of the list should not become unreferenced. The deallocator of the storage pool where the list items are kept, checks freed items for being unreferenced. When a freed item is still in a list, Program_Error is propagated out of Unchecked_Deallocation.

There is no special function to obtain the first element in the list because the list head is also the first element. So:

Element := Node (Container);

would do the job.

The following list operations are defined:

procedure Append
          (  Brand     : List_Identification_Type;
             Container : in out Web;
             Element   : Node;
          );

This procedure inserts Element is at the end of Container. Element is either a newly allocated item or an item outside any lists of the type Brand. Constraint_Error is propagated when Element already is in a list. This includes Container. Container can be empty before a call to the procedure, in which case Element becomes the head of it. See also Prepend.

procedure Append
          (  Brand     : List_Identification_Type;
             Container : in out Web;
             Element   : Node;
             Source    : in out Web
          );

This procedure is an equivalent to Remove followed by Append without the parameter Source. It moves Element from Source to Container. When Source and Container is the same list Container parameter takes advantage. Constraint_Error is propagated when Element is null. See also Prepend.

procedure Delete
          (  Brand     : List_Identification_Type;
             Container : in out Web;
             Element   : in out Node
          );

This procedure removes Element from Container. The item following Element becomes the new list head. The operation is void when Element is null. The parameter Container is ignored when null. When Element after its removal does not belong to any list its target object is finalized, freed, and then Element is set to null.

procedure Erase
          (  Brand     : List_Identification_Type;
             Container : in out Web
          );

This procedure removes all elements from Container. When an element after its removal does not belong to any list its target object is finalized and freed. 

procedure Insert
          (  Brand    : List_Identification_Type;
             Position : Node;
             Element  : Node
          );

This procedure inserts Element after the item specified by the parameter Position. Element may not be in any list. Constraint_Error is propagated otherwise or when Element is null. Constraint_Error is also propagated when Position is null or not in a list of Brand type. Insert is similar to Append, with the difference that an arbitrary list item is used to indicate the insertion position. For this reason Append can deal with empty lists, while Insert requires at least one item in. To insert Element before Position use:

Insert (Brand, Previous (Brand, Position), Element); 

procedure Insert
          (  Brand    : List_Identification_Type;
             Position : Node;
             Element  : Node;
             Source   : in out Web
          );

This procedure is an equivalent to Remove followed by Insert. It moves Element from Source to the list of Position. The parameter has the same meaning as in Insert. When Position and Element refer the same item, the procedure does nothing. Constraint_Error is propagated when Element or Position is null. It is also propagated when Position is not in a list of Brand type.