Still won't work
Dependencies: mbed wave_player 4DGL-uLCD-SE MMA8452
hash_table.cpp@5:142e66c8a7fa, 2019-04-12 (annotated)
- Committer:
- jtrux
- Date:
- Fri Apr 12 18:42:43 2019 +0000
- Revision:
- 5:142e66c8a7fa
- Parent:
- 2:7ae1e676b120
Still won't work;
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
rconnorlawson | 0:35660d7952f7 | 1 | /* |
jtrux | 2:7ae1e676b120 | 2 | Student Name: Jaden Truxal |
jtrux | 2:7ae1e676b120 | 3 | Date: 3.23.19 |
jtrux | 2:7ae1e676b120 | 4 | valgrind --leak-check=full ./ht_tests |
rconnorlawson | 0:35660d7952f7 | 5 | |
rconnorlawson | 0:35660d7952f7 | 6 | ======================= |
rconnorlawson | 0:35660d7952f7 | 7 | ECE 2035 Project 2-1: |
rconnorlawson | 0:35660d7952f7 | 8 | ======================= |
rconnorlawson | 0:35660d7952f7 | 9 | This file provides definition for the structs and functions declared in the |
rconnorlawson | 0:35660d7952f7 | 10 | header file. It also contains helper functions that are not accessible from |
rconnorlawson | 0:35660d7952f7 | 11 | outside of the file. |
rconnorlawson | 0:35660d7952f7 | 12 | |
rconnorlawson | 0:35660d7952f7 | 13 | FOR FULL CREDIT, BE SURE TO TRY MULTIPLE TEST CASES and DOCUMENT YOUR CODE. |
rconnorlawson | 0:35660d7952f7 | 14 | |
rconnorlawson | 0:35660d7952f7 | 15 | =================================== |
rconnorlawson | 0:35660d7952f7 | 16 | Naming conventions in this file: |
rconnorlawson | 0:35660d7952f7 | 17 | =================================== |
rconnorlawson | 0:35660d7952f7 | 18 | 1. All struct names use camel case where the first letter is capitalized. |
rconnorlawson | 0:35660d7952f7 | 19 | e.g. "HashTable", or "HashTableEntry" |
rconnorlawson | 0:35660d7952f7 | 20 | |
rconnorlawson | 0:35660d7952f7 | 21 | 2. Variable names with a preceding underscore "_" will not be called directly. |
rconnorlawson | 0:35660d7952f7 | 22 | e.g. "_HashTable", "_HashTableEntry" |
rconnorlawson | 0:35660d7952f7 | 23 | |
rconnorlawson | 0:35660d7952f7 | 24 | Recall that in C, we have to type "struct" together with the name of the struct |
rconnorlawson | 0:35660d7952f7 | 25 | in order to initialize a new variable. To avoid this, in hash_table.h |
rconnorlawson | 0:35660d7952f7 | 26 | we use typedef to provide new "nicknames" for "struct _HashTable" and |
rconnorlawson | 0:35660d7952f7 | 27 | "struct _HashTableEntry". As a result, we can create new struct variables |
rconnorlawson | 0:35660d7952f7 | 28 | by just using: |
rconnorlawson | 0:35660d7952f7 | 29 | - "HashTable myNewTable;" |
rconnorlawson | 0:35660d7952f7 | 30 | or |
rconnorlawson | 0:35660d7952f7 | 31 | - "HashTableEntry myNewHashTableEntry;" |
rconnorlawson | 0:35660d7952f7 | 32 | |
rconnorlawson | 0:35660d7952f7 | 33 | The preceding underscore "_" simply provides a distinction between the names |
rconnorlawson | 0:35660d7952f7 | 34 | of the actual struct defition and the "nicknames" that we use to initialize |
rconnorlawson | 0:35660d7952f7 | 35 | new structs. |
rconnorlawson | 0:35660d7952f7 | 36 | [See Hidden Definitions section for more information.] |
rconnorlawson | 0:35660d7952f7 | 37 | |
rconnorlawson | 0:35660d7952f7 | 38 | 3. Functions, their local variables and arguments are named with camel case, where |
rconnorlawson | 0:35660d7952f7 | 39 | the first letter is lower-case. |
rconnorlawson | 0:35660d7952f7 | 40 | e.g. "createHashTable" is a function. One of its arguments is "numBuckets". |
rconnorlawson | 0:35660d7952f7 | 41 | It also has a local variable called "newTable". |
rconnorlawson | 0:35660d7952f7 | 42 | |
rconnorlawson | 0:35660d7952f7 | 43 | 4. The name of a struct member is divided by using underscores "_". This serves |
rconnorlawson | 0:35660d7952f7 | 44 | as a distinction between function local variables and struct members. |
rconnorlawson | 0:35660d7952f7 | 45 | e.g. "num_buckets" is a member of "HashTable". |
rconnorlawson | 0:35660d7952f7 | 46 | |
rconnorlawson | 0:35660d7952f7 | 47 | */ |
rconnorlawson | 0:35660d7952f7 | 48 | |
rconnorlawson | 0:35660d7952f7 | 49 | /**************************************************************************** |
rconnorlawson | 0:35660d7952f7 | 50 | * Include the Public Interface |
rconnorlawson | 0:35660d7952f7 | 51 | * |
rconnorlawson | 0:35660d7952f7 | 52 | * By including the public interface at the top of the file, the compiler can |
rconnorlawson | 0:35660d7952f7 | 53 | * enforce that the function declarations in the the header are not in |
rconnorlawson | 0:35660d7952f7 | 54 | * conflict with the definitions in the file. This is not a guarantee of |
rconnorlawson | 0:35660d7952f7 | 55 | * correctness, but it is better than nothing! |
rconnorlawson | 0:35660d7952f7 | 56 | ***************************************************************************/ |
rconnorlawson | 0:35660d7952f7 | 57 | #include "hash_table.h" |
rconnorlawson | 0:35660d7952f7 | 58 | |
rconnorlawson | 0:35660d7952f7 | 59 | |
rconnorlawson | 0:35660d7952f7 | 60 | /**************************************************************************** |
rconnorlawson | 0:35660d7952f7 | 61 | * Include other private dependencies |
rconnorlawson | 0:35660d7952f7 | 62 | * |
rconnorlawson | 0:35660d7952f7 | 63 | * These other modules are used in the implementation of the hash table module, |
rconnorlawson | 0:35660d7952f7 | 64 | * but are not required by users of the hash table. |
rconnorlawson | 0:35660d7952f7 | 65 | ***************************************************************************/ |
rconnorlawson | 0:35660d7952f7 | 66 | #include <stdlib.h> // For malloc and free |
rconnorlawson | 0:35660d7952f7 | 67 | #include <stdio.h> // For printf |
rconnorlawson | 0:35660d7952f7 | 68 | |
rconnorlawson | 0:35660d7952f7 | 69 | |
rconnorlawson | 0:35660d7952f7 | 70 | /**************************************************************************** |
rconnorlawson | 0:35660d7952f7 | 71 | * Hidden Definitions |
rconnorlawson | 0:35660d7952f7 | 72 | * |
rconnorlawson | 0:35660d7952f7 | 73 | * These definitions are not available outside of this file. However, because |
rconnorlawson | 0:35660d7952f7 | 74 | * the are forward declared in hash_table.h, the type names are |
rconnorlawson | 0:35660d7952f7 | 75 | * available everywhere and user code can hold pointers to these structs. |
rconnorlawson | 0:35660d7952f7 | 76 | ***************************************************************************/ |
rconnorlawson | 0:35660d7952f7 | 77 | /** |
rconnorlawson | 0:35660d7952f7 | 78 | * This structure represents an a hash table. |
rconnorlawson | 0:35660d7952f7 | 79 | * Use "HashTable" instead when you are creating a new variable. [See top comments] |
rconnorlawson | 0:35660d7952f7 | 80 | */ |
rconnorlawson | 0:35660d7952f7 | 81 | struct _HashTable { |
rconnorlawson | 0:35660d7952f7 | 82 | /** The array of pointers to the head of a singly linked list, whose nodes |
rconnorlawson | 0:35660d7952f7 | 83 | are HashTableEntry objects */ |
rconnorlawson | 0:35660d7952f7 | 84 | HashTableEntry** buckets; |
rconnorlawson | 0:35660d7952f7 | 85 | |
rconnorlawson | 0:35660d7952f7 | 86 | /** The hash function pointer */ |
rconnorlawson | 0:35660d7952f7 | 87 | HashFunction hash; |
rconnorlawson | 0:35660d7952f7 | 88 | |
rconnorlawson | 0:35660d7952f7 | 89 | /** The number of buckets in the hash table */ |
rconnorlawson | 0:35660d7952f7 | 90 | unsigned int num_buckets; |
rconnorlawson | 0:35660d7952f7 | 91 | }; |
rconnorlawson | 0:35660d7952f7 | 92 | |
rconnorlawson | 0:35660d7952f7 | 93 | /** |
rconnorlawson | 0:35660d7952f7 | 94 | * This structure represents a hash table entry. |
rconnorlawson | 0:35660d7952f7 | 95 | * Use "HashTableEntry" instead when you are creating a new variable. [See top comments] |
rconnorlawson | 0:35660d7952f7 | 96 | */ |
rconnorlawson | 0:35660d7952f7 | 97 | struct _HashTableEntry { |
rconnorlawson | 0:35660d7952f7 | 98 | /** The key for the hash table entry */ |
rconnorlawson | 0:35660d7952f7 | 99 | unsigned int key; |
rconnorlawson | 0:35660d7952f7 | 100 | |
rconnorlawson | 0:35660d7952f7 | 101 | /** The value associated with this hash table entry */ |
rconnorlawson | 0:35660d7952f7 | 102 | void* value; |
rconnorlawson | 0:35660d7952f7 | 103 | |
rconnorlawson | 0:35660d7952f7 | 104 | /** |
rconnorlawson | 0:35660d7952f7 | 105 | * A pointer pointing to the next hash table entry |
rconnorlawson | 0:35660d7952f7 | 106 | * NULL means there is no next entry (i.e. this is the tail) |
rconnorlawson | 0:35660d7952f7 | 107 | */ |
rconnorlawson | 0:35660d7952f7 | 108 | HashTableEntry* next; |
rconnorlawson | 0:35660d7952f7 | 109 | }; |
rconnorlawson | 0:35660d7952f7 | 110 | |
rconnorlawson | 0:35660d7952f7 | 111 | |
rconnorlawson | 0:35660d7952f7 | 112 | /**************************************************************************** |
rconnorlawson | 0:35660d7952f7 | 113 | * Private Functions |
rconnorlawson | 0:35660d7952f7 | 114 | * |
rconnorlawson | 0:35660d7952f7 | 115 | * These functions are not available outside of this file, since they are not |
rconnorlawson | 0:35660d7952f7 | 116 | * declared in hash_table.h. |
rconnorlawson | 0:35660d7952f7 | 117 | ***************************************************************************/ |
rconnorlawson | 0:35660d7952f7 | 118 | /** |
rconnorlawson | 0:35660d7952f7 | 119 | * createHashTableEntry |
rconnorlawson | 0:35660d7952f7 | 120 | * |
rconnorlawson | 0:35660d7952f7 | 121 | * Helper function that creates a hash table entry by allocating memory for it on |
rconnorlawson | 0:35660d7952f7 | 122 | * the heap. It initializes the entry with key and value, initialize pointer to |
rconnorlawson | 0:35660d7952f7 | 123 | * the next entry as NULL, and return the pointer to this hash table entry. |
rconnorlawson | 0:35660d7952f7 | 124 | * |
rconnorlawson | 0:35660d7952f7 | 125 | * @param key The key corresponds to the hash table entry |
rconnorlawson | 0:35660d7952f7 | 126 | * @param value The value stored in the hash table entry |
rconnorlawson | 0:35660d7952f7 | 127 | * @return The pointer to the hash table entry |
rconnorlawson | 0:35660d7952f7 | 128 | */ |
rconnorlawson | 0:35660d7952f7 | 129 | static HashTableEntry* createHashTableEntry(unsigned int key, void* value) { |
rconnorlawson | 0:35660d7952f7 | 130 | |
jtrux | 2:7ae1e676b120 | 131 | //makes a new hashtable entry with a certain key, value and sets the next value to NULL |
jtrux | 2:7ae1e676b120 | 132 | HashTableEntry* htEntry = (HashTableEntry*)malloc(sizeof(HashTableEntry)); |
jtrux | 2:7ae1e676b120 | 133 | if (!htEntry) |
jtrux | 2:7ae1e676b120 | 134 | return NULL; |
jtrux | 2:7ae1e676b120 | 135 | htEntry->key = key; |
jtrux | 2:7ae1e676b120 | 136 | htEntry->value = value; |
jtrux | 2:7ae1e676b120 | 137 | htEntry->next = NULL; |
jtrux | 2:7ae1e676b120 | 138 | |
jtrux | 2:7ae1e676b120 | 139 | return htEntry; |
jtrux | 2:7ae1e676b120 | 140 | |
rconnorlawson | 0:35660d7952f7 | 141 | } |
rconnorlawson | 0:35660d7952f7 | 142 | |
rconnorlawson | 0:35660d7952f7 | 143 | /** |
rconnorlawson | 0:35660d7952f7 | 144 | * findItem |
rconnorlawson | 0:35660d7952f7 | 145 | * |
rconnorlawson | 0:35660d7952f7 | 146 | * Helper function that checks whether there exists the hash table entry that |
rconnorlawson | 0:35660d7952f7 | 147 | * contains a specific key. |
rconnorlawson | 0:35660d7952f7 | 148 | * |
rconnorlawson | 0:35660d7952f7 | 149 | * @param hashTable The pointer to the hash table. |
rconnorlawson | 0:35660d7952f7 | 150 | * @param key The key corresponds to the hash table entry |
rconnorlawson | 0:35660d7952f7 | 151 | * @return The pointer to the hash table entry, or NULL if key does not exist |
rconnorlawson | 0:35660d7952f7 | 152 | */ |
rconnorlawson | 0:35660d7952f7 | 153 | static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) { |
jtrux | 2:7ae1e676b120 | 154 | //finds an item in the hashtable using the key provided, if the item isn't in the hashtable, |
jtrux | 2:7ae1e676b120 | 155 | int index = hashTable->hash(key); |
jtrux | 2:7ae1e676b120 | 156 | HashTableEntry* htEntry = hashTable->buckets[index]; |
jtrux | 2:7ae1e676b120 | 157 | while(htEntry != NULL){ |
jtrux | 2:7ae1e676b120 | 158 | if(htEntry->key == key){ |
jtrux | 2:7ae1e676b120 | 159 | return htEntry; |
jtrux | 2:7ae1e676b120 | 160 | } |
jtrux | 2:7ae1e676b120 | 161 | htEntry = htEntry->next; |
jtrux | 2:7ae1e676b120 | 162 | } |
jtrux | 2:7ae1e676b120 | 163 | return NULL; |
rconnorlawson | 0:35660d7952f7 | 164 | } |
rconnorlawson | 0:35660d7952f7 | 165 | |
rconnorlawson | 0:35660d7952f7 | 166 | /**************************************************************************** |
rconnorlawson | 0:35660d7952f7 | 167 | * Public Interface Functions |
rconnorlawson | 0:35660d7952f7 | 168 | * |
rconnorlawson | 0:35660d7952f7 | 169 | * These functions implement the public interface as specified in the header |
rconnorlawson | 0:35660d7952f7 | 170 | * file, and make use of the private functions and hidden definitions in the |
rconnorlawson | 0:35660d7952f7 | 171 | * above sections. |
rconnorlawson | 0:35660d7952f7 | 172 | ****************************************************************************/ |
rconnorlawson | 0:35660d7952f7 | 173 | // The createHashTable is provided for you as a starting point. |
rconnorlawson | 0:35660d7952f7 | 174 | HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) { |
rconnorlawson | 0:35660d7952f7 | 175 | // The hash table has to contain at least one bucket. Exit gracefully if |
rconnorlawson | 0:35660d7952f7 | 176 | // this condition is not met. |
rconnorlawson | 0:35660d7952f7 | 177 | if (numBuckets==0) { |
rconnorlawson | 0:35660d7952f7 | 178 | printf("Hash table has to contain at least 1 bucket...\n"); |
rconnorlawson | 0:35660d7952f7 | 179 | exit(1); |
rconnorlawson | 0:35660d7952f7 | 180 | } |
rconnorlawson | 0:35660d7952f7 | 181 | |
rconnorlawson | 0:35660d7952f7 | 182 | // Allocate memory for the new HashTable struct on heap. |
rconnorlawson | 0:35660d7952f7 | 183 | HashTable* newTable = (HashTable*)malloc(sizeof(HashTable)); |
rconnorlawson | 0:35660d7952f7 | 184 | |
rconnorlawson | 0:35660d7952f7 | 185 | // Initialize the components of the new HashTable struct. |
rconnorlawson | 0:35660d7952f7 | 186 | newTable->hash = hashFunction; |
rconnorlawson | 0:35660d7952f7 | 187 | newTable->num_buckets = numBuckets; |
rconnorlawson | 0:35660d7952f7 | 188 | newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*)); |
rconnorlawson | 0:35660d7952f7 | 189 | |
jtrux | 2:7ae1e676b120 | 190 | // As the new buckets contain indeterminant values, init each bucket as NULL. |
rconnorlawson | 0:35660d7952f7 | 191 | unsigned int i; |
rconnorlawson | 0:35660d7952f7 | 192 | for (i=0; i<numBuckets; ++i) { |
rconnorlawson | 0:35660d7952f7 | 193 | newTable->buckets[i] = NULL; |
rconnorlawson | 0:35660d7952f7 | 194 | } |
rconnorlawson | 0:35660d7952f7 | 195 | |
rconnorlawson | 0:35660d7952f7 | 196 | // Return the new HashTable struct. |
rconnorlawson | 0:35660d7952f7 | 197 | return newTable; |
rconnorlawson | 0:35660d7952f7 | 198 | } |
rconnorlawson | 0:35660d7952f7 | 199 | |
jtrux | 2:7ae1e676b120 | 200 | |
jtrux | 2:7ae1e676b120 | 201 | |
jtrux | 2:7ae1e676b120 | 202 | |
jtrux | 2:7ae1e676b120 | 203 | |
jtrux | 2:7ae1e676b120 | 204 | |
jtrux | 2:7ae1e676b120 | 205 | |
rconnorlawson | 0:35660d7952f7 | 206 | |
jtrux | 2:7ae1e676b120 | 207 | void destroyHashTable(HashTable* hashTable) { |
jtrux | 2:7ae1e676b120 | 208 | //checks to make sure the hashtable has something in it |
jtrux | 2:7ae1e676b120 | 209 | if (hashTable == NULL){ |
jtrux | 2:7ae1e676b120 | 210 | printf("Invalid Hash Table."); |
jtrux | 2:7ae1e676b120 | 211 | } |
jtrux | 2:7ae1e676b120 | 212 | //Goes through each bucket, freeing each value in each node and then the |
jtrux | 2:7ae1e676b120 | 213 | //node itself. After, it frees the buckets and the hashtable ptr itself |
jtrux | 2:7ae1e676b120 | 214 | HashTableEntry* next; |
jtrux | 2:7ae1e676b120 | 215 | int i; |
jtrux | 2:7ae1e676b120 | 216 | for(i = 0;i < hashTable->num_buckets; i++){ |
jtrux | 2:7ae1e676b120 | 217 | HashTableEntry* htEntry = hashTable->buckets[i]; |
jtrux | 2:7ae1e676b120 | 218 | while(htEntry != NULL){ |
jtrux | 2:7ae1e676b120 | 219 | next = htEntry->next; |
jtrux | 2:7ae1e676b120 | 220 | //free node's value and ptr to node |
jtrux | 2:7ae1e676b120 | 221 | free(htEntry->value); |
jtrux | 2:7ae1e676b120 | 222 | free(htEntry); |
jtrux | 2:7ae1e676b120 | 223 | htEntry = next; |
jtrux | 2:7ae1e676b120 | 224 | } |
jtrux | 2:7ae1e676b120 | 225 | } |
jtrux | 2:7ae1e676b120 | 226 | free(hashTable->buckets); |
jtrux | 2:7ae1e676b120 | 227 | free(hashTable); |
rconnorlawson | 0:35660d7952f7 | 228 | |
rconnorlawson | 0:35660d7952f7 | 229 | } |
rconnorlawson | 0:35660d7952f7 | 230 | |
jtrux | 2:7ae1e676b120 | 231 | |
jtrux | 2:7ae1e676b120 | 232 | |
jtrux | 2:7ae1e676b120 | 233 | |
jtrux | 2:7ae1e676b120 | 234 | |
jtrux | 2:7ae1e676b120 | 235 | |
jtrux | 2:7ae1e676b120 | 236 | |
rconnorlawson | 0:35660d7952f7 | 237 | |
jtrux | 2:7ae1e676b120 | 238 | void* insertItem(HashTable* hashTable, unsigned int key, void* value) { |
jtrux | 2:7ae1e676b120 | 239 | int found = 0; |
jtrux | 2:7ae1e676b120 | 240 | void* retval = NULL; |
jtrux | 2:7ae1e676b120 | 241 | int index = hashTable->hash(key); |
jtrux | 2:7ae1e676b120 | 242 | //Test for a Null Hash Table |
jtrux | 2:7ae1e676b120 | 243 | if (hashTable == NULL){ |
jtrux | 2:7ae1e676b120 | 244 | printf("Invalid Hash Table."); |
jtrux | 2:7ae1e676b120 | 245 | return NULL; |
jtrux | 2:7ae1e676b120 | 246 | } |
jtrux | 2:7ae1e676b120 | 247 | else{ |
jtrux | 2:7ae1e676b120 | 248 | //See if value is in the list. if value is in the list, return the node's old value |
jtrux | 2:7ae1e676b120 | 249 | //and replace it with the new value that's read in |
jtrux | 2:7ae1e676b120 | 250 | HashTableEntry* htEntry; |
jtrux | 2:7ae1e676b120 | 251 | if((htEntry = findItem(hashTable, key))){ |
jtrux | 2:7ae1e676b120 | 252 | found = 1; |
jtrux | 2:7ae1e676b120 | 253 | retval = htEntry->value; |
jtrux | 2:7ae1e676b120 | 254 | htEntry->value = value; |
jtrux | 2:7ae1e676b120 | 255 | } |
jtrux | 2:7ae1e676b120 | 256 | |
jtrux | 2:7ae1e676b120 | 257 | |
jtrux | 2:7ae1e676b120 | 258 | |
jtrux | 2:7ae1e676b120 | 259 | //If entry wasn't found, create a new hash table entry for list |
jtrux | 2:7ae1e676b120 | 260 | //and put it at beginning of list. |
jtrux | 2:7ae1e676b120 | 261 | if (!found){ |
jtrux | 2:7ae1e676b120 | 262 | HashTableEntry* newHtEntry = createHashTableEntry(key, value); |
jtrux | 2:7ae1e676b120 | 263 | |
jtrux | 2:7ae1e676b120 | 264 | //If the llist isn't empty insert it at the beginning |
jtrux | 2:7ae1e676b120 | 265 | if(hashTable->buckets[index]){ |
jtrux | 2:7ae1e676b120 | 266 | newHtEntry->next = hashTable->buckets[index]; |
jtrux | 2:7ae1e676b120 | 267 | } |
jtrux | 2:7ae1e676b120 | 268 | //point the bucket ptr to the head of the new hashtable entry |
jtrux | 2:7ae1e676b120 | 269 | hashTable->buckets[index] = newHtEntry; |
jtrux | 2:7ae1e676b120 | 270 | retval = NULL; |
jtrux | 2:7ae1e676b120 | 271 | |
jtrux | 2:7ae1e676b120 | 272 | } |
rconnorlawson | 0:35660d7952f7 | 273 | } |
jtrux | 2:7ae1e676b120 | 274 | return retval; |
jtrux | 2:7ae1e676b120 | 275 | } |
rconnorlawson | 0:35660d7952f7 | 276 | |
jtrux | 2:7ae1e676b120 | 277 | |
jtrux | 2:7ae1e676b120 | 278 | |
jtrux | 2:7ae1e676b120 | 279 | |
jtrux | 2:7ae1e676b120 | 280 | |
jtrux | 2:7ae1e676b120 | 281 | |
jtrux | 2:7ae1e676b120 | 282 | |
jtrux | 2:7ae1e676b120 | 283 | |
jtrux | 2:7ae1e676b120 | 284 | |
jtrux | 2:7ae1e676b120 | 285 | |
jtrux | 2:7ae1e676b120 | 286 | |
jtrux | 2:7ae1e676b120 | 287 | |
jtrux | 2:7ae1e676b120 | 288 | |
jtrux | 2:7ae1e676b120 | 289 | |
rconnorlawson | 0:35660d7952f7 | 290 | |
jtrux | 2:7ae1e676b120 | 291 | |
jtrux | 2:7ae1e676b120 | 292 | |
jtrux | 2:7ae1e676b120 | 293 | void* removeItem(HashTable* hashTable, unsigned int key) { |
jtrux | 2:7ae1e676b120 | 294 | void* retval = NULL; |
jtrux | 2:7ae1e676b120 | 295 | //Test for a Null Hash Table |
jtrux | 2:7ae1e676b120 | 296 | if (hashTable == NULL){ |
jtrux | 2:7ae1e676b120 | 297 | printf("Invalid Hash Table."); |
jtrux | 2:7ae1e676b120 | 298 | return NULL; |
jtrux | 2:7ae1e676b120 | 299 | } |
jtrux | 2:7ae1e676b120 | 300 | else{ |
jtrux | 2:7ae1e676b120 | 301 | |
jtrux | 2:7ae1e676b120 | 302 | int index = hashTable->hash(key); |
jtrux | 2:7ae1e676b120 | 303 | //if the item is found, return the value of it, set the |
jtrux | 2:7ae1e676b120 | 304 | HashTableEntry* htEntry = hashTable->buckets[index]; |
jtrux | 2:7ae1e676b120 | 305 | if(htEntry == NULL){ |
jtrux | 2:7ae1e676b120 | 306 | return NULL; |
jtrux | 2:7ae1e676b120 | 307 | } |
jtrux | 2:7ae1e676b120 | 308 | else{ |
jtrux | 2:7ae1e676b120 | 309 | if(htEntry->key == key){ |
jtrux | 2:7ae1e676b120 | 310 | retval = htEntry->value; |
jtrux | 2:7ae1e676b120 | 311 | if(htEntry->next){ |
jtrux | 2:7ae1e676b120 | 312 | hashTable->buckets[index] = htEntry->next; |
jtrux | 2:7ae1e676b120 | 313 | } |
jtrux | 2:7ae1e676b120 | 314 | else{ |
jtrux | 2:7ae1e676b120 | 315 | hashTable->buckets[index] = NULL; |
jtrux | 2:7ae1e676b120 | 316 | } |
jtrux | 2:7ae1e676b120 | 317 | free(htEntry); |
jtrux | 2:7ae1e676b120 | 318 | } |
jtrux | 2:7ae1e676b120 | 319 | else{ |
rconnorlawson | 0:35660d7952f7 | 320 | |
jtrux | 2:7ae1e676b120 | 321 | //keep track of previous |
jtrux | 2:7ae1e676b120 | 322 | HashTableEntry* previous = htEntry; |
jtrux | 2:7ae1e676b120 | 323 | while (htEntry->next != NULL){ |
jtrux | 2:7ae1e676b120 | 324 | previous = htEntry; |
jtrux | 2:7ae1e676b120 | 325 | htEntry = htEntry->next; |
jtrux | 2:7ae1e676b120 | 326 | if (htEntry->key == key){ |
jtrux | 2:7ae1e676b120 | 327 | retval = htEntry->value; |
jtrux | 2:7ae1e676b120 | 328 | previous->next = htEntry->next; |
jtrux | 2:7ae1e676b120 | 329 | free(htEntry); |
jtrux | 2:7ae1e676b120 | 330 | break; |
jtrux | 2:7ae1e676b120 | 331 | } |
jtrux | 2:7ae1e676b120 | 332 | } |
jtrux | 2:7ae1e676b120 | 333 | } |
rconnorlawson | 0:35660d7952f7 | 334 | |
jtrux | 2:7ae1e676b120 | 335 | } |
jtrux | 2:7ae1e676b120 | 336 | |
jtrux | 2:7ae1e676b120 | 337 | } |
jtrux | 2:7ae1e676b120 | 338 | return retval; |
jtrux | 2:7ae1e676b120 | 339 | } |
jtrux | 2:7ae1e676b120 | 340 | |
jtrux | 2:7ae1e676b120 | 341 | |
jtrux | 2:7ae1e676b120 | 342 | |
jtrux | 2:7ae1e676b120 | 343 | |
jtrux | 2:7ae1e676b120 | 344 | |
jtrux | 2:7ae1e676b120 | 345 | |
jtrux | 2:7ae1e676b120 | 346 | void deleteItem(HashTable* hashTable, unsigned int key) { |
jtrux | 2:7ae1e676b120 | 347 | removeItem(hashTable, key); |
jtrux | 2:7ae1e676b120 | 348 | } |
jtrux | 2:7ae1e676b120 | 349 |