In all large programs, the need for “local” storage arises very frequently. “Local” storage or temporary storage is defined as storage needed by a subroutine for itself or any subroutine it calls. Invariably, local storage is required for work arrays whose sizes can be determined prior to their use. Local storage is not meant to be accessible when the subroutine is not executing.
An example requirement for local storage is a routine which squares a matrix. Because array multiplication cannot be done in place, one would require local storage to store a temporary array which would hold the squared matrix.
The data structure which is ideally suited for this task is a stack. At minimum, a stack consists of an array and an integer. Storage is allocated and freed from the top end of the array only. The integer is the stack pointer and keeps track of what part of the stack is in use. When a subroutine requires local storage, it gets it from the top of the stack. If it calls another subroutine which requires more local storage, the local storage currently being used is, in effect, buried, and the additional storage is allocated on the top of the stack. “Burying” such storage is reasonable because the first subroutine's execution is suspended when the next one is executing. When it finishes, the storage is freed, and the top of the stack moves back to where it was. The first subroutine then resumes execution with the same stack environment before the other subroutine was called.
As seen above, the stacks allow nested subroutines to each have their own local storage. This is very important because CONGEN uses many subroutines, and they can nest many levels. Using blank common for local storage fails because a nested subroutine would overwrite storage used by its caller.
CONGEN maintains two stacks, one for numeric data and one for character string data. (The Fortran standard forbids the mixing of numeric and character data in a common block, so for portability, we keep them separate even though one could get away with mixing them on most machines.)
The two stacks are stored in two common blocks named
Both common blocks are defined in stack.fcm or stack.h. The current
declaration is as follows:
C C Variables: C C LSTUSD Stack pointer which refers to last used element in C stack array. C MAXUSD Maximum value of LSTUSD seen during execution. C STACK Numeric variable stack. C LSTCUSD Character string version of LSTUSD C MAXCUSD Character string version of LSTUSD C CSTACK Character string stack. C C Parameters: C C STKSIZ Maximum size of stack. C CSTKSIZ Character string version of STKSIZ C INTEGER LSTUSD,STKSIZ,MAXUSD,STACK,ALLSTK,LSTCUSD,CSTKSIZ, 2 MAXCUSD,ALLCSTK PARAMETER (STKSIZ = 100000, CSTKSIZ = 100000) COMMON /STACK/ LSTUSD,MAXUSD,LSTCUSD,MAXCUSD, 2 STACK(STKSIZ) REAL RSTACK(STKSIZ) EQUIVALENCE (RSTACK(1),STACK(1)) CHARACTER*1 CSTACK COMMON /STACK_ST/ CSTACK(CSTKSIZ)
LSTCUSD hold the index of the last
element used in each stack; they are the stack pointers.
CSTKSIZ hold the size of the stacks which is used for
MAXCUSD accumulate the
maximum value of the stack pointers so that one determine how much
storage must be dimensioned for the stack without wasting any space. As
one can see, the stack must be dimensioned to some appropriately large
size, and all local storage requirements will be taken from it. If the
stack is not big enough for the needs of the program, the stack must be
redimensioned. Changing the size of the stack is far easier than
redimensioning every array that would have declared locally.
There are some valuable techniques for using the character
string stack. Note that the stack is declared as an array of
CHARACTER*1. This was done to allow any size character string
because on some machines (e.g. VAX/VMS), strings are limited to 32767
characters. When an allocated character string is passed to a
subroutine, the space should be referenced as a character substring of
the allocated length. Then, the subroutine will see the length of
character string as the allocated length, and subscript range checking
is simplified. If a character string array is allocated, the passed
length should still be the length of the string element. Please note
that if the passed length derives from a constant, then most compilers
will detect the apparent substring range violation. Therefore, it will
be necessary to allocate an extra integer variable, assign the constant
to it, and use the integer variable in the subroutine call.
To refer to the stack in a subroutine, use a
and refer to the file STACK.FCM.
For convenience in debugging, the stack is also declared as a
REAL array using an equivalence statement.
The stacks are limited in size, and it is not memory effective to increase their size greatly. Therefore, if you have large local storage needs, use heap storage, see Heaps, for the really big arrays.
A number of subroutines and functions are provided to perform all the necessary manipulations of each stack. They are found in the source code file, util.flx.
To initialize the stacks, one must
call INISTK with no arguments. INISTK sets all the stack variables appropriately,
DBG_ALLSTK is greater than zero (it normally is), the
stacks are filled with non-zero elements.
filling of the stacks helps to catch error which occur because local
storage is not properly initialized.
To obtain storage on the stacks, one uses the integer function
ALLCSTK. Both functions take one argument, the
number of elements required, and returns the index into the array,
CSTACK, of the first element allocated. In the
ALLSTK, the elements are integers. The function,
FSIZEOF, should always be used to calculate the number of
integers required for a given data type because the number of integers
is machine dependent. Never do this calculation in your own
ALLSTK will round your request up to the
nearest multiple of 2 so that double precision alignment will be
maintained. In the case of
ALLCSTK, the elements are characters. If
you are allocating space for a character string array, pass
INICSTK the product of the array length times the string lengths.
The functions revise the stack pointers,
LSTCUSD, to indicate the allocation, and they check for stack
overflow. Stack overflow results in the termination of the program.
Negative arguments are not permitted to these functions. Note that
common block predeclares this function for you.
To free storage on the stack, the subroutines
FRECSTK are used.
FRESTK is used for the numeric data
FRECSTK is used for the character string stack. They
each take one argument, the number of elements to be freed. They
decrement the stack pointers by their arguments to indicate the release
of storage, and they check to see that the stack pointers have not
become negative. If they have, an error message is output, and program
execution stops. Both routines check that their arguments are
non-negative. FRESTK will round its argument to the next
multiple of 2.
The integer function,
FSIZEOF, accepts two arguments,
SIZE, and returns the number of integers needed
SIZE variables of data type,
TYPE argument is a character string and may have one of the
following values: `REAL', `REAL*8',
`DOUBLE', `INTEGER', `INTEGER*1', `INTEGER*2',
`LOGICAL', `LOGICAL*1', `SHORT', `BYTE',
`CHARACTER', or `COMPLEX'. The lengths provided by
FSIZEOF vary from machine to machine.
PRINSTK, may be used to print the current state
of the stack. The debugging variable,
DBG_ALLSTK, may be used to
debug stack usage. The default setting of 1 results in the initialization
of the stack to non-zero values. If
DBG_ALLSTK is set to 2 or greater,
all calls to the allocation and freeing routines will generate messages
displaying the argument to each call.
The main method for using the space allocated on the stack is as
follows: Suppose we have a subroutine,
FOO, which requires local
storage to work. Suppose further that
FOO takes two arguments,
B, and needs two working arrays,
D. The code in subroutine
FOO will call
twice; once for each work array needed. Since
names of the work arrays, the indices into the stack returned by
ALLSTK are assigned to the variables
FOO1, is defined with four arguments, the
original two and two arguments which are work arrays. In
D are defined as arrays. Once
finished allocating the work storage, it calls
FOO1 as follows:
FOO1 actually does the computational work for
FOO then calls
FRESTK to free the
work storage used, and it returns having completed its task. In summary,
referencing the work arrays is accomplished by using a subroutine call
to map an array onto the stack.
A second method exists for accessing local storage on the stack. This involves using subroutines which access one element of an array at a time. They are not very useful for the stack, but they are discussed further in the section on data structures in the heap, see Dynamic Data Structures.
To illustrate the use of the stack, we show how the matrix
squaring subroutine is programmed. The main program sets up the stack
and calls the routine which is named
PROGRAM TSTMSQ C C TESTS MSQUAR, A MATRIX SQUARING ROUTINE. WE READ THE MATRIX IN C FROM UNIT 5 AND OUTPUT ITS SQUARE ON UNIT 6. THE SIZE OF THE TEST C MATRIX, A, IS 10 BY 10. C # include "stack.fcm" C REAL A(10,10) C CALL INISTK READ (5,100) ((A(I,J),J=1,10),I=1,10) 100 FORMAT(10F8.0,9(/10F8.0)) CALL MSQUAR(A,10) WRITE (6,200) ((A(I,J),J=1,10),I=1,10) 200 FORMAT(' RESULTS OF CALLING MSQUAR -- THE MATRIX A:'/ 2 10(/1X,1P10G11.4)) CALL PRINSTK(6) STOP END SUBROUTINE MSQUAR(A,N) C C SQUARES A WHICH IS A REAL ARRAY ASSUMED TO BE N BY N. WE USE THE C STACK TO STORE THE SQUARED ARRAY. C REAL A(N,N) # include "stack.fcm" INTEGER SQUARE INTEGER OLDLST C C WE ALLOCATE SPACE FOR THE SQUARED ARRAY. NOTE THAT WE SAVE THE C VALUE OF LSTUSD UPON ENTERING THIS SUBROUTINE. THIS MAKES IT C EASIER TO FREE THE AMOUNT OF STORAGE ALLOCATED BY EVERY ALLSTK C CALL WHEN THE SUBROUTINE QUITS. C OLDLST=LSTUSD SQUARE=ALLSTK(N*N) CALL MSQUA1(A,N,STACK(SQUARE)) CALL FRESTK(LSTUSD-OLDLST) RETURN END SUBROUTINE MSQUA1(A,N,SQUARE) C C MSQUA1 DOES THE JOB OF SQUARING THE MATRIX A. WE CAN NOW REFER TO C THE CONTENTS OF THE TEMPORARY ARRAY, SQUARE, DIRECTLY. C REAL A(N,N),SQUARE(N,N) C DO 1 I=1,N DO 1 J=1,N S=0.0 DO 2 K=1,N 2 S=S+A(I,K)*A(K,J) 1 SQUARE(I,J)=S C C NOW COPY SQUARE BACK INTO A C DO 3 I=1,N DO 3 J=1,N 3 A(I,J)=SQUARE(I,J) RETURN END
In this example, we show the use of the character string stack.
JOINWD is used to insert one character string,
onto the beginning of a second character string,
Stack space is required because we wish to avoid an overlapped copy.
JOINWD first copies
ST to local storage, copies
ST followed by space, and then copies the old value of
ST. Note the use of a substring reference into
in order to provide
COPYST the correct size of the string
it is copying into.
SUBROUTINE JOINWD(ST,STLEN,WD) C C DOES NEARLY THE INVERSE OF NEXTWD, I.E. JOINS WD ONTO C THE BEGINNING OF ST. C IMPLICIT INTEGER(A-Z) CHARACTER*(*) ST,WD # include "stack.fcm" C STL = STLEN WDLEN = LEN(WD) COPY = ALLCSTK(STL) CALL COPYST(CSTACK(COPY)(1:STL),COPYLN,ST(1:STLEN)) CALL COPYST(ST,STLEN,WD(1:WDLEN)) IF (COPYLN .GT. 0) CALL ADDST(ST,STLEN,' ') CALL ADDST(ST,STLEN,CSTACK(COPY)(1:COPYLN)) CALL FRECSTK(STL) RETURN END