Create A Program To Look Up Values In Linked List, C And ARM Assembly Assignment Solution

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