home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
modula2
/
tutorial
/
text
/
chap12.txt
< prev
next >
Wrap
Text File
|
1993-03-14
|
26KB
|
586 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 most 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 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. The pointer actually points to an address
somewhere within the computer memory, and can access the
data stored at that address.
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
Page 72
CHAPTER 12 - Pointers and Dynamic Allocation
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.
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 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. 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 a pointer "MyAge" that is pointing to it.
By using the pointer, we can store any INTEGER in it,
because that is its 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 it on the heap, and finally assigns the
address of the variable to the pointer itself. Thus "MyAge"
contains the address of the variable generated. The
variable itself is referenced by using the pointer to it
followed by a ^, and is read, "the variable to which the
pointer points".
The ALLOCATE procedure requires 2 arguments, the first
of which is a pointer which will be used to point to the
desired new block of dynamically allocated menory, 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.
Page 73
CHAPTER 12 - Pointers and Dynamic Allocation
The next statement assigns a place on the heap to an
ARRAY type variable and puts its address in "MyName".
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. By adding the dereference operator to the pointer
name, you can use the entire name just like any other
variable name.
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.
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.
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 chapter. For your own edification,
review the example program BIGREC.MOD before going ahead in
this chapter.
Page 74
CHAPTER 12 - Pointers and Dynamic Allocation
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 the VAR declaration, the first
four variables are defined as pointers here, and 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" before we defined it, which 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 case, but it was more
convenient to put it before, and in the next example
program, it will be required to put it before 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". We dynamically allocate a record with "Self"
pointing to it, and use the pointer to fill the new record.
Compare the statements that fill the record with the
corresponding statements in "BIGREC" 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.
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 the next
statement, but it doesn't work. All the statement 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. The proper way is given in the next two
statements 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.
Page 75
CHAPTER 12 - Pointers and Dynamic Allocation
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.
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, probably leading to a system
crash.
SO WHAT GOOD IS THIS ANYWAY?
Remember when you were initially studying BIGREC? 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 to see how many records it can handle,
remembering that the records are created dynamically, so you
will have to run 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 have a full memory of
640K, I would suggest you start somewhere around 8000
records of "Friend".
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 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
Page 76
CHAPTER 12 - Pointers and Dynamic Allocation
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 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 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.
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.
Lets look at the program itself now. First, 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
Page 77
CHAPTER 12 - Pointers and Dynamic Allocation
write a value to the display as 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.
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 a pointer to it in "TempPlace". Now we can create
another new record 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. The 3 data fields of the new
record are assigned nonsense data for our illustration, and
the pointer field of the new record is assigned NIL.
Lets review our progress to this point. We now have the
first record with a name, composed of 3 parts, 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, lets 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 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 only uses 4 bytes of memory.
We now have generated a linked list of twelve entries.
Page 78
CHAPTER 12 - Pointers and Dynamic Allocation
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 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 of using a
linked list, and it could be advantageous to use in a
database.
A graphic picture of the data should aid in your
understanding of what we have done so far.
StartOfList-->FirstName (first Record)
Initial
LastName
Next---->FirstName (Second Record)
Initial
LastName
Next---->FirstName (Third Record)
Note; The pointer Initial
actually points to LastName
all 4 elements of Next----> etc.
the record. .
.
.
.
etc.--->FirstName (Record 11)
Initial
LastName
Next---->FirstName (Record 12)
Initial
PlaceInList------->LastName
Next---->NIL
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.
Page 79
CHAPTER 12 - Pointers and Dynamic Allocation
Now that the list is defined, we will read the data from
the list and display it on the video monitor. 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 NIL as a pointer.
Finally, it is necessary to DEALLOCATE the list, being
careful to check for the ending NIL 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
many 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 EXERCISE
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. For a much more involved project, read in a list of
simple names and sort them alphabetically by searching
through the list to find where they should go. Insert
each new name into the list by changing pointer values.
For example, to add a new element between number 3 and
4, make the pointer in 3 point to the new element, and
make the pointer in the new element point to number 4.
It is important to note that adding data to the
beginning or end of the list must be handled as special
cases. This is definitely an advanced programming
exercise but you will be greatly rewarded for your
effort if you complete it.
Page 80
