src/Set.h

   1 /**
   2  * @file Set.h
   3  */
   4
   5 #ifndef CGDS_SET_H
   6 #define CGDS_SET_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 set.
  16  */
  17 typedef struct SetCell {
  18   void* item; ///< Generic data (key) contained in this cell.
  19   struct SetCell* next; ///< Pointer to next cell in the list.
  20 } SetCell;
  21
  22 /**
  23  * @brief Generic set containing any data (of same size).
  24  */
  25 typedef struct Set {
  26   UInt size; ///< Count elements in the set.
  27   size_t dataSize; ///< Size of a set cell element in bytes.
  28   size_t hashSize; ///< (Maximum) Number of stored hash keys.
  29   SetCell** head; ///< Pointers to the first cell in a list.
  30   UInt (*getHash)(void*, size_t); ///< Custom hash function (optional)
  31 } Set;
  32
  33 /**
  34  * @brief Initialize an empty set.
  35  */
  36 void _set_init(
  37   Set* set, ///< "this" pointer.
  38   size_t dataSize, ///< Size in bytes of a set element.
  39   size_t hashSize, ///< (Maximum) Number of stored hash keys.
  40   UInt (*getHash)(void*, size_t); ///< Custom hash function (optional)
  41 );
  42
  43 /**
  44  * @brief Return an allocated and initialized set.
  45  */
  46 Set* _set_new(
  47   size_t dataSize, ///< Size in bytes of a set element.
  48   size_t hashSize, ///< (Maximum) Number of stored hash keys.
  49   UInt (*getHash)(void*, size_t) ///< Custom hash function (nullable)
  50 );
  51
  52 /**
  53  * @brief Return an allocated and initialized set.
  54  * @param type Type of a set element (int, char*, ...).
  55  * @param hsize Size of the internal pointers array.
  56  * @param getHash Custom hash function (nullable)
  57  *
  58  * Usage: Set* set_new(<Type> type, UInt hash_size, UInt (*getHash)(void*, size_t))
  59  */
  60 #define set_new(type, hsize, getHash) \
  61   _set_new(sizeof(type), hsize, getHash)
  62
  63 /**
  64  * @brief Copy constructor (shallow copy, ok for basic types).
  65  */
  66 Set* set_copy(
  67   Set* set ///< "this" pointer.
  68 );
  69
  70 /**
  71  * @brief Check if the set is empty.
  72  */
  73 bool set_empty(
  74   Set* set ///< "this" pointer.
  75 );
  76
  77 /**
  78  * @brief Return current size.
  79  */
  80 UInt set_size(
  81   Set* set ///< "this" pointer.
  82 );
  83
  84 /**
  85  * @brief Lookup given element.
  86  *
  87  * Usage: bool set_has(Set* set, void* item)
  88  */
  89 bool set_has(
  90   Set* set, ///< "this" pointer.
  91   void* item ///< Element to search.
  92 );
  93
  94 /**
  95  * @brief Add an item to the set.
  96  */
  97 void _set_add(
  98   Set* set, ///< "this" pointer.
  99   void* item ///< Element to add.
 100 );
 101
 102 /**
 103  * @brief Add a key to the set.
 104  * @param set "this" pointer.
 105  * @param item Element to add.
 106  *
 107  * Usage: void set_add(Set* set, void item)
 108  */
 109 #define set_add(set, item) \
 110 { \
 111   typeof(item) tmp = item; \
 112   _set_add(set, &tmp); \
 113 }
 114
 115 /**
 116  * @brief Remove the given item.
 117  */
 118 void _set_delete(
 119   Set* set, ///< "this" pointer.
 120   void* item ///< Element to delete.
 121 );
 122
 123 /**
 124  * @brief Remove the given item.
 125  * @param item Element to remove.
 126  *
 127  * Usage: void set_delete(Set* set, void item)
 128  */
 129 #define set_delete(set, item) \
 130 { \
 131   typeof(item) tmp = item; \
 132   _set_delete(set, &tmp); \
 133 }
 134
 135 /**
 136  * @brief Initialize a vector with (pointers to) set elements.
 137  */
 138 Vector* set_to_vector(
 139   Set* set ///< "this" pointer.
 140 );
 141
 142 /**
 143  * @brief Clear the entire set.
 144  */
 145 void set_clear(
 146   Set* set ///< "this" pointer.
 147 );
 148
 149 /**
 150  * @brief Destroy the set: clear it, and free hashes array.
 151  */
 152 void set_destroy(
 153   Set* set ///< "this" pointer.
 154 );
 155
 156 #endif