CS 131 LECTURE 8 - ACCESS TYPES AND LINKED LISTS

ACCESS TYPES

Syntax Rule:

access_type_definition ::=

ACCESS subtype_indication

Meaning:

Variables Of An Access Type Are Pointers, Variables Which Contain The Address Of Other Variables

Access Type Declarations:

TYPE Character_Pointers IS ACCESS Character;

TYPE String_Pointers IS ACCESS String(1..80);

TYPE Any_Size_Pointers IS ACCESS String;

Access Object Declarations:

Character_Pointer: Character_Pointers;

String_Pointer: String_Pointers;

Important Points:

1. Access Variables Are Automatically Initialized To The Value Null, Which Is A Constant Of All Access Types

2. Access Variables Are The Only Variables Which Are Automatically Initialized

3. Initializing Access Variables Prevents Dangling References

MEMORY ALLOCATION AND DEALLOCATION

Syntax Rule:

allocator ::=

NEW subtype_indication | 
NEW qualified_expression

Action:

1. Variable Is Dynamically Allocated

2. Address Of Variable Becomes Value Of Expression

Memory Allocation Examples:

TYPE Integer_Pointers IS ACCESS Integer;
Integer_Pointer: Integer_Pointers;
Integer_Pointer := NEW Integer;
Integer_Pointer := NEW Integer'(0);

TYPE String_Pointers IS ACCESS String; String_Pointer: String_Pointers; String_Pointer := NEW String(1..5);

Memory Deallocation Example:

PROCEDURE Free IS NEW Unchecked_Deallocation
  (Integer, Integer_Pointer);

Free(Integer_Pointers);

Important Point:

1. Ada Compilers May Automatically Free Inaccessible Memory

OPERATIONS ON ACCESS TYPES

Assignment:

1. Access Variables Can Be Assigned To Allocator Expressions

2. Access Variables Can Be Assigned To Other Access Variables

String_Pointer_1: String_Pointers(1..5);
String_Pointer_2: String_Pointers;

String_Pointer_2 := String_Pointer_1 -- Always Succeeds String_Pointer_1 := String_Pointer_2; -- Succeeds If String_Pointer_2 Is Null Or -- Points To A String With 1..5 Subscripts

3. Access Variables Can Not Be Assigned To Address Of Declared Variables, C Permits This

Relational Operators:

1. = /= Are Permitted

2. > >= < <= Are Prohibited, C Permits This

Arithmetic And Address Operators:

No Arithmetic Is Permitted On Access Variables, C Permits Pointer Arithmetic

No Address Operator Is Provided, C Has & Operator

INDIRECTION OPERATOR

Syntax Rules:

selected_component ::=

prefix.selector

selector ::=

ALL

Scalar Variables:

Integer_Pointer_1.ALL :=
  Integer_Pointer_2.ALL;
Integer_Pointer_1 := Integer_Pointer_2;

Array Variables:

TYPE String_Pointers IS ACCESS String;
String_Pointer: String_Pointers;

String_Pointer := NEW String(1..10); String_Pointer.ALL(1) := 'A'; String_Pointer(1) := 'A'; -- Abbreviation For Preceding

Record Variables:

TYPE Date_Pointers IS ACCESS Dates;
Date_Pointer: Date_Pointers;
Date_Pointer := NEW Dates;
Date_Pointer.ALL.Month := October;
Date_Pointer.Month := October;
-- Abbreviation For Preceding

RECURSIVE DATA STRUCTURES

Terminology:

Recursive Data Structure: A Data Structure Whose

1. Type Definitions Are Self Referential

2. Components Are Dynamically Allocated

Major Issue:

1. Ada Requires That a Type Be Declared Before It Is Used, This Necessitates The Use Of Incomplete Type Definitions

Syntax Rule:

incomplete_type_definition ::=

TYPE identifier [discriminant_part];

Terminology:

Dangling Reference: A Pointer To Deallocated Or Never Allocated Memory

Garbage: Allocated Memory Which Is Not Accessible From Any Pointer

Important Points:

1. Ada Minimizes Dangling References By Prohibiting Pointers To Declared Variables, By Initializing Pointers And Discouraging Explicit Memory Deallocation

2. Ada Compilers Are Permitted To Do Garbage Collection

LINKED LIST PACKAGE

Linked List Package Specification

GENERIC
  TYPE Elements IS PRIVATE;
  WITH PROCEDURE Put(Item: IN Elements)
    IS <>;
PACKAGE Linked_List_Package IS
  TYPE Nodes;
  TYPE Lists IS ACCESS Nodes;
  TYPE Nodes IS
    RECORD
      Data: Elements;
      Next: Lists;
    END RECORD;
  PROCEDURE Put(Head: IN Lists);
  PROCEDURE Erase(Head: IN OUT Lists);
  FUNCTION Reversal(Head: Lists)
    RETURN Lists;
  FUNCTION Copy(Head: Lists) RETURN Lists;
  PROCEDURE Insert(Head: IN OUT Lists;
    Last: IN Lists; Data: IN Elements);
  PROCEDURE Delete(Head: IN OUT Lists;
    Last: IN OUT Lists);
END Linked_List_Package;

Important Point:

1. The Put For Elements Is Needed By The Put For Lists

LINKED LIST IMPLEMENTATION

Linked List Package Body

WITH Unchecked_Deallocation;
PACKAGE BODY Linked_List_Package IS
  PROCEDURE Deallocate_Node IS NEW
    Unchecked_Deallocation(Nodes,Lists);
  PROCEDURE Put(Head: IN Lists) IS SEPARATE;
  PROCEDURE Erase(Head: IN OUT Lists)
    IS SEPARATE;
  FUNCTION Reversal(Head: Lists)
    RETURN Lists IS SEPARATE;
  FUNCTION Copy(Head: Lists)
    RETURN Lists IS SEPARATE;
  PROCEDURE Insert(Head: IN OUT Lists;
    Last: IN Lists; Data: IN Elements)
    IS SEPARATE;
  PROCEDURE Delete(Head: IN OUT Lists;
    Last: IN OUT Lists) IS SEPARATE;
END Linked_List_Package;

Important Points:

1. The Deallocate Node Procedure Is Used By The Erase Procedure And The Delete Procedure

2. The Put, Erase And Reversal Subprograms All Perform List Traversals

3. Two Versions Of The Copy Function Are Included

SINGLY LINKED LIST TRAVERSALS

Singly Linked List Put Procedure

SEPARATE (Linked_List_Package)
PROCEDURE Put(Head: IN Lists) IS
  This: Lists := Head;
BEGIN
  WHILE This /= NULL LOOP
    Put(This.Data);
    This := This.Next;
  END LOOP;
END Put;

Singly Linked List Erase Procedure

SEPARATE (Linked_List_Package)
PROCEDURE Erase(Head: IN OUT Lists) IS
  Next: Lists;
BEGIN
  WHILE Head /= NULL LOOP
    Next := Head.Next;
    Deallocate_Node(Head);
    Head := Next;
  END LOOP;
END Erase;

Important Point:

1. The Erase Procedure Requires A Two Node Window

SINGLY LINKED LIST REVERSAL

Reversal Function

SEPARATE (Linked_List_Package)
FUNCTION Reversal(Head: Lists)
RETURN Lists IS
  Last,This,Next: Lists;
BEGIN
  This := NULL;
  Next := Head;
  WHILE Next /= NULL LOOP
    Last := This;
    This := Next;
    Next := This.Next;
    This.Next := Last;
  END LOOP;
  RETURN This;
END Reversal;

Singly Linked List Reversal Diagram

NON-RECURSIVE LIST COPY

Copy Function

SEPARATE (Linked_List_Package)
FUNCTION Copy(Head: Lists)
RETURN Lists IS
  This,Last,New_Head: Lists;
  Old_Head: Lists := Head;
BEGIN
  IF Old_Head = NULL THEN
    RETURN NULL;
  ELSE
    This := NULL;
    LOOP
      Last := This;
      This := NEW Nodes;
      IF Last = NULL THEN
        New_Head := This;
      ELSE
        Last.Next := This;
      END IF;
      This.Data := Old_Head.Data;
      Old_Head := Old_Head.Next;
      EXIT WHEN Old_Head = NULL;
    END LOOP;
    This.Next := NULL;
    RETURN New_Head;
  END IF;
END Copy;

RECURSIVE LIST COPY

Copy Function

SEPARATE (Linked_List_Package)
FUNCTION Copy(Head: Lists)
RETURN Lists IS
  This: Lists;
BEGIN
  IF Head = NULL THEN
    RETURN NULL;
  ELSE
    This := NEW Nodes;
    This.Data := Head.Data;
    This.Next := Copy(Head.Next);
    RETURN This;
  END IF;
END Copy;

Important Point:

1. The Recursive Copy Is Shorter And Simpler

Recursive Copy Diagram

SINGLY LINKED INSERTION

Single Insert Procedure:

SEPARATE (Linked_List_Package)
PROCEDURE Insert(Head: IN OUT Lists;
  Last: IN Lists; Data: IN Elements) IS
  This: Lists := NEW Nodes;
BEGIN
  This.Data := Data;
  IF Last = NULL THEN
    This.Next := Head;
    Head := This;
  ELSE
    This.Next := Last.Next;
    Last.Next := This;
  END IF;
END Insert;

Singly Linked List Insertion Diagram

SINGLY LINKED LIST DELETION

Single Delete Procedure:

SEPARATE (Linked_List_Package)
PROCEDURE Delete(Head: IN OUT Lists;
  Last: IN OUT Lists) IS
  This: Lists := Head;
BEGIN
  IF Last = NULL THEN
    Head := This.Next;
    Deallocate_Node(This);
  ELSE
    This := Last.Next;
    IF This /= NULL THEN
      Last.Next := This.Next;
      Deallocate_Node(This);
    END IF;
  END IF;
END Delete;

Singly Linked List Deletion Diagram

/ Top of Page /