Ctutor chapter 12

                      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