Shareware Overload/ShartewareOverload.cdr/progm/m2t-1.zip/CHAP12.TXT

Text File | 1989-01-18 | 25KB | 587 lines

                                                    Chapter 12

                               POINTERS AND DYNAMIC ALLOCATION



PREREQUISITES FOR THIS MATERIAL
______________________________________________________________

In order to understand this chapter, you should have a good
grasp of the entirety of Part I and a clear understanding of
chapter 11.

For certain types of programs, pointers and dynamic allocation
can be a tremendous advantage, but many programs do not need
such a high degree of data structure.  For that reason, it
would probably be to your advantage to lightly skim over these
topics and come back to them later when you have a substantial
base of Modula-2 programming experience.  It would be good to
at least skim over this material rather than completely
neglecting it, so you will have an idea of how pointers and
dynamic allocation work and that they are available for your
use when needed.

A complete understanding of this material will require deep
concentration as it is very complex and not at all intuitive.
Nevertheless, if you pay close attention, you will have a good
grasp of pointers and dynamic allocation in a short time.



WHAT ARE POINTERS, AND WHAT GOOD ARE THEY?
______________________________________________________________

If you examine POINTERS.MOD, you will see     ================
a very trivial example of pointers and how      POINTERS.MOD
they are used.  In the var declaration,       ================
you will see that the two variables have
the two reserved words POINTER TO in front of their respective
types.  These are not actually variables, instead they point
to dynamically allocated variables that have not been defined
yet, and they are called pointers.  We will see, when we get
to chapter 14, that a pointer can be used to point to any
variable, even a statically defined one, but that will have
to wait awhile.

The pointer MyName is a pointer to a 20 character string and
is therefore not a variable into which a value can be stored.
This is a very special type, and it cannot be assigned a
character string, only a pointer value or address.  Likewise
MyAge is a pointer to an integer type variable even though it
has nothing to point at.  Note that neither pointer has
anything to point at yet.  Note that Modula-2 does not
initialize pointers automatically.  It is up to you to
initialize all pointers prior to using them.

                                                          12-1

                  Chapter 12 - Pointers and Dynamic Allocation

Your computer has some amount of memory installed in it.  If
it is an IBM-PC or compatible, it can have up to 640K of RAM
which is addressable by various programs.  The operating
system requires about 60K of the total, and your program can
use up to 64K assuming that your compiler uses a small memory
model.  Adding those two numbers together results in about
124K.  Any memory you have installed in excess of that is
available for the stack and the heap.  The stack is a standard
DOS defined and controlled area that can grow and shrink as
needed.  Many books are available to define the stack if you
are interested in more information on it.


WHAT IS THE HEAP?
______________________________________________________________

The heap is a Modula-2 entity that utilizes otherwise unused
memory to store data.  It begins immediately following the
program and grows as necessary upward toward the stack which
is growing downward.  As long as they never meet, there is no
problem.  If they meet, a run-time error is generated.  The
heap is therefore outside of the actual program and local data
storage space.

If you did not understand the last two paragraphs, don't
worry.  Simply remember that dynamically allocated variables
are stored on the heap and do not count in the 64K limitation
placed upon you by some compilers.

Back to our example program, POINTERS.MOD.  When we actually
begin executing the program, we still have not defined the
variables we wish to use to store data in.  We only have 2
pointers defined at this point in the program, and the data
space can be pictured graphically as shown in fig 12-1 where
a pointer is a box with a dot in it.  The first executable
statement in line 15 generates a variable for us with no name
and stores it on the heap.  Since it has no name, we cannot
do anything with it, except for the fact that we do have the
pointer MyAge that is pointing to it.  By using the pointer,
we can store any integer type variable in it, because that is
its defined type, and later go back and retrieve it.


WHAT IS DYNAMIC ALLOCATION?
______________________________________________________________

The variable we have just described is a dynamically allocated
variable because it was not defined in a VAR declaration, but
with an ALLOCATE procedure.  The ALLOCATE procedure creates
a variable of the type defined by the pointer, puts the new
variable on the heap, and assigns the address of the variable
to the pointer itself.  Thus MyAge contains the address of the
variable generated.

                                                          12-2

                  Chapter 12 - Pointers and Dynamic Allocation

The allocate procedure requires 2 parameters, the first of
which is a pointer which will be used to point to the desired
new block of dynamically allocated memory, and the second
which gives the size of the block in bytes.  The supplied
function TSIZE will return the size of the block of data
required by the type supplied to it as an argument.  Be sure
to use the type of the data and not the type of the pointer
to the data for the argument.  Another procedure is available
named SIZE which returns the size of any variable in bytes.

The statement in line 16 dynamically allocates an array type
variable which is large enough to store 20 char type data
points, and assigns its address to MyName.  The data space
would now appear as depicted in fig 12-2.  Following the
allocate statements, we have two assignment statements in
which the two variables pointed at are assigned values
compatible with their respective types, and they are both
written out to the video display.  Notice that both of these
operations use the ^ which is the dereference operator which
tells the system to store the data at the location where the
pointer is pointing.  By adding the dereference operator to
the pointer name, you can use the entire name just like any
other variable name.  Figure 12-3 is a graphical
representation of the data space after the data has been
assigned.

Lines 21 through 26 illustrate use of the stored data, and the
last two statements are illustrations of the way the
dynamically allocated variables are removed from use.  When
they are no longer needed, they are disposed of with the
DEALLOCATE procedure, and the space on the heap is freed up
for use by other dynamically allocated variables.


ARE POINTERS REALLY USEFUL?
______________________________________________________________

In such a simple program, pointers cannot be appreciated, but
it is necessary for a simple illustration.  In a large, very
active program, it is possible to define many variables,
dispose of some of them, define more, and dispose of more,
etc.  Each time some variables are deallocated, their space
is then made available for additional variables defined with
the allocate procedure.

The heap can be made up of any assortment of variables, they
do not have to all be the same.  One thing must be remembered.
Anytime a variable is defined, it will have a pointer pointing
to it.  The pointer is the only means by which the variable
can be accessed.  If the pointer to the variable is lost or
changed, the data itself is lost for all practical purposes.



                                                          12-3

                  Chapter 12 - Pointers and Dynamic Allocation

WHAT ABOUT THE NEW AND DISPOSE PROCEDURES?
______________________________________________________________

The new and dispose procedures are a carryover from Pascal and
are available on some Modula-2 compilers.  When they are
available, they are simply translated internally into calls
to allocate and deallocate which must be imported in order to
use new and dispose.  Since they are being removed from the
language definition, their use should be discouraged in favor
of the more universal allocate and deallocate procedures.


DYNAMICALLY STORING RECORDS;
______________________________________________________________

The next example program, DYNREC.MOD, is a    ================
repeat of one we studied in an earlier           DYNREC.MOD
chapter.  For your own edification, review    ================
the example program BIGREC.MOD before
going ahead in this chapter.

Assuming that you are back in DYNREC.MOD, you will notice that
this program looks very similar to the earlier one, and in
fact, they do exactly the same thing.  The only difference in
the type declaration is the addition of a pointer PersonID,
and in lines 30 and 31 of the var declaration, the variables
are defined as pointers, whereas they were defined as record
variables in the last program.


WE JUST BROKE THE GREAT RULE OF MODULA-2
______________________________________________________________

Notice in the type declaration that we used the identifier
Person in line 22 prior to defining it, which we said earlier
is illegal in Modula-2.  Foreseeing the need to define a
pointer prior to the record, the designer of Modula-2 allows
us to break the rule in this one place.  The pointer could
have been defined after the record in this particular example,
but it was more convenient to put it first, and in the next
example program, it will be required to define it ahead of the
record.  We will get there soon.

Examining the var declaration, we see that Friend is really
50 pointers, so we have now defined 53 different pointers to
records, but no variables other than Temp and Index.  Figure
12-4 illustrates the data space at this time.  We dynamically
allocate a record with Self pointing to it in line 36, and use
the pointer to fill the new record in lines 38 through 49.
Compare the statements that fill the record with the
corresponding statements in BIGREC.MOD and you will see that
they are identical except for the addition of the ^ to each
use of the pointer to designate the data pointed to.  Once
again, this is called dereferencing the pointer.

                                                          12-4

                  Chapter 12 - Pointers and Dynamic Allocation

THIS IS A TRICK, BE CAREFUL
______________________________________________________________

Now go down to the place where Mother is assigned a record and
is then pointing to the record.  It seems an easy thing to do
then to simply assign all of the values of Self to all the
values of Mother as shown in line 52, but it doesn't work.
All the statement in line 52 does, is make the pointer Mother
point to the same place where Self is pointing.  The data
space that was allocated to the pointer Mother is now
somewhere on the heap, but since we have lost the original
pointer to it, we cannot find it, use it, or deallocate it.
This is an example of losing data on the heap.  Figure 12-5
illustrates the data space at this time.  The proper way of
assigning data from one dynamically allocated record to
another is given in line 55 where all fields of Father are
defined by all fields of Mother which is pointing at the
original Self record.

Note that since Mother and Self are both pointing at the same
record, changing the data with either pointer results in the
data appearing to be changed in both because there is, in
fact, only one data field.

The loop in lines 57 through 60 dynamically allocates 50
records and uses the 50 pointers in the Friend array to point
to them, then fills each record with the data contained in the
record pointed to by the pointer named Mother.  Three values
are finally output to the monitor in lines 63 through 65 for
illustrative purposes.


A NOTE FOR PASCAL PROGRAMMERS
______________________________________________________________

In order to write from or read into a dynamically assigned
record it is necessary to use a temporary record since
dynamically assigned records are not allowed to be used in I/O
statements in Pascal.  This is not true in Modula-2, and you
can write directly out of a dynamically allocated record in
Modula-2.  This is illustrated in the section of the program
that writes some data to the monitor.  Notice line 62 where
the data from a dynamically allocated record is assigned to
all fields of a statically defined record.

Finally, the dynamically allocated variables are deallocated
prior to ending the program.  For a simple program such as
this, it is not necessary to deallocate them because all
dynamic variables are deallocated automatically when the
program is terminated, but the deallocate steps are included
for illustration.  Notice that if the DEALLOCATE(Mother)
statement was included in the program, the data could not be
found due to the lost pointer, and the program would be
unpredictable, possibly leading to a system crash.

                                                          12-5

                  Chapter 12 - Pointers and Dynamic Allocation

WHAT GOOD IS THIS ANYWAY?
______________________________________________________________

Remember when you were initially studying BIGREC.MOD?  I
suggested that you see how big you could make the constant
NumberOfFriends before you ran out of memory.  At that time
you probably found that it could be made slightly greater than
1000 before you got the memory overflow message at
compilation.  If your compiler uses a large memory model, you
may have been able to go much larger.  Try the same thing with
DYNREC.MOD to see how many records it can handle, remembering
that the records are created dynamically, so you will have to
execute the program to actually run out of memory.  The final
result will depend on how much memory you have installed, and
how many memory resident programs you are using such as
Sidekick.  If you are using a personal computer and have a
full memory of 640K, I would suggest you start somewhere
around 8000 records of Friend.  If you are using a
minicomputer, you may be able to store considerably more
records before running out of memory.
Now you should have a good idea of why dynamic allocation can
be used to greatly increase the usefulness of your programs.
There is, however, one more important topic we must cover on
dynamic allocation.  That is the linked list.


WHAT IS A LINKED LIST?
______________________________________________________________

Understanding and using a linked list is      ================
by far the most baffling topic you will         LINKLIST.MOD
confront in Modula-2.  Many people simply     ================
throw up their hands and never try to use
a linked list.  I will try to help you understand it by use
of an example and lots of explanation.  Examine the program
LINKLIST.MOD for an example of a linked list.  I tried to keep
it short so you could see the entire operation and yet do
something meaningful.

To begin with, notice that there are two types defined, a
pointer to the record and the record itself.  The record,
however, has one thing about it that is new to us, the last
entry, Next is a pointer to this very record.  This record
then, has the ability to point to itself, which would be
trivial and meaningless, or to point to another record of the
same type, which would be extremely useful in some cases.  In
fact, this is the way a linked list is used.  I must point out
that the pointer to another record, in this case called Next,
does not have to be last in the list, it can be anywhere it
is convenient for you.

A couple of pages ago, we discussed the fact that we had to
break the great rule of Modula-2 and use an identifier before
it was defined.  This is the reason the exception to the rule

                                                          12-6

                  Chapter 12 - Pointers and Dynamic Allocation

was allowed.  Since the pointer points to the record, and the
record contains a reference to the pointer, one has to be
defined after being used, and by rules of Modula-2, the
pointer can be defined first.  That is a mouthful but if you
just use the syntax shown in the example, you will not get
into trouble with it.  Figure 12-6 is a graphical
representation of the data space at this time.


STILL NO VARIABLES?
______________________________________________________________

It may seem strange, but we still will have no variables
defined, except for our old friend Index.  In fact, for this
example, we will only define 3 pointers.  In the last example
we defined 54 pointers, and had lots of storage room.  Before
we are finished, we will have at least a dozen pointers but
they will be stored in our records, so they too will be
dynamically allocated.

Let's look at the program itself now.  In line 26, we create
a dynamically allocated record and define it by the pointer
PlaceInList.  It is composed of the three data fields, and
another pointer.  We define StartOfList to point to the first
record created, and we will leave it unchanged throughout the
program.  The pointer StartOfList will always point to the
first record in the linked list which we are building up.

We define the three variables in the record to be any name we
desire for illustrative purposes, and set the pointer in the
record to NIL.  NIL is a reserved word that doesn't put an
address in the pointer but defines it as empty.  A pointer
that is currently NIL cannot be used to access any data
because it has no value, but it can be tested in a logical
statement to see if it is NIL.  It is therefore a dummy
assignment.  With all of that, the first record is completely
defined, and the data space is illustrated in figure 12-7.


DEFINING THE SECOND RECORD
______________________________________________________________

When you were young you may have played a searching game in
which you were given a clue telling you where the next clue
was at.  The next clue had a clue to the location of the third
clue.  You kept going from clue to clue until you found the
prize.  You simply exercised a linked list.  We will now build
up the same kind of a list in which each record will tell us
where the next record is at.

We will now define the second record.  Our goal will be to
store a pointer to the second record in the pointer field of
the first record.  In order to keep track of the last record,
the one in which we need to update the pointer, we will keep

                                                          12-7

                  Chapter 12 - Pointers and Dynamic Allocation

a pointer to it in TempPlace, which we do in line 35.  Now we
can create another new record in line 36 and use PlaceInList
to point to it.  Since TempPlace is still pointing at the
first record, we can use it to store the value of the pointer
to the new record in the old record which we do in line 37.
The 3 data fields of the new record are assigned nonsense data
in lines 38 through 40 for our illustration, and the pointer
field of the new record is assigned NIL.  See figure 12-8.

Let's review our progress to this point.  We now have the
first record with a name, composed of 3 parts stored in it,
and a pointer to the second record.  We also have a second
record storing a different name and a pointer assigned NIL.
We also have three pointers, one pointing to the first record,
one pointing to the last record, and one we used just to get
here since it is only a temporary pointer.  If you understand
what is happening so far, let's go on to add some additional
records to the list.  If you are confused, go back over this
material again.


TEN MORE RECORDS
______________________________________________________________

The next section of code beginning in line 45, is contained
within a FOR loop so the statements are simply repeated ten
times.  If you observe carefully, you will notice that the
statements are identical to the second group of statements in
the program (except of course for the name assigned).  They
operate in exactly the same manner, and we end up with ten
more names added to the list.  You will now see why the
temporary pointer was necessary, but pointers are cheap, so
feel free to use them at will.  A pointer generally uses only
4 bytes of memory.

One additional feature is illustrated in line 47.  The
function procedure named Available is used to determine if
there is enough space available on the heap to allocate the
record.  This function procedure call passes the desired size
to the procedure which returns a boolean value.  In this case,
because the program is so small, we ignore the result, but a
meaningful program should test prior to each allocation call
and if it got a false returned, it would need to perform some
error recovery routine.

After one pass through the loop, the data space will appear
as shown in figure 12-9.  Each pass through the loop will add
one new record to the list.  Further graphs will not be drawn
but will be left to the student to draw, if he so desires.

After completing the loop in lines 46 through 54, we have a
linked list of twelve entries.  We have a pointer pointing at
the first entry, and another pointer pointing at the last.
The only data stored within the program itself are three

                                                          12-8

                  Chapter 12 - Pointers and Dynamic Allocation

pointers, and one integer, all of the dynamically allocated
data is on the heap.  This is one advantage to a linked list,
it uses very little internal memory, but it is costly in terms
of programming.  You should never use a linked list simply to
save memory, but only because a certain program lends itself
well to it.  Some sorting routines are extremely fast because
they use a linked list, and it could be advantageous to use
in a database.


HOW DO WE GET TO THE DATA NOW?
______________________________________________________________

Since the data is in a list, how can we get a copy of the
fourth entry, for example?  The only way is to start at the
beginning of the list and successively examine pointers until
you reach the desired one.  Suppose you are at the fourth and
then wish to examine the third.  You cannot back up, because
you didn't define the list that way, you can only start at the
beginning and count to the third.  You could have defined the
record with two pointers, one pointing forward, and one
pointing backward.  This would be a doubly-linked list and you
could then go directly from entry four to entry three.

Now that the list is defined, we will read the data from the
list and display it on the video monitor in lines 58 through
66.  We begin by defining the pointer, PlaceInList, as the
start of the list.  Now you see why it was important to keep
a copy of where the list started.  In the same manner as
filling the list, we go from record to record until we find
the record with the value of NIL stored in its pointer.

Finally, it is necessary to deallocate the list, being careful
to check for the ending NIL value before you deallocate it.
It will be left for you to deallocate the records if you have
such a desire.

There are entire books on how to use linked lists, and some
Modula-2 programmers will seldom, if ever, use them.  For this
reason, additional detail is considered unnecessary, but to
be a fully informed Modula-2 programmer, some insight into
linked lists is necessary.


PROGRAMMING EXERCISES
______________________________________________________________

1.   Write a program to store a few names dynamically, then
     display the stored names on the monitor.  As your first
     exercise in dynamic allocation, keep it very simple.

2.   Add the necessary code to LINKLIST.MOD to deallocate all
     of the records.


                                                          12-9

                  Chapter 12 - Pointers and Dynamic Allocation

Note; The figures referred to in this chapter are graphics
      which are impossible to include in a text file.  Since
      there is no way to include them, we have made it possi-
      ble for you to obtain a copy of these figures.  See the
      READ.ME file for details.
















































                                                         12-10