Instructions
Objective
Write a C assignment program to Look up values in linked list, C and ARM assembly.
Requirements and Specifications
The jungle is getting polluted due to human encroachment and the animals need your help to gauge how long they can suffer before they finally start a war against the humans. You need to help them with pollution statistics.
For this assignment, you shall be parsing the pollution data of a city provided in the form of a CSV (comma separated value) file . Your job is to build a system that stores this pollution data and is able to query it by date in near constant time. You shall do this by implementing a hash table-based in-memory database using single linked chains for collision resolution. The database will contain the following fields.You will load the CSV file into the database and then make a query of a date. If the date is not found in the database, your program will respond with a “not found” message. Otherwise, the program will print out the minimum, maximum, and average pm2.5 and TEMP of that date. You will also be asked to remove a date (a “year,” “month,” and “day” combination) from the database. In that case you need to remove all the entries related to that particular date.
Screenshots of output
Source Code
Hash.s
// CES30 assignment template
//
//
// Describe target Hardware to the assembler
.arch armv6
.arm
.fpu vfp
.syntax unified
.align 4
.bss
.data
/////////////////////////////////////////////////////////
.text // start of the text segment
/////////////////////////////////////////////////////////
// function hashFun
/////////////////////////////////////////////////////////
.type hashFun, %function // define as a function
.global hashFun // export function name
.equ FP_OFFSET, 28 // (regs - 1) * 4
/////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////
hashFun:
push {r4-r9, fp, lr} // use r4-r9 protected regs
add fp, sp, FP_OFFSET // locate our frame pointer
// do not edit the prologue above
// You can use temporary r0-r3 and preserved r4-r9
// Store return value (results) in r0
/////////////////////////////////////////////////////////
// TODO: Write your code here to implement the hash function.
// For reference, the C implementation is shown here:
// hash = c + (hash << 6) + (hash << 16) - hash;
lsl r2, r1, #6 // calculate hash << 6
lsl r3, r1, #16 // calculate hash << 16
add r0, r0, r2 // add c + hash << 6
add r0, r0, r3 // add c + hash << 6 + hash << 16
sub r0, r0, r1 // subtract c + hash << 6 + hash << 16 - hash
/////////////////////////////////////////////////////////
// do not edit the epilogue below
sub sp, fp, FP_OFFSET // restore sp
pop {r4-r9,fp, lr} // restore saved registers
bx lr // function return
.size hashFun,(. - hashFun)
Node_lookup.s
//file header
.arch armv6 //armv6 architecture
.arm //arm 32-bit IS
.fpu vfp //floating point co-processor
.syntax unified //modern syntax
//.data //uncomment if needed
.text //start of text segment
.global node_lookup //make node_lookup global for linking to
.type node_lookup, %function //define node_lookup to be a function
.equ FP_OFF, 12 // fp offset distance from sp = (regs - 1) * 4
node_lookup:
// function prologue
push {r4-r5, fp, lr} // use r4-r9 protected regs
add fp, sp, FP_OFF // locate our frame pointer
//function body
cmp r0, #0 // if null pointer
beq look_end // end returning NULL
ldr r4, [fp, #4] // load hour in r4
look_loop:
ldr r5, [r0, #0] // load year from node
cmp r5, r1 // see if years match
bne look_next // if not, go to next entry
ldr r5, [r0, #4] // load month from node
cmp r5, r2 // see if months match
bne look_next // if not, go to next entry
ldr r5, [r0, #8] // load day from node
cmp r5, r3 // see if days match
bne look_next // if not, go to next entry
ldr r5, [r0, #12] // load hour from node
cmp r5, r4 // see if hours match
beq look_end // if match, return r0 with the matching entry
look_next:
ldr r0, [r0, #24] // load next pointer in r0
cmp r0, #0 // if not null pointer
bne look_loop // repeat the loop
look_end:
// function epilogue
sub sp, fp, FP_OFF // restore sp
pop {r4-r5,fp, lr} // restore saved registers
bx lr // function return
// function footer - do not edit below
.size node_lookup, (. - node_lookup) // set size for function
//file footer
.section .note.GNU-stack,"",%progbits // stack/data non-exec (linker)
.end
Poll_lookup.c
/*
* CSE30 Summer Session 1 '22 HW3
* CSE30 username: cs30su122xxx (TODO: Fill in)
*/
#include "poll_lookup.h"
/*
* !!! DO NOT EDIT THIS FUNCTION !!!
* main
*
* Arguments: argc, argv
*
* Operation: Main driver for the program, calls other funttions to:
* parse the options, allocate the hash table, load the table, print
*out the table stats
* and make print population stats of the desired city/state
* Returns: EXIT_SUCCESS if all ok, EXIT_FAILURE otherwise
* !!! DO NOT EDIT THIS FUNCTION !!!
*/
int main(int argc, char *argv[]) {
node **table;
unsigned long size = TABLE_SIZE;
// name of csv file
char *filename;
int info = 0;
// Indicates days we want stats for/to remove
char *date = NULL;
char *del_date = NULL;
// Parse options
if (!parse_opts(argc, argv, &filename, &size, &info, &date, &del_date)) {
return EXIT_FAILURE;
}
// Allocate space for table
if ((table = calloc(size, sizeof(node *))) == NULL) {
fprintf(stderr, "%s: Unable to allocate space for hash table\n", argv[0]);
return EXIT_FAILURE;
}
// Load records from file
if (load_table(table, size, filename)) {
return EXIT_FAILURE;
}
// Delete data first
if (del_date) {
char *stripped_date = strip_date(del_date);
if (stripped_date) { // no malloc fail
delete_date(table, size, stripped_date);
free(stripped_date);
} else {
return EXIT_FAILURE;
}
}
// Produce data for a single date
if (date) {
char *stripped_date = strip_date(date);
if (stripped_date) { // no malloc fail
print_date_stats(table, size, stripped_date);
free(stripped_date);
} else {
return EXIT_FAILURE;
}
}
// Print metadata
if (info)
print_info(table, size);
// Clean up
delete_table(table, size);
return EXIT_SUCCESS;
}
/*
* !!! DO NOT EDIT THIS FUNCTION !!!
* hash
*
* Arguments: a null terminated string
*
* Operation: calculates a hash value for the string
*
* returns: the hash value
* !!! DO NOT EDIT THIS FUNCTION !!!
*/
unsigned long hash(char *str) {
unsigned long hash = 0;
unsigned int c;
#ifdef C_HASH
while ((c = (unsigned char)*str++) != '\0') {
hash = c + (hash << 6) + (hash << 16) - hash;
}
#else
while ((c = (unsigned char)*str++) != '\0') {
hash = hashFun((unsigned long)c, hash);
}
#endif
return hash;
}
/*
* add_node
*
* Arguments: linked list pointer head, year, month, day, hour, pm25, temp
*/
node *add_node(node *front, int year, int month, int day, int hour, int pm25,
int temp) {
node *new_node, *temp_node;
new_node = malloc(sizeof(node));
if (new_node == NULL)
{
return NULL;
}
else
{
new_node->year = year;
new_node->month = month;
new_node->day = day;
new_node->hour = hour;
new_node->pm25 = pm25;
new_node->temp = temp;
new_node->next = NULL;
// if there is a chain
if (front != NULL)
{
// find last node
temp_node = front;
while (temp_node -> next != NULL)
temp_node = temp_node->next;
// insert at the end
temp_node->next = new_node;
}
// if not, it's the first node
else
{
// set new node as the initial one
front = new_node;
}
return front;
}
}
/*
* print_date_stats
* Print the average stats for this date
*
* Arguments: pointer to hash table, hash table size, date as a string in the
*form YYYY-MM-DD
*/
void print_date_stats(node **table, unsigned long size, char *datestr) {
unsigned long hashval;
node *chain;
int min_pm25, max_pm25, avg_pm25;
int min_temp, max_temp, avg_temp;
const char split[] = "-";
char *token;
int cols[COL_DAY+1];
int count;
// hash date string
hashval = hash(datestr) % size;
chain = table[hashval];
// get date fields
token = strtok(datestr, split);
count = 0;
while (token != NULL) {
cols[count] = atoi(token);
token = strtok(NULL, split);
count++;
}
min_pm25 = 0;
max_pm25 = 0;
avg_pm25 = 0;
min_temp = 0;
max_temp = 0;
avg_temp = 0;
count = 0;
while (chain != NULL)
{
// add to stats if matching
if (chain->year == cols[COL_YEAR] && chain->month == cols[COL_MONTH]
&& chain->day == cols[COL_DAY])
{
avg_pm25 += chain->pm25;
avg_temp += chain->temp;
// if this is the first value, initialize all stats
if (count == 0)
{
min_pm25 = chain->pm25;
max_pm25 = chain->pm25;
min_temp = chain->temp;
max_temp = chain->temp;
}
// for remaining value, do the comparisons
else
{
if (chain->pm25 < min_pm25)
min_pm25 = chain->pm25;
if (chain->pm25 > max_pm25)
max_pm25 = chain->pm25;
if (chain->temp < min_temp)
min_temp = chain->temp;
if (chain->temp > max_temp)
max_temp = chain->temp;
}
count++;
}
chain = chain->next;
}
if (count != 0)
{
avg_pm25 = avg_pm25 / count;
avg_temp = avg_temp / count;
printf("Minimum pm2.5: %d\tMaximum pm2.5: %d\tAverage pm2.5: %d\n",
min_pm25, max_pm25, avg_pm25);
printf("Minimum temp: %d\tMaximum temp: %d\tAverage temp: %d\n",
min_temp, max_temp, avg_temp);
}
else
{
printf("Unable to find any data for the date %s.\n", datestr);
}
}
/*
* load_table
* Allocate memory for the hash table of node*s
*
* Arguments: pointer to hash table, hash table size, file name
*/
int load_table(node **table, unsigned long size, char *filename) {
// TODO: Implement load_table
FILE *file;
char *buffer, *line, *token;
char *cols[7];
char datestr[MAX_SIZE_DATESTR];
int year, month, day, hour, pm25, temp;
node *front, *chain;
int i;
unsigned long hashval;
// open file
file = fopen(filename, "rt");
if (file == NULL)
{
perror("load_table filename open");
return 1;
}
// allocate buffer
buffer = malloc(LINE_SIZE);
if (buffer == NULL)
{
perror("load_table malloc");
fclose(file);
return 1;
}
// allocate line
line = malloc(LINE_SIZE);
if (line == NULL)
{
perror("load_table malloc");
free(line);
fclose(file);
return 1;
}
// read lines in file
while (fgets(buffer, LINE_SIZE, file) != NULL)
{
// copy line
strcpy(line, buffer);
i = 0;
// tokenize string
token = strtok(buffer, ",\n");
while (token != NULL)
{
cols[i] = token;
token = strtok(NULL, ",\n");
i++;
}
// avoid adding empty lines
if (i == 6)
{
// convert columns to corresponding fields
year = atoi(cols[COL_YEAR]);
month = atoi(cols[COL_MONTH]);
day = atoi(cols[COL_DAY]);
hour = atoi(cols[COL_HOUR]);
pm25 = atoi(cols[COL_PM25]);
temp = atoi(cols[COL_TEMP]);
// make date string
snprintf(datestr, MAX_SIZE_DATESTR, "%d-%d-%d", year, month, day);
// hash date string
hashval = hash(datestr) % size;
chain = table[hashval];
// if duplicated
if (node_lookup(chain, year, month, day, hour) != NULL)
{
printf("load_table duplicate entry: %d-%d-%d %d\n",
year, month, day, hour);
}
else
{
front = add_node(chain, year, month, day, hour, pm25, temp);
// if unable to add
if (front == NULL)
printf("load_table could not add %s\n", line);
else
// update front
table[hashval] = front;
}
}
}
free(buffer);
free(line);
fclose(file);
return 0;
}
/*
* print_info
*
* Arguments: pointer to a hash table, number of elements
*/
void print_info(node **table, unsigned long size) {
unsigned long i;
unsigned long entries, len, longest, shortest, empty;
node *chain;
entries = 0;
longest = 0;
shortest = 0;
empty = 0;
// go through all chains
for (i = 0; i < size; i++)
{
chain = table[i];
// get the chain length
len = 0;
while (chain != NULL)
{
len++;
entries++;
chain = chain->next;
}
// if empty
if (len == 0)
empty++;
// if one or more entries in chain
else
{
if (len > longest)
longest = len;
if (shortest == 0 || len < shortest)
shortest = len;
}
}
printf("Table size: %lu\n", size);
printf("Total entries: %lu\n", entries);
printf("Longest chain: %lu\n", longest);
printf("Shortest chain: %lu\n", shortest);
printf("Empty buckets: %lu\n", empty);
}
/*
* delete_date
* Delete all nodes associated with a given date of form YYYY-MM-DD
* All leading zeros have been removed in the date string
*/
void delete_date(node **table, unsigned long size, char *datestr) {
unsigned long hashval = hash(datestr) % size;
node *chain = table[hashval];
node *tmp, *prev = NULL;
node* new_head = chain;
const char split[] = "-";
char *token = strtok(datestr, split);
int cols[COL_DAY+1];
int c = 0;
while (token != NULL) {
cols[c] = atoi(token);
token = strtok(NULL, split);
c++;
}
while (chain != NULL) {
tmp = chain->next;
// Delete if matching
if (chain->year == cols[COL_YEAR] && chain->month == cols[COL_MONTH]
&& chain->day == cols[COL_DAY]) {
// Only link previous if there was a previous
if (prev) {
prev->next = tmp;
// No previous: this was the head, now new head is the one in front of us
} else {
new_head = tmp;
}
free(chain);
// If not matching, don't delete and set prev as usual
} else {
prev = chain;
}
chain = tmp;
}
table[hashval] = new_head;
}
/*
* delete_table
*
* Arguments: pointer to hash table, hash table array size
*/
void delete_table(node **table, unsigned long size) {
unsigned int i;
node *tmp;
node *curr_tmp;
for (i = 0; i < size; i++) {
curr_tmp = table[i];
while (curr_tmp != NULL) {
tmp = curr_tmp->next;
free(curr_tmp);
curr_tmp = tmp;
}
}
free(table);
}