Make a hashtable in C.
lab5-starter-code/Dictionary.c
#include <stdlib.h> #include <stdio.h> #include "Dictionary.h" #include "list.h" typedef struct DictionaryObj { } DictionaryObj; typedef struct EntryObj { } EntryObj; // allows EntryObj* to be called Entry in this file typedef struct EntryObj* Entry; /* * * YOUR FUNCTION IMPLEMENTATIONS GO BELOW HERE * */ /* * * YOUR FUNCTION IMPLEMENTATIONS GO ABOVE HERE * */ /* * YOUR CODE GOES ABOVE THIS COMMENT * DO NOT ALTER THESE FUNCTIONS * THESE ARE THE THREE FUNCTIONS THAT WILL ALLOW YOU TO CONVERT * A STRING INTO A VALID ARRAY INDEX * YOU WILL ONLY NEED TO CALL hash(Dictionary D, char* key) */ // rotate_left() // rotate the bits in an unsigned int unsigned int rotate_left(unsigned int value, int shift) { int sizeInBits = 8*sizeof(unsigned int); shift = shift & (sizeInBits - 1); if ( shift == 0 ) { return value; } return (value << shift) | (value >> (sizeInBits - shift)); } // pre_hash() // turn a string into an unsigned int unsigned int pre_hash(char* input) { unsigned int result = 0xBAE86554; while (*input) { result ^= *input++; result = rotate_left(result, 5); } return result; } // hash() // turns a string into an int in the range 0 to tableSize-1 int hash(Dictionary D, char* key){ return pre_hash(key) % D->tableSize; }
lab5-starter-code/Dictionary.h
//----------------------------------------------------------------------------- // Dictionary.h // Header file for the Dictionary ADT //----------------------------------------------------------------------------- #ifndef _DICTIONARY_H_INCLUDE_ #define _DICTIONARY_H_INCLUDE_ // Dictionary // Exported reference type // Allows DictionaryObj* to be called Dictionary instead typedef struct DictionaryObj* Dictionary; // newDictionary() // constructor for the Dictionary type Dictionary newDictionary(int tableSize); // freeDictionary() // destructor for the Dictionary type void freeDictionary(Dictionary* pD); // isEmpty() // returns 1 (true) if D is empty, 0 (false) otherwise // pre: none int isEmpty(Dictionary D); // size() // returns the number of (key, value) pairs in D // pre: none int size(Dictionary D); // lookup() // returns the value v such that (k, v) is in D, or returns NULL if no // such value v exists. // pre: none char* lookup(Dictionary D, char* k); // insert() // inserts new (key,value) pair into D // pre: lookup(D, k)==NULL void insert(Dictionary D, char* k, char* v); // delete() // deletes pair with the key k // pre: lookup(D, k)!=NULL void delete(Dictionary D, char* k); // makeEmpty() // re-sets D to the empty state. // pre: none void makeEmpty(Dictionary D); // printDictionary() // pre: none // prints a text representation of D to the file pointed to by out void printDictionary(FILE* out, Dictionary D); #endif
lab5-starter-code/DictionaryClient.c
//----------------------------------------------------------------------------- // DictionaryClient.c // Test client for the Dictionary ADT //----------------------------------------------------------------------------- #include<stdio.h> #include<stdlib.h> #include<string.h> #include"Dictionary.h" #define MAX_LEN 180 int main(int argc, char* argv[]){ Dictionary A = newDictionary(101); char* k; char* v; char* word1[] = {"one","two","three","four","five","six","seven"}; char* word2[] = {"foo","bar","blah","galumph","happy","sad","blue"}; int i; for(i=0; i<7; i++){ insert(A, word1[i], word2[i]); } printDictionary(stdout, A); for(i=0; i<7; i++){ k = word1[i]; v = lookup(A, k); printf("key=\"%s\" %s\"%s\"\n", k, (v==NULL?"not found ":"value="), v); } // insert(A, "five", "glow"); // error: duplicate keys delete(A, "one"); delete(A, "three"); delete(A, "seven"); printDictionary(stdout, A); for(i=0; i<7; i++){ k = word1[i]; v = lookup(A, k); printf("key=\"%s\" %s\"%s\"\n", k, (v==NULL?"not found ":"value="), v); } // delete(A, "one"); // error: key not found printf("%s\n", (isEmpty(A)?"true":"false")); printf("%d\n", size(A)); makeEmpty(A); printf("%s\n", (isEmpty(A)?"true":"false")); freeDictionary(&A); return(EXIT_SUCCESS); }
lab5-starter-code/DictionaryClient2.c
//----------------------------------------------------------------------------- // DictionaryClient2.c // Another test client for the Dictionary ADT //----------------------------------------------------------------------------- #include<stdio.h> #include<stdlib.h> #include<string.h> #include"Dictionary.h" #define MAX_LEN 180 int main(int argc, char* argv[]){ Dictionary A = newDictionary(101); FILE* in = fopen("DictionaryClient2.c", "r"); FILE* out = fopen("DictionaryClient2-out", "w"); char* key; char* value; char* keyBuffer = NULL; char* valBuffer = NULL; int keyBufferOffset = 0, valBufferOffset = 0; int keyBufferLength = 0, valBufferLength = 0; char line[MAX_LEN+1]; char label[MAX_LEN+1]; int i, labelLength, lineLength, lineNumber = 0; // read input files while( fgets(line, MAX_LEN, in)!=NULL ){ // put line in valBuffer lineNumber++; lineLength = strlen(line)-1; line[lineLength] = '\0'; // overwrite newline '\n' with null '\0' valBufferLength += (lineLength+1); valBuffer = realloc(valBuffer, valBufferLength*sizeof(char) ); value = &valBuffer[valBufferOffset]; strcpy(value, line); valBufferOffset = valBufferLength; // put label in keyBuffer sprintf(label, "line %d:\t", lineNumber); labelLength = strlen(label); keyBufferLength += (labelLength+1); keyBuffer = realloc(keyBuffer, keyBufferLength*sizeof(char) ); key = &keyBuffer[keyBufferOffset]; strcpy(key, label); keyBufferOffset = keyBufferLength; } // put keys and values in dictionary A keyBufferOffset = valBufferOffset = 0; for(i=0; i<lineNumber; i++){ key = &keyBuffer[keyBufferOffset]; value = &valBuffer[valBufferOffset]; insert(A, key, value); keyBufferOffset += (strlen(key) + 1); valBufferOffset += (strlen(value) + 1); } printDictionary(out, A); // free memory and close files freeDictionary(&A); free(keyBuffer); free(valBuffer); fclose(in); fclose(out); return(EXIT_SUCCESS); }
lab5-starter-code/HashDemo.c
//----------------------------------------------------------------------------- // HashDemo.c // Demonstrate functions rotate_left(), pre_hash(), hash() and showBits() // // compile: gcc -std=c99 -o HashDemo HashDemo.c // //----------------------------------------------------------------------------- #include <stdio.h> #include <string.h> #include <stdlib.h> const int tableSize = 101; // rotate_left() // rotate the bits in an unsigned int unsigned int rotate_left(unsigned int value, int shift) { int sizeInBits = 8*sizeof(unsigned int); shift = shift & (sizeInBits - 1); if ( shift == 0 ) return value; return (value << shift) | (value >> (sizeInBits - shift)); } // pre_hash() // turn a string into an unsigned int unsigned int pre_hash(char* input) { unsigned int result = 0xBAE86554; while (*input) { result ^= *input++; result = rotate_left(result, 5); } return result; } // hash() // turns a string into an int in the range 0 to tableSize-1 int hash(char* key){ return pre_hash(key)%tableSize; } // showBits() // print out the bits in an unsigned int void showBits(unsigned int x) { int i; int sizeInBits = 8*sizeof(unsigned int); char symbol[2] = {'0','1'}; char* binary = malloc(sizeInBits + 1); memset(binary, 0, sizeInBits + 1); for (i=0; i<sizeInBits; i++) { binary[sizeInBits-i-1] = symbol[(x>>i) & 0x01]; } printf("%s\n", binary); free(binary); } int main(void){ char str1[] = "iron-heartedly"; char str2[] = "ironheartedly"; char str3[] = "Ironheartedly"; printf("When tableSize=%d:\n", tableSize); printf("%s hashes to index: %d\n", str1, hash(str1)); printf("%s hashes to index: %d\n", str2, hash(str2)); printf("%s hashes to index: %d\n", str3, hash(str3)); printf("\n\n"); printf("Number of bytes in unsigned int = %d\n", sizeof(unsigned int)); printf("Number of bits in unsigned int = %d\n", 8*sizeof(unsigned int)); showBits(0xBAE86554); showBits(rotate_left(0xBAE86554, 5)); showBits(0xBAE86554 << 5); showBits(0xBAE86554 >> (8*sizeof(unsigned int) - 5) ); showBits( (0xBAE86554 << 5) | (0xBAE86554 >> (8*sizeof(unsigned int) - 5) ) ); printf("\n\n"); printf("\'a\' = "); showBits('a'); printf("\'b\' = "); showBits('b'); printf("\'c\' = "); showBits('c'); return EXIT_SUCCESS; }
lab5-starter-code/list.c
#include <stdlib.h> #include "list.h" #include <stdio.h> Node* make_node(void* data, Node* next){ Node* node = calloc(1,sizeof(Node)); node->data = data; node->next = next; return node; } List* make_list(){ List* list = calloc(1,sizeof(List)); list->head = NULL; list->size = 0; return list; } void free_node(Node* node){ if(node != NULL){ free(node->data); } free(node); } void free_list(List* list) { Node* current = list->head; while (current != NULL){ Node* next = current->next; free_node(current); current = next; } free(list); } void add(List* list, int index, void* data) { Node* current = list-> head; list->size++; if (index == 0){ list->head = make_node(data,current); } else { while (index-1 > 0){ current = current->next; index--; } current->next = make_node(data,current->next); } } void* get(List* list, int index){ Node* current = list->head; while (index != 0){ current = current->next; index--; } return current->data; } void remove_node(List* list, int index){ if (index == 0){ Node* to_remove = list->head; list->head = list->head->next; free(to_remove); } else { Node* current = list->head; while (index > 1){ current = current->next; index--; } Node* to_remove = current->next; current->next = current->next->next; free(to_remove); } list->size--; } void set(List* list, int index, void* data){ Node* current = list->head; while (index != 0){ current = current->next; index--; } current->data = data; }
lab5-starter-code/list.h
#ifndef CMPS12B_LIST #define CMPS12B_LIST typedef struct node_type{ /* * TODO 1 */ struct node_type* next; void* data; /* * TODO 1 */ } Node; typedef struct { /* * TODO 1 */ Node* head; int size; /* * TODO 1 */ } List; Node* make_node(void* data, Node* next); List* make_list(); void free_node(Node* node); void free_list(List* list); void add(List* list, int index, void* data); void* get(List* list, int index); void set(List* list, int index, void* data); void remove_node(List* list, int index); #endif