[an error occurred while processing this directive]

SymbolTable Module Implementation Specifications

Client Specifications

Implementation Data Model

Basic implementation model

The SymbolTable module implements a single symbol table using a stack of Tables implemented with a dynamic array named stack. This array is declared as a static global variable in the file SymbolTable.C, along with a variable named topLevel to keep track of the current scoping level.

The topLevel variable is returned by calls to currentLevel(), and also serves as the index for the top of the stack. When enterScope() is called, a new Table is pushed onto the stack. When exitScope() is called, the top Table is popped from the stack.

When a Descriptor is added to the SymbolTable by a call to addDescriptor(), the Descriptor is added to the top Table in the stack.

The level() function checks all tables in Tables in the stack for the target identifier, working from top to bottom. When it locates the identifier, it returns its level.

The descriptorFor() function selects a Table as described in the next subsection. The Descriptor for the identifier is then retrieved from the selected Table.

Caching

To improve efficiency of descriptorFor(), level() caches its identifier argument in a variable named cacheId and the level where it found the identifier in a variable named cacheLevel. When descriptorFor() is called, it checks cacheId to see if it the same as its identifier argument. If it is not the same, then level() is called to set cacheId and cacheLevel. Then cacheLevel is used as an index in the stack array to select a Table.

The cache variables cacheId and cacheLevel can be invalid. This occurs before level() has been called the first time and may occur after a call to exitScope(). This condition is signified by a null value for cacheId. It can be rectified by calling level().

Dynamic stack allocation

The client specifications for this module do not mention any limit on the number of levels, so an unbounded implementation is needed for the stack. With an array implementation, this requires dynamic allocation and reallocation. To support this, a variable named capacity is used to keep track of the current capacity of the stack. The private function doubleStackCapacity() is called to double the capacity of the stack whenever a new level is added that exceeds the current capacity.

The private function initializeStack() is provided for the initial stack allocation. This function also creates the level 0 Table and pushes it onto the stack.

Since there is no public function for initialization, topLevel is initialized to -1 to indicate that the stack is not yet initialized. Public functions addDescriptor(), currentLevel(), and enterScope() must check topLevel and initialize the stack if it is -1.

Error handling

Two kinds of error conditions arise in this module that lead to program termination: precondition violations for public functions, and system errors. The precondition violations can occur in addDescriptor() due to the presence of an entry in the top-level Table with the same key as the identifier argument, in descriptorFor() when there is no entry whose key is the identifier argument, and in exitScope() when attemting to exit the level 0 scope. All three of these conditions should lead to program termination with an error message that describes the nature of the problem to the client of this module. The precondition in the private function doubleStackCapacity() is not checked.

System errors can arise from dynamic memory allocation in initializeStack() and reallocation in doubleStackCapacity(). The returned values from C library functions calloc() and realloc() should be checked for null values that indicate memory allocation failure. A null returned value should lead to program termination with an error message that indicates the nature of the problem.

Private Importing Information

The SymbolTable module code file requires standard library functions from stdio.h, stlib.h, and string.h. In addition, it requires the following includes.

#include "Descriptor.h"
#include "Table.h"
#include "SymbolTable.h"

Private Data Type Implementations

There is no private data type defined for a symbol table since this module implements a single symbol table. This symbol table contains the following data variables, each declared as a static variable that is global in the file SymbolTable.C.

Table * stack - the stack of Tables.
int capacity - the capacity of the stack.
int topLevel - the level number of the top Table in the stack. This variable must be initialized to -1.
char * cacheId - the identifier parameter for the most recent call to level(). This variable must be initialized to null, and must be set to null whenever there is a possibility that the entry for this identifier has been removed.
int cacheLevel - the level where cacheId can be found.

Public Data Type Implementations

The SymbolTable module does not export any data types.

Private Function Specifications

void initializeStack(void)
initializeStack() initializes the stack of Tables and pushes a new Table onto it.
void doubleStackCapacity(void)
doubleStackCapacity() doubles the capacity of the stack of Tables.
Preconditions:
The stack has been initialized.

Private Function Algorithms

initializeStack
Specification

topLevel = 0
capacity = 4
allocate array for stack with capacity entries (use calloc())
if calloc returns null
    terminate the program with a system error message
put a new Table at stack[topLevel]

doubleStackCapacity
Specification

double capacity
reallocate array for stack with capacity entries (use realloc())
if realloc returns null
    terminate the program with a system error message

Public Function Algorithms

level
Client Specification

parameter: char * id
local variable: int currentLevel

cacheId = id
currentLevel = topLevel
while currentLevel >= 0
    if id is a key in stack[currentLevel]
	break
    decrement currentLevel
cacheLevel = currentLevel
return currentLevel

descriptorFor
Client Specification

parameter: char * id

if cacheId is null or cacheId is not the same as id
    call level(id)
if cacheLevel < 0
    terminate the program with a precondition violation error message
return the data from stack[cacheLevel] for key id

addDescriptor
Client Specification

parameter: char * id
parameter: Descriptor dscr

if topLevel is -1
    initialize the stack
if the stack[topLevel] has an entry whose key is id
    terminate the program with a precondition violation error message
add dscr to stack[topLevel] with key id

currentLevel
Client Specification

if topLevel is -1
    initialize the stack
return topLevel

enterScope
Client Specification

if topLevel is -1
    initialize the stack
increment topLevel
if topLevel >= capacity
    double capacity of stack
put a new Table at stack[topLevel]

exitScope
Client Specification

if topLevel <= 0
    terminate the program with a precondition violation error message
free stack[topLevel]
decrement topLevel
if topLevel < cacheLevel
    cacheId = null

[an error occurred while processing this directive]