Memory Management

This page describes how memories used by the clent C program are handled by the GCS interpreter program.

Four Data Structs

There are four data structs at the base of this discussion.
struct darray
member explanation
int dimen number of subscripts of the array
int size[4] size of each subscripts. If dimen is 3, and i, j, and k are the values of each subscripts, the offset from the base is i*size[1]*size[2]+j*size[1]+k
double *dat pointer to the data which could be suitable for some use
int offs offset in memory.bdouble[]
int mem offset in mem[]

The strucr iarray is the int version of darray.
struct iarray
member explanation
int dimen number of subscripts of the array
int size[4] size of each subscripts. If dimen is 3, and i, j, and k are the values of each subscripts, the offset from the base is i*size[1]*size[2]+j*size[1]+k
int *dat pointer to the data which could be suitable for some use
int offs offset in memory.bint[]
int mem offset in mem[]

The struct memory is a block of memory that corresponds to a scope. The blocks of memories are stacked and indexed by mem[].
struct memory
member explanation
int scop correponding scope number
char *bchar base of arry of characters
int *bstring base of string offsets in bchar[]
double *bdouble base of array of doubles
int *bint base of array of ints
darray *bdarr base of darrays
iarray *biarr base of iarrays
int schar start offset of bchar[0] in global subscript
int sstring start offset of bstring[0] in global subscript
int sdouble start offset of bdouble[0] in global subscript
int sint start offset of bint[0] in global subscript
int sdarr start offset of bdarr[0] in global subscript
int siarr start offset of biarr[0] in global subscript

The global subscript is used interchangeably with the pointer here.
The fourth struct scope contains the fundamental properties of the scope of the memory and the information for the execution of the scope.
struct scope
member explanation
char name[30] name of the scope. function names exept for the first one which is named global.
int noderoot starting node or root node of the scope
int nodedecl declaration node of the scope
int nodeexec execution node of the scope
int nchar number of characters in memory
int nstring number of strings in memory
int ndouble number of doubles in memory
int nint number of ints in memory
int ndarr number of darrays in memory
int niarr number of iarrays in memory
int nident number of identifiers declared in the scope
int *ident indices in ident[].
int *kind kind of identifiers
1:char 2:string 3:double 4:int 5:darray 6:iarray
7:char* 8:string* 9:double* 10:int* 11:darray* 12:iarray*
int *offs offset to identifier data
memory mem memory prototype of the scope

Source code processing


At the end of lexer processing, the input C program is converted into a sequence of integers in tmnl[]. Those integers are terminal symbol numbers exept for those that immediately follow certain terminals.
Terminals and the accompanying data
terminal number terminal the data that follows
46 character constant index in chcon[]. chcon value in turn is an index in inpchar[]. inpchar is zero terminated string.
57 floating constant index in flcon[]. flcon value is of type double.
60 identifier index in ident[]. ident value in turn is an index in inpchar[]. inpchar is zero terminated string.
63 integer constant integer value

Once those data are set there is no need for the original text C source code data to be around.
At this point we get into the parser phase.
The parser generates 5 data arrays all indexed with the node number. They are gsymbol, produc, parent, child, sibli and attri1. Among these arrays, attri1[] is very much related to the memory management.
At the time of shift, whenever a shifted terminals is either 46, 57, 60 or 63, the value of the next element of the terminal array is entered into attri1 array.

Construction of scop[] and mem[]


After the parse tree is constructed, the tree is examined to identify the number of user-defined functions it contains. It has at least one such function, the main function. We count each fuction as a scope, and then add the global scope upon them. The resulting number of scopes is the number of functions plus one.
Next, the array of scope structs, scop[], is allocated and has its data established. The data of mem which is a member of the scope struct is determined by traversing the parse tree, first traversing the function header part and then traversing the variables declaration part.
The mem[] array declared in the main function is an array of pointers that point to memory structs. While scop[] is static, mem[] is dynamic. Whenever a user-defined function is called, the memory data struct defined by the function's scope is newly created, and its pointer is added to the mem[] array. When the control returns from the user-defined function, after some data retrieval works by the calling function, the memory struct used by the called function is no more needed. It is destroyed and the corrsponding entry in mem[] array is removed.
When a program starts executing, the point of start is always the first executable statement in the main function. At that time, there are two members in mem[] array, one that corresponds to the global scope and the other that corresponds to the main scope. As those two memory structs are always there and never created more than one, their corresponding mem[] pointers point to the memory structs that are the members of the scope structs.

Passing the parameters between the calling and the called functions


When a function is called, the corresponding scope can be identified from its name. The memory for the new memory struct is allocated and its pointer aded to the mem[] array. The data is copied from the scope's mem to the newly created memory, as some of the data may have their values initialized.
The first element of the int buffer of the newly created memory contains the number of interface variables of the function call. It corresponds to the number of arguments of the function plus one that accounts for the returned value.
The first identifier elements of this number correspond to the interface variables, the first element being the returned value of the function. Identifiers are indexed with identifier number and their properties are scope.ident[], scope,kind[] and scope.offs[].
Arguments of Functions
kind type offs
1 char index in bchar[]
2 string index in bstring[]
3 double index in bdouble[]
4 int index in bint[]
5 darray index in bdarray[]
6 iarray index in biarray[]
7 char * universal index in bchar[]
8 string * universal index in bstrimg[]
9 double * universal index in bdouble[]
10 int * universal index in bint[]
11 darray * universal index in bdarr[]
12 iarray * universal index in biarr[]

Here the distinction between index and universal index is that index is used within the difined function's memory, while universal index is the index counted from the array in mem[0].
In order to fascilitate the conversion between local index and the universal index, start of the universal indices for each arrays are contained in members schar, sstring etc in each memory struct.

This is the called function's side of the interface.
The calling function's side of the interface is the the multi-purpose-stack or mpstk.
mpstk data
mpstk[i*2] meaning mpstk[i*2+1]
0 return node node number
1 sibling node node number
2 loop control node node number
3 gsymbol grammar symbol number
4 char constant subscript in chcon[]
5 double constant subscript in flcon[]
6 integer constant constant value
7 identifier id subscript in ident[]
8 double stack pointer subscript in dstk[]
9    
10 return from user function  
11 processed data  
12 used with an array subscript in dat of darray or iarray
21 char subscript in current memory.bchar
22 string subscript in current memory.bstring
23 double subscript in current memory.bdouble
24 int subscript in current memory.bint
25 darray subscript in current memory.bdarr
26 iarray subscript in current memory.biarr
27 char * global subscript in memory.bchar
28 string * global subscript in memory.bstring
29 double * global subscript in memory.bdouble
30 int * global subscript in memory.bint
31 darray * global subscript in memory.bdarr
32 iarray * global subscript in memory.biarr
41 char subscript in global memory.bchar
42 string subscript in global memory.bstring
43 double subscript in global memory.bdouble
44 int subscript in global memory.bint
45 darray subscript in global memory.bdarr
46 iarray subscript in global memory.biarr
61 subscript in local memory.bdouble 2nd subscript in double[][]
62 subscript in global memory.bdouble 2nd subscript in double[][]
63 subscript in universal memory.bdouble 2nd subscript in double[][]

Declaration and corresponding Internal Representaion


The declarations of functions and variables are processed to form respective entries in scope structs, before the execution is started. This table depicts the types of declarations and the corresponding entries in the struct's elements.
Declaration and corresponding Internal Representaion
Declaration Internal Representation
kind offs note
char a;
funct(char a); 		1 in local.bchar[] one unsigned byte
char a[10]; 2 in local.bstring[] string terminated by /0
local.bstring[] contains index in local.bchar[]
char a[]="text"; 7 in local.bstring[] string terminated by /0
local.bstring[] contains index in local.bchar[]
char *a[]={"text1","text2"}; 8 in local.bstring[] array of strings
funct(char *a); 7 in universal.bstring[], set by the calling function universal.bstring[] contains index in universal.bchar
char funct(...); 1 in local.bchar[] retrieved in calling function
char *funct(...); * unimplemented use func(char *a) instead
double a;
funct(double a); 		3 in local.bdouble[] double
double a[10];
double a[3][3];
double a[]={1.0,2.0};
double a[3][3]={1.0,...}; 		5 in local.bdarr[] struct darray is created and tied to local.bdarr[]
func(double *a); 9 in local.bint[] set by the calling function so that local.bint[] contains the index in universal.bdouble[]
func(double a[]); 11 in local.bint[] set by the calling function so that local.bint[] contains the index in universal.bdarr[]
double funct(...); 3 in local.bdouble[] retrieved in calling function
double *funct(...); * unimplemented use func(double *a) instead
int a;
funct(int a); 		4 in local.bint[] int
int a[10];
int a[3][3];
int a[]={1,2};
int a[3][3]={1,...}; 		6 in local.biarr[] struct iarray is created and tied to local.biarr[]
func(int *a); 10 in local.bint[] set by the calling function so that local.bint[] contains the index in universal.bint[]
func(int a[]); 12 in local.bint[] set by the calling function so that local.bint[] contains the index in universal.biarr[]
int funct(...); 4 in local.bint[] retrieved in calling function
int *funct(...); * unimplemented use func(int *a) instead

Action taken when an identifier is encountered during the traversal


The identifier is checked against the identifiers of the current scope. If the corresponding identifier is found, the kind number plus 20 and the offs number are pushed on the multi-purpose stack in a pair.
If the corresponding identifier is not found in the current scope, the same check will made against the identifiers of the global scope. If the corresponding identifier is found in the global scope, the kind number plus 40 and the offs number are pushed on the multi-purpose stack in a pair.