Alvin Jorgih / Mbed 2 deprecated Snake-game-fall2020-student-Shell

hgftf

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.cpp@10:0b2f37cef9b9, 2021-04-17 (annotated)

Committer:
ajorgih3
Date:
Sat Apr 17 14:09:46 2021 +0000
Revision:
10:0b2f37cef9b9
Parent:
3:bb6f73642f01 
huhu

Who changed what in which revision?

UserRevisionLine numberNew contents of line
ajorgih3 3:bb6f73642f01 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.
ajorgih3 3:bb6f73642f01 7 //=================================================================
ajorgih3 3:bb6f73642f01 8
DCchico 1:10330bce85cb 9 /*
ajorgih3 3:bb6f73642f01 10 Student Name: Alvin Jorgih
ajorgih3 3:bb6f73642f01 11 Date: 10/26/2020
ajorgih3 3:bb6f73642f01 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.
ajorgih3 3:bb6f73642f01 19
DCchico 1:10330bce85cb 20 FOR FULL CREDIT, BE SURE TO TRY MULTIPLE TEST CASES and DOCUMENT YOUR CODE.
ajorgih3 3:bb6f73642f01 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"
ajorgih3 3:bb6f73642f01 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"
ajorgih3 3:bb6f73642f01 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;"
ajorgih3 3:bb6f73642f01 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.]
ajorgih3 3:bb6f73642f01 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".
ajorgih3 3:bb6f73642f01 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".
ajorgih3 3:bb6f73642f01 53
DCchico 1:10330bce85cb 54 */
ajorgih3 3:bb6f73642f01 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"
ajorgih3 3:bb6f73642f01 65
DCchico 1:10330bce85cb 66 /****************************************************************************
DCchico 1:10330bce85cb 67 * Include other private dependencies
DCchico 1:10330bce85cb 68 *
DCchico 1:10330bce85cb 69 * These other modules are used in the implementation of the hash table module,
DCchico 1:10330bce85cb 70 * but are not required by users of the hash table.
DCchico 1:10330bce85cb 71 ***************************************************************************/
ajorgih3 3:bb6f73642f01 72 #include <stdlib.h> // For malloc and free
ajorgih3 3:bb6f73642f01 73 #include <stdio.h> // For printf
ajorgih3 3:bb6f73642f01 74
DCchico 1:10330bce85cb 75 /****************************************************************************
DCchico 1:10330bce85cb 76 * Hidden Definitions
DCchico 1:10330bce85cb 77 *
DCchico 1:10330bce85cb 78 * These definitions are not available outside of this file. However, because
DCchico 1:10330bce85cb 79 * the are forward declared in hash_table.h, the type names are
DCchico 1:10330bce85cb 80 * available everywhere and user code can hold pointers to these structs.
DCchico 1:10330bce85cb 81 ***************************************************************************/
DCchico 1:10330bce85cb 82 /**
DCchico 1:10330bce85cb 83 * This structure represents an a hash table.
DCchico 1:10330bce85cb 84 * Use "HashTable" instead when you are creating a new variable. [See top comments]
DCchico 1:10330bce85cb 85 */
ajorgih3 3:bb6f73642f01 86 struct _HashTable
ajorgih3 3:bb6f73642f01 87 {
DCchico 1:10330bce85cb 88 /** The array of pointers to the head of a singly linked list, whose nodes
DCchico 1:10330bce85cb 89 are HashTableEntry objects */
ajorgih3 3:bb6f73642f01 90 HashTableEntry **buckets;
ajorgih3 3:bb6f73642f01 91
DCchico 1:10330bce85cb 92 /** The hash function pointer */
DCchico 1:10330bce85cb 93 HashFunction hash;
ajorgih3 3:bb6f73642f01 94
DCchico 1:10330bce85cb 95 /** The number of buckets in the hash table */
DCchico 1:10330bce85cb 96 unsigned int num_buckets;
DCchico 1:10330bce85cb 97 };
ajorgih3 3:bb6f73642f01 98
DCchico 1:10330bce85cb 99 /**
DCchico 1:10330bce85cb 100 * This structure represents a hash table entry.
DCchico 1:10330bce85cb 101 * Use "HashTableEntry" instead when you are creating a new variable. [See top comments]
DCchico 1:10330bce85cb 102 */
ajorgih3 3:bb6f73642f01 103 struct _HashTableEntry
ajorgih3 3:bb6f73642f01 104 {
DCchico 1:10330bce85cb 105 /** The key for the hash table entry */
DCchico 1:10330bce85cb 106 unsigned int key;
ajorgih3 3:bb6f73642f01 107
DCchico 1:10330bce85cb 108 /** The value associated with this hash table entry */
ajorgih3 3:bb6f73642f01 109 void *value;
ajorgih3 3:bb6f73642f01 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 */
ajorgih3 3:bb6f73642f01 115 HashTableEntry *next;
DCchico 1:10330bce85cb 116 };
ajorgih3 3:bb6f73642f01 117
DCchico 1:10330bce85cb 118 /****************************************************************************
DCchico 1:10330bce85cb 119 * Private Functions
DCchico 1:10330bce85cb 120 *
DCchico 1:10330bce85cb 121 * These functions are not available outside of this file, since they are not
DCchico 1:10330bce85cb 122 * declared in hash_table.h.
DCchico 1:10330bce85cb 123 ***************************************************************************/
DCchico 1:10330bce85cb 124 /**
DCchico 1:10330bce85cb 125 * createHashTableEntry
DCchico 1:10330bce85cb 126 *
DCchico 1:10330bce85cb 127 * Helper function that creates a hash table entry by allocating memory for it on
DCchico 1:10330bce85cb 128 * the heap. It initializes the entry with key and value, initialize pointer to
DCchico 1:10330bce85cb 129 * the next entry as NULL, and return the pointer to this hash table entry.
DCchico 1:10330bce85cb 130 *
DCchico 1:10330bce85cb 131 * @param key The key corresponds to the hash table entry
DCchico 1:10330bce85cb 132 * @param value The value stored in the hash table entry
DCchico 1:10330bce85cb 133 * @return The pointer to the hash table entry
DCchico 1:10330bce85cb 134 */
ajorgih3 3:bb6f73642f01 135 static HashTableEntry *createHashTableEntry(unsigned int key, void *value)
ajorgih3 3:bb6f73642f01 136 {
ajorgih3 3:bb6f73642f01 137 // init hash table entry by allocating memory for it on the heap
ajorgih3 3:bb6f73642f01 138 HashTableEntry *newEntry = (HashTableEntry *)malloc(sizeof(HashTableEntry));
ajorgih3 3:bb6f73642f01 139 // init the key on the key field in the entry
ajorgih3 3:bb6f73642f01 140 newEntry->key = key;
ajorgih3 3:bb6f73642f01 141 // init the value on the value field in the entry
ajorgih3 3:bb6f73642f01 142 newEntry->value = value;
ajorgih3 3:bb6f73642f01 143 // init the value on the next field in the entry
ajorgih3 3:bb6f73642f01 144 newEntry->next = NULL;
ajorgih3 3:bb6f73642f01 145 // return to the hash table of the entry
ajorgih3 3:bb6f73642f01 146 return newEntry;
DCchico 1:10330bce85cb 147 }
ajorgih3 3:bb6f73642f01 148
DCchico 1:10330bce85cb 149 /**
DCchico 1:10330bce85cb 150 * findItem
DCchico 1:10330bce85cb 151 *
DCchico 1:10330bce85cb 152 * Helper function that checks whether there exists the hash table entry that
DCchico 1:10330bce85cb 153 * contains a specific key.
DCchico 1:10330bce85cb 154 *
DCchico 1:10330bce85cb 155 * @param hashTable The pointer to the hash table.
DCchico 1:10330bce85cb 156 * @param key The key corresponds to the hash table entry
DCchico 1:10330bce85cb 157 * @return The pointer to the hash table entry, or NULL if key does not exist
DCchico 1:10330bce85cb 158 */
ajorgih3 3:bb6f73642f01 159 static HashTableEntry *findItem(HashTable *hashTable, unsigned int key)
ajorgih3 3:bb6f73642f01 160 {
ajorgih3 3:bb6f73642f01 161 // initialize bucket key
ajorgih3 3:bb6f73642f01 162 unsigned int bucketKey;
ajorgih3 3:bb6f73642f01 163 // get the bucketkey by hashing the key and dereferencing the value
ajorgih3 3:bb6f73642f01 164 bucketKey = hashTable->hash(key);
ajorgih3 3:bb6f73642f01 165 // pointer to the bucket head, the first item in the bucket with
ajorgih3 3:bb6f73642f01 166 // the corresponding input key
ajorgih3 3:bb6f73642f01 167 HashTableEntry *bucketHead = hashTable->buckets[bucketKey];
ajorgih3 3:bb6f73642f01 168
ajorgih3 3:bb6f73642f01 169 // edge case where there is nothing inside the bucket
ajorgih3 3:bb6f73642f01 170 if (bucketHead == NULL) {
ajorgih3 3:bb6f73642f01 171 return NULL;
ajorgih3 3:bb6f73642f01 172 }
ajorgih3 3:bb6f73642f01 173
ajorgih3 3:bb6f73642f01 174 // else if bucket is not NULL
ajorgih3 3:bb6f73642f01 175 if (bucketHead != NULL)
ajorgih3 3:bb6f73642f01 176 {
ajorgih3 3:bb6f73642f01 177 // we loop through the items
ajorgih3 3:bb6f73642f01 178 while (bucketHead != NULL)
ajorgih3 3:bb6f73642f01 179 {
ajorgih3 3:bb6f73642f01 180 // and if the key of one of the items matches with a key
ajorgih3 3:bb6f73642f01 181 if (bucketHead->key == key)
ajorgih3 3:bb6f73642f01 182 {
ajorgih3 3:bb6f73642f01 183 // return the following item
ajorgih3 3:bb6f73642f01 184 return bucketHead;
ajorgih3 3:bb6f73642f01 185 }
ajorgih3 3:bb6f73642f01 186 else
ajorgih3 3:bb6f73642f01 187 {
ajorgih3 3:bb6f73642f01 188 // else we continue traversing
ajorgih3 3:bb6f73642f01 189 bucketHead = bucketHead->next;
ajorgih3 3:bb6f73642f01 190 }
ajorgih3 3:bb6f73642f01 191 }
ajorgih3 3:bb6f73642f01 192 }
ajorgih3 3:bb6f73642f01 193 return NULL;
DCchico 1:10330bce85cb 194 }
ajorgih3 3:bb6f73642f01 195
DCchico 1:10330bce85cb 196 /****************************************************************************
DCchico 1:10330bce85cb 197 * Public Interface Functions
DCchico 1:10330bce85cb 198 *
DCchico 1:10330bce85cb 199 * These functions implement the public interface as specified in the header
DCchico 1:10330bce85cb 200 * file, and make use of the private functions and hidden definitions in the
DCchico 1:10330bce85cb 201 * above sections.
DCchico 1:10330bce85cb 202 ****************************************************************************/
DCchico 1:10330bce85cb 203 // The createHashTable is provided for you as a starting point.
ajorgih3 3:bb6f73642f01 204 HashTable *createHashTable(HashFunction hashFunction, unsigned int numBuckets)
ajorgih3 3:bb6f73642f01 205 {
DCchico 1:10330bce85cb 206 // The hash table has to contain at least one bucket. Exit gracefully if
DCchico 1:10330bce85cb 207 // this condition is not met.
ajorgih3 3:bb6f73642f01 208 if (numBuckets == 0)
ajorgih3 3:bb6f73642f01 209 {
DCchico 1:10330bce85cb 210 printf("Hash table has to contain at least 1 bucket...\n");
DCchico 1:10330bce85cb 211 exit(1);
DCchico 1:10330bce85cb 212 }
ajorgih3 3:bb6f73642f01 213
DCchico 1:10330bce85cb 214 // Allocate memory for the new HashTable struct on heap.
ajorgih3 3:bb6f73642f01 215 // size of HashTable: determined by the type of the HashTable
ajorgih3 3:bb6f73642f01 216 // malloc: allocates size for the HashTable
ajorgih3 3:bb6f73642f01 217 HashTable *newTable = (HashTable *)malloc(sizeof(HashTable));
ajorgih3 3:bb6f73642f01 218
DCchico 1:10330bce85cb 219 // Initialize the components of the new HashTable struct.
ajorgih3 3:bb6f73642f01 220 // new table assigning value to hash
ajorgih3 3:bb6f73642f01 221 // new table assigning value to num_buckets
ajorgih3 3:bb6f73642f01 222 // new table assigning value to buckets
DCchico 1:10330bce85cb 223 newTable->hash = hashFunction;
DCchico 1:10330bce85cb 224 newTable->num_buckets = numBuckets;
ajorgih3 3:bb6f73642f01 225 newTable->buckets = (HashTableEntry **)malloc(numBuckets * sizeof(HashTableEntry *));
ajorgih3 3:bb6f73642f01 226
ajorgih3 3:bb6f73642f01 227 // As the new buckets contain indeterminant values, init each bucket as NULL.
DCchico 1:10330bce85cb 228 unsigned int i;
ajorgih3 3:bb6f73642f01 229 for (i = 0; i < numBuckets; ++i)
ajorgih3 3:bb6f73642f01 230 {
DCchico 1:10330bce85cb 231 newTable->buckets[i] = NULL;
DCchico 1:10330bce85cb 232 }
ajorgih3 3:bb6f73642f01 233
DCchico 1:10330bce85cb 234 // Return the new HashTable struct.
DCchico 1:10330bce85cb 235 return newTable;
DCchico 1:10330bce85cb 236 }
ajorgih3 3:bb6f73642f01 237
ajorgih3 3:bb6f73642f01 238 /**
ajorgih3 3:bb6f73642f01 239 * destroyHashTable
ajorgih3 3:bb6f73642f01 240 *
ajorgih3 3:bb6f73642f01 241 * Destroy the hash table. The nodes (HashTableEntry objects) of singly linked
ajorgih3 3:bb6f73642f01 242 * list, the values stored on the linked list, the buckets, and the hashtable
ajorgih3 3:bb6f73642f01 243 * itself are freed from the heap. In other words, free all the allocated memory
ajorgih3 3:bb6f73642f01 244 * on heap that is associated with heap, including the values that users store in
ajorgih3 3:bb6f73642f01 245 * the hash table.
ajorgih3 3:bb6f73642f01 246 *
ajorgih3 3:bb6f73642f01 247 */
ajorgih3 3:bb6f73642f01 248 //need to ask Dr. Wills about this
ajorgih3 3:bb6f73642f01 249 void destroyHashTable(HashTable *hashTable)
ajorgih3 3:bb6f73642f01 250 {
ajorgih3 3:bb6f73642f01 251 // iterate through each buckets, condition the number of buckets
ajorgih3 3:bb6f73642f01 252 // if it is NULL, means no head, thus continue iteration
ajorgih3 3:bb6f73642f01 253 // no direct access to num buckets, thus we use pointer to num buckets
ajorgih3 3:bb6f73642f01 254 unsigned int i;
ajorgih3 3:bb6f73642f01 255 // for loop to traverse through the hash table buckets
ajorgih3 3:bb6f73642f01 256 for (i = 0; i < (hashTable->num_buckets); ++i)
ajorgih3 3:bb6f73642f01 257 {
ajorgih3 3:bb6f73642f01 258 //points to the value preceding the next one, for memory purposes
ajorgih3 3:bb6f73642f01 259 HashTableEntry *pointer1 = hashTable->buckets[i];
ajorgih3 3:bb6f73642f01 260 // if pointer1 is NULL, pointer 2 then will create SegFault
ajorgih3 3:bb6f73642f01 261 if (pointer1 != NULL)
ajorgih3 3:bb6f73642f01 262 {
ajorgih3 3:bb6f73642f01 263 // pointer2 if they have a value for pointer 1
ajorgih3 3:bb6f73642f01 264 HashTableEntry *pointer2 = pointer1->next;
ajorgih3 3:bb6f73642f01 265 // while pointer2 is not NULL
ajorgih3 3:bb6f73642f01 266 while (pointer2 != NULL)
ajorgih3 3:bb6f73642f01 267 {
ajorgih3 3:bb6f73642f01 268 // free the value of pointer1
ajorgih3 3:bb6f73642f01 269 free(pointer1->value);
ajorgih3 3:bb6f73642f01 270 // free the entry of pointer1
ajorgih3 3:bb6f73642f01 271 free(pointer1);
ajorgih3 3:bb6f73642f01 272 // pointer1 moves to pointer 2
ajorgih3 3:bb6f73642f01 273 pointer1 = pointer2;
ajorgih3 3:bb6f73642f01 274 // pointer 2 moves to the next after pointer 2
ajorgih3 3:bb6f73642f01 275 pointer2 = pointer2->next;
ajorgih3 3:bb6f73642f01 276 }
ajorgih3 3:bb6f73642f01 277 // free the last value of the pointer
ajorgih3 3:bb6f73642f01 278 free(pointer1->value);
ajorgih3 3:bb6f73642f01 279 // free the pointer itself
ajorgih3 3:bb6f73642f01 280 free(pointer1);
ajorgih3 3:bb6f73642f01 281 }
ajorgih3 3:bb6f73642f01 282 }
ajorgih3 3:bb6f73642f01 283
ajorgih3 3:bb6f73642f01 284 // if everything is done, we free up the hashTable
ajorgih3 3:bb6f73642f01 285 free(hashTable->buckets);
ajorgih3 3:bb6f73642f01 286 // free the hashtable
ajorgih3 3:bb6f73642f01 287 free(hashTable);
ajorgih3 3:bb6f73642f01 288 // return
ajorgih3 3:bb6f73642f01 289 return;
DCchico 1:10330bce85cb 290 }
ajorgih3 3:bb6f73642f01 291
ajorgih3 3:bb6f73642f01 292 /**
ajorgih3 3:bb6f73642f01 293 * insertItem
ajorgih3 3:bb6f73642f01 294 *
ajorgih3 3:bb6f73642f01 295 * Insert the value into the hash table based on the key.
ajorgih3 3:bb6f73642f01 296 * In other words, create a new hash table entry and add it to a specific bucket.
ajorgih3 3:bb6f73642f01 297 *
ajorgih3 3:bb6f73642f01 298 */
ajorgih3 3:bb6f73642f01 299 void *insertItem(HashTable *hashTable, unsigned int key, void *value)
ajorgih3 3:bb6f73642f01 300 {
ajorgih3 3:bb6f73642f01 301 // init index after hashing
ajorgih3 3:bb6f73642f01 302 unsigned int bucketHashIndex = hashTable->hash(key);
ajorgih3 3:bb6f73642f01 303 //init a pointer to the head of the bucket
ajorgih3 3:bb6f73642f01 304 HashTableEntry *bucketHead = hashTable->buckets[bucketHashIndex];
ajorgih3 3:bb6f73642f01 305
ajorgih3 3:bb6f73642f01 306 // while bucket head is not null
ajorgih3 3:bb6f73642f01 307 while (bucketHead != NULL)
ajorgih3 3:bb6f73642f01 308 {
ajorgih3 3:bb6f73642f01 309 //if the bucket head has the same value like the key
ajorgih3 3:bb6f73642f01 310 if (bucketHead->key == key)
ajorgih3 3:bb6f73642f01 311 {
ajorgih3 3:bb6f73642f01 312 // store the old value of the key to be returned
ajorgih3 3:bb6f73642f01 313 void *oldValue = bucketHead->value;
ajorgih3 3:bb6f73642f01 314 // change the bucket head value
ajorgih3 3:bb6f73642f01 315 bucketHead->value = value;
ajorgih3 3:bb6f73642f01 316 //return to the old value
ajorgih3 3:bb6f73642f01 317 return oldValue;
ajorgih3 3:bb6f73642f01 318 }
ajorgih3 3:bb6f73642f01 319
ajorgih3 3:bb6f73642f01 320 // else keep traversing
ajorgih3 3:bb6f73642f01 321 else
ajorgih3 3:bb6f73642f01 322 {
ajorgih3 3:bb6f73642f01 323 // reaching the last entry in the bucket
ajorgih3 3:bb6f73642f01 324 bucketHead = bucketHead->next;
ajorgih3 3:bb6f73642f01 325 }
ajorgih3 3:bb6f73642f01 326 }
ajorgih3 3:bb6f73642f01 327
ajorgih3 3:bb6f73642f01 328 // init new entry, should be here just because, if this is declared at the top
ajorgih3 3:bb6f73642f01 329 // it will cause a memory leak due to the fact it may become unused
ajorgih3 3:bb6f73642f01 330 HashTableEntry *newEntry = createHashTableEntry(key, value);
ajorgih3 3:bb6f73642f01 331
ajorgih3 3:bb6f73642f01 332 // we are adding the entry from the front
ajorgih3 3:bb6f73642f01 333 newEntry->next = hashTable->buckets[bucketHashIndex];
ajorgih3 3:bb6f73642f01 334 hashTable->buckets[bucketHashIndex] = newEntry;
ajorgih3 3:bb6f73642f01 335
ajorgih3 3:bb6f73642f01 336 return NULL;
ajorgih3 3:bb6f73642f01 337 }
ajorgih3 3:bb6f73642f01 338
ajorgih3 3:bb6f73642f01 339 /**
ajorgih3 3:bb6f73642f01 340 * getItem
ajorgih3 3:bb6f73642f01 341 *
ajorgih3 3:bb6f73642f01 342 * Get the value that corresponds to the key in the hash table.
ajorgih3 3:bb6f73642f01 343 *
ajorgih3 3:bb6f73642f01 344 */
ajorgih3 3:bb6f73642f01 345 // get item utilizes the static function from findItem
ajorgih3 3:bb6f73642f01 346 void *getItem(HashTable *hashTable, unsigned int key)
ajorgih3 3:bb6f73642f01 347 {
ajorgih3 3:bb6f73642f01 348 // call findItem and set it as a variable
ajorgih3 3:bb6f73642f01 349 HashTableEntry *item = findItem(hashTable, key);
ajorgih3 3:bb6f73642f01 350 // if it is not NULL, then we make another pointer to the value of the variable
ajorgih3 3:bb6f73642f01 351 if (item != NULL)
ajorgih3 3:bb6f73642f01 352 {
ajorgih3 3:bb6f73642f01 353 // return the value of the item
ajorgih3 3:bb6f73642f01 354 return item->value;
ajorgih3 3:bb6f73642f01 355 }
ajorgih3 3:bb6f73642f01 356
ajorgih3 3:bb6f73642f01 357 // else return NULL
ajorgih3 3:bb6f73642f01 358 return NULL;
DCchico 1:10330bce85cb 359 }
ajorgih3 3:bb6f73642f01 360
ajorgih3 3:bb6f73642f01 361 /**
ajorgih3 3:bb6f73642f01 362 * removeItem
ajorgih3 3:bb6f73642f01 363 *
ajorgih3 3:bb6f73642f01 364 * Remove the item in hash table based on the key and return the value stored in it.
ajorgih3 3:bb6f73642f01 365 * In other words, return the value and free the hash table entry from heap.
ajorgih3 3:bb6f73642f01 366 *
ajorgih3 3:bb6f73642f01 367 */
ajorgih3 3:bb6f73642f01 368 void *removeItem(HashTable *hashTable, unsigned int key)
ajorgih3 3:bb6f73642f01 369 {
ajorgih3 3:bb6f73642f01 370
ajorgih3 3:bb6f73642f01 371 // we need to consider three cases: when the entry is on the head of the node
ajorgih3 3:bb6f73642f01 372 // when the entry is sandwiched between two nodes
ajorgih3 3:bb6f73642f01 373 // when the entry is at the end of the node
ajorgih3 3:bb6f73642f01 374 // when the entry is not found
ajorgih3 3:bb6f73642f01 375
ajorgih3 3:bb6f73642f01 376 int bucketKey = hashTable->hash(key);
ajorgih3 3:bb6f73642f01 377 HashTableEntry *pointer1 = hashTable->buckets[bucketKey];
ajorgih3 3:bb6f73642f01 378
ajorgih3 3:bb6f73642f01 379 // if the list is empty
ajorgih3 3:bb6f73642f01 380 if (pointer1 == NULL) {
ajorgih3 3:bb6f73642f01 381 return NULL;
ajorgih3 3:bb6f73642f01 382 }
ajorgih3 3:bb6f73642f01 383
ajorgih3 3:bb6f73642f01 384 // if the entry is not null
ajorgih3 3:bb6f73642f01 385 if (pointer1 != NULL)
ajorgih3 3:bb6f73642f01 386 {
ajorgih3 3:bb6f73642f01 387 HashTableEntry *pointer2 = pointer1->next;
ajorgih3 3:bb6f73642f01 388 // if the value of the key is in on the head of the node
ajorgih3 3:bb6f73642f01 389 if (pointer1->key == key)
ajorgih3 3:bb6f73642f01 390 {
ajorgih3 3:bb6f73642f01 391 // deleted value saved to a variable called deleted value
ajorgih3 3:bb6f73642f01 392 void *deletedValue = pointer1->value;
ajorgih3 3:bb6f73642f01 393 // free the entry
ajorgih3 3:bb6f73642f01 394 free(pointer1);
ajorgih3 3:bb6f73642f01 395 // connects the head to the next pointer
ajorgih3 3:bb6f73642f01 396 hashTable->buckets[bucketKey] = pointer2;
ajorgih3 3:bb6f73642f01 397 // returns deleted value
ajorgih3 3:bb6f73642f01 398 return deletedValue;
ajorgih3 3:bb6f73642f01 399 }
ajorgih3 3:bb6f73642f01 400
ajorgih3 3:bb6f73642f01 401 // when the entry is in the middle or at the end
ajorgih3 3:bb6f73642f01 402 else
ajorgih3 3:bb6f73642f01 403 {
ajorgih3 3:bb6f73642f01 404 while (pointer2 != NULL)
ajorgih3 3:bb6f73642f01 405 {
ajorgih3 3:bb6f73642f01 406 if (pointer2->key == key)
ajorgih3 3:bb6f73642f01 407 {
ajorgih3 3:bb6f73642f01 408 // points to the deleted value
ajorgih3 3:bb6f73642f01 409 void *deletedValue = pointer2->value;
ajorgih3 3:bb6f73642f01 410
ajorgih3 3:bb6f73642f01 411 // if the key is in the last place
ajorgih3 3:bb6f73642f01 412 if (pointer2->next == NULL)
ajorgih3 3:bb6f73642f01 413 {
ajorgih3 3:bb6f73642f01 414 // pointer points to NULL
ajorgih3 3:bb6f73642f01 415 pointer1->next = NULL;
ajorgih3 3:bb6f73642f01 416 }
ajorgih3 3:bb6f73642f01 417
ajorgih3 3:bb6f73642f01 418 // if the entry is in the middle
ajorgih3 3:bb6f73642f01 419 else
ajorgih3 3:bb6f73642f01 420 {
ajorgih3 3:bb6f73642f01 421 pointer1->next = pointer2->next;
ajorgih3 3:bb6f73642f01 422 }
ajorgih3 3:bb6f73642f01 423 // free the value of the second pointer
ajorgih3 3:bb6f73642f01 424 free(pointer2);
ajorgih3 3:bb6f73642f01 425 // return deleted value
ajorgih3 3:bb6f73642f01 426 return deletedValue;
ajorgih3 3:bb6f73642f01 427 }
ajorgih3 3:bb6f73642f01 428
ajorgih3 3:bb6f73642f01 429 // else pointer next
ajorgih3 3:bb6f73642f01 430 else
ajorgih3 3:bb6f73642f01 431 {
ajorgih3 3:bb6f73642f01 432 // pointer 1 is now pointer 2
ajorgih3 3:bb6f73642f01 433 pointer1 = pointer2;
ajorgih3 3:bb6f73642f01 434 // pointer 2 is now the next value of its first value
ajorgih3 3:bb6f73642f01 435 pointer2 = pointer2->next;
ajorgih3 3:bb6f73642f01 436 }
ajorgih3 3:bb6f73642f01 437 }
ajorgih3 3:bb6f73642f01 438 }
ajorgih3 3:bb6f73642f01 439 }
ajorgih3 3:bb6f73642f01 440
ajorgih3 3:bb6f73642f01 441 // else return NULL
ajorgih3 3:bb6f73642f01 442 return NULL;
DCchico 1:10330bce85cb 443 }
ajorgih3 3:bb6f73642f01 444
ajorgih3 3:bb6f73642f01 445 /**
ajorgih3 3:bb6f73642f01 446 * deleteItem
ajorgih3 3:bb6f73642f01 447 *
ajorgih3 3:bb6f73642f01 448 * Delete the item in the hash table based on the key. In other words, free the
ajorgih3 3:bb6f73642f01 449 * value stored in the hash table entry and the hash table entry itself from
ajorgih3 3:bb6f73642f01 450 * the heap.
ajorgih3 3:bb6f73642f01 451 *
ajorgih3 3:bb6f73642f01 452 */
ajorgih3 3:bb6f73642f01 453 void deleteItem(HashTable *hashTable, unsigned int key)
ajorgih3 3:bb6f73642f01 454 {
ajorgih3 3:bb6f73642f01 455
ajorgih3 3:bb6f73642f01 456 // we need to consider three cases: when the entry is on the head of the node
ajorgih3 3:bb6f73642f01 457 // when the entry is sandwiched between two nodes
ajorgih3 3:bb6f73642f01 458 // when the entry is at the end of the node
ajorgih3 3:bb6f73642f01 459 // when the entry is not found
ajorgih3 3:bb6f73642f01 460
ajorgih3 3:bb6f73642f01 461 int bucketKey = hashTable->hash(key);
ajorgih3 3:bb6f73642f01 462 HashTableEntry *pointer1 = hashTable->buckets[bucketKey];
ajorgih3 3:bb6f73642f01 463
ajorgih3 3:bb6f73642f01 464 // if the list is empty
ajorgih3 3:bb6f73642f01 465 if (pointer1 == NULL) {
ajorgih3 3:bb6f73642f01 466 return;
ajorgih3 3:bb6f73642f01 467 }
ajorgih3 3:bb6f73642f01 468
ajorgih3 3:bb6f73642f01 469 // if the entry is not null
ajorgih3 3:bb6f73642f01 470 if (pointer1 != NULL)
ajorgih3 3:bb6f73642f01 471 {
ajorgih3 3:bb6f73642f01 472 HashTableEntry *pointer2 = pointer1->next;
ajorgih3 3:bb6f73642f01 473 // if the value of the key is in on the head of the node
ajorgih3 3:bb6f73642f01 474 if (pointer1->key == key)
ajorgih3 3:bb6f73642f01 475 {
ajorgih3 3:bb6f73642f01 476 // free the value of the pointer
ajorgih3 3:bb6f73642f01 477 free(pointer1->value);
ajorgih3 3:bb6f73642f01 478 pointer1->value = NULL;
ajorgih3 3:bb6f73642f01 479 // free the entry
ajorgih3 3:bb6f73642f01 480 free(pointer1);
ajorgih3 3:bb6f73642f01 481 // connects the head to the next pointer
ajorgih3 3:bb6f73642f01 482 hashTable->buckets[bucketKey] = pointer2;
ajorgih3 3:bb6f73642f01 483 // returns deleted value
ajorgih3 3:bb6f73642f01 484 return;
ajorgih3 3:bb6f73642f01 485 }
ajorgih3 3:bb6f73642f01 486
ajorgih3 3:bb6f73642f01 487 // when the entry is in the middle or at the end
ajorgih3 3:bb6f73642f01 488 else
ajorgih3 3:bb6f73642f01 489 {
ajorgih3 3:bb6f73642f01 490 while (pointer2 != NULL)
ajorgih3 3:bb6f73642f01 491 {
ajorgih3 3:bb6f73642f01 492 if (pointer2->key == key)
ajorgih3 3:bb6f73642f01 493 {
ajorgih3 3:bb6f73642f01 494 // if the key is in the last place
ajorgih3 3:bb6f73642f01 495 if (pointer2->next == NULL)
ajorgih3 3:bb6f73642f01 496 {
ajorgih3 3:bb6f73642f01 497 // pointer points to NULL
ajorgih3 3:bb6f73642f01 498 pointer1->next = NULL;
ajorgih3 3:bb6f73642f01 499 }
ajorgih3 3:bb6f73642f01 500
ajorgih3 3:bb6f73642f01 501 // if the entry is in the middle
ajorgih3 3:bb6f73642f01 502 else
ajorgih3 3:bb6f73642f01 503 {
ajorgih3 3:bb6f73642f01 504 pointer1->next = pointer2->next;
ajorgih3 3:bb6f73642f01 505 }
ajorgih3 3:bb6f73642f01 506 // free the value of the pointer
ajorgih3 3:bb6f73642f01 507 free(pointer2->value);
ajorgih3 3:bb6f73642f01 508 // free the value of the second pointer
ajorgih3 3:bb6f73642f01 509 free(pointer2);
ajorgih3 3:bb6f73642f01 510 // return deleted value
ajorgih3 3:bb6f73642f01 511 return;
ajorgih3 3:bb6f73642f01 512 }
ajorgih3 3:bb6f73642f01 513
ajorgih3 3:bb6f73642f01 514 // else pointer next
ajorgih3 3:bb6f73642f01 515 else
ajorgih3 3:bb6f73642f01 516 {
ajorgih3 3:bb6f73642f01 517 // pointer 1 is now pointer 2
ajorgih3 3:bb6f73642f01 518 pointer1 = pointer2;
ajorgih3 3:bb6f73642f01 519 // pointer 2 is now the next value of its first value
ajorgih3 3:bb6f73642f01 520 pointer2 = pointer2->next;
ajorgih3 3:bb6f73642f01 521 }
ajorgih3 3:bb6f73642f01 522 }
ajorgih3 3:bb6f73642f01 523 }
ajorgih3 3:bb6f73642f01 524 }
ajorgih3 3:bb6f73642f01 525
ajorgih3 3:bb6f73642f01 526 // else return if the value is not in the hash table
ajorgih3 3:bb6f73642f01 527 return;
DCchico 1:10330bce85cb 528 }