Hung Nguyen / Mbed 2 deprecated snake-game

tao lao

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.cpp@3:33bf11645fe1, 2020-11-24 (annotated)

Committer:
hnguyen403
Date:
Tue Nov 24 05:05:10 2020 +0000
Revision:
3:33bf11645fe1
Parent:
2:4947d6a82971 
tao lao;

Who changed what in which revision?

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