 Previous |
 Contents |
 Next |
Previous |
Contents |
Next |
A retentive memory is a good thing, but the
ability to forget is the true token of greatness.
— Elbert Hubbard, Epigrams
It’s time to take another look at the linked list package, since there’s still one problem with it that I’ve been carefully ignoring. When you declare a linked list, memory is allocated using new. At the end of the block where the list is declared, the list object is destroyed. Since the list object contains a pointer to an object allocated by new, this pointer is lost and there is no longer any way of accessing the object it pointed to. This is known as a memory leak and if it happens often enough you will eventually run out of memory. Memory leaks can be a major headache. You may not notice there is a problem until the program is at full stretch, which usually happens after it’s been debugged and released for use in a production environment. Also, it’s usually very difficult to track down the leak since it’s caused by the absence of something in your code.
Some systems (but not all) use a garbage collector as a way of solving this problem. At some point (e.g. when you try to allocate some memory) the garbage collector scans the heap looking for blocks of memory that are no longer accessible and reclaims them for recycling. Unfortunately, since not all systems use garbage collection, you can’t rely on it being there to tidy up after you. The only time that Ada guarantees to reclaim inaccessible objects is at the point where the declaration of the access type itself goes out of scope, since by then there won’t be any access variables left which might point to the objects. In the case of a generic package the access type is effectively declared at the point where you instantiate the package so this isn’t as bad as it might sound. The only other alternative is to use Unchecked_Deallocation as described in chapter 11. As the name implies, this is done at your own risk; if you deallocate something and you still have an access variable which points to it (a dangling pointer) you run the risk of crashing your system. Using a dangling pointer to access something that isn’t there any more can make a real mess of things. However, in the case of a linked list you can usually make sure that this doesn’t happen.
So to guarantee that your linked lists don’t cause memory leaks you will need to provide a procedure which will use Unchecked_Deallocation to clean up the linked list (possibly called Close by analogy with closing a file):
declare
X : List_Type;
begin
Process (X); -- use the list X
Close (X); -- free memory allocated to X
end;
The disadvantage of doing this is that it puts an extra burden on the users of your linked list package; they will have to remember to call Close at the end of every block where a list is declared, and if they forget they will end up with memory leaks.
Ada provides a way of automating the cleaning-up process. The package Ada.Finalization defines two tagged types called Controlled and Limited_Controlled (collectively referred to as controlled types). As the names imply, Controlled is a non-limited type and Limited_Controlled is a limited type. Both types are abstract so that you can’t directly declare Controlled or Limited_Controlled objects.
You can derive new controlled types by deriving them from Controlled or Limited_Controlled. Controlled types inherit a primitive operation called Finalize from their parent type:
procedure Finalize (Object : in out Controlled);
procedure Finalize (Object : in out Limited_Controlled);
Finalize is unusual in that it is automatically called when a controlled object goes out of scope (i.e. at the end of the block where it is declared). Finalize is therefore like the Close procedure described above except that you don’t need to call it explicitly; the compiler will automatically provide a call to Finalize at the end of the block. Finalize can be used for any last-minute cleaning up (finalisation) that needs to be done; this often involves deallocating memory, but you could use it to save the object automatically to disk, add an entry to a log file, clear the screen, play a tune, or do anything else you might think is appropriate. The versions of Finalize that you inherit from Controlled and Limited_Controlled do nothing, so that you don’t have to override Finalize for your derived type if you don’t need to do any finalisation operations.
British readers should be careful not to use the normal British spelling (‘Finalise’ instead of ‘Finalize’) when attempting to override operations of controlled types. If you declared a procedure called Finalise, you'd end up with a brand new primitive operation called Finalise in addition to the inherited version of Finalize, and Finalise would not be called automatically. A good compiler should warn you about this!
In the case of a linked list you can define Finalize to deallocate all the items in a list automatically at the end of its scope. Here’s how the linked list package from chapter 12 can be modified to allow this:
with Ada.Finalization; use Ada.Finalization;
generic
type Item_Type is private;
package JE.Lists is
type List_Type is limited private;
... -- as before
private
... -- as before
type List_Type is new Limited_Controlled with
record
Header : List_Access := new List_Header;
end record;
procedure Finalize (Object : in out List_Type);
... -- as before
end JE.Lists;
List_Type is automatically a limited type because it is derived from the limited type Limited_Controlled. Finalize is declared in the private part of the package; this makes it a primitive operation of List_Type (so that it overrides the ‘do-nothing’ version inherited from Limited_Controlled) but it’s invisible to package clients. Child packages can still access it; this means that if a further type derived from List_Type wants to override Finalize, it can call List_Type’s version of Finalize as part of its own finalisation code. Note that if the visible part of the package revealed that List_Type were derived from Limited_Controlled, package clients could call Finalize directly since Finalize is visibly known to be a primitive operation of Limited_Controlled types and so would be known to be inherited by List_Type.
Since Ada.Finalization.Limited_Controlled and Ada.Finalization.Controlled are both library-level types, all controlled types must be derived by instantiation at library level. Since generic packages are treated as being declared at the point of instantiation, this means that JE.Lists can only be instantiated at library level, usually within the specification of another library package. In particular, this means that we can no longer use JE.Lists to build opaque types as described in chapter 13; instantiating JE.Lists inside a package body is no longer permissible. Moving the instantiation into the package specification solves the problem, although this means that the type is no longer opaque since implementation information has to go in the package specification. Another solution is to have a non-generic definition for the list types, and then use inheritance to derive an extended type for the list nodes which includes the data to be stored in the list, although getting this right isn’t trivial either.
The definition of Finalize for a linked list might look like this:
procedure Finalize (Object : in out List_Type) is
procedure Delete_Header is new Ada.Unchecked_Deallocation
(List_Header, List_Access);
begin
while First(Object) /= Last(Object) loop
Delete (First(Object));
end loop;
Delete_Header (Object.List);
end Finalize;
This loops until the list is empty, removing and deleting the first element of the list each time around the loop, and then deletes the list header.
As well as Finalize, controlled types have another primitive operation called Initialize. Initialize is declared in exactly the same way as Finalize is:
procedure Initialize (Object : in out Controlled);
procedure Initialize (Object : in out Limited_Controlled);
Like Finalize, the default behaviour is to do nothing. If you override Initialize for a derived controlled type, it is called automatically whenever an object of that type is created that has no initial value specified. If an initial value is specified in the object declaration, Initialize doesn’t get called.
One remaining problem is what to do in the case of a list of pointers. Finalising the list will deallocate the elements of the list, but this will cause a memory leak since the pointers that they contain will disappear. One solution to this is to define a smart pointer type which finalises itself automatically and to use this as the type of list element to be used instead of a plain access type:
type Pointer_Type is new Controlled with
record
Value : Some_Access_Type;
end record;
procedure Finalize (Object : in out Pointer_Type);
The Finalize operation for Pointer_Type can be used to delete the pointer it contains. We’ll also need an accessor function to let us get at the pointer inside the Pointer_Type object:
function Value (Pointer : Pointer_Type) return Some_Access_Type is
begin
return Pointer.Value;
end Value;
This is best done in a generic package so that we can instantiate it for use with any access type:
generic
type Item_Type(<>) is limited private;
type Access_Type is access Item_Type;
package JE.Pointers is
...
end JE.Pointers;
Note that Item_Type is defined to be an unconstrained limited private type; this means that it can be instantiated using absolutely any type at all. Access_Type can be any (pool-specific) access type which accesses Item_Type.
Inside the package, the declaration of Pointer_Type doesn’t need to specify publicly that Pointer_Type is a tagged type since this would give clients the freedom to derive from Pointer_Type and override the Finalize operation if they wanted to, so the package can look something like this:
with Ada.Finalization;
generic
type Item_Type(<>) is limited private;
type Access_Type is access Item_Type;
package JE.Pointers is
type Pointer_Type is private;
function Value (Pointer : Pointer_Type) return Access_Type;
private
type Pointer_Type is new Ada.Finalization.Controlled with
record
Value : Access_Type;
end record;
procedure Finalize (Object : in out Pointer_Type);
end JE.Pointers;
Here’s how the package might be used:
with JE.Pointers;
package JE.Coords is
type Coord_Type is
record
X, Y : Float;
end record;
type Coord_Access is access Coord_Type;
package Coord_Pointers is
new JE.Pointers (Item_Type => Coord_Type, Access_Type => Coord_Access);
A : Coord_Access;
B : Coord_Pointers.Pointer_Type;
end JE.Coords;
This instantiates JE.Pointers in a library-level package; this is necessary because of the rule that derived types must be declared at the same level as the parent type.
There are two objects declared in this package: A is a normal access variable while B is a smart pointer. Where you would refer to the components of the object that A points to as A.X, A.Y or A.all, you refer to Value(B).X, Value(B).Y and Value(B).all to get at the components of the object that B points to. B starts off as a null pointer, so you’ll need a constructor function that generates a Pointer_Type object from an Access_Type value:
function Pointer (Value : Access_Type) return Pointer_Type is
Object : Pointer_Type;
begin
Object.Value := Value;
return Object;
end Pointer;
This just takes a copy of the parameter and encapsulates it in a smart pointer. This means that you should avoid using the parameter elsewhere; don’t deallocate it using Ada.Unchecked_Deallocation or use it to initialise another smart pointer, since it will then end up being deallocated twice. This will usually be fatal for the memory management system and your program will probably crash shortly afterwards in a mystifying way. Here is how you should use Pointer:
B : Coord_Pointers.Pointer_Type := Coord_Pointers.Pointer( new Coord_Type'(1.0,1.0) );
The parameter to Pointer is a value created using new which won’t be used elsewhere. As you can see, you can use Pointer to generate an initial value for use in a declaration; if a declaration doesn’t provide an initial value, the variable will start off with a null pointer as usual.
One problem with this is that it’s still possible to cause a disaster by assigning one Pointer_Type object to another. If you do this you will end up with two Pointer_Type objects pointing to the same thing so that when they are finalised the same object will be deleted twice, generally with disastrous results as mentioned above. The ideal solution would be to overload the assignment operator ‘:=’, but you can’t do this because in fact ‘:=’ isn’t counted as being an operator in Ada. Fortunately the Finalization package provides a solution to this problem too. The type Controlled has a primitive operation called Adjust which is used during assignment operations, so that types derived from Controlled can override this to modify the behaviour of assignments. Adjust looks just like Initialize and Finalize:
procedure Adjust (Object : in out Controlled);
There is of course no version of Adjust for Limited_Controlled since Limited_Controlled (as well as any type derived from it) is a limited type and so assignment isn’t possible anyway.
When a value is assigned to a controlled object, Adjust is automatically called after copying the new value into the object. If A and B are objects of the same controlled type, the assignment A := B involves taking a copy of B, finalising the current value of A before it gets destroyed by being overwritten, copying the copy of B into A, adjusting A, and then finalising the copy of B before it’s destroyed:
A := B; -- compiled as: Temp := B;
Finalize(A);
A := Temp;
Adjust(A);
Finalize(Temp);
This looks like a laborious business but the compiler can generally optimise it so that it ends up like this:
A := B; -- compiled as: Finalize(A);
A := B;
Adjust(A);
The extra copy of B is usually unnecessary, but it caters for the case where an object is assigned to itself:
B := B; -- compiled as: Temp := B;
Finalize(B);
B := Temp;
Adjust(B);
Finalize(Temp);
A copy of B’s value is made before B is finalised, and it’s this copy that’s assigned back into B and then adjusted.
Adjust can take care of any post-assignment adjustments that may be needed. In the case of Pointer_Type we can make assignment work properly by using Adjust and Finalize to maintain a reference count showing how many references there are to the same object, and only deleting an object when the reference count reaches zero. This means that Pointer_Type will need to point to an object which holds the reference count as well as the actual pointer to the data; keeping the reference count in the Pointer_Type object wouldn’t work since other Pointer_Type objects would have no idea it was there. Having multiple Pointer_Type objects point to a common item means that the item itself can keep track of the reference count. This means that we’ll need Pointer_Type objects to point to reference counted objects which contain a reference count and a pointer to the actual data being managed. This will involve a number of changes to the existing package:
with Ada.Finalization;
generic
type Item_Type(<>) is limited private;
type Access_Type is access Item_Type;
package JE.Pointers is
type Pointer_Type is private;
function Pointer (Value : Access_Type) return Pointer_Type;
function Value (Pointer : Pointer_Type) return Access_Type;
private
type Reference_Counted_Object is
record
Value : Access_Type;
Count : Natural;
end record;
type Reference_Counted_Pointer is access Reference_Counted_Object;
type Pointer_Type is new Ada.Finalization.Controlled with
record
Pointer : Reference_Counted_Pointer;
end record;
procedure Finalize (Object : in out Pointer_Type);
procedure Adjust (Object : in out Pointer_Type);
end JE.Pointers;
Pointer_Type now points to a Reference_Counted_Pointer which contains the actual pointer value together with a reference count. You still have to be a bit careful since circular lists of reference counted objects will never be deallocated because each object will always be pointed to by the preceding object in the list so the reference count will never become zero. A Pointer_Type object will start off as a null pointer, so it’ll be necessary to check for null within each of the operations provided by the package. The definitions of Pointer and Value both need changing to reflect this:
procedure Delete_Item is
new Ada.Unchecked_Deallocation (Item_Type, Access_Type);
function Pointer (Value : Access_Type) return Pointer_Type is
Object : Pointer_Type;
begin
Object.Pointer := new Reference_Counted_Object'(Value => Value, Count => 1);
return Object;
end Pointer;
function Value (Pointer : Pointer_Type) return Access_Type is
begin
if Pointer.Pointer = null then
return null;
else
return Pointer.Pointer.Value;
end if;
end Value;
Pointer has to create an object which points to a new Reference_Counted_Object with a reference count of 1 while Value has to check whether its parameter contains a null pointer and then return either null or the access value in the Reference_Counted_Object it points to.
If a Pointer_Type object being finalised doesn’t contain a null pointer, Finalize will need to decrement the reference count and then delete the object if the count has reached zero:
procedure Delete_Pointer is
new Ada.Unchecked_Deallocation (Reference_Counted_Object,
Reference_Counted_Pointer);
procedure Finalize (Object : in out Pointer_Type) is
begin
if Object.Pointer /= null then
Object.Pointer.Count := Object.Pointer.Count - 1;
if Object.Pointer.Count = 0 then
Delete_Item (Object.Pointer.Value);
Delete_Pointer (Object.Pointer);
end if;
end if;
end Finalize;
Adjust will need to increment the reference count when a non-null value is assigned to a Pointer_Type object:
procedure Adjust (Object : in out Pointer_Type) is
begin
if Object.Pointer /= null then
Object.Pointer.Count := Object.Pointer.Count + 1;
end if;
end Adjust;
Assigning another Pointer_Type value to Object means that Object will just point to the same reference counted object as the other one does. The old value of Object will be finalised, so that the reference counted object it points to will have its reference count decremented and will be deleted if necessary. The new value will then be copied into Object. Finally, Adjust will increment the reference count if it isn’t a null pointer to mark the fact that there is now one extra Pointer_Type object pointing to the same Reference_Counted_Object.
Note that Adjust will also be called if an initial value is specified as part of the declaration of a Pointer_Type object:
A : Point_Access.Pointer_Type; -- as defined earlier
B : Point_Access.Pointer_Type := A;
The value of A will be copied into B so that A and B will end up pointing to the same reference counted object, and then Adjust will be called to increment the object’s reference count.
One of the problems with testing controlled types lies in the fact that the procedures Initialize, Finalize and Adjust are called automatically without there being any sign in your program that they are being called. A good way to test that controlled types work as expected is to make Initialize, Finalize and Adjust display a message to show when they are being called:
procedure Initialize (Object : in out Pointer_Type) is
begin
... -- do initialisation
Put_Line ("Initialize called for Pointer_Type");
end Initialize;
procedure Finalize (Object : in out Pointer_Type) is
begin
... -- do finalisation
Put_Line ("Finalize called for Pointer_Type");
end Finalize;
procedure Adjust (Object : in out Pointer_Type) is
begin
... -- do post-assignment adjustment
Put_Line ("Adjust called for Pointer_Type");
end Adjust;
A little ingenuity with global variables in the package body where these functions are declared will let you associate unique identifiers with each Pointer_Type object that’s created (as in the Bank_Account example mentioned in chapter 6) to display even better messages to keep track of what’s going on. In the case of Pointer_Type, you might want to include a numeric ID in each Reference_Counted_Object and display the object ID and reference count every time the object is updated:
type Reference_Counted_Object is
record
Value : Access_Type;
Count : Natural;
Ident : Positive; -- a unique object number
end record;
The function Pointer will need to allocate numbers for the Ident component of Reference_Counted_Objects as they are created:
-- In the package body:
RCO_Number : Positive := 1;
function Pointer (Value : Access_Type) return Pointer_Type is
Object : Pointer_Type;
begin
Object.Pointer := new Reference_Counted_Object'(Value => Value,
Count => 1,
Ident => RCO_Number);
RCO_Number := RCO_Number + 1;
return Object;
end Pointer;
Finalize and Adjust can display the Ident component and the corresponding reference count as changes are made:
procedure Finalize (Object : in out Pointer_Type) is
begin
if Object.Pointer /= null then
Put ("Finalising ");
Put (Object.Pointer.Ident, Width => 1);
Object.Pointer.Count := Object.Pointer.Count - 1;
Put (", reference count is now ");
Put (Object.Pointer.Count, Width => 1);
if Object.Pointer.Count = 0 then
Put (" so deleting it");
Delete_Item (Object.Pointer.Value);
Delete_Pointer (Object.Pointer);
end if;
New_Line;
end if;
end Finalize;
procedure Adjust (Object : in out Pointer_Type) is
begin
if Object.Pointer /= null then
Put ("Adjusting ");
Put (Object.Pointer.Ident, Width => 1);
Object.Pointer.Count := Object.Pointer.Count + 1;
Put (", reference count is now ");
Put (Object.Pointer.Count, Width => 1);
New_Line;
end if;
end Adjust;
This will make it much easier to track down the exact order of events when you’re dealing with controlled objects. You can’t use your text editor to track down the places where Initialize, Finalize and Adjust are called since the compiler inserts invisible calls to these procedures, so you need to design controlled types so that they will provide the debugging information automatically. At this point it’s worth pointing out a possible use for the parent package JE:
package JE is
procedure Debug (On : in Boolean); -- set a hidden flag
function Debugging return Boolean; -- test the hidden flag
end JE;
This lets you turn a flag on or off and then test it in the child units to determine whether to display debugging information. You could even use an enumeration or an integer value instead of a Boolean to choose between different levels of detail. That way if anything goes wrong, your debugging tools are ready and waiting to be turned on if you need them. They make your application larger when you don’t need them, but discarding your debugging tools to save space has been compared to leaving your parachute at home once you get your pilot’s licence. Need I say more?
| 16.1 | Modify the playing card package from exercise 9.2 to make a pack of cards a controlled type. Declaring a pack of cards should create a shuffled set of all 52 cards automatically. |
| 16.2 | Create a generic package which defines a controlled type containing a random number generator from Ada.Numerics.Discrete_Random (see exercise 5.1). The controlled type’s Initialize operation should call Reset to guarantee that the random number generator is initially randomised. |
| 16.3 | Modify the diary program so that diaries are loaded and saved automatically at initialisation and finalisation. For the sake of simplicity, use filenames suffixed by a number (Diary1, Diary2 and so on) for each diary object you declare; to do this, use a global diary number which is incremented every time a diary object is declared and use the diary number to generate the filename. |
| 16.4 | Modify the linked list package to make it possible to do ‘deep copying’ of lists. This means that when one list is assigned to another, copies of all the items in the list are made so that a completely separate duplicate copy is produced. You can do this by making List_Type a controlled type and overriding Adjust. |
Previous |
Contents |
Next |
This file is part of Ada 95: The Craft
of Object-Oriented Programming by John English.
Copyright © John
English 2000. All rights reserved.
Permission is given to redistribute this work for non-profit educational
use only, provided that all the constituent files are distributed without
change.
$Revision: 1.2 $
$Date: 2001/11/17 12:00:00 $