Category : C Source Code
Archive   : TC_MAN.ZIP
Filename : SEC___42.RNO
.he 'SECTION 4.2''V.003'
.fo ''-#-''
.sp 4
SECTION 4.2 STACKS, TABLES, AND DATA STRUCTURES
.sp 2
There are five data spaces in the tiny-c interpreter:
.in +5
.ne 18
.sp 1
.nf
`pr' the program buffer; holds tiny-c program text AND
.in +10
variables values including all array elements.
.in -10
.sp 1
`stackb' the tiny-c value stack; holds partial
.in +10
results in expression evaluations.
.in -10
.sp 1
`varb' the variable table; holds the description BUT NOT
.in +10
the value of each variable and function name.
.in -10
.sp 1
`funb' the function table; holds pointers into the variable
.in +10
table which define the scope of variable names.
.in 0
.sp 1
.fi
In this section we will describe each of these data spaces in detail
and document the functions used for their care and feeding.
.sp 2
THE VARIABLE TABLE
.sp 2
All functions and all currently active variables are described in the variable
table. An entry in the variable table is 14 bytes:
.sp 2
.ne 14
.in 10
.nf
BYTES ENTRY
===== =====
0-7 canonicalized eight-byte name
8 class
9 size of one datum
10-11 length in data elements
12-13 address of first value
.sp 2
.in 0
.fi
A class value of 'E' means the entry represents a function name.
Size and length are ignored in this case. The address value is where
the cursor must be placed to begin execution of the function.
.sp 1
.ne 7
Currently active variables are:
.in 10
.nf
.ne 7
.sp 1
- all library symbols, including system library functions
- all global symbols, including functions
- all local variables for active functions,
.in +2
including function arguments.
.sp 1
.in 0
.fi
A function is ACTIVE if it has been invoked but has not completed. In the
case of recursion, each incarnation counts as an active function. All
function names are either global or library and all are entered in the
variable table. Note that the function's name is entered without
regard for its active or inactive status. The active function simply
determines which local variables are currently active.
.sp 1
.ne 41
Suppose the following code is being interpreted and control is
currently in `function_1':
.sp 2
.in 10
.nf
char global_symbol
main [
.in +4
int local_symbol
function_1(2, 3)
function_2
.in -4
]
function_1 int x,y [
.in +4
int n
.in +2
'
' <---- statement currently executing
'
.in -6
]
function_2 [
.in +4
char another_symbol
.in +6
'
'
'
.in -10
]
.in 0
.sp 2
.ne 10
The global symbols are:
.in 10
.sp 1
global_symbol
main
function_1
function_2
.in 0
.fi
.ne 6
The active functions are `main' and `function_1'. Their local variables are:
.sp 1
.in 10
.ne 8
.nf
local_symbol
x
y
n
.sp 1
.in 0
.fi
These eight variables - the four globals and the four locals - are the
ones allocated in the variable table. Later when
`function_1' returns, `x', `y' and `n' are de-allocated. When `function_2'
is invoked,
`another_symbol' is allocated. At this point six symbols are in the table:
.sp 1
.in 10
.ne 12
.nf
global_symbol
main
function_1
function_2
local_symbol
another_symbol
.in 0
.fi
.sp 1
The variable table is organized into layers so only those symbols
accessible to a function will be searched. A symbol is accessible if it is
.in 10
.sp 1
.ne 6
.nf
- local to the function
- global to the program
- in the system library
.sp 1
.in 0
.fi
.ne 36
This excludes variables local to active functions not currently executing.
Thus:
.nf
.sp 2
.in 10
int g
main [
.in +4
int x
function_1
.in -4
]
function_1 [
.in +4
int y
function_2
.in -4
]
function_2 [
.in +4
int z
.in +2
'
' <---- currently executing statement
'
.in -6
]
.in 0
.sp 2
.fi
The variables `g' and `z' are accessible to `function_2'. `x' and `y',
although active, are not accessible to `function_2'.
.sp 1
Layer 0 is reserved for system library symbols - function names and system-wide
global variables, if any. Program globals are in layer 1 initially
but can occur in other layers. After layer 1, if
there are n currently active functions, i.e. a main program, a function
invoked by main, a function invoked by that function, etc., n levels deep,
then those n functions are in layers 2, 3, ..., n+1. The locals for
main are in layer 2. The locals for the currently executing
function are in layer n+1. This layer is pointed to by the interpreter
global variable `curfun'.
.sp 1
.ne 12
When a symbol is needed, the hunt for it is carried out as follows:
.in 10
.nf
.sp 2
First, all symbols in the `curfun' layer are searched.
.in +3
If it isn't found there, then
.in -3
Second, all symbols in the global layer are searched.
.in +3
If it isn't found there, then
.in -3
Last, all symbols in the library layer are searched.
.in +3
If it isn't found there, a symbol error is raised.
.in 0
.fi
.sp 2
Notice this order of search guarantees the properties in described in
Section 2.1
.sp 2
THE FUNCTION TABLE
.sp 2
The mechanism for layering is the function table.
An entry in the function table has four addresses.
.sp 2
.in 10
.ne 24
.nf
BYTES ENTRY
===== =====
0-1 The address of the first variable
.in +15
table entry for this function.
.sp 1
.in -15
2-3 The address of the last variable
.in +15
table entry for this function.
.in -15
.sp 1
4-5 The address of the variable table
.in +15
entry for the variable most
recently used by this function.
.in -15
.sp 1
6-7 The address in the program buffer of
.in +15
.fi
the value of the last variable entry for this function.
.sp 2
.in 0
.fi
The address in `curfun' points to the first byte of the function table entry
of the currently executing function. The address in `curglobal' points to
the first byte of the function table entry for current globals.
.sp 1
Library symbols are always in layer 0, and `funb' points to the first byte
of that layer. So the implementation of the search order described above
is simply to search symbols spanned by the function table entry
pointed to by `curfun', then the function table entry pointed to by
`curglobal', and finally the function table entry at `funb'.
.sp 2
SYMBOL TABLE TOOLS
.sp 2
The following functions manipulate and search the variable and function
tables:
.sp 1
.nf
.ne 8
.in 10
`newfun'
`fundone'
`newvar'
`addrval'
.sp 1
.in 0
.fi
these subroutines use the auxiliary subroutine
.sp 1
.in 10
`canon'
.in -10
.sp 1
to canonicalize variable names to eight bytes. These five functions
comprise the source file SYMBOL.C.
.nf
.sp 1
.ne 12
Function: `newfun'
Arguments: None
Results: None
Errors: Too many functions
Action: Allocates a new layer in the function table,
.in +12
.fi
with zero entries in the variable table.
.in 0
.nf
.sp 2
.ne 16
Function: `fundone'
Arguments: None
Results: None
Errors: None
Action: Deallocates a layer in the function table.
.in +12
.fi
Deallocates all variables in that layer. Deallocates
all value space seized within that layer.
.in 0
.sp 2
.nf
.ne 16
Function: `newvar'
Arguments: Canonicalized variable name, class, size, length,
.in +12
and value.
.in -12
Results: Address of first byte of allocated space.
Errors: Too many variables or too many values.
Action: Enters a new variable in the current layer of
.in +12
the variable table.
.in 0
.sp 2
.fi
There are several considerations in allocating a value for a variable. If the
variable is local or global, space is allocated and set to 0. If the
variable is an argument to a function, and is class 0 (i.e. a single datum, not
an array name) then space is allocated, and the passed value copied into the
space. If the variable is an argument to a function, and is class greater
than zero, then it is the address of an existing array. Space is not
reallocated for these variables. The passed value - the array address - is
entered as the new variable's address-of-first-value (bytes 12-13
of variable table). Thus, in effect, the array is passed.
.sp 1
Values are allocated in the program buffer. The global variable `progend'
points to the
last byte used for program text and the global variable `prused' points to
the last byte
used for program text and variables values.
.sp 2
.nf
.ne 22
Function: `addrval'
.sp 1
Arguments: Canonicalized variable name.
Results: Address of first byte of allocated space, class,
.in +12
size, and length.
.in -12
Errors: Variable name not found.
Action: Searches for the variable name and returns its
.in +12
.fi
properties. Searches locals, globals, and system library symbols in that order.
.in 0
.sp 2
.ne 12
.ne 24
.nf
Function: `canon'
.sp 1
Arguments: Addresses of first and last bytes of an
.in +12
.fi
uncanonicalized variable name and the address of an eight-byte buffer.
.in -12
.nf
Results: Canonicalized variable name in buffer.
Errors: None
Action: Eight bytes are placed in the buffer. If the
.in +12
.fi
character string is shorter than eight bytes, it is padded on the
right with nulls. If the variable name is longer than eight bytes,
the first seven bytes and the last byte are placed in the buffer.
.in 0
.sp 2
THE tiny-c STACK
.sp 2
tiny-c has a stack for use in evaluating expressions. This stack is
implemented in software, and is not to be confused with the 8088
machine stack.
.sp 1
.ne 8
An entry on the tiny-c stack is 5 bytes:
.sp 2
.in 10
.ne 12
.nf
BYTE ENTRY
==== =====
0 class
1 lvalue
2 size
4-5 stuff
.in 0
.sp 2
.fi
An lvalue (left-side-value) is any symbol that can be written to the left
of an equal sign. Allowable lvalues include variable names,
subscripted array names, and unsubscripted array names.
.sp 1
The variable names and subscripted array names have class 0, and their
value is a single character or integer datum. The unsubscripted array names
have class 1 and their values are addresses.
.sp 1
Processing of an expression is done left to right. Whenever an lvalue is
recognized, its attributes are put on the tiny-c stack. Bytes 4 and 5,
stuff, are set to the address where the value is stored. An ASCII 'L'
is put in byte 1, lvalue, signifying stuff is a REFERENCE to the actual value.
.sp 1
Whenever a constant is processed or the results of arithmetic must be stacked,
the actual data value is put into stuff. An 'A' is put into
lvalue, signifying stuff IS actual data.
.sp 1
.ne 7
Consider the processing of the following expression
.sp 1
.in 10
K = J + 1
.sp 1
.in 0
where `K' and `J' are both integers. Suppose `K' has address 4000, `J' has
address 4002, and `J' has value 7.
.sp 2
.nf
.ne 11
.in 36
tiny-c STACK
.in -34
STEP ELEMENT CLASS LVALUE SIZE STUFF
.in +2
1 K Top ---> 0 L 2 4000
.sp 1
2 J Top ---> 0 L 2 4002
.in +25
0 L 2 4000
.in -25
.sp 1
3 1 Top ---> 0 A 2 1
.in +25
0 L 2 4002
0 L 2 4000
.in 0
.sp 2
.fi
At this point the plus operation is performed. First, the 1
is popped off the stack. It is an actual value so it is
left as a 1. Then the 4002 is popped. It is an lvalue so
the contents of addresses 4002 and 4003 (two bytes because
size is 2) are retrieved. This is the value of `J', 7. They
are added, and the sum pushed as an actual:
.nf
.sp 2
.ne 3
.in 36
tiny-c STACK
.in -34
STEP CLASS LVALUE SIZE STUFF
.in +2
4 Top ---> 0 A 2 8
.in +25
0 L 2 4000
.in 0
.sp 2
.fi
Now the equal operation is performed. The top entry, 8, is popped
and held. The next entry is popped. It must be an lvalue but it is
not converted to an actual because the current value of `K' is irrelevant.
Only the address of `K' is needed, and that is 4000. The held 8 is stored
in bytes 4000 and 4001, thus performing the assignment.
.sp 1
The value of the expression is 8. (Recall that all expressions, including
those with an equal sign, have values.) So the last step in processing this
expression is to push the 8 back on the stack as an actual.
.sp 1
.in 36
.nf
tiny-c STACK
.in -34
STEP CLASS LVALUE SIZE STUFF
.in +2
5 Top ---> 0 A 2 8
.in 0
.fi
.sp 2
STACK TOOLS
.sp 2
The following subroutines manipulate the tiny-c stack:
.sp 1
.in 10
.ne 10
.nf
`push'
`pushint'
`pop'
`toptoi'
`eq'
.in 0
.sp 1
These five functions comprise the source code file STACK.C.
.sp 2
.ne 17
Function: `push'
Arguments: Class, lvalue, size, stuff
Results: None
Errors: Stack full
Action: The arguments are pushed onto the stack as its
.in +12
top entry.
.in 0
.sp 2
.ne 14
Function `pushint'
Arguments: Stuff
Results: None
Errors: Stack full
Action: Stuff is pushed onto the stack with class 0,
.in +12
lvalue A, size 2.
.in 0
.sp 2
.ne 12
Function: `pop'
Arguments: None
Results: Stuff
Errors: None
Action: The stack is popped and stuff returned.
.sp 2
.ne 24
Function: `toptoi'
Arguments: None
Results: An actual value in integer form.
Errors: None
Action: The stack is popped. If the popped entry is an
.in +12
.fi
lvalue, it is converted to an actual. Otherwise, the datum in stuff is
used. If the resulting datum is of size 2 or of class greater
than 0 (i.e., a two-byte address) it is returned. If the datum is of
size 1 and class 0, it is first converted to an equivalent two-byte
integer and then returned.
.in 0
.sp 2
.nf
.ne 26
Function: `eq'
Arguments: None
Results: None
Errors: Left-value error
Action: The top level is popped and converted to an
.in +12
.fi
actual if necessary. The next level is popped and must be an lvalue
or an lvalue error is raised. The value referenced by the lvalue is
replaced by the actual. Eight bits are replaced if the lvalue represents
a class 0 eight-bit datum (i.e. a character). 16 bits are replaced
if the lvalue represents a class greater than 0 (i.e. an address) or a
class 0 16-bit datum (i.e. an integer).
.in 0
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/