Next: Dynamic Data Structures, Previous: Stacks, Up: Storage Management
The stack is a very efficient means of providing dynamic storage
for a great variety of uses. However, its limitation to local storage
presents a problem when a subroutine must allocate storage for use by
the routine which calls it. An example where the stack cannot be used is
as follows: Suppose we wanted to write a routine, NBO, which finds all
close non-bonded interactions, and suppose further that we wanted NBO to
allocate the storage itself without any preset limitations. The stack
cannot be used for this because the storage being allocated for the
non-bonded list is not local; it must be used by the subroutine which
calls NBO.
To circumvent this problem, we need a storage mechanism which allows completely arbitrary allocation of storage. Such flexibility is obtained with a heap.
A heap consists of an array and a list. The array is used for storing data. The list, referred to as the free list, keeps track of what areas in the heap are free. Before the heap is used, the free list is initialized to indicate that the entire heap is free. When space is required, the free list is searched for a space large enough to accommodate the request. The free list is then modified to indicate that less storage is available. To free storage, the freed area of storage must be put back on the list and recombined with adjacent free areas if possible.
As with the stacks, CONGEN provides two heaps, one for numeric
data and one for character string data. The numeric data heap is managed
entirely within Fortran, but the character string heap is really nothing more
than the heap maintained by the C run time library routines malloc and
free. There is a character string heap array, and the pointers
returned by malloc are mapped into the address for the character
string heap.
In CONGEN, the heaps are implemented using three common blocks.
HEAPCM stores numerical information and the numeric heap,
SVHEAP stores a copy of critical heap pointer for error
detection, and HEAP_ST stores the initial address for the
character string heap. All of the declarations are in the files,
heap.fcm and heap.h, and the appropriate file should be
#include'd wherever the heaps are used. The real number array,
RHEAP and the logical array, QHEAP, are equivalenced to the HEAP
so references to other data types are simplified. (It should be noted
that the use of these equivalences presumes that these data types have
the same sizes as integers. This presumption may not always be true.)
There are a number of subprograms which simplify the use of the heaps.
INITHP
To initialize the heap, INITHP is used. First, one sets HEAPSZ
to the dimension of the heap, and then, INITHP is called with no
arguments.
ALLHP and ALLCHP
To obtain storage on the heap, we use the integer function
ALLHP. ALLHP is called with one argument, the amount of
storage needed on the HEAP array, in units of INTEGERs.
You should always use the INTEGER function FSIZEOF, see Stacks, to
determine the number of integers required for particular data type and
number of elements. ALLHP then returns the index of the first
element of the array allocated in the heap. This index shall be referred
to as the base of the allocated storage.
ALLCHP works in a similar way to ALLHP except that it
operates on the character string heap. The argument to ALLCHP is the number
of characters to be allocated, and the return value is the index into CHEAP
for the storage. Internally, ALLCHP is implemented using malloc.
FREHP and FRECHP
To return storage to the heap, one calls FREHP or
FRECHP. Unlike FRESTK, FREHP and FRECHP
require two arguments, a base and a length. FREHP and
FRECHP return the storage demarked by the base and length to
their respective free lists. If this storage can be recombined with
adjacent free areas of storage, it is done.
ALLHP, ALLCHP, FREHP, and FRECHP
make extensive checks on their arguments
and on themselves. Since these two routines are vital to the operation
of CONGEN, they are designed to catch many programming errors that can
result from using the heap. In addition, there are debugging variables that
can be used to improve the error detecting capabilities of the heap
subprograms. See the source code for the usage of the debugging variables
alloc and allhp.
PRINHP
To obtain a listing of the free storage areas available on the
heap, PRINHP is available. It is called with one argument, a unit number
to which the output is sent.
Referencing the data in the heap can be done using the same techniques as described for the stack. However, a more sophisticated method of referencing data on the heap is the subject of the next section.
To illustrate the use of a heap, consider the following example: Suppose we want a subroutine which reads in a list of card images from a file and stores them into an array on the heap. Assume that the number of cards which can be read is to be limited only by the space available on the heap.
To implement this, we assume that we can store 4 characters to a
word and that our cards have 80 columns. The card array is then
dimensioned (20,N). The subroutine which is called to get the card
images is called RDCARD.
PROGRAM TSTRDC
C
C This program tests RDCARD. It initializes the HEAP, calls RDCARD
C on unit 5, prints the card images, and then prints the HEAP.
C
# include "heap.fcm"
INTEGER CRDBAS,CARDSZ
C
CALL INITHP
CARDSZ = 80
CALL RDCARD(CRDBAS,5,NCARD,CARDSZ)
CALL PRTCRD(CHEAP(CRDBAS)(1:CARDSZ),NCARD)
CALL PRINHP(6)
STOP
END
SUBROUTINE RDCARD(BASE,UNIT,NCARD,CARDSZ)
C
C Reads all the card images from UNIT into the HEAP. BASE is
C returned giving the first word in the HEAP where the card images
C are stored. NCARD returns the number of cards found.
C
INTEGER BASE,UNIT,NCARD,START,END,CARDSZ
# include "heap.fcm"
LOGICAL EOF
INTEGER INC
PARAMETER (INC = 100)
C
C Initially, we allocate space for INC cards. If this is exceeded
C during the reading of the file, space for an additional INC cards
C will be allocated, and the reading will continue.
C
LIMIT=INC
BASE = ALLCHP(LIMIT*CARDSZ)
NCARD=0
C
C RDCAR1 actually reads the file, putting card images into the HEAP.
C
REPEAT UNTIL (EOF)
CALL RDCAR1(CHEAP(BASE)(1:CARDSZ),NCARD,LIMIT,UNIT,EOF)
UNLESS (EOF)
C
C At this point, we know that RDCAR1 ran out of space. We allocate a
C array larger in size and copy the cards already obtained into the
C new array, and then free the old array.
C
NEWBAS = ALLCHP(CARDSZ*(LIMIT+INC))
CALL COPYCA(CHEAP(NEWBAS)(1:CARDSZ),LIMIT+INC,
2 CHEAP(BASE)(1:CARDSZ),LIMIT)
CALL FRECHP(BASE,CARDSZ*LIMIT)
LIMIT = LIMIT+INC
BASE = NEWBAS
FIN
FIN
END
SUBROUTINE RDCAR1(CARDS,NCARD,LIMIT,UNIT,EOF)
C
C Reads cards from UNIT into CARDS, setting EOF if end of file is
C found. If the routine returns with EOF not set, it means that
C space was exhausted in the card array.
C
CHARACTER*(*) CARDS(LIMIT)
INTEGER UNIT
LOGICAL EOF
C
EOF = .FALSE.
REPEAT WHILE (NCARD .LT. LIMIT)
NCARD=NCARD+1
READ (UNIT,100,END=99) CARDS(NCARD)
100 FORMAT(A)
FIN
RETURN
C
C Come here on end of file. We must decrement NCARD by one because
C the READ statement did not add another card image to the array.
C
99 NCARD = NCARD-1
EOF = .TRUE.
RETURN
END
SUBROUTINE PRTCRD(CARDS,NCARD)
C
C Prints the card images in CARDS onto unit 6, the printer.
C
CHARACTER*(*) CARDS(*)
C
WRITE (6,200) NCARD
200 FORMAT('0OUTPUT OF ',I5,' CARDS:')
DO (I=1,NCARD)
WRITE (6,201) CARDS(I)
201 FORMAT(1X,A)
FIN
RETURN
END
SUBROUTINE COPYCA(ST1A,NST1A,ST2A,NST2A)
C
C Copies strings from ST2A into ST1A. The lengths of the arrays are
C given by NST2A and NST1A, respectively.
C
IMPLICIT INTEGER(A-Z)
CHARACTER*(*) ST1A(*),ST2A(*)
INTEGER NST1A,NST2A
C
DO (I = 1,MIN(NST1A,NST2A))
ST1A(I) = ST2A(I)
FIN
RETURN
END