Programmer 7500

home *** CD-ROM | disk | FTP | other *** search

/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / PASCTUT1.ZIP / CHAP12.TXT < prev next >

Wrap

Text File | 1986-07-14 | 21.9 KB | 521 lines

CHAPTER 12 - Pointers and Dynamic Allocation 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 Pascal 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, 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 a ^ 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. The pointer "my_name" 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 Pascal 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 if you are using TURBO Pascal it requires about 35K. The TURBO Pascal program can use up to 64K. Adding those three numbers together results in about 159K. 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. Page 60 CHAPTER 12 - Pointers and Dynamic Allocation The heap is a Pascal defined 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 64K limitation of TURBO Pascal and many other Pascal compilers. 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. 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 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 "my_name" that is pointing to it. By using the pointer, we can store up to 20 characters 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 a "new" procedure. The "new" 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 "my_name" 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 next statement assigns a place on the heap to an INTEGER type variable and puts its address in "my_age". Following the "new" 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. 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 "dispose" procedure. 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 Page 61 CHAPTER 12 - Pointers and Dynamic Allocation many variables, dispose of some of them, define more, and dispose of more, etc. Each time some variables are disposed of, their space is then made available for additional variables defined with the "new" 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. DYNAMICALLY STORING RECORDS; The next example program, DYNREC, is a repeat of one we studied in an earlier chapter. For your own edification, review the example program BIGREC before going ahead in this chapter. Assuming that you are back in DYNREC, 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 "person_id", 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 PASCAL Notice in the TYPE declaration that we used the identifier "person" before we defined it, which is illegal to do in Pascal. Foreseeing the need to define a pointer prior to the record, the designers of Pascal allow 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. Since "friend" is really 50 pointers, we have now defined 53 different pointers to records, but so far have defined no variables other than "temp" and "index". We immediately define a record with "self" pointing to it, and use the pointer so defined to fill the record defined. Compare this to "BIGREC" and you will see that it is identical except for the addition of the "new" and adding the ^ to each use of the pointer to designate the data pointed to. Page 62 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 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 that was allocated to the pointer "mother" is now somewhere on the heap, but we don't know where, so 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 field. 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. This is illustrated in the section of the program that writes some data to the monitor. Finally, the dynamically allocated variables are disposed of prior to ending the program. For a simple program such as this, it is not necessary to dispose of them because all dynamic variables are disposed of automatically when the program is terminated. Notice that if the "dispose(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 "number_of_friends" before you ran out of memory. At that time we found that it could be made slightly greater than 1000 before we got the memory overflow message at compilation. 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 above 8000 records of "friend". Page 63 CHAPTER 12 - Pointers and Dynamic Allocation 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 Pascal. 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 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 Pascal 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 Pascal, the pointer can be defined first, provided that the record is defined immediately following it. 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. Page 64 CHAPTER 12 - Pointers and Dynamic Allocation Lets look at the program itself now. First, we create a dynamically allocated record and define it by the pointer "place_in_list". It is composed of the three data fields, and another pointer. We define "start_of_list" to point to the first record created, and we will leave it unchanged throughout the program. The pointer "start_of_list" 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 written 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 "temp_place". Now we can create another "new" record and use "place_in_list" to point to it. Since "temp_place" is now pointing at the first record, we can use it to store the value of the pointer which points to the new 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 and a pointer to the second record, and a second record with 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. Page 65 CHAPTER 12 - Pointers and Dynamic Allocation 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. 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 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. 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. We begin by defining the pointer, "place_in_list", 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. There are entire books on how to use linked lists, and most Pascal programmers will seldom, if ever, use them. For this reason, additional detail is considered unnecessary, but to be a fully informed Pascal programmer, some insight is necessary. Page 66 CHAPTER 12 - Pointers and Dynamic Allocation 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. Page 67