P4A uses some basic commands that allow you to add and list entries in the symbol table. The following commands are test

[answerhappygod]

P4A uses some basic commands that allow you to add and list
entries in the symbol table. The following commands are tested in
this part of the assignment.
These commands require the implementation of any functions used
to perform these operations, such as:
You might find it useful to also
implement symbol_search() for use in
the symbol_add() function.
P4B
P4B uses all of the remaining commands. You can run the program
and type help to view a list of all commands which will
be tested. This will require you to implement any functions
in symbol.c that were not implemented in P4A.
Goals of Assignment
In this assignment you will build a symbol
table. This assignment serves several purposes:
Overview
A symbol table is a data structure that relates an identifier to
information about that identifier. For this assignment, the
identifiers are the labels on lines of LC3 assembly language
statements. The information associated with the label is its
address. For more information on symbol tables see
this wikipedia entry.
In this assignment, you will use a hash table with chaining. You
will learn more about hash tables in your Data Structures course.
The data structures you use are already defined for you
in symbol.h/symbol.c.
The hash function you will use computes an integer value from a
string. More than one string may hash to
the same value. However, a good hash
function will minimize this. You can think of the hash value as an
"alias" for the string. Thus, when searching for a string, you
first search for the hash value (using integer comparison, which is
fast) and only when you find an equal hash value,
use strcasecmp() (much slower than integer comparison) to
verify you have found the string of interest.
The symbol table contains a hash_table which is an
array. The index into this array is calculated as index =
hash-value % size-of-hash-table. A given index in the hash table
contains a pointer to the head of a singly linked list of nodes
containing symbols whose hash values share the same index.
There is a second table in the symbol table structure. It is a
dynamically allocated array of char* (C's version of
strings), that allow a fast lookup of a symbols name given its
address.
Here is a graphical representation of the data structure.
Make sure you understand how the declarations relate to the
drawing.
Getting Started
Implementing symbol_init()
In this function, you must allocate space for your symbol table
and initialize it appropriately. Compare malloc()/calloc().
You will also allocate and
initialize addr_table[] and hash_table[].
The hash_table should be the size of the capacity
parameter and the addr_table should be an array
of char pointers the size of the LC3 memory space.
Here is a graphical representation of the data structure.
Make sure you understand how the declarations relate to the
drawing.
Implementing symbol_search()
This function will do a lot of the work needed for the
functions symbol_add() and symbol_find_by_name().
The basic algorithm to search for a symbol by name is:
You can test implementation by using the
command search in the test driver.
Implementing symbol_add()
This function adds a symbol to the symbol table if it does not
already exist. If it does not exist, you must allocate memory for
the appropriate structure, initialize the fields of the structure
appropriately and store in at the correct index in the symbol
table. The entry at a given index of the symbol table is a pointer
to the head of a linked list of nodes. The symbol just created
should become the new head of the list.
You may test your implementation using the add command
with the test driver.
A hash table is designed to spread out the entries, often
sacrificing space for speed. To thoroughly test your function, you
will need to force multiple names to occupy the same index in the
hash table. Think about the pigeon hole principle from CS165, study
the code and you should understand what to modify to test your
code. Your code will be tested with a different values.
NOTE: The name parameter that symbol_add()
receives is not a pointer to dynamic memory. Simply assigning a new
symbol that pointer will cause you problems. You may wish to read
up on strdup from the c string
library.
Implementing the remaining functions
Implement the remaining functions one by one and test them as
you go.
Testing your code
Thoroughly test your code using the test driver. You may find it
convenient to build a file containing a series of commands to
execute, then use this file to test your program without having to
type in commands over and over. Execute
Example command line test
The following is a simple example of what your code should be
able to do in P4A: