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