home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C!T ROM 2
/
ctrom_ii_b.zip
/
ctrom_ii_b
/
PROGRAM
/
PASCAL
/
PASTUT34
/
HEAP&PTR.TXT
< prev
next >
Wrap
Text File
|
1993-06-12
|
14KB
|
312 lines
DYNAMIC MEMORY MANAGEMENT AND POINTERS.
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
Most variables dealt with so far have been 'static', i.e. their form and
size is pre-determined, and they exist throughout the entire execution of
the block in which they are declared. They may of course change in value,
but not in form and size.
Programs, however, frequently need the use of a data structure which varies
in form and size during execution. 'Dynamic' variables serve this purpose
as they are generated as the need arises and may be discarded after use.
Such dynamic variables are not declared in an explicit variable declaration
like static variables, and they cannot be referenced directly by identifier
Instead, a special variable containing the memory address of the variable
is used to point to the variable. This special variable is called a
'pointer' variable.
Pointer variables themselves are just 4 bytes in size and contain the
address, as segment and offset values, of the place in memory where the
data structure is located. The data structure at that address can be of
any size and form.
A pointer type is defined by the symbol ^ (caret) succeeded by the type
identifier of the dynamic variable to be referenced by the pointer
variable. The example program POINTERS.PAS shows how to declare a record
with associated pointers. The type PersonPointer is declared as a pointer
to variables of the type PersonRecord, as shown below:
Type
PersonPointer = ^PersonRecord; { Pointer type declaration }
{ Read as 'PersonPointer is a pointer to the record-type PersonRecord' }
PersonRecord = Record { Record-type declaration }
Name : string[50]; { Field 51 bytes in size }
Job : string[50]; { Field 51 bytes in size }
Next : PersonPointer; { Pointer to next record, }
end; { 4 bytes in size }
Var
FirstPerson, LastPerson, NewPerson : PersonPointer;
The variables FirstPerson, LastPerson, and NewPerson are thus pointer
variables which can point at records of the type PersonRecord. As shown,
the type identifier in a pointer type definition (PersonRecord) may refer
to an identifier which is only subsequently defined.
Although each pointer variable, such as NewPerson, only occupies 4 bytes
of static memory in the data segment, it is cumbersome and unnecessary to
use a static pointer for each record on the heap. As shown above, it is
better to include one, or more, pointers as field(s) in the dynamic type
variable PersonRecord. The field Next contains a pointer, of type
PersonPointer, which points to the next record.
Records types, which contain pointer fields, are called linked lists and
these are discussed in detail later in this note.
The dynamic variable pointed to by a pointer is dereferenced by using
the pointer symbol (^) after the pointer variable, as shown in the
program POINTERS.PAS at line number 77:
NewPerson^.Name := Name;
where NewPerson^.Name refers to the Name field of the record pointed to
by the pointer NewPerson.
Allocating Dynamic Variables.
═════════════════════════════
Before it is sensible to use these pointer variables, there must be some
variables to point at. New variables of any type are allocated with the
standard procedure 'New'. The one parameter of New is the pointer variable
of the type to be created, as now illustrated:
New(FirstPerson);
This has the effect of having 'FirstPerson' point at the start address of
a dynamically allocated record of the type 'PersonRecord'.
Thus 'FirstPerson' contains the 4-byte address of a variable of type
'PersonRecord' and the required space (106 bytes) has been allocated in
memory to hold such a variable.
The pointer value NIL is compatible with all pointer types. NIL points
to the address 0:0 and may be assigned to pointer variables to indicate
the absence of a usable pointer. Care must be taken never to write to the
address 0:0 because it is the start address of the Vector Interrupt Table,
used by the operating system.
Dynamic variables created by the standard procedure 'New' are allocated
space on a stack-like structure, called the 'Heap', at run-time.
Turbo Pascal controls the heap by maintaining a heap pointer which at the
beginning of a program is initialized to the address of the first free
byte in memory. On each call to 'New', the heap pointer is moved towards
the top of free memory by the number of bytes corresponding to the size of
the new dynamic variable.
The size of both the Stack and the Heap can be set by selecting Options
from the menu bar at the top of the screen, when using the Integrated
Development Environment, and then choosing Memory sizes from the sub-menu.
These memory sizes can also be set by using Compiler Directives within the
program. Generally and especially for large databases, it is wise to set
the heap upper limit to its maximum value, typically 655360.
If there is insufficient memory available on the heap to allocate space
for a new dynamic variable, a standard function, HeapFunc, is called and
it sets the variable HeapError to 0, so causing a run-time error, which
halts the program. To avoid halting the program, the user can write an
alternative function, HeapFunc, to replace the standard one and avoid
the run-time error, but instead provide a warning. See page 217 of the
Programmer's Guide for more information.
Removing Dynamic Variables.
═══════════════════════════
When a dynamic variable is no longer required by the program, it can be
removed by a call to the Dispose procedure, which requires one parameter,
the pointer variable name.
e.g. Dispose(FirstPerson);
Dispose removes the address contained in the pointer variable in static
memory (FirstPerson) and also removes the data structure, to which it
points, from the heap.
Dispose only removes one dynamic variable from the heap for each call and
since the heap is not automatically compacted, there are resultant 'holes'
in the heap. Should it be necessary to remove a block of dynamic variables,
from a given address onwards to the end of the heap, then the procedures
Mark and Release must be used.
The Mark procedure assigns the value of the heap pointer to a variable.
The syntax is:
Mark(P);
where P is a pointer-type variable.
The Release procedure sets the heap pointer to the address contained in
the argument. The syntax is:
Release(P);
where P is the pointer-type variable, previously set by Mark.
Release thus discards all dynamic variables above this address and cannot
release the space used by variables in the middle of the heap.
Heap Management.
════════════════
The standard function 'MemAvail' is available to determine the available
space on the heap. Other memory management procedures and functions are
listed on page 126 of the Programmer's Guide.
Linked lists, queues, stacks and binary trees.
══════════════════════════════════════════════
Linked Lists.
─────────────
The program POINTERS.PAS is an example of a linked list. The last 'field'
of the record 'PersonRecord' is a pointer called 'Next', which is of type
'PersonPointer', a pointer to PersonRecord. Thus any record, except the
last one, points to the next record. In the program, the entry in the Next
field of the last record is set to 'nil', so indicating the end of the
linked list.
There are three advantages to using linked lists on the heap:
1. Additional records can be added at run-time as often as required,
until the heap is full. There is no need to pre-declare large arrays
to contain the data.
2. The size of the heap is only limited by the size of the remaining
memory, whereas array variables are located in the data segment of
memory, which is limited to 64k.
3. It is relatively easy to traverse a linked list to search for a
specific entry.
Another example program is HEAPLIST.PAS, which can be inspected. On
running this program, memory can be inspected to see the list
information on the heap.
The program HEAPDEMO.EXE is also available on the diskette and may be
run from DOS. It displays on the screen the sequence of events as a
linked list is created on the heap. (For anyone unfamiliar with DOS,
it is run by typing HEAPDEMO and then pressing the ENTER key).
The linked lists described above are single linked lists, which can only
be traversed in one direction. A double linked list has two pointer
variables, one pointing to the previous record and the other pointing
to next record.
The program TWOLINKS.PAS is a program to display on the screen the
creation of a double-linked list on the Heap and to show the action
as the records of the list are traversed both forward and backward
under the control of the right and left arrow keys.
The functions Seg and Ofs are used to determine the addresses on
Heap of each record of the linked list and these addresses are then
displayed as Seg:Ofs for the record and for its fields Previous and
Next. The Number field is also displayed.
In this case, the convention used by Turbo Vision (under which this
Tutor program operates) is employed. This convention uses a capital
letter T to prefix the name of any non-pointer variable type and a
capital P to prefix the name of any pointer variable type. Thus the
type declaration part of the program and part of the Var declaration
is as follows:
Type
PItem = ^ TItem;
TItem = record
Previous : PItem;
Number : integer;
Next : PItem;
End;
Var
First, Last, This : PItem;
The whole program is 363 line long, but during the display, as it is run,
the essential statements for the creation of the linked list are shown,
as below:
New(This)
If First = Nil then First := This else Last^.Next := This; {old Last}
This^.Number := i;
If First = This then This^.Previous := Nil else This^.Previous := Last;
Last := This; {new Last}
Last^.Next := Nil;
Queues.
───────
Queues operate on the First In First Out principle (FIFO) and can be built
out of linked lists. New members of the queue join at the rear, whilst
members leave the queue at the front. Again using 'next' as the field
containing the linking pointer, the code for adding to the rear of the
queue is:
new(temp); { allocate a new record (temp) and then }
rear^.next := temp; { point the old rear record to this new one}
{ instead of the original 'nil' pointer }
temp^.contents := data; { store the new data in the new record and }
temp^.next := nil; { set the pointer of this record to 'nil' }
{ as it is now the new rear record }
rear := temp; { set the rear pointer to point to the new }
{ last record in the queue. }
The code for members leaving at the front is:
temp := front; { assign a temporary pointer to also point }
{ at the front of the queue }
front := front^.next; { change the pointer 'front' to point to }
{ the next, or second, record in the queue }
dispose(temp); { temp points to the old front record and }
{ so can be disposed. }
A typical application of queues is for printer buffering.
Stacks.
───────
A stack operates on a Last In First Out basis (LIFO) and items joining the
stack are said to be 'pushed' on to the stack, whilst items leaving are
said to be 'popped' from the stack. The code for pushing is:
new(temp); { assign a new record (temp) }
temp^.contents := item; { store the new item in this record and }
temp^.next := StackTop; { make the new record point to the top of }
{ the stack }
The code for popping is:
temp := StackTop; { set temporary pointer to stack top }
item := StackTop^.contents { store data from top record }
StackTop := StackTop^.next { make StackTop point to next record }
dispose(temp); { dispose record pointed to by temp. }
A typical application of stacks is for saving register values when a DOS
interrupt procedure is called.
Binary Trees.
─────────────
A Binary Tree has two pointers in each record and they point to a left
branch and a right branch respectively.
If the record is now called a node, then the node at the top is called
the 'root', with 'parents and 'siblings' down the tree to the 'leaf' nodes,
which have both pointers set to 'nil'.
For the simple case of a record of integer values, the declaration of the
record would be:
type
PNode = ^TNode; {PNode is a pointer type which points to a type TNode}
Tnode = record {TNode is a record type with two pointer}
left : PNode; {type fields and one integer type field.}
number : integer;
right : PNode;
end;
A binary tree can be used to sort numbers into order, as shown in the
example program BINTREE.PAS which can be run to check that it does so.
HEAP&PTR.TXT
Revised 22.1.93