Programmer 7500

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

/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / C / CTUTOR1.ZIP / CHAP12.TXT < prev next >

Wrap

Text File | 1986-06-30 | 26.4 KB | 587 lines

Chapter 12 - Dynamic Allocation WHAT IS DYNAMIC ALLOCATION? Dynamic allocation is very intimidating to a person the first time he comes across it, but that need not be. Simply relax and read this chapter carefully and you will have a good grounding in a very valuable programming resource. All of the variables in every program up to this point have been static variables as far as we are concerned. (Actually, some of them have been "automatic" and were dynamically allocated for you by the system, but it was transparent to you.) In this chapter, we will study some dynamically allocated variables. They are simply variables that do not exist when the program is loaded, but are created dynamically as they are needed. It is possible, using these techniques, to create as many variables as needed, use them, and deallocate their space for use by other variables. As usual, the best teacher is an example, so load and display the program named DYNLIST.C. We begin by defining a named structure "animal" with a few fields pertaining to dogs. We do not define any variables of this type, only three pointers. If you search through the remainder of the program, you will find no variables defined so we have nothing to store data in. All we have to work with are three pointers, each of which point to the defined structure. In order to do anything, we need some variables, so we will create some dynamically. DYNAMIC VARIABLE CREATION The first program statement, which assigns something to the pointer "pet1" will create a dynamic structure containing three variables. The heart of the statement is the "malloc" function buried in the middle of the statement. This is a "memory allocate" function that needs the other things to completely define it. The "malloc" function, by default, will allocate a piece of memory on a "heap" that is "n" characters in length and will be of type character. The "n" must be specified as the only argument to the function. We will discuss "n" shortly, but first we need to define a "heap". WHAT IS A HEAP? Every compiler has a set of limitations on it as to how big the executable file can be, how many variables can be used, how long the source file can be, etc. One limitation placed on users by many compilers for the IBM-PC and compatibles is a limit of 64K for the executable code. This is because the IBM-PC uses a microprocessor with a 64K segment size, and it requires special calls to use data Page 83 Chapter 12 - Dynamic Allocation outside of a single segment. In order to keep the program small and efficient, these calls are not used, and the program is limited but still adequate for most programs. A heap is an area outside of this 64K boundary which can be accessed by the program to store data and variables. The data and variables are put on the "heap" by the system as calls to "malloc" are made. The system keeps track of where the data is stored. Data and variables can be deallocated as desired leading to holes in the heap. The system knows where the holes are and will use them for additional data storage as more "malloc" calls are made. The structure of the heap is therefore a very dynamic entity, changing constantly. MORE ABOUT SEGMENTS Some of the more expensive compilers give the user a choice of memory models to use. Examples are Lattice and Microsoft, which allow the programmer a choice of using a model with a 64K limitation on program size but more efficient running, or using a model with a 640K limitation and requiring longer address calls leading to less efficient addressing. Using the larger address space requires inter segment addressing resulting in the slightly slower running time. The time is probably insignificant in most programs, but there are other considerations. If a program uses no more than 64K bytes for the total of its code and memory and if it doesn't use a stack, it can be made into a .COM file. Since a .COM file is already in a memory image format, it can be loaded very quickly whereas a file in a .EXE format must have its addresses relocated as it is loaded. Therefore a small memory model can generate a program that loads faster than one generated with a larger memory model. Don't let this worry you, it is a fine point that few programmers worry about. Using dynamic allocation, it is possible to store the data on the "heap" and that may be enough to allow you to use the small memory model. Of course, you wouldn't store local variables such as counters and indexes on the heap, only very large arrays or structures. Even more important than the need to stay within the small memory model is the need to stay within the computer. If you had a program that used several large data storage areas, but not at the same time, you could load one block storing it dynamically, then get rid of it and reuse the space for the next large block of data. Dynamically storing each block of data in succession, and using the same storage Page 84 Chapter 12 - Dynamic Allocation for each block may allow you to run your entire program in the computer without breaking it up into smaller programs. BACK TO THE "MALLOC" FUNCTION Hopefully the above description of the "heap" and the overall plan for dynamic allocation helped you to understand what we are doing with the "malloc" function. It simply asks the system for a block of memory of the size specified, and gets the block with the pointer pointing to the first element of the block. The only argument in the parentheses is the size of the block desired and in our present case, we desire a block that will hold one of the structures we defined at the beginning of the program. The "sizeof" is a new function, new to us at least, that returns the size in bytes of the argument within its parentheses. It therefore, returns the size of the structure named animal, in bytes, and that number is sent to the system with the "malloc" call. At the completion of that call, we have a block on the heap allocated to us, with pet1 pointing to the first byte of the block. WHAT IS A CAST? We still have a funny looking construct at the beginning of the "malloc" function call. That is called a "cast". The "malloc" function returns a block with the pointer pointing to it being a pointer of type "char" by default. Many times, if not most, you do not want a pointer to a "char" type variable, but to some other type. You can define the pointer type with the construct given on the example line. In this case we want the pointer to point to a structure of type "animal", so we tell the compiler with this strange looking construct. Even if you omit the cast, most compilers will return a pointer correctly, give you a warning, and go on to produce a working program. It is better programming practice to provide the compiler with the cast to prevent getting the warning message. USING THE DYNAMICALLY ALLOCATED MEMORY BLOCK If you remember our studies of structures and pointers, you will recall that if we have a structure with a pointer pointing to it, we can access any of the variables within the structure. In the next three lines of the program, we assign some silly data to the structure for illustration. It should come as no surprise to you that these assignment statements look just like assignments to statically defined variables. Page 85 Chapter 12 - Dynamic Allocation In the next statement, we assign the value of "pet1" to "pet2" also. This creates no new data, we simply have two pointers to the same object. Since "pet2" is pointing to the structure we created above, "pet1" can be reused to get another dynamically allocated structure which is just what we do next. Keep in mind that "pet2" could have just as easily been used for the new allocation. The new structure is filled with silly data for illustration. Finally, we allocate another block on the heap using the pointer "pet3", and fill its block with illustrative data. Printing the data out should pose no problem to you since there is nothing new in the three print statements. It is left for you to study. GETTING RID OF THE DYNAMICALLY ALLOCATED DATA Another new function is used to get rid of the data and free up the space on the heap for reuse, the function "free". To use it, you simply call it with the pointer to the block as the only argument, and the block is deallocated. In order to illustrate another aspect of the dynamic allocation and deallocation of data, an additional step is included in the program on your monitor. The pointer "pet1" is assigned the value of "pet3". In doing this, the block that "pet1" was pointing to is effectively lost since there is no pointer that is now pointing to that block. It can therefore never again be referred to, changed, or disposed of. That memory, which is a block on the heap, is wasted from this point on. This is not something that you would ever purposely do in a program. It is only done here for illustration. The first "free" function call removes the block of data that "pet1" and "pet3" were pointing to, and the second "free" call removes the block of data that "pet2" was pointing to. We therefore have lost access to all of our data generated earlier. There is still one block of data that is on the heap but there is no pointer to it since we lost the address to it. Trying to "free" the data pointed to by "pet1" would result in an error because it has already been "freed" by the use of "pet3". There is no need to worry, when we return to DOS, the entire heap will be disposed of with no regard to what we have put on it. The point does need to made that losing a pointer to a block of the heap, forever removes that block of data storage from our program and we may need that storage later. Page 86 Chapter 12 - Dynamic Allocation Compile and run the program to see if it does what you think it should do based on this discussion. THAT WAS A LOT OF DISCUSSION It took nearly four pages to get through the discussion of the last program but it was time well spent. It should be somewhat exciting to you to know that there is nothing else to learn about dynamic allocation, the last four pages covered it all. Of course, there is a lot to learn about the technique of using dynamic allocation, and for that reason, there are two more files to study. But the fact remains, there is nothing more to learn about dynamic allocation than what was given so far in this chapter. AN ARRAY OF POINTERS Load and display the file BIGDYNL.C for another example of dynamic allocation. This program is very similar to the last one since we use the same structure, but this time we define an array of pointers to illustrate the means by which you could build a large database using an array of pointers rather than a single pointer to each element. To keep it simple we define 12 elements in the array and another working pointer named "point". The "*pet[12]" is new to you so a few words would be in order. What we have defined is an array of 12 pointers, the first being "pet[0]", and the last "pet[11]". Actually, since an array is itself a pointer, the name "pet" by itself is a pointer to a pointer. This is valid in C, and in fact you can go farther if needed but you will get quickly confused. I know of no limit as to how many levels of pointing are possible, so a definition such as "int ****pt" is legal as a pointer to a pointer to a pointer to a pointer to an integer type variable, if I counted right. Such usage is discouraged until you gain considerable experience. Now that we have 12 pointers which can be used like any other pointer, it is a simple matter to write a loop to allocate a data block dynamically for each and to fill the respective fields with any data desirable. In this case, the fields are filled with simple data for illustrative purposes, but we could be reading in a database, readings from some test equipment, or any other source of data. A few fields are randomly picked to receive other data to illustrate that simple assignments can be used, and the data is printed out to the monitor. The pointer "point" is used in the printout loop only to serve as an illustration, Page 87 Chapter 12 - Dynamic Allocation the data could have been easily printed using the "pet[n]" means of definition. Finally, all 12 blocks of data are freed before terminating the program. Compile and run this program to aid in understanding this technique. As stated earlier, there was nothing new here about dynamic allocation, only about an array of pointers. A LINKED LIST We finally come to the grandaddy of all programming techniques as far as being intimidating. Load the program DYNLINK.C for an example of a dynamically allocated linked list. It sounds terrible, but after a little time spent with it, you will see that it is simply another programming technique made up of simple components that can be a powerful tool. In order to set your mind at ease, consider the linked list you used when you were a child. Your sister gave you your birthday present, and when you opened it, you found a note that said, "Look in the hall closet." You went to the hall closet, and found another note that said, "Look behind the TV set." Behind the TV you found another note that said, "Look under the coffee pot." You continued this search, and finally you found your pair of socks under the dogs feeding dish. What you actually did was to execute a linked list, the starting point being the wrapped present and the ending point being under the dogs feeding dish. The list ended at the dogs feeding dish since there were no more notes. In the program DYNLINK.C, we will be doing the same thing as your sister forced you to do. We will however, do it much faster and we will leave a little pile of data at each of the intermediate points along the way. We will also have the capability to return to the beginning and retraverse the entire list again and again if we so desire. THE DATA DEFINITIONS This program starts similarly to the last two with the addition of the definition of a constant to be used later. The structure is nearly the same as that used in the last two programs except for the addition of another field within the structure, the pointer. This pointer is a pointer to another structure of this same type and will be used to point to the next structure in order. To continue the above analogy, this pointer will point to the next note, which in turn will contain a pointer to the next note after that. Page 88 Chapter 12 - Dynamic Allocation We define three pointers to this structure for use in the program, and one integer to be used as a counter, and we are ready to begin using the defined structure for whatever purpose we desire. In this case, we will once again generate nonsense data for illustrative purposes. THE FIRST FIELD Using the "malloc" function, we request a block of storage on the "heap" and fill it with data. The additional field in this example, the pointer, is assigned the value of NULL, which is only used to indicate that this is the end of the list. We will leave the pointer "start" at this structure, so that it will always point to the first structure of the list. We also assign "prior" the value of "start" for reasons we will see soon. Keep in mind that the end points of a linked list will always have to be handled differently than those in the middle of a list. We have a single element of our list now and it is filled with representative data. FILLING ADDITIONAL STRUCTURES The next group of assignments and control statements are included within a "for" loop so we can build our list fast once it is defined. We will go through the loop a number of times equal to the constant "RECORDS" defined at the beginning of our program. Each time through, we allocate memory, fill the first three fields with nonsense, and fill the pointers. The pointer in the last record is given the address of this new record because the "prior" pointer is pointing to the prior record. Thus "prior->next" is given the address of the new record we have just filled. The pointer in the new record is assigned the value "NULL", and the pointer "prior" is given the address of this new record because the next time we create a record, this one will be the prior one at that time. That may sound confusing but it really does make sense if you spend some time studying it. When we have gone through the "for" loop 6 times, we will have a list of 7 structures including the one we generated prior to the loop. The list will have the following characteristics. 1. "start" points to the first structure in the list. 2. Each structure contains a pointer to the next structure. Page 89 Chapter 12 - Dynamic Allocation 3. The last structure has a pointer that points to NULL and can be used to detect the end. start->struct1 This diagram should aid in name understanding the structure of breed the data at this point. age point->struct2 name breed age point->struct3 name breed age point-> . . . . struct7 name breed age point->NULL It should be clear to you, if you understand the above structure, that it is not possible to simply jump into the middle of the structure and change a few values. The only way to get to the third structure is by starting at the beginning and working your way down through the structure one record at a time. Although this may seem like a large price to pay for the convenience of putting so much data outside of the program area, it is actually a very good way to store some kinds of data. A word processor would be a good application for this type of data structure because you would never need to have random access to the data. In actual practice, this is the basic type of storage used for the text in a word processor with one line of text per record. Actually, a program with any degree of sophistication would use a doubly linked list. This would be a list with two pointers per record, one pointing down to the next record, and the other pointing up to the record just prior to the one in question. Using this kind of a record structure would allow traversing the data in either direction. PRINTING THE DATA OUT To print the data out, a similar method is used as that used to generate the data. The pointers are initialized and are then used to go from record to record reading and displaying each record one at a time. Printing is terminated when the NULL on the last record is found, so the Page 90 Chapter 12 - Dynamic Allocation program doesn't even need to know how many records are in the list. Finally, the entire list is deleted to make room in memory for any additional data that may be needed, in this case, none. Care must be taken to assure that the last record is not deleted before the NULL is checked. Once the data is gone, it is impossible to know if you are finished yet. MORE ABOUT DYNAMIC ALLOCATION AND LINKED LISTS It is not difficult, and it is not trivial, to add elements into the middle of a linked lists. It is necessary to create the new record, fill it with data, and point its pointer to the record it is desired to precede. If the new record is to be installed between the 3rd and 4th, for example, it is necessary for the new record to point to the 4th record, and the pointer in the 3rd record must point to the new one. Adding a new record to the beginning or end of a list are each special cases. Consider what must be done to add a new record in a doubly linked list. Entire books are written describing different types of linked lists and how to use them, so no further detail will be given. The amount of detail given should be sufficient for a beginning understanding of C and its capabilities. ANOTHER NEW FUNCTION - CALLOC One more function must be mentioned, the "calloc" function. This function allocates a block of memory and clears it to all zeros which may be useful in some circumstances. It is similar to "malloc" and will be left as an exercise for you to read about and use "calloc" if you desire. PROGRAMMING EXERCISES 1. Rewrite the example program STRUCT1.C from chapter 11 to dynamically allocate the two structures. 2. Rewrite the example program STRUCT2.C from chapter 11 to dynamically allocate the 12 structures. Page 91