Fix the functions that have had code started in them (C Programing)

#include

#include

#include

#include

#include

#include "Debug.h"

#include "symbol.h"

/** @file symbol.c

* @brief You will modify this file and implement the symbol.h interface

* @details 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 (}).

*

* @author Your name goes here

*/

/** 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) */

};

/** djb hash - found at http://www.cse.yorku.ca/~oz/hash.html

* tolower() call to make case insensitive.

*/

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) {

struct sym_table *table;

table = malloc(1 * sizeof(struct sym_table));

table->size= capacity;

table->hash_table = malloc(capacity * sizeof(struct node *));

int i;

//printf("%d ", table->size);

for(i = 0; i < table->size; i++) {

table->hash_table[i] = NULL;

}

return table;

}

/** @todo implement this function */

void symbol_term (sym_table_t* symTab) {

}

/** @todo implement this function */

void symbol_reset(sym_table_t* symTab) {

}

/** @todo implement this function */

int symbol_add (sym_table_t* symTab, const char* name, int addr) {

int hash;

int index;

strdup(name);

struct node *node_new;

node_new = malloc(1 * sizeof(struct node));

node_new->next = symbol_search(symTab, name, &hash, &index);

if(node_new->next == NULL) {

return 0;

}

node_new->symbol.name = strdup(name);

node_new->symbol.addr = addr;

symTab->hash_table[index] = node_new;

printf("%s ", symTab->hash_table[index]->symbol.name);

return 1;

}

/** @todo implement this function */

struct node* symbol_search (sym_table_t* symTab, const char* name, int* hash, int* index) {

*hash = symbol_hash(name);

*index = *hash % symTab->size;

struct node *node_new;

node_new = malloc(1 * sizeof(struct node));

if(symbol_find_by_name(symTab,name) == NULL){

node_new->next = symTab->hash_table[*index];

return node_new;

}

return NULL;

}

/** @todo implement this function */

symbol_t* symbol_find_by_name (sym_table_t* symTab, const char* name) {

int i;

for(i = 0; i < symTab->size; i++) {

if(!(symTab->hash_table[i] == NULL))

{

if(strcasecmp(symTab->hash_table[i]->symbol.name,name)==0) {

// printf("%s ", "duplicate");

// printf("%s", symTab->hash_table[0]->symbol.name);

return symTab->hash_table[i]->symbol.name;

}

}

}

return NULL;

}

/** @todo implement this function */

char* symbol_find_by_addr (sym_table_t* symTab, int addr) {

return NULL;

}

/** @todo implement this function */

void symbol_iterate (sym_table_t* symTab, iterate_fnc_t fnc, void* data) {

int i;

for(i = 0; i < symTab->size; i++) {

if(!(symTab->hash_table[i] == NULL))

{

printf("%s", symTab->hash_table[i]->symbol.name);

}

}

}

/** @todo implement this function */

int symbol_size (sym_table_t* symTab) {

return 0;

}

/** @todo implement this function */

int compare_names (const void* vp1, const void* vp2) {

// symbol_t* sym1 = *((symbol_t**) vp1); // study qsort to understand this

return 0;

}

/** @todo implement this function */

int compare_addresses (const void* vp1, const void* vp2) {

return 0;

}

/** @todo implement this function */

symbol_t** symbol_order (sym_table_t* symTab, int order) {

// will call qsort with either compare_names or compare_addresses

return NULL;

}

====================================================================

====================================================================

====================================================================

====================================================================

#ifndef __SYMBOL_H__ #define __SYMBOL_H__

/** @file symbol.h

* @brief Defines the interface to symbol.c functions (do not modify) * @details This file defines the interface to a C file symbol.c that * you will complete. 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;

/** 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);

/** Find a name by its LC3 address * @param symTab - pointer to the symbol table * @param addr - an LC3 address * @return the label at that address or NULL if no symbol is * associated with the adddress. */ char* symbol_find_by_addr (sym_table_t* symTab, int addr);

/** Find a symbol by its name * @param symTab - pointer to the symbol table * @param name - the symbols name * @return the symbols information or NULL if no symbol is associated with * the name. * Most of the work is done by symbol_search(). That routine * returns a node_t*, but this routine returns a * symbol_t*. Study * this posting to understand how you might solve this. */ symbol_t* symbol_find_by_name (sym_table_t* symTab, const char* name);

/** 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);

/** Remove all the symbols from the symbol table. After this call the opaque * symbol table pointer is still valid and new symbols may be added to it. * If needed, clear the addr_table. * @param symTab - pointer to the symbol table */ void symbol_reset (sym_table_t* symTab);

/** 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);

/** Remove all symbols from the symbol table, and free all allocated memory. * This function is a destructor for a symbol table. * There must not be any memory leaks. After executing this function, the * opaque pointer to the symbol table is no longer valid. */ void symbol_term(sym_table_t* symTab);

/** 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 (i.e. figure out which function to call). Recall that in Java the * code obj.equals(object) will call one of possibly many * different methods depending on the actual type of obj. This * is because the method .equals() may be overridden. *

* 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);

/** This function calls the function for every entry in the symbol table. * The assigment 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);

/** A callback function for qsort to order by name in a case * insensative way. * @param vp1 pointer to first element * @param vp2 pointer to second element * @ return a number representing the correct ordering (neg, 0, pos) */ int compare_names (const void* vp1, const void* vp2);

/** A callback function for qsort to order by address * NOTE: If two elements have the same address, then return the result * of comparing by name, so that name becomes the secondary sort key. * @param vp1 pointer to first element * @param vp2 pointer to second element * @ return a number representing the correct ordering (neg, 0, pos) */ int compare_addresses (const void* vp1, const void* vp2);

/** Return the number of elements currently in the symbol table * @param symTab - pointer to the symbol table * @return number of elements */ int symbol_size (sym_table_t* symTab);

/** This function returns an ordered, dymanically allocated array of * symbol_t*. You may wish to use qsort() to order * it. The caller will free() the return value. * @param symTab - pointer to the symbol table * @param order - defines the sorting order for the list (HASH, NAME, ADDR) * @return pointer to an array of symbol_t* */ symbol_t** symbol_order (sym_table_t* symTab, int order);

#endif /* __SYMBOL_H__ */