Finished V1
Dependencies: mbed wave_player 4DGL-uLCD-SE MMA8452
Diff: hash_table.cpp
- Revision:
- 4:2297a714936f
- Parent:
- 0:35660d7952f7
--- a/hash_table.cpp Mon Oct 28 05:26:35 2019 +0000 +++ b/hash_table.cpp Tue Nov 19 16:53:47 2019 +0000 @@ -125,8 +125,21 @@ * @param value The value stored in the hash table entry * @return The pointer to the hash table entry */ +//my code for createHashTableEntry static HashTableEntry* createHashTableEntry(unsigned int key, void* value) { - + + HashTableEntry *newHashTableEntry; + + newHashTableEntry = (HashTableEntry*) malloc(sizeof(HashTableEntry));//malloc space + if(!newHashTableEntry){ + return NULL; + } + + newHashTableEntry -> key = key; //assign key + newHashTableEntry -> value = value; //assign value + + + return newHashTableEntry; //return the address of the HashTableEntry } /** @@ -139,8 +152,17 @@ * @param key The key corresponds to the hash table entry * @return The pointer to the hash table entry, or NULL if key does not exist */ +//myCode static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) { - + + HashTableEntry* this_node = hashTable -> buckets[hashTable->hash(key)];//head + while(this_node){//while there is a next node + if(this_node -> key == key){//if the nodes key is equal to one we are searching for + return this_node; + } + this_node = this_node -> next;//goes to next node + } + return NULL;//returns null if not found } /**************************************************************************** @@ -167,7 +189,7 @@ newTable->num_buckets = numBuckets; newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*)); - // As the new buckets are empty, init each bucket as NULL. + // As the new buckets contain indeterminant values, init each bucket as NULL. unsigned int i; for (i=0; i<numBuckets; ++i) { newTable->buckets[i] = NULL; @@ -177,22 +199,170 @@ return newTable; } -void destroyHashTable(HashTable* hashTable) { - +/** + * destroyHashTable + * + * Destroy the hash table. The nodes (HashTableEntry objects) of singly linked + * list, the values stored on the linked list, the buckets, and the hashtable + * itself are freed from the heap. In other words, free all the allocated memory + * on heap that is associated with heap, including the values that users store in + * the hash table. + * + * @param myHashTable The pointer to the hash table. + * + */ + //mycode +void destroyHashTable(HashTable* hashTable) {//destroy everything + unsigned int numBuckets = hashTable -> num_buckets;// pull num_buckets + //hashTable -> buckets[i]; + for(int i = 0; i < numBuckets; i++){//loop thorugh every bucket + HashTableEntry* this_node = hashTable -> buckets[i]; + + while(this_node){//loop thorugh every node in a bucket + HashTableEntry* temp = this_node -> next; + free(this_node -> value); + free(this_node); + this_node = temp; + } + } + free(hashTable);//MR + return; } - +/** + * insertItem + * + * Insert the value into the hash table based on the key. + * In other words, create a new hash table entry and add it to a specific bucket. + * + * @param myHashTable The pointer to the hash table. + * @param key The key that corresponds to the value. + * @param value The value to be stored in the hash table. + * @return old value if it is overwritten, or NULL if not replaced + */ + //my code + //og had: void* insertItem(HashTable* hashTable, unsigned int key, void* value) void* insertItem(HashTable* hashTable, unsigned int key, void* value) { - + HashTableEntry* this_node; + + if(this_node = findItem(hashTable, key)){//key in list + void* ret_value = this_node -> value;//save value + this_node -> value = value; //give new value + return ret_value; //return old value + } + + //key not in list + this_node = createHashTableEntry(key, value); //create new node + int bHash = hashTable -> hash(key); //get the index of bucket it is in + + this_node ->next = hashTable -> buckets[bHash]; //this_node -> next = head + hashTable -> buckets[bHash] = this_node; //head = this_node + return NULL; + } - +/** + * getItem + * + * Get the value that corresponds to the key in the hash table. + * + * @param myHashTable The pointer to the hash table. + * @param key The key that corresponds to the item. + * @return the value corresponding to the key, or NULL if the key is not present + */ void* getItem(HashTable* hashTable, unsigned int key) { + + HashTableEntry* found_node = findItem(hashTable, key); //head_node = head + + //if it found the node return the value of it + if(found_node){ + return found_node -> value; + } + //otherwise return null + return NULL; +} +/** + * removeItem + * + * Remove the item in hash table based on the key and return the value stored in it. + * In other words, return the value and free the hash table entry from heap. + * + * @param myHashTable The pointer to the hash table. + * @param key The key that corresponds to the item. + * @return the pointer of the value corresponding to the key, or NULL if the key is not present + */ +void* removeItem(HashTable* hashTable, unsigned int key) { + HashTableEntry* this_node = hashTable -> buckets[hashTable->hash(key)]; //this_node = head -} - -void* removeItem(HashTable* hashTable, unsigned int key) { - + //case empty + if(!this_node) + return NULL; + + //case first element + if(this_node -> key == key){ + void* ret_value = this_node -> value;//save the value + hashTable -> buckets[hashTable->hash(key)] = this_node -> next;//set head to the next node + //free all components + + free(this_node); + return ret_value; + } + + //case need to walk the list + while(this_node -> next){//already checked first node + if(this_node -> next -> key == key){//delete this if true + HashTableEntry* temp_node = this_node -> next; + void* ret_value = temp_node -> value;//save the value + this_node -> next = this_node -> next -> next; + + free(temp_node); + return ret_value; + + } + this_node = this_node -> next; + } + + return NULL;//did not find anything to remove } +/** + * deleteItem + * + * Delete the item in the hash table based on the key. In other words, free the + * value stored in the hash table entry and the hash table entry itself from + * the heap. + * + * @param myHashTable The pointer to the hash table. + * @param key The key that corresponds to the item. + * + */ + + void deleteItem(HashTable* hashTable, unsigned int key){ + HashTableEntry* this_node = hashTable -> buckets[hashTable->hash(key)]; //this_node = head -void deleteItem(HashTable* hashTable, unsigned int key) { - -} \ No newline at end of file + //case empty + if(!this_node) + return; + + //case first element + if(this_node -> key == key){ + hashTable -> buckets[hashTable->hash(key)] = this_node -> next;//set head to the next node + //free all components + free(this_node -> value); + free(this_node); + return; + } + + //case need to walk the list + while(this_node -> next){//already checked first node + if(this_node -> next -> key == key){//delete this if true + HashTableEntry* temp_node = this_node -> next; + + this_node -> next = this_node -> next -> next; + free(temp_node->value); + free(temp_node); + return; + + } + this_node = this_node -> next; + } + + return; + } \ No newline at end of file