Snake
Dependencies: mbed wave_player 4DGL-uLCD-SE MMA8452
hash_table.cpp@2:4947d6a82971, 2020-10-23 (annotated)
- Committer:
- DCchico
- Date:
- Fri Oct 23 16:30:18 2020 -0400
- Revision:
- 2:4947d6a82971
- Parent:
- 1:10330bce85cb
- Child:
- 3:2fe73b263a9a
shell
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
DCchico | 2:4947d6a82971 | 1 | // Copyright 2020 Georgia Tech. All rights reserved. |
DCchico | 2:4947d6a82971 | 2 | // The materials provided by the instructor in this course are for |
DCchico | 2:4947d6a82971 | 3 | // the use of the students currently enrolled in the course. |
DCchico | 2:4947d6a82971 | 4 | // Copyrighted course materials may not be further disseminated. |
DCchico | 2:4947d6a82971 | 5 | // This file must not be made publicly available anywhere. |
DCchico | 1:10330bce85cb | 6 | /* |
DCchico | 1:10330bce85cb | 7 | Student Name: |
DCchico | 1:10330bce85cb | 8 | Date: |
DCchico | 1:10330bce85cb | 9 | |
DCchico | 1:10330bce85cb | 10 | ======================= |
DCchico | 1:10330bce85cb | 11 | ECE 2035 Project 2-1: |
DCchico | 1:10330bce85cb | 12 | ======================= |
DCchico | 1:10330bce85cb | 13 | This file provides definition for the structs and functions declared in the |
DCchico | 1:10330bce85cb | 14 | header file. It also contains helper functions that are not accessible from |
DCchico | 1:10330bce85cb | 15 | outside of the file. |
DCchico | 1:10330bce85cb | 16 | |
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 | =================================== |
DCchico | 1:10330bce85cb | 20 | Naming conventions in this file: |
DCchico | 1:10330bce85cb | 21 | =================================== |
DCchico | 1:10330bce85cb | 22 | 1. All struct names use camel case where the first letter is capitalized. |
DCchico | 1:10330bce85cb | 23 | e.g. "HashTable", or "HashTableEntry" |
DCchico | 1:10330bce85cb | 24 | |
DCchico | 1:10330bce85cb | 25 | 2. Variable names with a preceding underscore "_" will not be called directly. |
DCchico | 1:10330bce85cb | 26 | e.g. "_HashTable", "_HashTableEntry" |
DCchico | 1:10330bce85cb | 27 | |
DCchico | 1:10330bce85cb | 28 | Recall that in C, we have to type "struct" together with the name of the struct |
DCchico | 1:10330bce85cb | 29 | in order to initialize a new variable. To avoid this, in hash_table.h |
DCchico | 1:10330bce85cb | 30 | we use typedef to provide new "nicknames" for "struct _HashTable" and |
DCchico | 1:10330bce85cb | 31 | "struct _HashTableEntry". As a result, we can create new struct variables |
DCchico | 1:10330bce85cb | 32 | by just using: |
DCchico | 1:10330bce85cb | 33 | - "HashTable myNewTable;" |
DCchico | 1:10330bce85cb | 34 | or |
DCchico | 1:10330bce85cb | 35 | - "HashTableEntry myNewHashTableEntry;" |
DCchico | 1:10330bce85cb | 36 | |
DCchico | 1:10330bce85cb | 37 | The preceding underscore "_" simply provides a distinction between the names |
DCchico | 1:10330bce85cb | 38 | of the actual struct defition and the "nicknames" that we use to initialize |
DCchico | 1:10330bce85cb | 39 | new structs. |
DCchico | 1:10330bce85cb | 40 | [See Hidden Definitions section for more information.] |
DCchico | 1:10330bce85cb | 41 | |
DCchico | 1:10330bce85cb | 42 | 3. Functions, their local variables and arguments are named with camel case, where |
DCchico | 1:10330bce85cb | 43 | the first letter is lower-case. |
DCchico | 1:10330bce85cb | 44 | e.g. "createHashTable" is a function. One of its arguments is "numBuckets". |
DCchico | 1:10330bce85cb | 45 | It also has a local variable called "newTable". |
DCchico | 1:10330bce85cb | 46 | |
DCchico | 1:10330bce85cb | 47 | 4. The name of a struct member is divided by using underscores "_". This serves |
DCchico | 1:10330bce85cb | 48 | as a distinction between function local variables and struct members. |
DCchico | 1:10330bce85cb | 49 | e.g. "num_buckets" is a member of "HashTable". |
DCchico | 1:10330bce85cb | 50 | |
DCchico | 1:10330bce85cb | 51 | */ |
DCchico | 1:10330bce85cb | 52 | |
DCchico | 1:10330bce85cb | 53 | /**************************************************************************** |
DCchico | 1:10330bce85cb | 54 | * Include the Public Interface |
DCchico | 1:10330bce85cb | 55 | * |
DCchico | 1:10330bce85cb | 56 | * By including the public interface at the top of the file, the compiler can |
DCchico | 1:10330bce85cb | 57 | * enforce that the function declarations in the the header are not in |
DCchico | 1:10330bce85cb | 58 | * conflict with the definitions in the file. This is not a guarantee of |
DCchico | 1:10330bce85cb | 59 | * correctness, but it is better than nothing! |
DCchico | 1:10330bce85cb | 60 | ***************************************************************************/ |
DCchico | 1:10330bce85cb | 61 | #include "hash_table.h" |
DCchico | 1:10330bce85cb | 62 | |
DCchico | 1:10330bce85cb | 63 | |
DCchico | 1:10330bce85cb | 64 | /**************************************************************************** |
DCchico | 1:10330bce85cb | 65 | * Include other private dependencies |
DCchico | 1:10330bce85cb | 66 | * |
DCchico | 1:10330bce85cb | 67 | * These other modules are used in the implementation of the hash table module, |
DCchico | 1:10330bce85cb | 68 | * but are not required by users of the hash table. |
DCchico | 1:10330bce85cb | 69 | ***************************************************************************/ |
DCchico | 1:10330bce85cb | 70 | #include <stdlib.h> // For malloc and free |
DCchico | 1:10330bce85cb | 71 | #include <stdio.h> // For printf |
DCchico | 1:10330bce85cb | 72 | |
DCchico | 1:10330bce85cb | 73 | |
DCchico | 1:10330bce85cb | 74 | /**************************************************************************** |
DCchico | 1:10330bce85cb | 75 | * Hidden Definitions |
DCchico | 1:10330bce85cb | 76 | * |
DCchico | 1:10330bce85cb | 77 | * These definitions are not available outside of this file. However, because |
DCchico | 1:10330bce85cb | 78 | * the are forward declared in hash_table.h, the type names are |
DCchico | 1:10330bce85cb | 79 | * available everywhere and user code can hold pointers to these structs. |
DCchico | 1:10330bce85cb | 80 | ***************************************************************************/ |
DCchico | 1:10330bce85cb | 81 | /** |
DCchico | 1:10330bce85cb | 82 | * This structure represents an a hash table. |
DCchico | 1:10330bce85cb | 83 | * Use "HashTable" instead when you are creating a new variable. [See top comments] |
DCchico | 1:10330bce85cb | 84 | */ |
DCchico | 1:10330bce85cb | 85 | struct _HashTable { |
DCchico | 1:10330bce85cb | 86 | /** The array of pointers to the head of a singly linked list, whose nodes |
DCchico | 1:10330bce85cb | 87 | are HashTableEntry objects */ |
DCchico | 1:10330bce85cb | 88 | HashTableEntry** buckets; |
DCchico | 1:10330bce85cb | 89 | |
DCchico | 1:10330bce85cb | 90 | /** The hash function pointer */ |
DCchico | 1:10330bce85cb | 91 | HashFunction hash; |
DCchico | 1:10330bce85cb | 92 | |
DCchico | 1:10330bce85cb | 93 | /** The number of buckets in the hash table */ |
DCchico | 1:10330bce85cb | 94 | unsigned int num_buckets; |
DCchico | 1:10330bce85cb | 95 | }; |
DCchico | 1:10330bce85cb | 96 | |
DCchico | 1:10330bce85cb | 97 | /** |
DCchico | 1:10330bce85cb | 98 | * This structure represents a hash table entry. |
DCchico | 1:10330bce85cb | 99 | * Use "HashTableEntry" instead when you are creating a new variable. [See top comments] |
DCchico | 1:10330bce85cb | 100 | */ |
DCchico | 1:10330bce85cb | 101 | struct _HashTableEntry { |
DCchico | 1:10330bce85cb | 102 | /** The key for the hash table entry */ |
DCchico | 1:10330bce85cb | 103 | unsigned int key; |
DCchico | 1:10330bce85cb | 104 | |
DCchico | 1:10330bce85cb | 105 | /** The value associated with this hash table entry */ |
DCchico | 1:10330bce85cb | 106 | void* value; |
DCchico | 1:10330bce85cb | 107 | |
DCchico | 1:10330bce85cb | 108 | /** |
DCchico | 1:10330bce85cb | 109 | * A pointer pointing to the next hash table entry |
DCchico | 1:10330bce85cb | 110 | * NULL means there is no next entry (i.e. this is the tail) |
DCchico | 1:10330bce85cb | 111 | */ |
DCchico | 1:10330bce85cb | 112 | HashTableEntry* next; |
DCchico | 1:10330bce85cb | 113 | }; |
DCchico | 1:10330bce85cb | 114 | |
DCchico | 1:10330bce85cb | 115 | |
DCchico | 1:10330bce85cb | 116 | /**************************************************************************** |
DCchico | 1:10330bce85cb | 117 | * Private Functions |
DCchico | 1:10330bce85cb | 118 | * |
DCchico | 1:10330bce85cb | 119 | * These functions are not available outside of this file, since they are not |
DCchico | 1:10330bce85cb | 120 | * declared in hash_table.h. |
DCchico | 1:10330bce85cb | 121 | ***************************************************************************/ |
DCchico | 1:10330bce85cb | 122 | /** |
DCchico | 1:10330bce85cb | 123 | * createHashTableEntry |
DCchico | 1:10330bce85cb | 124 | * |
DCchico | 1:10330bce85cb | 125 | * Helper function that creates a hash table entry by allocating memory for it on |
DCchico | 1:10330bce85cb | 126 | * the heap. It initializes the entry with key and value, initialize pointer to |
DCchico | 1:10330bce85cb | 127 | * the next entry as NULL, and return the pointer to this hash table entry. |
DCchico | 1:10330bce85cb | 128 | * |
DCchico | 1:10330bce85cb | 129 | * @param key The key corresponds to the hash table entry |
DCchico | 1:10330bce85cb | 130 | * @param value The value stored in the hash table entry |
DCchico | 1:10330bce85cb | 131 | * @return The pointer to the hash table entry |
DCchico | 1:10330bce85cb | 132 | */ |
DCchico | 1:10330bce85cb | 133 | static HashTableEntry* createHashTableEntry(unsigned int key, void* value) { |
DCchico | 1:10330bce85cb | 134 | |
DCchico | 1:10330bce85cb | 135 | } |
DCchico | 1:10330bce85cb | 136 | |
DCchico | 1:10330bce85cb | 137 | /** |
DCchico | 1:10330bce85cb | 138 | * findItem |
DCchico | 1:10330bce85cb | 139 | * |
DCchico | 1:10330bce85cb | 140 | * Helper function that checks whether there exists the hash table entry that |
DCchico | 1:10330bce85cb | 141 | * contains a specific key. |
DCchico | 1:10330bce85cb | 142 | * |
DCchico | 1:10330bce85cb | 143 | * @param hashTable The pointer to the hash table. |
DCchico | 1:10330bce85cb | 144 | * @param key The key corresponds to the hash table entry |
DCchico | 1:10330bce85cb | 145 | * @return The pointer to the hash table entry, or NULL if key does not exist |
DCchico | 1:10330bce85cb | 146 | */ |
DCchico | 1:10330bce85cb | 147 | static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) { |
DCchico | 1:10330bce85cb | 148 | |
DCchico | 1:10330bce85cb | 149 | } |
DCchico | 1:10330bce85cb | 150 | |
DCchico | 1:10330bce85cb | 151 | /**************************************************************************** |
DCchico | 1:10330bce85cb | 152 | * Public Interface Functions |
DCchico | 1:10330bce85cb | 153 | * |
DCchico | 1:10330bce85cb | 154 | * These functions implement the public interface as specified in the header |
DCchico | 1:10330bce85cb | 155 | * file, and make use of the private functions and hidden definitions in the |
DCchico | 1:10330bce85cb | 156 | * above sections. |
DCchico | 1:10330bce85cb | 157 | ****************************************************************************/ |
DCchico | 1:10330bce85cb | 158 | // The createHashTable is provided for you as a starting point. |
DCchico | 1:10330bce85cb | 159 | HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) { |
DCchico | 1:10330bce85cb | 160 | // The hash table has to contain at least one bucket. Exit gracefully if |
DCchico | 1:10330bce85cb | 161 | // this condition is not met. |
DCchico | 1:10330bce85cb | 162 | if (numBuckets==0) { |
DCchico | 1:10330bce85cb | 163 | printf("Hash table has to contain at least 1 bucket...\n"); |
DCchico | 1:10330bce85cb | 164 | exit(1); |
DCchico | 1:10330bce85cb | 165 | } |
DCchico | 1:10330bce85cb | 166 | |
DCchico | 1:10330bce85cb | 167 | // Allocate memory for the new HashTable struct on heap. |
DCchico | 1:10330bce85cb | 168 | HashTable* newTable = (HashTable*)malloc(sizeof(HashTable)); |
DCchico | 1:10330bce85cb | 169 | |
DCchico | 1:10330bce85cb | 170 | // Initialize the components of the new HashTable struct. |
DCchico | 1:10330bce85cb | 171 | newTable->hash = hashFunction; |
DCchico | 1:10330bce85cb | 172 | newTable->num_buckets = numBuckets; |
DCchico | 1:10330bce85cb | 173 | newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*)); |
DCchico | 1:10330bce85cb | 174 | |
DCchico | 1:10330bce85cb | 175 | // As the new buckets are empty, init each bucket as NULL. |
DCchico | 1:10330bce85cb | 176 | unsigned int i; |
DCchico | 1:10330bce85cb | 177 | for (i=0; i<numBuckets; ++i) { |
DCchico | 1:10330bce85cb | 178 | newTable->buckets[i] = NULL; |
DCchico | 1:10330bce85cb | 179 | } |
DCchico | 1:10330bce85cb | 180 | |
DCchico | 1:10330bce85cb | 181 | // Return the new HashTable struct. |
DCchico | 1:10330bce85cb | 182 | return newTable; |
DCchico | 1:10330bce85cb | 183 | } |
DCchico | 1:10330bce85cb | 184 | |
DCchico | 1:10330bce85cb | 185 | void destroyHashTable(HashTable* hashTable) { |
DCchico | 1:10330bce85cb | 186 | |
DCchico | 1:10330bce85cb | 187 | } |
DCchico | 1:10330bce85cb | 188 | |
DCchico | 1:10330bce85cb | 189 | void* insertItem(HashTable* hashTable, unsigned int key, void* value) { |
DCchico | 1:10330bce85cb | 190 | } |
DCchico | 1:10330bce85cb | 191 | |
DCchico | 1:10330bce85cb | 192 | void* getItem(HashTable* hashTable, unsigned int key) { |
DCchico | 1:10330bce85cb | 193 | |
DCchico | 1:10330bce85cb | 194 | } |
DCchico | 1:10330bce85cb | 195 | |
DCchico | 1:10330bce85cb | 196 | void* removeItem(HashTable* hashTable, unsigned int key) { |
DCchico | 1:10330bce85cb | 197 | |
DCchico | 1:10330bce85cb | 198 | } |
DCchico | 1:10330bce85cb | 199 | |
DCchico | 1:10330bce85cb | 200 | void deleteItem(HashTable* hashTable, unsigned int key) { |
DCchico | 1:10330bce85cb | 201 | |
DCchico | 1:10330bce85cb | 202 | } |