Next: Heaps, Previous: Storage Management, Up: Storage Management
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 STACK and STACK_ST.
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)
LSTUSD and LSTCUSD hold the index of the last
element used in each stack; they are the stack pointers. STKSIZ
and CSTKSIZ hold the size of the stacks which is used for
overflow checking. MAXUSD and 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 #include statement
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.
INISTK
To initialize the stacks, one must
call INISTK with no arguments. INISTK sets all the stack variables appropriately,
and if DBG_ALLSTK is greater than zero (it normally is), the
stacks are filled with non-zero elements.
The initial
filling of the stacks helps to catch error which occur because local
storage is not properly initialized.
ALLSTK and ALLCSTK
To obtain storage on the stacks, one uses the integer function
ALLSTK or ALLCSTK. Both functions take one argument, the
number of elements required, and returns the index into the array,
STACK or CSTACK, of the first element allocated. In the
case of 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
code! Also, 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, LSTUSD or
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.
FRESTK and FRECSTK
To free storage on the stack, the subroutines FRESTK or
FRECSTK are used. FRESTK is used for the numeric data
stack, and 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.
FSIZEOF
The integer function, FSIZEOF, accepts two arguments,
TYPE and SIZE, and returns the number of integers needed
to store SIZE variables of data type, TYPE. The
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.
The function, 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,
A and B, and needs two working arrays, C and
D. The code in subroutine FOO will call ALLSTK
twice; once for each work array needed. Since C and D are
names of the work arrays, the indices into the stack returned by
ALLSTK are assigned to the variables C and D. A
second subroutine, FOO1, is defined with four arguments, the
original two and two arguments which are work arrays. In FOO1,
C and D are defined as arrays. Once FOO has
finished allocating the work storage, it calls FOO1 as follows:
CALL FOO1(A,B,STACK(C),STACK(D))
FOO1 actually does the computational work for FOO. Once
FOO1 completes, 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 MSQUAR.
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
JOINWDIn this example, we show the use of the character string stack.
JOINWD is used to insert one character string, WD,
onto the beginning of a second character string, ST.
Stack space is required because we wish to avoid an overlapped copy.
JOINWD first copies ST to local storage, copies WD
to ST followed by space, and then copies the old value of ST
back into ST. Note the use of a substring reference into CSTACK
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