src/HashTable.h

   1 /**
   2  * @file HashTable.h
   3  */
   4
   5 #ifndef CGDS_HASH_TABLE_H
   6 #define CGDS_HASH_TABLE_H
   7
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include "cgds/safe_alloc.h"
  11 #include "cgds/types.h"
  12 #include "cgds/Vector.h"
  13
  14 /**
  15  * @brief Cell of a dictionary.
  16  */
  17 typedef struct HashCell {
  18     char* key; ///< Key (as a string).
  19   void* data; ///< Generic data contained in this cell.
  20     struct HashCell* next; ///< Pointer to next cell in the list.
  21 } HashCell;
  22
  23 /**
  24  * @brief Generic dictionary string --> any data.
  25  */
  26 typedef struct HashTable {
  27   UInt size; ///< Count elements in the dictionary.
  28     size_t dataSize; ///< Size of a dict cell element in bytes.
  29   size_t hashSize; ///< (Maximum) Number of stored hash keys.
  30     HashCell** head; ///< Pointers to the first cell in a list.
  31 } HashTable;
  32
  33 /**
  34  * @brief Initialize an empty dictionary.
  35  */
  36 void _hashtable_init(
  37     HashTable* hashTable, ///< "this" pointer.
  38     size_t dataSize, ///< Size in bytes of a dictionary element.
  39   size_t hashSize ///< (Maximum) Number of stored hash keys.
  40 );
  41
  42 /**
  43  * @brief Return an allocated and initialized dictionary.
  44  */
  45 HashTable* _hashtable_new(
  46     size_t dataSize, ///< Size in bytes of a dictionary element.
  47   size_t hashSize ///< (Maximum) Number of stored hash keys.
  48 );
  49
  50 /**
  51  * @brief Return an allocated and initialized vector.
  52  * @param type Type of a vector element (int, char*, ...).
  53  *
  54  * Usage: HashTable* hashtable_new(<Type> type, UInt hash_size)
  55  */
  56 #define hashtable_new(type, hsize) \
  57     _hashtable_new(sizeof(type), hsize)
  58
  59 /**
  60  * @brief Copy constructor (shallow copy, ok for basic types).
  61  */
  62 HashTable* hashtable_copy(
  63     HashTable* hashTable ///< "this" pointer.
  64 );
  65
  66 /**
  67  * @brief Check if the dictionary is empty.
  68  */
  69 bool hashtable_empty(
  70     HashTable* hastTable ///< "this" pointer.
  71 );
  72
  73 /**
  74  * @brief Return current size.
  75  */
  76 UInt hashtable_size(
  77     HashTable* hastTable ///< "this" pointer.
  78 );
  79
  80 /**
  81  * @brief Lookup element of given key.
  82  */
  83 void* _hashtable_get(
  84     HashTable* hashTable, ///< "this" pointer.
  85     char* key ///< Key of the element to retrieve.
  86 );
  87
  88 /**
  89  * @brief Lookup element of given key.
  90  * @param hashTable "this" pointer.
  91  * @param key Key of the element to retrieve..
  92  * @param data 'out' variable to contain the result.
  93  *
  94  * Usage: void hashtable_get(HashTable* hashTable, char* key, void data)
  95  */
  96 #define hashtable_get(hashTable, key, data) \
  97 { \
  98     void* pData = _hashtable_get(hashTable, key); \
  99     data = *((typeof(&data))pData); \
 100 }
 101
 102 /**
 103  * @brief Add the entry (key, value) to dictionary.
 104  */
 105 void _hashtable_set(
 106     HashTable* hashTable, ///< "this" pointer.
 107     char* key, ///< Key of the element to add or modify.
 108     void* data ///< Pointer to new data at given key.
 109 );
 110
 111 /**
 112  * @brief Add the entry (key, value) to dictionary.
 113  * @param hashTable "this" pointer.
 114  * @param key Key of the element to add or modify.
 115  * @param data New data at given key.
 116  *
 117  * Usage: void hashtable_set(HashTable* hashTable, char* key, void data)
 118  */
 119 #define hashtable_set(hashTable, key, data) \
 120 { \
 121     typeof((data)) tmp = data; \
 122     _hashtable_set(hashTable, key, &tmp); \
 123 }
 124
 125 /**
 126  * @brief Remove the given key (+ associated value).
 127  */
 128 void hashtable_delete(
 129     HashTable* hashTable, ///< "this" pointer.
 130   char* key ///< Key of the element to delete.
 131 );
 132
 133 /**
 134  * @brief Clear the entire dictionary.
 135  */
 136 void hashtable_clear(
 137     HashTable* hashTable ///< "this" pointer.
 138 );
 139
 140 /**
 141  * @brief Destroy the dictionary: clear it, and free hashes array.
 142  */
 143 void hashtable_destroy(
 144     HashTable* hashTable ///< "this" pointer.
 145 );
 146
 147 #endif