



Dynamic Memory





	For some variables, memory requirements are easy to anticipate or estimate:

	type Person_Type is

		record

			Age : Integer;

			Weight : Float;

			Height : Float;

		end record;



	type People_Info_Type is array (1..100) of Person_Type;



	type Temperature_List_Type is array (1..24) of Float;



	People_Info					: People_Info_Type;

	Temperatures					: Temperature_List_Type;



	X					: Integer;

	Y					: Float;





Dynamic Memory, Cont.





	However, in many cases the size of a data object may not be known, or may vary greatly.

	For example, consider inputting some number of student names from a file.



	type Student_List_Type is array (1..?) of String(1..16);







	Using an artificially large maximum upper bound may work in some cases, but not all.

-	What if each student has an enormous amount of associated information?

-	More generally, what if the number of data items grows and shrinks frequently, over a wide range?



	Solution => Dynamic memory allows memory to be allocated when needed, and deallocated when not needed.





Access Types and Variables





	Every location in memory has an associated address.

	Every variable has an associated (starting) address.

	Most (Ada) programming does not deal with addresses, directly.



	X : Integer;







Pointers





	In the same way that a variable can contain an integer, float, character, record, array, etc., a variable can also store 
an "address."

	A variable that contains a memory address is commonly referred to as a pointer.

	In general, if a pointer variable P points to a particular location, it is depicted as follows.





A Note On Terminology





	In Ada a "pointer" variable may contain several pieces of information:

-	Base Address

-	Offset

-	Size of location referenced

-	Number of dimensions (if referenced location is an array)

-	Other information about the referenced location





	Consequently, a pointer variable/type in Ada is called an access variable/type.

	An access variable is similar, yet different from, for example, pointers in "C."





Access Variables





	Several access variables can reference the same location.

	An access variable may point to nothing, in which case it contains null.







Access Variables, Cont.





	It is important to distinguish between an access variable, and the location to which it refers.

	If p is an access variable, then p.all is the location to which it refers.

	Accessing the location referred to by an access variable is called de-referencing.







Declaring Access Types and Variables





	Examples of access type and variable declarations:



	type Integer_Ptr is access Integer;



	A : Integer_Ptr;

	B : Integer_Ptr;

	C : Integer;









Allocation





	Memory is allocated by using the allocator new.



	type Integer_Ptr is access Integer;



	A : Integer_Ptr;

	B : Integer_Ptr;

	C : Integer;



	A := new Integer					;				-- Allocate space for an integer

	B := new Integer'(17);									-- Allocate space for an integer, and initialize it to 17

	C := 5;





Operations on De-Referenced Access Variables



	Remember, it is important to distinguish between an access variable and what it refers to:

	type Integer_Ptr is access Integer;



	A : Integer_Ptr;

	B : Integer_Ptr;

	C : Integer := 5;

	D : Integer_Ptr;



	A := new Integer'(12);

	B := new Integer'(10);

	D := new Integer'(4);



	A.all := C;										-- This and the following statements all perform operations on the locations

	B.all := A.all + 30;										-- referred to by access variables

	C := A.all + B.all;



	Integer_IO.Put(C);

	Integer_IO.Put(A.all);



	if (A.all > C) then

		A.all := 0;

	end if;



Operations on Access Variables



	Same declarations:

	type Integer_Ptr is access Integer;



	A : Integer_Ptr;

	B : Integer_Ptr;

	C : Integer := 5;

	D : Integer_Ptr;

	A := new Integer'(12);

	B := new Integer'(10);

	D := new Integer'(4);



	A := B;																-- This and the following statements all perform operations

	if (A = D) then																-- on access variables

			Text_IO.Put("A and D are equal.")													

	end if;



	B := null;



	while (D != null) loop

			Text_IO.Put("Keep going around!");

	end loop;



Illegal Operations



	Same declarations:

	type Integer_Ptr is access Integer;



	A : Integer_Ptr;

	B : Integer_Ptr;

	C : Integer := 5;

	D : Integer_Ptr;

	A := new Integer'(12);

	B := new Integer'(10);

	D := new Integer'(4);



	A := B.all;																-- This and the following statements are all illegal, and do not

	if (D = C) then																-- compile

			Text_IO.Put("D and C are equal.")													

	end if;



	Integer_IO.Put(B);



	C := null;

	A := B + 1;								-- Sorry "C" programmers :)





De-Allocation





	Dynamic memory that is no longer needed can, and should, be given back.

	Memory is de-allocated by using the generic Unchecked_Deallocation.

	

	generic

		type Object is limited private;

		type Name is access Object;

	procedure Unchecked_Deallocation (X : in out Name);





	Question: What does the body of Unchecked_Deallocation look like?

	Answer: It is system dependent (so don't worry about it).

	As with any generic, before using Unchecked_Deallocation, it must be instantiated.





Instantiating Unchecked-Deallocation





	with Unchecked_Deallocation;

	procedure Main is

		type Integer_Ptr is access Integer;



		procedure Free is new Unchecked_Deallocation(																Object			=> Integer,

																		Name			=> Integer_Ptr);



		P : Integer_Ptr;

	begin

		P := new Integer'(25);

		Free(P);								-- De-allocates the memory referenced by P (but not P itself)

		-- P contains "null" at this point

	end Main;





Memory Leaks





	Consider the following declaration and statements:

	type Integer_Ptr is access Integer;



	B : Integer_Ptr;

	B := new Integer;

	B.all := 10;

	B := null;



	Note that the location referenced by B is no longer accessible.

	This is commonly referred to as a memory leak.

	No exception is raised when memory is leaked, unless it becomes excessive, in which case the exception 
STORAGE_ERROR is raised.

	The memory may be reclaimed by the implementation, but this is not required by the Ada LRM.

	The process of reclaiming such memory is referred to as garbage collection.





De-Referencing A Null Access Value







	Attempting to de-reference a null access variable will raise CONSTRAINT_ERROR:

	type Integer_Ptr is access Integer;



	A : Integer_Ptr;

	A := null;

	A.all := 10;							-- Will raise CONSTRAINT_ERROR





	De-allocating a null access variable does not raise an exception, however:

	type Integer_Ptr is access Integer;



	A : Integer_Ptr := new Integer'(45);

	B : Integer_Ptr := new Integer'(75);



	A := null;

	Free(A);						-- This is legal



	Free(B);						-- This is legal, "B" now contains null

	Free(B);						-- This is legal





Dangling Pointers





	Accessing a dangling pointer will produce unpredictable errors:

	A : Integer_Ptr := new Integer'(25);

	B : Integer_Ptr;



	B := A;

	Free(A);											-- "A" is now null



	if (B.all > 10) then											-- Invalid reference

		Integer_IO.Put(B.all);										-- Invalid reference

	end if;



	B.all := 30;											-- Invalid reference





Access Values Referencing Composite Types



	Previous examples all used access values referencing integers, but this should be rarely, if ever, used.

	Access types typically refer to composite types, such as records and arrays.

	type Person_Type is

		record

			Name : String(1..32);

			Age : Integer;

			Weight : Float;

		end record;



	type Person_Ptr is access Person_Type;



	P1, P2 : Person_Ptr;																		if (P1.all.Age > X) then

	P1 := new Person_Type;																			P1 := null;

	P2 := new Person_Type;																		end if;

	P1.all.Name := "Bob Jones                       ";																		if (P1 = P2) then

	P1.all.Age := 55;																			Text_IO.Put("Access values are equal");

	P1.all.Weight := 175.0;																		end if;

	P2.all := ("Jim Jones                           ",65,192.0);																		if (P1.all = P2.all) then

	P2.all.Age := P1.all.Age + 25;																			Text_IO.Put("Data is equal");

	P2.all.Weight := P1.all.Weight;																		end if;

																			P1.all := P2.all;

																			Free(P1);





Common Errors



	type Person_Type is

		record

			Name : String(1..32);

			Age : Integer;

			Weight : Float;

		end record;

	type Person_Ptr is access Person_Type;





	Compiler Errors:

	P1, P2 : Person_Ptr;																		if (P1.all = P2) then

	P1 := new Person_Type;																			P1 := null;

	P2 := new Person_Type;																		end if;

	P1.all.Name := 10;																		if (P1 > P2) then

	P1.all.Age := "abc";																			Text_IO.Put("Access values are equal");

	P1 := P2.all;																		end if;

	P2 := ("Jim Jones                           ",65,192.0);																		if (P1.all <= P2.all) then

	P2.all.Age := P1.all.Name;																			Text_IO.Put("Data is equal");

	P2 := P1.all;																		end if;





Common Errors



	Run-Time Exceptions (de-referencing a null pointer):

	Free(P1);

	P1.all.Age := 10;								-- P1 contains null now

	P1.all := P2.all;								-- P1 contains null now





	Dangling Pointers:

	P1 := new Person_Type;

	P2 := P1;

	Free(P1);

	P2.all.Age := 45;								-- The behavior of this statement is unpredictable





	Memory Leaks:

	P1 := new Person_Type;

	P1 := null;





Linked Lists



	A linked-list is dynamic memory based varying length data structure for storing a list of data items.

	Abstractly, a linked-list containing a list of three (3) integers can be visualized as follows:







	Physically, the list consists of:

-	A collection of cells, each containing a piece of data, and an access value that points to the next cell in 
the list, except for the last cell in the list which contains null.

-	An access variable that points to the first cell in the list.



Linked List Operations



	Data can be added to the list by allocating a new cell, and assigning the data and access value fields appropriately.

	Note that other cells will have access fields modified as a result.

	For example, inserting 65 at the end of the list results in the following.



	Next inserting 47 at the beginning of the list results in the following.



Linked List Operations, Cont.





	Next inserting 51 in the middle of the list results in the following.

	For each insertion, the following takes place:

-	Allocation of a cell (by making a call to new)

-	Assignment of the data field

-	Assignment of the next-cell access field

-	Re-assignment of an existing cell's next-cell access field or assignment of the list's first-cell access 
variable.



Linked List Operations, Cont.





Deleting the first cell in the list results in the following.



	Deleting the last cell in the list results in the following.



Linked List Operations, Cont.



	Deleting a cell from the middle of the list results in the following.

	Deleting all the cells from the list results in the following.

	For each deletion, the following takes place:

-	Re-assignment of an existing cell's next-cell access field, or assignment of the list's first-cell access 
variable.

-	De-allocation of the deleted cell.





Implementing A Linked List, Cont.





	The following declarations are requred to implement a linked-list:

	type Cell_Ptr is access Cell_Type;

	type Cell_Type is

		record

			Data : Integer;

			Next : Cell_Ptr;

		end record;







	Both declarations depend on one another, consequently the following must precede both of the above.

	type Cell_Type;







	It is frequently handy, although unnecessary, to have a List_Type declaration as well.

	type List_Type is Cell_Ptr;





Implementing A Linked List





	The complete set of declarations is as follows.

	type Cell_Type;

	type List_Type is access Cell_Type;

	subtype Cell_Ptr is List_Type;															-- Note how this has been made a subtype rather than a type

	type Cell_Type is

		record

			Data : Integer;

			Next : Cell_Ptr;

		end record;





A List Package Based On Arrays



	Recall the following list implementation.

package Integer_List is



	subtype Item_Type is Integer;

	type List_Type is limited private;



	procedure Clear_List (List : in out List_Type);

	procedure Add (Item : in Item_Type; List : in out List_Type);

	function Length (List : in List_Type) return Natural;

	function Full (List : in List_Type) return Boolean;

	procedure Retrieve (List :  in List_Type; Position :  in Index_Type; Item : out Item_Type);

	procedure Search (List :  in List_Type; ID : in Student_Types.ID_Type; Position : out Index_Type; Found : out Boolean);



private



	Max_Length: constant := 100;

	type Item_Array is array (Integer range <>) of Item_Type;

	subtype List_Array is Item_Array(1..Max_Length);

	type List_Type is

		record

			Length : Natural := 0;

			Items : List_Array;

		end record;



end Integer_List;





A List Package Based On Access Types



	Recall the following list implementation.

package Integer_List is



	subtype Item_Type is Integer;

	type List_Type is limited private;															-- Does this need to be limited private, or would private be sufficient?



	procedure Clear_List (List : in out List_Type);

	procedure Add (Item : in Item_Type; List : in out List_Type);

	function Length (List : in List_Type) return Natural;

	function Full (List : in List_Type) return Boolean;

	procedure Retrieve (List :  in List_Type; Position :  in Positive; Item : out Item_Type);

	procedure Search (List :  in List_Type; ID : in Integer; Position : out Postive; Found : out Boolean);



private



	type Cell_Type;

	type List_Type is access Cell_Type;

	subtype Cell_Ptr is List_Type;

	type Cell_Type is

		record

			Data : Integer;

			Next : Cell_Ptr;

		end record;



end Integer_List;





Subprogram Implementation - Length







	function Length (L : in List_Type) return Natural is

		Len : Natural;

		P : Cell_Ptr;

	begin

		Len := 0;

		P := L;

		while (P /= null) loop

			P := P.all.Next;

			Len := Len + 1;

		end loop;



		return Len;

	end Length;





Subprogram Implementation - Clear List





	What is wrong with the following?

	procedure Clear_List (List : in out List_Type) is

		P : Cell_Ptr;

	begin

		P := List;

		while (P /= null) loop

			Free(P);

			P := P.all.Next;

		end loop;

	end Clear_List;





Subprogram Implementation - Clear List





	procedure Clear_List (List : in out List_Type) is

		P : Cell_Ptr;

	begin

		while (List /= null) loop

			P := List;

			List := List.all.Next;

			Free(P);

		end loop;

	end Clear_List;





Subprogram Implementation - Add & Full





	procedure Add (Item : in Item_Type; List : in out List_Type) is

		P : Cell_Ptr;

	begin

		P := new Cell_Type;								-- P := new Cell_Type'(Item,List);

		P.all.Data := Item;								-- List := P;

		P.all.Next := List;

		List := P;

	end Add;





	function Full (List : in List_Type) return Boolean is

	begin

		return False;

	end Full;





Subprogram Implementation - Retrieve





	What is wrong with the following?

	procedure Retrieve (List :  in List_Type; Position :  in Positive; Item : out Item_Type) is

		P : Cell_Ptr;

		X : Natural := 1;

	begin

		P := List;

		while (X < Position) loop

			P := P.all.Next;

			X := X + 1;

		end loop;



		Item := P.all.Data;

	end Retrieve;





Subprogram Implementation - Retrieve





	procedure Retrieve (List :  in List_Type; Position :  in Positive; Item : out Item_Type) is

		P : Cell_Ptr;

		X : Natural := 1;

	begin

		P := List;

		while (P /= null) and (X < Position) loop

			P := P.all.Next;

			X := X + 1;

		end loop;



		if (P /= null) then

			Item := P.all.Data;

		else

			Text_IO.Put_Line("Error: Position Does Not Exist In List");

		end if;

	end Retrieve;





Subprogram Implementation - Search





	One way to do a search is a follows.

	procedure Search (List : in List_Type; ID : in Integer; Position : out Positive; Found : out Boolean) is

		P : Cell_Ptr;

		X : Positive;

	begin

		P := List;

		X := 1;

		Found := false;

		while (P /= null) and (not Found) loop

			if (P.all.Data = ID) then

				Found := true;

			else

				P := P.all.Next;

				X := X + 1;

			end if;

		end loop;



		if (Found) then

			Position := X;

		end if;

	end Search;





Subprogram Implementation - Search





	What is wrong with the following?

	procedure Search (List : in List_Type; ID : in Integer; Position : out Positive; Found : out Boolean) is

		P : Cell_Ptr;

		X : Integer;

	begin

		X := 1;

		P := List;

		while (P /= null) and (P.all.Data /= ID) loop

			P := P.all.Next;

			X := X + 1;

		end loop;



		if (P = null) then

			Found := False;

		else

			Found := True;

			Position := X;

		end if;

	end Search;





Subprogram Implementation - Search





	Another way is as follows.

	procedure Search (List : in List_Type; ID : in Integer; Position : out Positive; Found : out Boolean) is

		P : Cell_Ptr;

		X : Integer;

	begin

		X := 1;

		P := List;

		while (P /= null) and then (P.all.Data /= ID) loop

			P := P.all.Next;

			X := X + 1;

		end loop;



		if (P = null) then

			Found := False;

		else

			Found := True;

			Position := X;

		end if;

	end Search;





Subprogram Implementation - Delete





	Consider the addition of a delete subprogram, which was not in the package specification.

	What is wrong with the following version of the subprogram?



	procedure Delete (List :  in List_Type; Position :  in Positive) is

		P : Cell_Ptr;

		X : Positive;

	begin

		X := 1;

		P := List;

		while (X < Position) loop

			P := P.all.Next;

			X := X + 1;

		end loop;



		Free(P);

	end Delete;



Subprogram Implementation - Delete





	procedure Delete (List :  in out List_Type; Position :  in Positive) is

		P, Q : Cell_Ptr;

		X : Positive;

	begin

		X := 1;

		P := List;

		while (P /= null) and (X < Position) loop

			Q := P;

			P := P.all.Next;

			X := X + 1;

		end loop;



		if (P = null) then

			Text_IO.Put_Line("No Such Position Exists");

		elsif (X = 1) then									-- P = Q if X = 1

			L := P.all.Next;

			Free(P);

		else

			Q.all.Next := P.all.Next;

			Free(P);

		end if;

	end Delete;





A Main Example





	An example of a main program that uses the Integer_List package is as follows.



	-- Some standard imports

	with Integer_List;

	with Ada.Text_IO;

	with Ada.Integer_Text_IO;

	use Ada;



	-- Some typical variable declarations

	procedure Main is

		L				: Integer_List.List_Type;

		X				: Integer;

		Pos				: Positive;

		Found_It				: Boolean;

		Count				: Natural := 0;

	begin





A Main Example, Cont.





	Note that the following main is not dependent on whether or not the list is stored in an array, or a linked-list.



	-- Input a list of integers, and insert them into a list

	Text_IO.Put_Line ("Please Enter A List Of Integers");

	Text_IO.Put("?>");

	while (not Text_IO.End_Of_File) loop

		Integer_Text_IO.Get(X);

		Integer_List.Add(X,L);

		Count := Count + 1;

		Text_IO.Put("?>");

	end loop;



	-- Output the list of integers

	Text_IO.New_Line;

	Text_IO.Put("The List Entered Was :");

	for I in 1..Count loop

		Integer_List.Retrieve(L,I,X);

		Integer_Text_IO.Put(X);

	end loop;

	Text_IO.New_Line;





A Main Example, Cont.





		-- Input an integer, and determine if it is the list.

		Text_IO.New_Line;

		Text_IO.Put("Enter An Integer To Search For : ");

		Integer_Text_IO.Get(X);

		Text_IO.New_Line;

		Integer_List.Search(L,X,Pos,Found_It);

		if (Found_It) then

			Text_IO.Put("Integer Was In Position : ");

			Integer_Text_IO.Put(Pos);

		else

			Text_IO.Put("Integer Was Not In List");

		end if;

		Text_IO.New_Line;



	end Main;





Handling Errors





	Recall the Retrieve subprogram, and note how the error is handled.



	procedure Retrieve (List :  in List_Type; Position :  in Positive; Item : out Item_Type) is

		P : Cell_Ptr;

		X : Natural := 1;

	begin

		P := List;

		while (P /= null) and (X < Position) loop

			P := P.all.Next;

			X := X + 1;

		end loop;



		if (P = null) then

			Text_IO.Put_Line("Error: Position Does Not Exist In List");

		else

			Item := P.all.Data;

		end if;

	end Retrieve;





Handling Errors In The Main





	What happens when the following main is executed?



	procedure Main is

		L : Integer_List.List_Type;

		X : Integer;

	begin

			:

		for I in 1..10 loop

			Integer_List.Add(I,L);

		end loop;

			:

		Integer_List.Retrieve(L,200,X);

		Integer_Text_IO.Put(X);

			:

	end Main;





	The main is unaware that the call to Retrieve was erroneous.

	Some mechanism should be used to let the main know that an error occurred.





Handling Errors With Booleans





	One mechanism makes use of an additional boolean error-flag parameter.



	procedure Retrieve (List :  in List_Type; Position :  in Positive; Item : out Item_Type; Error : out Boolean) is

		P : Cell_Ptr;

		X : Natural := 1;

	begin

		P := List;

		while (P /= null) and (X < Position) loop

			P := P.all.Next;

			X := X + 1;

		end loop;



		if (P = null) then

			Text_IO.Put_Line("Error: Position Does Not Exist In List");

			Error := true;

		else

			Item := P.all.Data;

			Error := false;

		end if;

	end Retrieve;





Handling Errors In The Main Using The Error Flag





	The main must check the error flag after calling the subprogram.



	procedure Main is

		L : Integer_List.List_Type;

		X : Integer;

		Bad_Call : Boolean;

	begin

			:

		for I in 1..10 loop

			Integer_List.Add(I,L);

		end loop;

			:

		Integer_List.Retrieve(L,200,X,Bad_Call);

		if (not Bad_Call) then

			Integer_Text_IO.Put(X);

		else

			-- Output an error message, terminate program, or whatever is appropriate.

		end if;

			:

	end Main;



Signalling Errors With User-Defined Exceptions



	In Ada, error conditions are typically indicated by using exceptions.

package Integer_List is



	subtype Item_Type is Integer;

	type List_Type is limited private;



	procedure Clear_List (List : in out List_Type);

	procedure Add (Item : in Item_Type; List : in out List_Type);

	function Length (List : in List_Type) return Natural;

	function Full (List : in List_Type) return Boolean;

	procedure Retrieve (List :  in List_Type; Position :  in Positive; Item : out Item_Type);

	procedure Search (List :  in List_Type; ID : in Integer; Position : out Postive; Found : out Boolean);



	No_Such_Position : exception;										-- A user-defined exception.

											-- Define others as needed.

private



	type Cell_Type;

	type List_Type is access Cell_Type;

	subtype Cell_Ptr is List_Type;

	type Cell_Type is

		record

			Data : Integer;

			Next : Cell_Ptr;

		end record;



end Integer_List;





Rasing The Exception





	The Retrieve subprogram is modified to raise the exception when the error condition occurs.



	procedure Retrieve (List :  in List_Type; Position :  in Positive; Item : out Item_Type) is

		P : Cell_Ptr;

		X : Natural := 1;

	begin

		P := List;

		while (P /= null) and (X < Position) loop

			P := P.all.Next;

			X := X + 1;

		end loop;



		if (P = null) then

			raise No_Such_Position;

		else

			Item := P.all.Data;

		end if;

	end Retrieve;





Handling Errors In The Main Using The Exception



	The main must be modified to handle the exception when it is raised.



	procedure Main is

		L : Integer_List.List_Type;

		X : Integer;

		Bad_Call : Boolean;

	begin

			:

		for I in 1..10 loop

			Integer_List.Add(I,L);

		end loop;

			:

		Integer_List.Retrieve(L,200,X);

		Integer_Text_IO.Put(X);

			:

	-- Add an exception handler in the calling subprogram.

	exception

		when Integer_List.No_Such_Position =>

			Text_IO.Put_Line("Invalid Position Referenced, Terminating Program.");

	end Main;





Handling Errors In The Main Using The Exception



	Another way to catch the exception in the main is as follows.



	procedure Main is

		L : Integer_List.List_Type;

		X : Integer;

		Bad_Call : Boolean;

	begin

			:

		for I in 1..10 loop

			Integer_List.Add(I,L);

		end loop;

			:

		-- Add a new block for the exception handler.

		begin

			Integer_List.Retrieve(L,200,X);

		when Integer_List.No_Such_Position =>

			Text_IO.Put_Line("Invalid Position Referenced, Terminating Program.");

			return;

		end;

		Integer_Text_IO.Put(X);

			:

	end Main;



Viewing Postscript Files









	Postscript files can be viewed using a variety of tools, one of which is Ghostview.

	Ghostview can be obtained at www.cs.wisc.edu/~ghost
00000000

00000001

00000010

00000011

00000100

        :

11111111
X
00000000

00000001

00000010

00000011

00000100

        :

11111111
p
00000011
p
p
q
r
p1
null
p
q
r
p
p.all
???
A
B
C
null
null
???
A
B
C
17
A.all
5
???
B.all
A
B
null
15
L
?
21
36
15
L
21
36
65
15
L
21
36
65
47
51
15
L
21
36
15
L
21
36
65
47
65
47
51
L
21
51
36
15
51
L
21
36
15
???
L
???
