C programing Symbol Table

symbol.c IMPLEMENT CODE IN THIS FILE HEADER FILE IS BELOW IT

HIGHLIGHTED FUNCTIONS ARE TO BE MODIFIED THERE ARE 4

EXPLINATIONS FOR EACH FUNCTION IS IN THE HEADER FILE (also type def)

(for all the files and how to make the exicutable reference www. cs.colostate.edu/~cs270/.Fall18/assignments/P4/doc/index.html)

#include #include #include #include #include

#include "Debug.h" #include "symbol.h"

/** * You will modify this file and implement the symbol.h interface * Your implementation of the functions defined in symbol.h. * You may add other functions if you find it helpful. Added functions * should be declared static to indicate they are only used * within this file. The reference implementation added approximately * 110 lines of code to this file. This count includes lines containing * only a single closing bracket (}). */

/** size of LC3 memory */ #define LC3_MEMORY_SIZE (1 << 16)

/** Provide prototype for strdup() */ char *strdup(const char *s);

/** defines data structure used to store nodes in hash table */ typedef struct node { struct node* next; /**< linked list of symbols at same index */ int hash; /**< hash value - makes searching faster */ symbol_t symbol; /**< the data the user is interested in */ } node_t;

/** defines the data structure for the hash table */ struct sym_table { int capacity; /**< length of hast_table array */ int size; /**< number of symbols (may exceed capacity) */ node_t** hash_table; /**< array of head of linked list for this index */ char** addr_table; /**< look up symbols by addr (optional) */ };

static int symbol_hash (const char* name) { unsigned char* str = (unsigned char*) name; unsigned long hash = 5381; int c;

while ((c = *str++)) hash = ((hash << 5) + hash) + tolower(c); /* hash * 33 + c */

c = hash & 0x7FFFFFFF; /* keep 31 bits - avoid negative values */

return c; }

/** @todo implement this function */ sym_table_t* symbol_init (int capacity) { return NULL; }

/** @todo implement this function */ int symbol_add (sym_table_t* symTab, const char* name, int addr) { return 0; }

/** @todo implement this function */ struct node* symbol_search (sym_table_t* symTab, const char* name, int* hash, int* index) { *hash = symbol_hash(name); return NULL; }

/** @todo implement this function */ void symbol_iterate (sym_table_t* symTab, iterate_fnc_t fnc, void* data) { }

------------------------------------------------------------------------------------------------------

symbol.h HEADER FILE

#ifndef __SYMBOL_H__ #define __SYMBOL_H__

/** * Defines the interface to symbol.c functions (do not modify) * This file defines the interface to a C file symbol.c . The underlying data structure(s) used will be * defined by the actual assignment. The assignment will define whether symbols * are case sensitive or case in-sensitive. * In this implementation, you will learn about dynamic memory management using * malloc/free. You will also learn about function pointers (callback functions). */

/** order in list is order in hash table */ #define HASH 0

/** order in list is alphabetical by name */ #define NAME 1

/** order in list is by increasing address */ #define ADDR 2

/** This defines an opaque type. The actual contents of the structure are hidden * in the implementation (symbol.c) and only a pointer to this structure is * used externally to that file. A pointer to an opaque structure is sometimes * referred to as a handle. */

typedef struct sym_table sym_table_t;

/** The symbol_find methods return a pointer to this data structure. It is up * to the implementor to decide how to use this stucture in the implementation. */

typedef struct symbol { char* name; /**< the name of the symbol */ int addr; /**< symbol's address in the LC3 memory */ } symbol_t;

/** Defines the signature of a callback function (also known as a function * pointer). This is how languages such as Java and C++ do dynamic * binding * In the LC3, dynamic binding is based on the JSRR opcode. With this * opcode, the address of the routine to call is stored in a register and can * be changed at runtime. Compare this to a JSR nameOfRoutine opcode which * specifies what routine to call from the label that follows it. Thus, the * address is fixed at assembly time. * This is used in the symbol_iterate() function. An interesting variation * would be to have the callback function return an integer which determines * whether the iteration should contibue or terminate. * @param symTab - pointer to the symbol table * @param data - any additional information to be passed on to fnc. The called * function will cast this to whatever type was actually passed. */ typedef void (*iterate_fnc_t)(symbol_t* sym, void* data);

/** Add a symbol to the symbol table. * @param symTab - pointer to the symbol table * @param name - the name of the symbol * @param addr - the address of the symbol * @return 1 if name is currently in the symbol table, * 0 otherwise */ int symbol_add (sym_table_t* symTab, const char* name, int addr);

/** Create a new symbol table and return a pointer to it. This function is a * constructor for a symbol table. It allocates and initializes both the * hash_table and the addr_table. The latter is * an array of char* that is indexed by an LC3 * address to find the label (if any) associated with that address. * @param capacity - the size of the hash table. * @return a pointer to the symbol table. */ sym_table_t* symbol_init (int capacity);

/** This function is only used internally and should be declared static. It is * a useful support function for the add()/find() functions. * It is declared here for documentation purposes. The function returns * three values: one in the return value, and the other two using * the pointers to the hash and index values. * @param symTab - pointer to the symbol table * @param name - the name of the symbol * @param hash - pointer to location where hash value will be stored * @param index - pointer to location where index will be stored * @return the nodes information or NULL if no symbol is associated with * the name. */ struct node* symbol_search (sym_table_t* symTab, const char* name, int* hash, int* index);

/** This function calls the function for every entry in the symbol table. * Theassigment will define the order in which the entries should be visited. * @param symTab - pointer to the symbol table * @param fnc - the function to be called on every element * @param data - any additional information to be passed on to fnc. The called * function will cast this to whatever type was actually passed. */ void symbol_iterate (sym_table_t*symTab, iterate_fnc_t fnc, void* data);

#endif /* __SYMBOL_H__ */