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 { \
  58   _hashtable_new(sizeof(type), hsize); \
  59 }
  60
  61 /**
  62  * @brief Copy constructor (shallow copy, ok for basic types).
  63  */
  64 HashTable* hashtable_copy(
  65   HashTable* hashTable ///< "this" pointer.
  66 );
  67
  68 /**
  69  * @brief Check if the dictionary is empty.
  70  */
  71 bool hashtable_empty(
  72   HashTable* hastTable ///< "this" pointer.
  73 );
  74
  75 /**
  76  * @brief Return current size.
  77  */
  78 UInt hashtable_size(
  79   HashTable* hastTable ///< "this" pointer.
  80 );
  81
  82 /**
  83  * @brief Lookup element of given key.
  84  */
  85 void* _hashtable_get(
  86   HashTable* hashTable, ///< "this" pointer.
  87   char* key ///< Key of the element to retrieve.
  88 );
  89
  90 /**
  91  * @brief Lookup element of given key.
  92  * @param hashTable "this" pointer.
  93  * @param key Key of the element to retrieve..
  94  * @param data 'out' variable to contain the result.
  95  *
  96  * Usage: void hashtable_get(HashTable* hashTable, char* key, void data)
  97  */
  98 #define hashtable_get(hashTable, key, data) \
  99 { \
 100   void* pData = _hashtable_get(hashTable, key); \
 101   data = *((typeof(&data))pData); \
 102 }
 103
 104 /**
 105  * @brief Add the entry (key, value) to dictionary.
 106  */
 107 void _hashtable_set(
 108   HashTable* hashTable, ///< "this" pointer.
 109   char* key, ///< Key of the element to add or modify.
 110   void* data ///< Pointer to new data at given key.
 111 );
 112
 113 /**
 114  * @brief Add the entry (key, value) to dictionary.
 115  * @param hashTable "this" pointer.
 116  * @param key Key of the element to add or modify.
 117  * @param data New data at given key.
 118  *
 119  * Usage: void hashtable_set(HashTable* hashTable, char* key, void data)
 120  */
 121 #define hashtable_set(hashTable, key, data) \
 122 { \
 123   typeof((data)) tmp = data; \
 124   _hashtable_set(hashTable, key, &tmp); \
 125 }
 126
 127 /**
 128  * @brief Remove the given key (+ associated value).
 129  */
 130 void hashtable_delete(
 131   HashTable* hashTable, ///< "this" pointer.
 132   char* key ///< Key of the element to delete.
 133 );
 134
 135 /**
 136  * @brief Clear the entire dictionary.
 137  */
 138 void hashtable_clear(
 139   HashTable* hashTable ///< "this" pointer.
 140 );
 141
 142 /**
 143  * @brief Destroy the dictionary: clear it, and free hashes array.
 144  */
 145 void hashtable_destroy(
 146   HashTable* hashTable ///< "this" pointer.
 147 );
 148
 149 #endif