C!T ROM 2/ctrom_ii_b.zip/ctrom_ii_b/PROGRAM/PASCAL/PASTUT34/HEAP&PTR.TXT

Text File | 1993-06-12 | 14KB | 312 lines

                  DYNAMIC MEMORY MANAGEMENT AND POINTERS.
                  ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀

 Most variables dealt with so far have been 'static', i.e. their form and
 size is pre-determined, and they exist throughout the entire execution of
 the block in which they are declared. They may of course change in value,
 but not in form and size.

 Programs, however, frequently need the use of a data structure which varies
 in form and size during execution. 'Dynamic' variables serve this purpose
 as they are generated as the need arises and may be discarded after use.

 Such dynamic variables are not declared in an explicit variable declaration
 like static variables, and they cannot be referenced directly by identifier
 Instead, a special variable containing the memory address of the variable
 is used to point to the variable. This special variable is called a
 'pointer' variable.

 Pointer variables themselves are just 4 bytes in size and contain the
 address, as segment and offset values, of the place in memory where the
 data structure is located. The data structure at that address can be of
 any size and form.

 A pointer type is defined by the symbol ^ (caret) succeeded by the type
 identifier of the dynamic variable to be referenced by the pointer
 variable. The example program POINTERS.PAS shows how to declare a record
 with associated pointers. The type PersonPointer is declared as a pointer
 to variables of the type PersonRecord, as shown below:

 Type
   PersonPointer = ^PersonRecord;              { Pointer type declaration }

   { Read as 'PersonPointer is a pointer to the record-type PersonRecord' }

   PersonRecord = Record                        { Record-type declaration }
                    Name : string[50];          { Field 51 bytes in size  }
                    Job  : string[50];          { Field 51 bytes in size  }
                    Next : PersonPointer;       { Pointer to next record, }
                  end;                          { 4 bytes in size         }

 Var
   FirstPerson, LastPerson, NewPerson : PersonPointer;


 The variables FirstPerson, LastPerson, and NewPerson are thus pointer
 variables which can point at records of the type PersonRecord.  As shown,
 the type identifier in a pointer type definition (PersonRecord) may refer
 to an identifier which is only subsequently defined.

 Although each pointer variable, such as NewPerson, only occupies 4 bytes
 of static memory in the data segment, it is cumbersome and unnecessary to
 use a static pointer for each record on the heap. As shown above, it is
 better to include one, or more, pointers as field(s) in the dynamic type
 variable PersonRecord. The field Next contains a pointer, of type
 PersonPointer, which points to the next record.

 Records types, which contain pointer fields, are called linked lists and
 these are discussed in detail later in this note.

 The dynamic variable pointed to by a pointer is dereferenced by using
 the pointer symbol (^) after the pointer variable, as shown in the
 program POINTERS.PAS at line number 77:
                                         NewPerson^.Name := Name;

 where NewPerson^.Name  refers to the Name field of the record pointed to
 by the pointer NewPerson.


 Allocating Dynamic Variables.
 ═════════════════════════════
 Before it is sensible to use these pointer variables, there must be some
 variables to point at. New variables of any type are allocated with the
 standard procedure 'New'. The one parameter of New is the pointer variable
 of the type to be created, as now illustrated:
                                                  New(FirstPerson);

 This has the effect of having 'FirstPerson' point at the start address of
 a dynamically allocated record of the type 'PersonRecord'.
 Thus 'FirstPerson' contains the 4-byte address of a variable of type
 'PersonRecord' and the required space (106 bytes) has been allocated in
 memory to hold such a variable.

 The pointer value NIL is compatible with all pointer types. NIL points
 to the address 0:0 and may be assigned to pointer variables to indicate
 the absence of a usable pointer. Care must be taken never to write to the
 address 0:0 because it is the start address of the Vector Interrupt Table,
 used by the operating system.

 Dynamic variables created by the standard procedure 'New' are allocated
 space on a stack-like structure, called the 'Heap', at run-time.
 Turbo Pascal controls the heap by maintaining a heap pointer which at the
 beginning of a program is initialized to the address of the first free
 byte in memory. On each call to 'New', the heap pointer is moved towards
 the top of free memory by the number of bytes corresponding to the size of
 the new dynamic variable.

 The size of both the Stack and the Heap can be set by selecting Options
 from the menu bar at the top of the screen, when using the Integrated
 Development Environment, and then choosing Memory sizes from the sub-menu.
 These memory sizes can also be set by using Compiler Directives within the
 program. Generally and especially for large databases, it is wise to set
 the heap upper limit to its maximum value, typically 655360.

 If there is insufficient memory available on the heap to allocate space
 for a new dynamic variable, a standard function, HeapFunc, is called and
 it sets the variable HeapError to 0, so causing a run-time error, which
 halts the program. To avoid halting the program, the user can write an
 alternative function, HeapFunc, to replace the standard one and avoid
 the run-time error, but instead provide a warning. See page 217 of the
 Programmer's Guide for more information.


 Removing Dynamic Variables.
 ═══════════════════════════

 When a dynamic variable is no longer required by the program, it can be
 removed by a call to the Dispose procedure, which requires one parameter,
 the pointer variable name.
                           e.g.  Dispose(FirstPerson);

 Dispose removes the address contained in the pointer variable in static
 memory (FirstPerson) and also removes the data structure, to which it
 points, from the heap.

 Dispose only removes one dynamic variable from the heap for each call and
 since the heap is not automatically compacted, there are resultant 'holes'
 in the heap. Should it be necessary to remove a block of dynamic variables,
 from a given address onwards to the end of the heap, then the procedures
 Mark and Release must be used.

 The Mark procedure assigns the value of the heap pointer to a variable.
 The syntax is:
               Mark(P);

 where P is a pointer-type variable.

 The Release procedure sets the heap pointer to the address contained in
 the argument. The syntax is:
                             Release(P);

 where P is the pointer-type variable, previously set by Mark.

 Release thus discards all dynamic variables above this address and cannot
 release the space used by variables in the middle of the heap.

 Heap Management.
 ════════════════
 The standard function 'MemAvail' is available to determine the available
 space on the heap. Other memory management procedures and functions are
 listed on page 126 of the Programmer's Guide.



 Linked lists, queues, stacks and binary trees.
 ══════════════════════════════════════════════

 Linked Lists.
 ─────────────
 The program POINTERS.PAS is an example of a linked list.  The last 'field'
 of the record 'PersonRecord' is a pointer called 'Next', which is of type
 'PersonPointer', a pointer to PersonRecord.  Thus any record, except the
 last one, points to the next record. In the program, the entry in the Next
 field of the last record is set to 'nil', so indicating the end of the
 linked list.

 There are three advantages to using linked lists on the heap:

   1. Additional records can be added at run-time as often as required,
      until the heap is full. There is no need to pre-declare large arrays
      to contain the data.

   2. The size of the heap is only limited by the size of the remaining
      memory, whereas array variables are located in the data segment of
      memory, which is limited to 64k.

   3. It is relatively easy to traverse a linked list to search for a
      specific entry.


 Another example program is HEAPLIST.PAS, which can be inspected. On
 running this program, memory can be inspected to see the list
 information on the heap.

 The program HEAPDEMO.EXE is also available on the diskette and may be
 run from DOS. It displays on the screen the sequence of events as a
 linked list is created on the heap. (For anyone unfamiliar with DOS,
 it is run by typing HEAPDEMO and then pressing the ENTER key).

 The linked lists described above are single linked lists, which can only
 be traversed in one direction. A double linked list has two pointer
 variables, one pointing to the previous record and the other pointing
 to next record.

 The program TWOLINKS.PAS is a program to display on the screen the
 creation of a double-linked list on the Heap and to show the action
 as the records of the list are traversed both forward and backward
 under the control of the right and left arrow keys.
 The functions Seg and Ofs are used to determine the addresses on
 Heap of each record of the linked list and these addresses are then
 displayed as Seg:Ofs for the record and for its fields Previous and
 Next. The Number field is also displayed.

 In this case, the convention used by Turbo Vision (under which this
 Tutor program operates) is employed. This convention uses a capital
 letter T to prefix the name of any non-pointer variable type and a
 capital P to prefix the name of any pointer variable type. Thus the
 type declaration part of the program and part of the Var declaration
 is as follows:

 Type
   PItem = ^ TItem;
   TItem = record
     Previous : PItem;
     Number   : integer;
     Next     : PItem;
   End;

 Var
   First, Last, This : PItem;

 The whole program is 363 line long, but during the display, as it is run,
 the essential statements for the creation of the linked list are shown,
 as below:

  New(This)
  If First = Nil then First := This else Last^.Next := This;    {old Last}
  This^.Number := i;
  If First = This then This^.Previous := Nil else This^.Previous := Last;
  Last := This;      {new Last}
  Last^.Next := Nil;


 Queues.
 ───────
 Queues operate on the First In First Out principle (FIFO) and can be built
 out of linked lists.  New members of the queue join at the rear, whilst
 members leave the queue at the front.  Again using 'next' as the field
 containing the linking pointer, the code for adding to the rear of the
 queue is:

      new(temp);               { allocate a new record (temp) and then    }
      rear^.next := temp;      { point the old rear record to this new one}
                               { instead of the original 'nil' pointer    }
      temp^.contents := data;  { store the new data in the new record and }
      temp^.next := nil;       { set the pointer of this record to 'nil'  }
                               { as it is now the new rear record         }
      rear := temp;            { set the rear pointer to point to the new }
                               { last record in the queue.                }

 The code for members leaving at the front is:

      temp := front;           { assign a temporary pointer to also point }
                               { at the front of the queue                }
      front := front^.next;    { change the pointer 'front' to point to   }
                               { the next, or second, record in the queue }
      dispose(temp);           { temp points to the old front record and  }
                               { so can be disposed.                      }

 A typical application of queues is for printer buffering.


 Stacks.
 ───────
 A stack operates on a Last In First Out basis (LIFO) and items joining the
 stack are said to be 'pushed' on to the stack, whilst items leaving are
 said to be 'popped' from the stack. The code for pushing is:

      new(temp);               { assign a new record (temp)               }
      temp^.contents := item;  { store the new item in this record and    }
      temp^.next := StackTop;  { make the new record point to the top of  }
                               { the stack                                }

 The code for popping is:

      temp := StackTop;             { set temporary pointer to stack top  }
      item := StackTop^.contents    { store data from top record          }
      StackTop := StackTop^.next    { make StackTop point to next record  }
      dispose(temp);                { dispose record pointed to by temp.  }

 A typical application of stacks is for saving register values when a DOS
 interrupt procedure is called.


 Binary Trees.
 ─────────────
 A Binary Tree has two pointers in each record and they point to a left
 branch and a right branch respectively.

 If the record is now called a node, then the node at the top is called
 the 'root', with 'parents and 'siblings' down the tree to the 'leaf' nodes,
 which have both pointers set to 'nil'.

 For the simple case of a record of integer values, the declaration of the
 record would be:

 type
   PNode = ^TNode;   {PNode is a pointer type which points to a type TNode}
   Tnode  = record                {TNode is a record type with two pointer}
       left    : PNode;           {type fields and one integer type field.}
       number  : integer;
       right   : PNode;
   end;

 A binary tree can be used to sort numbers into order, as shown in the
 example program BINTREE.PAS which can be run to check that it does so.


 HEAP&PTR.TXT
 Revised 22.1.93