Yehowshua Immanuel / Mbed 2 deprecated Generic_Platformer

A lightweight game engine for the MBED.

Dependencies:   mbed 4DGL-uLCD-SE MMA8452

hash_table/hash_table.h@2:5645cb2d9316, 2019-03-13 (annotated)

Committer:
Yehowshua Immanuel
Date:
Wed Mar 13 09:48:27 2019 -0400
Revision:
2:5645cb2d9316
Added hashtable

Who changed what in which revision?

UserRevisionLine numberNew contents of line
Yehowshua Immanuel 2:5645cb2d9316 1 /****************************************************************************
Yehowshua Immanuel 2:5645cb2d9316 2 * Include guards
Yehowshua Immanuel 2:5645cb2d9316 3 *
Yehowshua Immanuel 2:5645cb2d9316 4 * By using a preprecessor include guard like this one (along with the #endif
Yehowshua Immanuel 2:5645cb2d9316 5 * at the bottom of the file), we can guarantee that the public interface for
Yehowshua Immanuel 2:5645cb2d9316 6 * this module is only included once in each compilation unit. This prevents
Yehowshua Immanuel 2:5645cb2d9316 7 * transitive dependencies from mistakenly including headers many times, and
Yehowshua Immanuel 2:5645cb2d9316 8 * can also prevent infinite #include loops due to circular dependencies.
Yehowshua Immanuel 2:5645cb2d9316 9 ***************************************************************************/
Yehowshua Immanuel 2:5645cb2d9316 10 #pragma once
Yehowshua Immanuel 2:5645cb2d9316 11 /****************************************************************************
Yehowshua Immanuel 2:5645cb2d9316 12 * Forward Declarations
Yehowshua Immanuel 2:5645cb2d9316 13 *
Yehowshua Immanuel 2:5645cb2d9316 14 * These declarations are for interface types that are private to the module,
Yehowshua Immanuel 2:5645cb2d9316 15 * but are needed for external interfaces. Without a definition, the compiler
Yehowshua Immanuel 2:5645cb2d9316 16 * (and therefore the user) does not have access to information about the
Yehowshua Immanuel 2:5645cb2d9316 17 * member variables, and so the members cannot be used directly from modules
Yehowshua Immanuel 2:5645cb2d9316 18 * that include this header. However, we do know that these structures are
Yehowshua Immanuel 2:5645cb2d9316 19 * valid, and we can use pointers to them. This technique allows hiding the
Yehowshua Immanuel 2:5645cb2d9316 20 * implementation details of the hash table module behind a clean public
Yehowshua Immanuel 2:5645cb2d9316 21 * interface.
Yehowshua Immanuel 2:5645cb2d9316 22 ***************************************************************************/
Yehowshua Immanuel 2:5645cb2d9316 23 /**
Yehowshua Immanuel 2:5645cb2d9316 24 * This defines a type that is a pointer to a function which takes
Yehowshua Immanuel 2:5645cb2d9316 25 * an unsigned int argument and returns an unsigned int value.
Yehowshua Immanuel 2:5645cb2d9316 26 * The name of the type is "HashFunction".
Yehowshua Immanuel 2:5645cb2d9316 27 */
Yehowshua Immanuel 2:5645cb2d9316 28 typedef unsigned int (*HashFunction)(unsigned int key);
Yehowshua Immanuel 2:5645cb2d9316 29
Yehowshua Immanuel 2:5645cb2d9316 30 /**
Yehowshua Immanuel 2:5645cb2d9316 31 * This defines a type that is a _HashTable struct. The definition for
Yehowshua Immanuel 2:5645cb2d9316 32 * _HashTable is implemented in hash_table.c.
Yehowshua Immanuel 2:5645cb2d9316 33 *
Yehowshua Immanuel 2:5645cb2d9316 34 * In other words, "HashTable" is an alternative name for "struct _HashTable".
Yehowshua Immanuel 2:5645cb2d9316 35 * "HashTable" can be used to create a new struct variable.
Yehowshua Immanuel 2:5645cb2d9316 36 */
Yehowshua Immanuel 2:5645cb2d9316 37 typedef struct _HashTable HashTable;
Yehowshua Immanuel 2:5645cb2d9316 38
Yehowshua Immanuel 2:5645cb2d9316 39 /**
Yehowshua Immanuel 2:5645cb2d9316 40 * This defines a type that is a _HashTableEntry struct. The definition for
Yehowshua Immanuel 2:5645cb2d9316 41 * _HashTableEntry is implemented in hash_table.c.
Yehowshua Immanuel 2:5645cb2d9316 42 *
Yehowshua Immanuel 2:5645cb2d9316 43 * In other words, "HashTableEntry" is an alternative name for "struct _HashTableEntry".
Yehowshua Immanuel 2:5645cb2d9316 44 * "HashTableEntry" can be used to create a new struct variable.
Yehowshua Immanuel 2:5645cb2d9316 45 */
Yehowshua Immanuel 2:5645cb2d9316 46 typedef struct _HashTableEntry HashTableEntry;
Yehowshua Immanuel 2:5645cb2d9316 47
Yehowshua Immanuel 2:5645cb2d9316 48 /**
Yehowshua Immanuel 2:5645cb2d9316 49 * createHashTable
Yehowshua Immanuel 2:5645cb2d9316 50 *
Yehowshua Immanuel 2:5645cb2d9316 51 * Creates a hash table by allocating memory for it on the heap. Initialize num_buckets
Yehowshua Immanuel 2:5645cb2d9316 52 * and hash based on function arguments. Allocate memory for buckets as an array of
Yehowshua Immanuel 2:5645cb2d9316 53 * pointers to HashTableEntry objects based on the number of buckets available.
Yehowshua Immanuel 2:5645cb2d9316 54 * Each bucket contains a singly linked list, whose nodes are HashTableEntry objects.
Yehowshua Immanuel 2:5645cb2d9316 55 *
Yehowshua Immanuel 2:5645cb2d9316 56 * @param myHashFunc The pointer to the custom hash function.
Yehowshua Immanuel 2:5645cb2d9316 57 * @param numBuckets The number of buckets available in the hash table.
Yehowshua Immanuel 2:5645cb2d9316 58 * @return a pointer to the new hash table
Yehowshua Immanuel 2:5645cb2d9316 59 */
Yehowshua Immanuel 2:5645cb2d9316 60 HashTable* createHashTable(HashFunction myHashFunc, unsigned int numBuckets);
Yehowshua Immanuel 2:5645cb2d9316 61
Yehowshua Immanuel 2:5645cb2d9316 62 /**
Yehowshua Immanuel 2:5645cb2d9316 63 * destroyHashTable
Yehowshua Immanuel 2:5645cb2d9316 64 *
Yehowshua Immanuel 2:5645cb2d9316 65 * Destroy the hash table. The nodes (HashTableEntry objects) of singly linked
Yehowshua Immanuel 2:5645cb2d9316 66 * list, the values stored on the linked list, the buckets, and the hashtable
Yehowshua Immanuel 2:5645cb2d9316 67 * itself are freed from the heap. In other words, free all the allocated memory
Yehowshua Immanuel 2:5645cb2d9316 68 * on heap that is associated with heap, including the values that users store in
Yehowshua Immanuel 2:5645cb2d9316 69 * the hash table.
Yehowshua Immanuel 2:5645cb2d9316 70 *
Yehowshua Immanuel 2:5645cb2d9316 71 * @param myHashTable The pointer to the hash table.
Yehowshua Immanuel 2:5645cb2d9316 72 *
Yehowshua Immanuel 2:5645cb2d9316 73 */
Yehowshua Immanuel 2:5645cb2d9316 74 void destroyHashTable(HashTable* myHashTable);
Yehowshua Immanuel 2:5645cb2d9316 75
Yehowshua Immanuel 2:5645cb2d9316 76 /**
Yehowshua Immanuel 2:5645cb2d9316 77 * insertItem
Yehowshua Immanuel 2:5645cb2d9316 78 *
Yehowshua Immanuel 2:5645cb2d9316 79 * Insert the value into the hash table based on the key.
Yehowshua Immanuel 2:5645cb2d9316 80 * In other words, create a new hash table entry and add it to a specific bucket.
Yehowshua Immanuel 2:5645cb2d9316 81 *
Yehowshua Immanuel 2:5645cb2d9316 82 * @param myHashTable The pointer to the hash table.
Yehowshua Immanuel 2:5645cb2d9316 83 * @param key The key that corresponds to the value.
Yehowshua Immanuel 2:5645cb2d9316 84 * @param value The value to be stored in the hash table.
Yehowshua Immanuel 2:5645cb2d9316 85 * @return old value if it is overwritten, or NULL if not replaced
Yehowshua Immanuel 2:5645cb2d9316 86 */
Yehowshua Immanuel 2:5645cb2d9316 87 void* insertItem(HashTable* myHashTable, unsigned int key, void* value);
Yehowshua Immanuel 2:5645cb2d9316 88
Yehowshua Immanuel 2:5645cb2d9316 89 /**
Yehowshua Immanuel 2:5645cb2d9316 90 * getItem
Yehowshua Immanuel 2:5645cb2d9316 91 *
Yehowshua Immanuel 2:5645cb2d9316 92 * Get the value that corresponds to the key in the hash table.
Yehowshua Immanuel 2:5645cb2d9316 93 *
Yehowshua Immanuel 2:5645cb2d9316 94 * @param myHashTable The pointer to the hash table.
Yehowshua Immanuel 2:5645cb2d9316 95 * @param key The key that corresponds to the item.
Yehowshua Immanuel 2:5645cb2d9316 96 * @return the value corresponding to the key, or NULL if the key is not present
Yehowshua Immanuel 2:5645cb2d9316 97 */
Yehowshua Immanuel 2:5645cb2d9316 98 void* getItem(HashTable* myHashTable, unsigned int key);
Yehowshua Immanuel 2:5645cb2d9316 99
Yehowshua Immanuel 2:5645cb2d9316 100 /**
Yehowshua Immanuel 2:5645cb2d9316 101 * removeItem
Yehowshua Immanuel 2:5645cb2d9316 102 *
Yehowshua Immanuel 2:5645cb2d9316 103 * Remove the item in hash table based on the key and return the value stored in it.
Yehowshua Immanuel 2:5645cb2d9316 104 * In other words, return the value and free the hash table entry from heap.
Yehowshua Immanuel 2:5645cb2d9316 105 *
Yehowshua Immanuel 2:5645cb2d9316 106 * @param myHashTable The pointer to the hash table.
Yehowshua Immanuel 2:5645cb2d9316 107 * @param key The key that corresponds to the item.
Yehowshua Immanuel 2:5645cb2d9316 108 * @return the pointer of the value corresponding to the key, or NULL if the key is not present
Yehowshua Immanuel 2:5645cb2d9316 109 */
Yehowshua Immanuel 2:5645cb2d9316 110 void* removeItem(HashTable* myHashTable, unsigned int key);
Yehowshua Immanuel 2:5645cb2d9316 111
Yehowshua Immanuel 2:5645cb2d9316 112 /**
Yehowshua Immanuel 2:5645cb2d9316 113 * deleteItem
Yehowshua Immanuel 2:5645cb2d9316 114 *
Yehowshua Immanuel 2:5645cb2d9316 115 * Delete the item in the hash table based on the key. In other words, free the
Yehowshua Immanuel 2:5645cb2d9316 116 * value stored in the hash table entry and the hash table entry itself from
Yehowshua Immanuel 2:5645cb2d9316 117 * the heap.
Yehowshua Immanuel 2:5645cb2d9316 118 *
Yehowshua Immanuel 2:5645cb2d9316 119 * @param myHashTable The pointer to the hash table.
Yehowshua Immanuel 2:5645cb2d9316 120 * @param key The key that corresponds to the item.
Yehowshua Immanuel 2:5645cb2d9316 121 *
Yehowshua Immanuel 2:5645cb2d9316 122 */
Yehowshua Immanuel 2:5645cb2d9316 123 void deleteItem(HashTable* myHashTable, unsigned int key);
Yehowshua Immanuel 2:5645cb2d9316 124