project for 2035
Dependencies: mbed wave_player 4DGL-uLCD-SE MMA8452
hash_table.cpp@22:33f1a0dff46c, 2020-11-25 (annotated)
- Committer:
- kblake9
- Date:
- Wed Nov 25 04:48:22 2020 +0000
- Revision:
- 22:33f1a0dff46c
- Parent:
- 8:2e18a96e0c77
final
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
kblake9 | 8:2e18a96e0c77 | 1 | //================================================================= |
DCchico | 2:4947d6a82971 | 2 | // Copyright 2020 Georgia Tech. All rights reserved. |
DCchico | 2:4947d6a82971 | 3 | // The materials provided by the instructor in this course are for |
DCchico | 2:4947d6a82971 | 4 | // the use of the students currently enrolled in the course. |
DCchico | 2:4947d6a82971 | 5 | // Copyrighted course materials may not be further disseminated. |
DCchico | 2:4947d6a82971 | 6 | // This file must not be made publicly available anywhere. |
kblake9 | 8:2e18a96e0c77 | 7 | //================================================================= |
kblake9 | 8:2e18a96e0c77 | 8 | |
DCchico | 1:10330bce85cb | 9 | /* |
kblake9 | 8:2e18a96e0c77 | 10 | Student Name: Kate Blake |
kblake9 | 8:2e18a96e0c77 | 11 | Date: 11/2/2020 |
kblake9 | 8:2e18a96e0c77 | 12 | |
DCchico | 1:10330bce85cb | 13 | ======================= |
DCchico | 1:10330bce85cb | 14 | ECE 2035 Project 2-1: |
DCchico | 1:10330bce85cb | 15 | ======================= |
DCchico | 1:10330bce85cb | 16 | This file provides definition for the structs and functions declared in the |
DCchico | 1:10330bce85cb | 17 | header file. It also contains helper functions that are not accessible from |
DCchico | 1:10330bce85cb | 18 | outside of the file. |
kblake9 | 8:2e18a96e0c77 | 19 | |
DCchico | 1:10330bce85cb | 20 | FOR FULL CREDIT, BE SURE TO TRY MULTIPLE TEST CASES and DOCUMENT YOUR CODE. |
kblake9 | 8:2e18a96e0c77 | 21 | |
DCchico | 1:10330bce85cb | 22 | =================================== |
DCchico | 1:10330bce85cb | 23 | Naming conventions in this file: |
DCchico | 1:10330bce85cb | 24 | =================================== |
DCchico | 1:10330bce85cb | 25 | 1. All struct names use camel case where the first letter is capitalized. |
DCchico | 1:10330bce85cb | 26 | e.g. "HashTable", or "HashTableEntry" |
kblake9 | 8:2e18a96e0c77 | 27 | |
DCchico | 1:10330bce85cb | 28 | 2. Variable names with a preceding underscore "_" will not be called directly. |
DCchico | 1:10330bce85cb | 29 | e.g. "_HashTable", "_HashTableEntry" |
kblake9 | 8:2e18a96e0c77 | 30 | |
DCchico | 1:10330bce85cb | 31 | Recall that in C, we have to type "struct" together with the name of the struct |
DCchico | 1:10330bce85cb | 32 | in order to initialize a new variable. To avoid this, in hash_table.h |
DCchico | 1:10330bce85cb | 33 | we use typedef to provide new "nicknames" for "struct _HashTable" and |
DCchico | 1:10330bce85cb | 34 | "struct _HashTableEntry". As a result, we can create new struct variables |
DCchico | 1:10330bce85cb | 35 | by just using: |
DCchico | 1:10330bce85cb | 36 | - "HashTable myNewTable;" |
DCchico | 1:10330bce85cb | 37 | or |
DCchico | 1:10330bce85cb | 38 | - "HashTableEntry myNewHashTableEntry;" |
kblake9 | 8:2e18a96e0c77 | 39 | |
DCchico | 1:10330bce85cb | 40 | The preceding underscore "_" simply provides a distinction between the names |
DCchico | 1:10330bce85cb | 41 | of the actual struct defition and the "nicknames" that we use to initialize |
DCchico | 1:10330bce85cb | 42 | new structs. |
DCchico | 1:10330bce85cb | 43 | [See Hidden Definitions section for more information.] |
kblake9 | 8:2e18a96e0c77 | 44 | |
DCchico | 1:10330bce85cb | 45 | 3. Functions, their local variables and arguments are named with camel case, where |
DCchico | 1:10330bce85cb | 46 | the first letter is lower-case. |
DCchico | 1:10330bce85cb | 47 | e.g. "createHashTable" is a function. One of its arguments is "numBuckets". |
DCchico | 1:10330bce85cb | 48 | It also has a local variable called "newTable". |
kblake9 | 8:2e18a96e0c77 | 49 | |
DCchico | 1:10330bce85cb | 50 | 4. The name of a struct member is divided by using underscores "_". This serves |
DCchico | 1:10330bce85cb | 51 | as a distinction between function local variables and struct members. |
DCchico | 1:10330bce85cb | 52 | e.g. "num_buckets" is a member of "HashTable". |
kblake9 | 8:2e18a96e0c77 | 53 | |
DCchico | 1:10330bce85cb | 54 | */ |
kblake9 | 8:2e18a96e0c77 | 55 | |
DCchico | 1:10330bce85cb | 56 | /**************************************************************************** |
DCchico | 1:10330bce85cb | 57 | * Include the Public Interface |
DCchico | 1:10330bce85cb | 58 | * |
DCchico | 1:10330bce85cb | 59 | * By including the public interface at the top of the file, the compiler can |
DCchico | 1:10330bce85cb | 60 | * enforce that the function declarations in the the header are not in |
DCchico | 1:10330bce85cb | 61 | * conflict with the definitions in the file. This is not a guarantee of |
DCchico | 1:10330bce85cb | 62 | * correctness, but it is better than nothing! |
DCchico | 1:10330bce85cb | 63 | ***************************************************************************/ |
DCchico | 1:10330bce85cb | 64 | #include "hash_table.h" |
kblake9 | 8:2e18a96e0c77 | 65 | |
kblake9 | 8:2e18a96e0c77 | 66 | |
DCchico | 1:10330bce85cb | 67 | /**************************************************************************** |
DCchico | 1:10330bce85cb | 68 | * Include other private dependencies |
DCchico | 1:10330bce85cb | 69 | * |
DCchico | 1:10330bce85cb | 70 | * These other modules are used in the implementation of the hash table module, |
DCchico | 1:10330bce85cb | 71 | * but are not required by users of the hash table. |
DCchico | 1:10330bce85cb | 72 | ***************************************************************************/ |
DCchico | 1:10330bce85cb | 73 | #include <stdlib.h> // For malloc and free |
DCchico | 1:10330bce85cb | 74 | #include <stdio.h> // For printf |
kblake9 | 8:2e18a96e0c77 | 75 | |
kblake9 | 8:2e18a96e0c77 | 76 | |
DCchico | 1:10330bce85cb | 77 | /**************************************************************************** |
DCchico | 1:10330bce85cb | 78 | * Hidden Definitions |
DCchico | 1:10330bce85cb | 79 | * |
DCchico | 1:10330bce85cb | 80 | * These definitions are not available outside of this file. However, because |
DCchico | 1:10330bce85cb | 81 | * the are forward declared in hash_table.h, the type names are |
DCchico | 1:10330bce85cb | 82 | * available everywhere and user code can hold pointers to these structs. |
DCchico | 1:10330bce85cb | 83 | ***************************************************************************/ |
DCchico | 1:10330bce85cb | 84 | /** |
DCchico | 1:10330bce85cb | 85 | * This structure represents an a hash table. |
DCchico | 1:10330bce85cb | 86 | * Use "HashTable" instead when you are creating a new variable. [See top comments] |
DCchico | 1:10330bce85cb | 87 | */ |
DCchico | 1:10330bce85cb | 88 | struct _HashTable { |
DCchico | 1:10330bce85cb | 89 | /** The array of pointers to the head of a singly linked list, whose nodes |
DCchico | 1:10330bce85cb | 90 | are HashTableEntry objects */ |
DCchico | 1:10330bce85cb | 91 | HashTableEntry** buckets; |
kblake9 | 8:2e18a96e0c77 | 92 | |
DCchico | 1:10330bce85cb | 93 | /** The hash function pointer */ |
DCchico | 1:10330bce85cb | 94 | HashFunction hash; |
kblake9 | 8:2e18a96e0c77 | 95 | |
DCchico | 1:10330bce85cb | 96 | /** The number of buckets in the hash table */ |
DCchico | 1:10330bce85cb | 97 | unsigned int num_buckets; |
DCchico | 1:10330bce85cb | 98 | }; |
kblake9 | 8:2e18a96e0c77 | 99 | |
DCchico | 1:10330bce85cb | 100 | /** |
DCchico | 1:10330bce85cb | 101 | * This structure represents a hash table entry. |
DCchico | 1:10330bce85cb | 102 | * Use "HashTableEntry" instead when you are creating a new variable. [See top comments] |
DCchico | 1:10330bce85cb | 103 | */ |
DCchico | 1:10330bce85cb | 104 | struct _HashTableEntry { |
DCchico | 1:10330bce85cb | 105 | /** The key for the hash table entry */ |
DCchico | 1:10330bce85cb | 106 | unsigned int key; |
kblake9 | 8:2e18a96e0c77 | 107 | |
DCchico | 1:10330bce85cb | 108 | /** The value associated with this hash table entry */ |
DCchico | 1:10330bce85cb | 109 | void* value; |
kblake9 | 8:2e18a96e0c77 | 110 | |
DCchico | 1:10330bce85cb | 111 | /** |
DCchico | 1:10330bce85cb | 112 | * A pointer pointing to the next hash table entry |
DCchico | 1:10330bce85cb | 113 | * NULL means there is no next entry (i.e. this is the tail) |
DCchico | 1:10330bce85cb | 114 | */ |
DCchico | 1:10330bce85cb | 115 | HashTableEntry* next; |
DCchico | 1:10330bce85cb | 116 | }; |
kblake9 | 8:2e18a96e0c77 | 117 | |
kblake9 | 8:2e18a96e0c77 | 118 | |
DCchico | 1:10330bce85cb | 119 | /**************************************************************************** |
DCchico | 1:10330bce85cb | 120 | * Private Functions |
DCchico | 1:10330bce85cb | 121 | * |
DCchico | 1:10330bce85cb | 122 | * These functions are not available outside of this file, since they are not |
DCchico | 1:10330bce85cb | 123 | * declared in hash_table.h. |
DCchico | 1:10330bce85cb | 124 | ***************************************************************************/ |
DCchico | 1:10330bce85cb | 125 | /** |
DCchico | 1:10330bce85cb | 126 | * createHashTableEntry |
DCchico | 1:10330bce85cb | 127 | * |
DCchico | 1:10330bce85cb | 128 | * Helper function that creates a hash table entry by allocating memory for it on |
DCchico | 1:10330bce85cb | 129 | * the heap. It initializes the entry with key and value, initialize pointer to |
DCchico | 1:10330bce85cb | 130 | * the next entry as NULL, and return the pointer to this hash table entry. |
DCchico | 1:10330bce85cb | 131 | * |
DCchico | 1:10330bce85cb | 132 | * @param key The key corresponds to the hash table entry |
DCchico | 1:10330bce85cb | 133 | * @param value The value stored in the hash table entry |
DCchico | 1:10330bce85cb | 134 | * @return The pointer to the hash table entry |
DCchico | 1:10330bce85cb | 135 | */ |
DCchico | 1:10330bce85cb | 136 | static HashTableEntry* createHashTableEntry(unsigned int key, void* value) { |
kblake9 | 8:2e18a96e0c77 | 137 | //allocate memory for new hash table entry |
kblake9 | 8:2e18a96e0c77 | 138 | HashTableEntry* newHashTableEntry = (HashTableEntry*)malloc(sizeof(HashTableEntry)); |
kblake9 | 8:2e18a96e0c77 | 139 | |
kblake9 | 8:2e18a96e0c77 | 140 | //assign key var in struct to key parameter |
kblake9 | 8:2e18a96e0c77 | 141 | newHashTableEntry->key = key; |
kblake9 | 8:2e18a96e0c77 | 142 | //assign value var in struct to value parameter |
kblake9 | 8:2e18a96e0c77 | 143 | newHashTableEntry->value = value; |
kblake9 | 8:2e18a96e0c77 | 144 | //assign next var to default NULL |
kblake9 | 8:2e18a96e0c77 | 145 | newHashTableEntry->next = NULL; |
kblake9 | 8:2e18a96e0c77 | 146 | |
kblake9 | 8:2e18a96e0c77 | 147 | //return the new entry |
kblake9 | 8:2e18a96e0c77 | 148 | return newHashTableEntry; |
DCchico | 1:10330bce85cb | 149 | } |
kblake9 | 8:2e18a96e0c77 | 150 | |
DCchico | 1:10330bce85cb | 151 | /** |
DCchico | 1:10330bce85cb | 152 | * findItem |
DCchico | 1:10330bce85cb | 153 | * |
DCchico | 1:10330bce85cb | 154 | * Helper function that checks whether there exists the hash table entry that |
DCchico | 1:10330bce85cb | 155 | * contains a specific key. |
DCchico | 1:10330bce85cb | 156 | * |
DCchico | 1:10330bce85cb | 157 | * @param hashTable The pointer to the hash table. |
DCchico | 1:10330bce85cb | 158 | * @param key The key corresponds to the hash table entry |
DCchico | 1:10330bce85cb | 159 | * @return The pointer to the hash table entry, or NULL if key does not exist |
DCchico | 1:10330bce85cb | 160 | */ |
DCchico | 1:10330bce85cb | 161 | static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) { |
kblake9 | 8:2e18a96e0c77 | 162 | //check to make sure recieved valid hashTable |
kblake9 | 8:2e18a96e0c77 | 163 | if (hashTable != NULL) { |
kblake9 | 8:2e18a96e0c77 | 164 | //bucketNum variable to track what array space it takes up |
kblake9 | 8:2e18a96e0c77 | 165 | unsigned int bucketNum = hashTable->hash(key); |
kblake9 | 8:2e18a96e0c77 | 166 | //make sure the bucket exists |
kblake9 | 8:2e18a96e0c77 | 167 | if (hashTable->buckets[bucketNum] != NULL) { |
kblake9 | 8:2e18a96e0c77 | 168 | //currentEntry for tracking nested entries |
kblake9 | 8:2e18a96e0c77 | 169 | HashTableEntry* currentEntry = hashTable->buckets[bucketNum]; |
kblake9 | 8:2e18a96e0c77 | 170 | //while loop for nested search |
kblake9 | 8:2e18a96e0c77 | 171 | while (currentEntry->key != key && currentEntry->next != NULL) { |
kblake9 | 8:2e18a96e0c77 | 172 | currentEntry = currentEntry->next; |
kblake9 | 8:2e18a96e0c77 | 173 | } |
kblake9 | 8:2e18a96e0c77 | 174 | //did we find it? |
kblake9 | 8:2e18a96e0c77 | 175 | if (currentEntry-> key == key) { |
kblake9 | 8:2e18a96e0c77 | 176 | return currentEntry; |
kblake9 | 8:2e18a96e0c77 | 177 | } |
kblake9 | 8:2e18a96e0c77 | 178 | } |
kblake9 | 8:2e18a96e0c77 | 179 | } |
kblake9 | 8:2e18a96e0c77 | 180 | //otherwise return NULL |
kblake9 | 8:2e18a96e0c77 | 181 | return NULL; |
DCchico | 1:10330bce85cb | 182 | } |
kblake9 | 8:2e18a96e0c77 | 183 | |
DCchico | 1:10330bce85cb | 184 | /**************************************************************************** |
DCchico | 1:10330bce85cb | 185 | * Public Interface Functions |
DCchico | 1:10330bce85cb | 186 | * |
DCchico | 1:10330bce85cb | 187 | * These functions implement the public interface as specified in the header |
DCchico | 1:10330bce85cb | 188 | * file, and make use of the private functions and hidden definitions in the |
DCchico | 1:10330bce85cb | 189 | * above sections. |
DCchico | 1:10330bce85cb | 190 | ****************************************************************************/ |
DCchico | 1:10330bce85cb | 191 | // The createHashTable is provided for you as a starting point. |
DCchico | 1:10330bce85cb | 192 | HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) { |
DCchico | 1:10330bce85cb | 193 | // The hash table has to contain at least one bucket. Exit gracefully if |
DCchico | 1:10330bce85cb | 194 | // this condition is not met. |
DCchico | 1:10330bce85cb | 195 | if (numBuckets==0) { |
DCchico | 1:10330bce85cb | 196 | printf("Hash table has to contain at least 1 bucket...\n"); |
DCchico | 1:10330bce85cb | 197 | exit(1); |
DCchico | 1:10330bce85cb | 198 | } |
kblake9 | 8:2e18a96e0c77 | 199 | |
DCchico | 1:10330bce85cb | 200 | // Allocate memory for the new HashTable struct on heap. |
DCchico | 1:10330bce85cb | 201 | HashTable* newTable = (HashTable*)malloc(sizeof(HashTable)); |
kblake9 | 8:2e18a96e0c77 | 202 | |
DCchico | 1:10330bce85cb | 203 | // Initialize the components of the new HashTable struct. |
DCchico | 1:10330bce85cb | 204 | newTable->hash = hashFunction; |
DCchico | 1:10330bce85cb | 205 | newTable->num_buckets = numBuckets; |
DCchico | 1:10330bce85cb | 206 | newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*)); |
kblake9 | 8:2e18a96e0c77 | 207 | |
kblake9 | 8:2e18a96e0c77 | 208 | // As the new buckets contain indeterminant values, init each bucket as NULL. |
DCchico | 1:10330bce85cb | 209 | unsigned int i; |
DCchico | 1:10330bce85cb | 210 | for (i=0; i<numBuckets; ++i) { |
DCchico | 1:10330bce85cb | 211 | newTable->buckets[i] = NULL; |
DCchico | 1:10330bce85cb | 212 | } |
kblake9 | 8:2e18a96e0c77 | 213 | |
DCchico | 1:10330bce85cb | 214 | // Return the new HashTable struct. |
DCchico | 1:10330bce85cb | 215 | return newTable; |
DCchico | 1:10330bce85cb | 216 | } |
kblake9 | 8:2e18a96e0c77 | 217 | |
DCchico | 1:10330bce85cb | 218 | void destroyHashTable(HashTable* hashTable) { |
kblake9 | 8:2e18a96e0c77 | 219 | //make sure a hashtable exists to destroy |
kblake9 | 8:2e18a96e0c77 | 220 | if (hashTable != NULL) { |
kblake9 | 8:2e18a96e0c77 | 221 | unsigned int i; |
kblake9 | 8:2e18a96e0c77 | 222 | //search the buckets for entries to free |
kblake9 | 8:2e18a96e0c77 | 223 | for (i=0; i<hashTable->num_buckets; ++i) { |
kblake9 | 8:2e18a96e0c77 | 224 | if (hashTable->buckets[i] != NULL) { |
kblake9 | 8:2e18a96e0c77 | 225 | HashTableEntry* currentEntry = hashTable->buckets[i]; |
kblake9 | 8:2e18a96e0c77 | 226 | HashTableEntry* pastEntry; |
kblake9 | 8:2e18a96e0c77 | 227 | //get the nested entries as well |
kblake9 | 8:2e18a96e0c77 | 228 | while (currentEntry -> next != NULL) { |
kblake9 | 8:2e18a96e0c77 | 229 | pastEntry = currentEntry; |
kblake9 | 8:2e18a96e0c77 | 230 | currentEntry = currentEntry -> next; |
kblake9 | 8:2e18a96e0c77 | 231 | if (pastEntry -> value != NULL) { |
kblake9 | 8:2e18a96e0c77 | 232 | //freeee them |
kblake9 | 8:2e18a96e0c77 | 233 | free(pastEntry->value); |
kblake9 | 8:2e18a96e0c77 | 234 | pastEntry->value = NULL; |
kblake9 | 8:2e18a96e0c77 | 235 | } |
kblake9 | 8:2e18a96e0c77 | 236 | //free them all |
kblake9 | 8:2e18a96e0c77 | 237 | if (pastEntry != NULL) { |
kblake9 | 8:2e18a96e0c77 | 238 | free(pastEntry); |
kblake9 | 8:2e18a96e0c77 | 239 | pastEntry = NULL; |
kblake9 | 8:2e18a96e0c77 | 240 | } |
kblake9 | 8:2e18a96e0c77 | 241 | } |
kblake9 | 8:2e18a96e0c77 | 242 | if (currentEntry -> value != NULL) { |
kblake9 | 8:2e18a96e0c77 | 243 | //make sure you catch all those bad boys |
kblake9 | 8:2e18a96e0c77 | 244 | free(currentEntry->value); |
kblake9 | 8:2e18a96e0c77 | 245 | currentEntry->value = NULL; |
kblake9 | 8:2e18a96e0c77 | 246 | } |
kblake9 | 8:2e18a96e0c77 | 247 | //this catches the one the while loop ignores |
kblake9 | 8:2e18a96e0c77 | 248 | if (currentEntry != NULL) { |
kblake9 | 8:2e18a96e0c77 | 249 | free(currentEntry); |
kblake9 | 8:2e18a96e0c77 | 250 | currentEntry = NULL; |
kblake9 | 8:2e18a96e0c77 | 251 | } |
kblake9 | 8:2e18a96e0c77 | 252 | } |
kblake9 | 8:2e18a96e0c77 | 253 | } |
kblake9 | 8:2e18a96e0c77 | 254 | //see if theres anything in the buckets |
kblake9 | 8:2e18a96e0c77 | 255 | if (hashTable->buckets != NULL) { |
kblake9 | 8:2e18a96e0c77 | 256 | //empty the buckets |
kblake9 | 8:2e18a96e0c77 | 257 | free(hashTable->buckets); |
kblake9 | 8:2e18a96e0c77 | 258 | hashTable->buckets = NULL; |
kblake9 | 8:2e18a96e0c77 | 259 | } |
kblake9 | 8:2e18a96e0c77 | 260 | //double check that hashtable just to be safe before freeing |
kblake9 | 8:2e18a96e0c77 | 261 | if (hashTable != NULL) { |
kblake9 | 8:2e18a96e0c77 | 262 | free(hashTable); |
kblake9 | 8:2e18a96e0c77 | 263 | hashTable = NULL; |
kblake9 | 8:2e18a96e0c77 | 264 | } |
kblake9 | 8:2e18a96e0c77 | 265 | } |
DCchico | 1:10330bce85cb | 266 | } |
kblake9 | 8:2e18a96e0c77 | 267 | |
DCchico | 1:10330bce85cb | 268 | void* insertItem(HashTable* hashTable, unsigned int key, void* value) { |
kblake9 | 8:2e18a96e0c77 | 269 | //make sure a valid hashtable is provided |
kblake9 | 8:2e18a96e0c77 | 270 | if (hashTable == NULL) { |
kblake9 | 8:2e18a96e0c77 | 271 | return NULL; |
kblake9 | 8:2e18a96e0c77 | 272 | } |
kblake9 | 8:2e18a96e0c77 | 273 | //find what bucket this boys in |
kblake9 | 8:2e18a96e0c77 | 274 | unsigned int bucketNum = hashTable->hash(key); |
kblake9 | 8:2e18a96e0c77 | 275 | //create the entry for the boy |
kblake9 | 8:2e18a96e0c77 | 276 | HashTableEntry* hashTableEntry = createHashTableEntry(key, value); |
kblake9 | 8:2e18a96e0c77 | 277 | //checks if theres something already in the bucket |
kblake9 | 8:2e18a96e0c77 | 278 | if (hashTable->buckets[bucketNum] != NULL) { |
kblake9 | 8:2e18a96e0c77 | 279 | //are the keys the same? |
kblake9 | 8:2e18a96e0c77 | 280 | if (hashTable->buckets[bucketNum]->key == key) { |
kblake9 | 8:2e18a96e0c77 | 281 | //if so grab old value |
kblake9 | 8:2e18a96e0c77 | 282 | void* oldval = hashTable->buckets[bucketNum]->value; |
kblake9 | 8:2e18a96e0c77 | 283 | //free the old boy |
kblake9 | 8:2e18a96e0c77 | 284 | if (hashTable->buckets[bucketNum] != NULL) { |
kblake9 | 8:2e18a96e0c77 | 285 | free(hashTable->buckets[bucketNum]); |
kblake9 | 8:2e18a96e0c77 | 286 | } |
kblake9 | 8:2e18a96e0c77 | 287 | //overwrite |
kblake9 | 8:2e18a96e0c77 | 288 | hashTable->buckets[bucketNum] = hashTableEntry; |
kblake9 | 8:2e18a96e0c77 | 289 | //return old value |
kblake9 | 8:2e18a96e0c77 | 290 | return oldval; |
kblake9 | 8:2e18a96e0c77 | 291 | } else { |
kblake9 | 8:2e18a96e0c77 | 292 | //check for nested keys |
kblake9 | 8:2e18a96e0c77 | 293 | HashTableEntry* currentEntry = hashTable->buckets[bucketNum]; |
kblake9 | 8:2e18a96e0c77 | 294 | HashTableEntry* pastEntry; |
kblake9 | 8:2e18a96e0c77 | 295 | while(currentEntry->next !=NULL && currentEntry-> key != key){ |
kblake9 | 8:2e18a96e0c77 | 296 | //if there is another nested entry and the keys dont match keep cycling through the nested |
kblake9 | 8:2e18a96e0c77 | 297 | pastEntry = currentEntry; |
kblake9 | 8:2e18a96e0c77 | 298 | currentEntry = currentEntry->next; |
kblake9 | 8:2e18a96e0c77 | 299 | } |
kblake9 | 8:2e18a96e0c77 | 300 | //if the keys match take the old value replace it and return the old value |
kblake9 | 8:2e18a96e0c77 | 301 | if (currentEntry-> key == key) { |
kblake9 | 8:2e18a96e0c77 | 302 | void* oldval = currentEntry->value; |
kblake9 | 8:2e18a96e0c77 | 303 | if (hashTable->buckets[bucketNum] != NULL) { |
kblake9 | 8:2e18a96e0c77 | 304 | free(currentEntry); |
kblake9 | 8:2e18a96e0c77 | 305 | } |
kblake9 | 8:2e18a96e0c77 | 306 | //append to where old entry was |
kblake9 | 8:2e18a96e0c77 | 307 | pastEntry->next = hashTableEntry; |
kblake9 | 8:2e18a96e0c77 | 308 | return oldval; |
kblake9 | 8:2e18a96e0c77 | 309 | } |
kblake9 | 8:2e18a96e0c77 | 310 | //otherwise append to end of nested chain |
kblake9 | 8:2e18a96e0c77 | 311 | currentEntry->next = hashTableEntry; |
kblake9 | 8:2e18a96e0c77 | 312 | } |
kblake9 | 8:2e18a96e0c77 | 313 | } else { |
kblake9 | 8:2e18a96e0c77 | 314 | //if the bucket is uninhabited the boy now lives there |
kblake9 | 8:2e18a96e0c77 | 315 | hashTable->buckets[bucketNum] = hashTableEntry; |
kblake9 | 8:2e18a96e0c77 | 316 | } |
kblake9 | 8:2e18a96e0c77 | 317 | return NULL; |
DCchico | 1:10330bce85cb | 318 | } |
kblake9 | 8:2e18a96e0c77 | 319 | |
DCchico | 1:10330bce85cb | 320 | void* getItem(HashTable* hashTable, unsigned int key) { |
kblake9 | 8:2e18a96e0c77 | 321 | //make sure a valid hashtable was provided |
kblake9 | 8:2e18a96e0c77 | 322 | if (hashTable == NULL) { |
kblake9 | 8:2e18a96e0c77 | 323 | return NULL; |
kblake9 | 8:2e18a96e0c77 | 324 | } |
kblake9 | 8:2e18a96e0c77 | 325 | //find which bucket it is |
kblake9 | 8:2e18a96e0c77 | 326 | unsigned int bucketNum = hashTable -> hash(key); |
kblake9 | 8:2e18a96e0c77 | 327 | //make sure bucket isnt empty |
kblake9 | 8:2e18a96e0c77 | 328 | if (hashTable->buckets[bucketNum] == NULL) { |
kblake9 | 8:2e18a96e0c77 | 329 | return NULL; |
kblake9 | 8:2e18a96e0c77 | 330 | } else { |
kblake9 | 8:2e18a96e0c77 | 331 | //otherwise find the entry |
kblake9 | 8:2e18a96e0c77 | 332 | HashTableEntry* foundHashEntry = findItem(hashTable, key); |
kblake9 | 8:2e18a96e0c77 | 333 | //make sure entry is valid |
kblake9 | 8:2e18a96e0c77 | 334 | if (foundHashEntry != NULL) { |
kblake9 | 8:2e18a96e0c77 | 335 | //return entry |
kblake9 | 8:2e18a96e0c77 | 336 | return foundHashEntry->value; |
kblake9 | 8:2e18a96e0c77 | 337 | } |
kblake9 | 8:2e18a96e0c77 | 338 | return NULL; |
kblake9 | 8:2e18a96e0c77 | 339 | } |
DCchico | 1:10330bce85cb | 340 | } |
kblake9 | 8:2e18a96e0c77 | 341 | |
DCchico | 1:10330bce85cb | 342 | void* removeItem(HashTable* hashTable, unsigned int key) { |
kblake9 | 8:2e18a96e0c77 | 343 | //make sure valid hashtable is provided |
kblake9 | 8:2e18a96e0c77 | 344 | if (hashTable == NULL) { |
kblake9 | 8:2e18a96e0c77 | 345 | return NULL; |
kblake9 | 8:2e18a96e0c77 | 346 | } |
kblake9 | 8:2e18a96e0c77 | 347 | //initialize booleans to check for nesting conditions and bucket number |
kblake9 | 8:2e18a96e0c77 | 348 | unsigned int isNested = 0; |
kblake9 | 8:2e18a96e0c77 | 349 | unsigned int isntTail = 1; |
kblake9 | 8:2e18a96e0c77 | 350 | unsigned int bucketNum = hashTable->hash(key); |
kblake9 | 8:2e18a96e0c77 | 351 | //make sure bucket isnt empty |
kblake9 | 8:2e18a96e0c77 | 352 | if (hashTable->buckets[bucketNum] != NULL) { |
kblake9 | 8:2e18a96e0c77 | 353 | //define entries for nesting |
kblake9 | 8:2e18a96e0c77 | 354 | HashTableEntry* currentEntry = hashTable->buckets[bucketNum]; |
kblake9 | 8:2e18a96e0c77 | 355 | HashTableEntry* pastEntry; |
kblake9 | 8:2e18a96e0c77 | 356 | HashTableEntry* futureEntry; |
kblake9 | 8:2e18a96e0c77 | 357 | //check for nesting and update variables as needed |
kblake9 | 8:2e18a96e0c77 | 358 | while (currentEntry->next !=NULL && currentEntry->key !=key) { |
kblake9 | 8:2e18a96e0c77 | 359 | pastEntry = currentEntry; |
kblake9 | 8:2e18a96e0c77 | 360 | currentEntry = currentEntry->next; |
kblake9 | 8:2e18a96e0c77 | 361 | isNested = 1; |
kblake9 | 8:2e18a96e0c77 | 362 | if (currentEntry->next == NULL) { |
kblake9 | 8:2e18a96e0c77 | 363 | isntTail = 0; |
kblake9 | 8:2e18a96e0c77 | 364 | } else { |
kblake9 | 8:2e18a96e0c77 | 365 | futureEntry = currentEntry -> next; |
kblake9 | 8:2e18a96e0c77 | 366 | } |
kblake9 | 8:2e18a96e0c77 | 367 | } |
kblake9 | 8:2e18a96e0c77 | 368 | //make sure entry is valid |
kblake9 | 8:2e18a96e0c77 | 369 | if (currentEntry != NULL){ |
kblake9 | 8:2e18a96e0c77 | 370 | //check for sandwiched entry to be removed |
kblake9 | 8:2e18a96e0c77 | 371 | if (isNested == 1 && isntTail == 1) { |
kblake9 | 8:2e18a96e0c77 | 372 | pastEntry->next = futureEntry; |
kblake9 | 8:2e18a96e0c77 | 373 | //otherwise assume its the tail if its nested |
kblake9 | 8:2e18a96e0c77 | 374 | } else if (isNested == 1) { |
kblake9 | 8:2e18a96e0c77 | 375 | pastEntry->next = NULL; |
kblake9 | 8:2e18a96e0c77 | 376 | } |
kblake9 | 8:2e18a96e0c77 | 377 | //assign removed entry to return |
kblake9 | 8:2e18a96e0c77 | 378 | void* removedEntryVal = currentEntry->value; |
kblake9 | 8:2e18a96e0c77 | 379 | //double check for valid entry |
kblake9 | 8:2e18a96e0c77 | 380 | if (currentEntry != NULL) { |
kblake9 | 8:2e18a96e0c77 | 381 | //check whether it is only thing in bucket |
kblake9 | 8:2e18a96e0c77 | 382 | if (currentEntry->next !=NULL && isNested == 0) { |
kblake9 | 8:2e18a96e0c77 | 383 | futureEntry = currentEntry->next; |
kblake9 | 8:2e18a96e0c77 | 384 | hashTable->buckets[bucketNum] = futureEntry; |
kblake9 | 8:2e18a96e0c77 | 385 | } else if (isntTail == 1 && isNested == 0) { |
kblake9 | 8:2e18a96e0c77 | 386 | hashTable->buckets[bucketNum] = NULL; |
kblake9 | 8:2e18a96e0c77 | 387 | } |
kblake9 | 8:2e18a96e0c77 | 388 | //free removed entry |
kblake9 | 8:2e18a96e0c77 | 389 | free(currentEntry); |
kblake9 | 8:2e18a96e0c77 | 390 | currentEntry = NULL; |
kblake9 | 8:2e18a96e0c77 | 391 | } |
kblake9 | 8:2e18a96e0c77 | 392 | //return the entry |
kblake9 | 8:2e18a96e0c77 | 393 | return removedEntryVal; |
kblake9 | 8:2e18a96e0c77 | 394 | } |
kblake9 | 8:2e18a96e0c77 | 395 | } |
kblake9 | 8:2e18a96e0c77 | 396 | return NULL; |
DCchico | 1:10330bce85cb | 397 | } |
kblake9 | 8:2e18a96e0c77 | 398 | |
DCchico | 1:10330bce85cb | 399 | void deleteItem(HashTable* hashTable, unsigned int key) { |
kblake9 | 8:2e18a96e0c77 | 400 | if (hashTable == NULL) { |
kblake9 | 8:2e18a96e0c77 | 401 | printf("Hash table doesn't exist.\n"); |
kblake9 | 8:2e18a96e0c77 | 402 | exit(1); |
kblake9 | 8:2e18a96e0c77 | 403 | } |
kblake9 | 8:2e18a96e0c77 | 404 | //initialize booleans to check for nesting conditions and bucket number |
kblake9 | 8:2e18a96e0c77 | 405 | unsigned int isNested = 0; |
kblake9 | 8:2e18a96e0c77 | 406 | unsigned int isntTail = 1; |
kblake9 | 8:2e18a96e0c77 | 407 | unsigned int bucketNum = hashTable->hash(key); |
kblake9 | 8:2e18a96e0c77 | 408 | //make sure bucket isnt empty |
kblake9 | 8:2e18a96e0c77 | 409 | if (hashTable->buckets[bucketNum] != NULL) { |
kblake9 | 8:2e18a96e0c77 | 410 | //define entries for nesting |
kblake9 | 8:2e18a96e0c77 | 411 | HashTableEntry* currentEntry = hashTable->buckets[bucketNum]; |
kblake9 | 8:2e18a96e0c77 | 412 | HashTableEntry* pastEntry; |
kblake9 | 8:2e18a96e0c77 | 413 | HashTableEntry* futureEntry; |
kblake9 | 8:2e18a96e0c77 | 414 | //check for nesting and update variables as needed |
kblake9 | 8:2e18a96e0c77 | 415 | while (currentEntry->next !=NULL && currentEntry->key !=key) { |
kblake9 | 8:2e18a96e0c77 | 416 | pastEntry = currentEntry; |
kblake9 | 8:2e18a96e0c77 | 417 | currentEntry = currentEntry->next; |
kblake9 | 8:2e18a96e0c77 | 418 | isNested = 1; |
kblake9 | 8:2e18a96e0c77 | 419 | if (currentEntry->next == NULL) { |
kblake9 | 8:2e18a96e0c77 | 420 | isntTail = 0; |
kblake9 | 8:2e18a96e0c77 | 421 | } else { |
kblake9 | 8:2e18a96e0c77 | 422 | futureEntry = currentEntry -> next; |
kblake9 | 8:2e18a96e0c77 | 423 | } |
kblake9 | 8:2e18a96e0c77 | 424 | } |
kblake9 | 8:2e18a96e0c77 | 425 | //make sure entry is valid |
kblake9 | 8:2e18a96e0c77 | 426 | if (currentEntry != NULL){ |
kblake9 | 8:2e18a96e0c77 | 427 | //check for sandwiched entry to be removed |
kblake9 | 8:2e18a96e0c77 | 428 | if (isNested == 1 && isntTail == 1) { |
kblake9 | 8:2e18a96e0c77 | 429 | pastEntry->next = futureEntry; |
kblake9 | 8:2e18a96e0c77 | 430 | //otherwise assume its the tail if its nested |
kblake9 | 8:2e18a96e0c77 | 431 | } else if (isNested == 1) { |
kblake9 | 8:2e18a96e0c77 | 432 | pastEntry->next = NULL; |
kblake9 | 8:2e18a96e0c77 | 433 | } |
kblake9 | 8:2e18a96e0c77 | 434 | //double check for valid entry |
kblake9 | 8:2e18a96e0c77 | 435 | if (currentEntry != NULL) { |
kblake9 | 8:2e18a96e0c77 | 436 | //check whether it is only thing in bucket |
kblake9 | 8:2e18a96e0c77 | 437 | if (currentEntry->next !=NULL && isNested == 0) { |
kblake9 | 8:2e18a96e0c77 | 438 | futureEntry = currentEntry->next; |
kblake9 | 8:2e18a96e0c77 | 439 | hashTable->buckets[bucketNum] = futureEntry; |
kblake9 | 8:2e18a96e0c77 | 440 | } else if (isntTail == 1 && isNested == 0) { |
kblake9 | 8:2e18a96e0c77 | 441 | hashTable->buckets[bucketNum] = NULL; |
kblake9 | 8:2e18a96e0c77 | 442 | } |
kblake9 | 8:2e18a96e0c77 | 443 | if (currentEntry -> value != NULL) { |
kblake9 | 8:2e18a96e0c77 | 444 | //free value |
kblake9 | 8:2e18a96e0c77 | 445 | free(currentEntry->value); |
kblake9 | 8:2e18a96e0c77 | 446 | currentEntry->value = NULL; |
kblake9 | 8:2e18a96e0c77 | 447 | } |
kblake9 | 8:2e18a96e0c77 | 448 | //free removed entry |
kblake9 | 8:2e18a96e0c77 | 449 | free(currentEntry); |
kblake9 | 8:2e18a96e0c77 | 450 | currentEntry = NULL; |
kblake9 | 8:2e18a96e0c77 | 451 | } |
kblake9 | 8:2e18a96e0c77 | 452 | } |
kblake9 | 8:2e18a96e0c77 | 453 | } |
kblake9 | 8:2e18a96e0c77 | 454 | } |