src/List.h

   1 /**
   2  * @file List.h
   3  */
   4
   5 #ifndef CGDS_LIST_H
   6 #define CGDS_LIST_H
   7
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include "cgds/safe_alloc.h"
  11 #include "cgds/types.h"
  12
  13 ////////////////
  14 // List logic //
  15 ////////////////
  16
  17 /**
  18  * @brief Cell of a double-linked list.
  19  */
  20 typedef struct ListCell {
  21     void* data; ///< Generic data contained in this cell.
  22     struct ListCell* prev; ///< Pointer to previous cell in the list.
  23     struct ListCell* next; ///< Pointer to next cell in the list.
  24 } ListCell;
  25
  26 /**
  27  * @brief Double-linked list data structure.
  28  */
  29 typedef struct List {
  30     UInt size; ///< Count elements in the list.
  31     size_t dataSize; ///< Size of a list cell element in bytes.
  32     ListCell* head; ///< Pointer to the first cell in the list.
  33     ListCell* tail; ///< Pointer to the last cell in the list.
  34 } List;
  35
  36 /**
  37  * @brief Initialize an empty list.
  38  */
  39 void _list_init(
  40     List* list, ///< "this" pointer.
  41     size_t dataSize ///< Size of a list cell elements in bytes.
  42 );
  43
  44 /**
  45  * @brief Return an allocated and initialized list.
  46  * @param dataSize Size in bytes of a list element.
  47  */
  48 List* _list_new(
  49     size_t dataSize ///< Size of a list cell elements in bytes.
  50 );
  51
  52 /**
  53  * @brief Return an allocated and initialized list.
  54  * @param type Type of a list element (int, char*, ...).
  55  *
  56  * Usage: List* list_new(<Type> type)
  57  */
  58 #define list_new(type) \
  59     _list_new(sizeof(type))
  60
  61 /**
  62  * @brief Copy constructor (shallow copy, ok for basic types).
  63  */
  64 List* list_copy(
  65     List* list ///< "this" pointer.
  66 );
  67
  68 /**
  69  * @brief Check if the list is empty.
  70  */
  71 bool list_empty(
  72     List* list ///< "this" pointer.
  73 );
  74
  75 /**
  76  * @brief return the size of current list.
  77  */
  78 UInt list_size(
  79     List* list ///< "this" pointer.
  80 );
  81
  82 /**
  83  * @brief Get data at the given list cell argument.
  84  */
  85 void* _list_get(
  86     ListCell* listCell ///< Pointer to a cell inside "this" list.
  87 );
  88
  89 /**
  90  * @brief Get data at the given list cell argument.
  91  * @param listCell Pointer to a cell inside "this" list.
  92  * @param data Data to be assigned.
  93  *
  94  * Usage: void list_get(ListCell* listCell, void data)
  95  */
  96 #define list_get(listCell, data) \
  97 { \
  98     void* pData = _list_get(listCell); \
  99     data = *((typeof(&data))pData); \
 100 }
 101
 102 /**
 103  * @brief Set data at the given list cell argument.
 104  */
 105 void _list_set(
 106     List* list, ///< "this" pointer.
 107     ListCell* listCell, ///< Pointer to a cell inside "this" list.
 108     void* data ///< Pointer to data to be set.
 109 );
 110
 111 /**
 112  * @brief Set data at the given list cell argument.
 113  * @param list "this" pointer.
 114  * @param listCell Pointer to a cell inside "this" list.
 115  * @param data Data to be set.
 116  *
 117  * Usage: void list_set(List* list, ListCell* listCell, void data);
 118  */
 119 #define list_set(list, listCell, data) \
 120 { \
 121     typeof((data)) tmp = data; \
 122     _list_set(list, listCell, &tmp); \
 123 }
 124
 125 /**
 126  * @brief Add data to the list when list is empty.
 127  */
 128 void _list_insert_first_element(
 129     List* list, ///< "this" pointer.
 130     void* data ///< Pointer to data to be added
 131 );
 132
 133 /**
 134  * @brief Add data before list cell argument.
 135  */
 136 void _list_insert_before(
 137     List* list, ///< "this" pointer.
 138     ListCell* listCell, ///< Pointer to a cell inside "this" list.
 139     void* data ///< Pointer to data to be added.
 140 );
 141
 142 /**
 143  * @brief Add data before list cell argument.
 144  * @param list "this" pointer.
 145  * @param listCell Pointer to a cell inside "this" list.
 146  * @param data Data to be inserted.
 147  *
 148  * Usage: void list_insert_before(List* list, ListCell* listCell, void data)
 149  */
 150 #define list_insert_before(list, listCell, data) \
 151 { \
 152     typeof((data)) tmp = data; \
 153     _list_insert_before(list, listCell, &tmp); \
 154 }
 155
 156 /**
 157  * @brief Add data after list cell argument.
 158  */
 159 void _list_insert_after(
 160     List* list, ///< "this" pointer.
 161     ListCell* listCell, ///< Pointer to a cell inside "this" list.
 162     void* data ///< Pointer to data to be inserted.
 163 );
 164
 165 /**
 166  * @brief Add data after list cell argument.
 167  * @param list "this" pointer.
 168  * @param listCell Pointer to a cell inside "this" list.
 169  * @param data Data to be inserted.
 170  *
 171  * Usage: void list_insert_after(List* list, ListCell* listCell, void data)
 172  */
 173 #define list_insert_after(list, listCell, data) \
 174 { \
 175     typeof((data)) tmp = data; \
 176     _list_insert_after(list, listCell, &tmp); \
 177 }
 178
 179 /**
 180  * @brief Add data at the beginning of the list.
 181  */
 182 void _list_insert_front(
 183     List* list, ///< "this" pointer.
 184     void* data ///< Pointer to data to be inserted.
 185 );
 186
 187 /**
 188  * @brief Add data at the beginning of the list.
 189  * @param list "this" pointer.
 190  * @param data Data to be inserted.
 191  *
 192  * Usage: void list_insert_front(List* list, void data)
 193  */
 194 #define list_insert_front(list, data) \
 195 { \
 196     typeof((data)) tmp = data; \
 197     _list_insert_front(list, &tmp); \
 198 }
 199
 200 /**
 201  * @brief Add data at the end of the list.
 202  */
 203 void _list_insert_back(
 204     List* list, ///< "this" pointer.
 205     void* data ///< Pointer to data to be inserted.
 206 );
 207
 208 /**
 209  * @brief Add data at the end of the list.
 210  * @param list "this" pointer.
 211  * @param data Data to be inserted.
 212  *
 213  * Usage: void list_insert_back(List* list, void data)
 214  */
 215 #define list_insert_back(list, data) \
 216 { \
 217     typeof((data)) tmp = data; \
 218     _list_insert_back(list, &tmp); \
 219 }
 220
 221 /**
 222  * @brief Remove data at position given by 'listCell'.
 223  */
 224 void list_remove(
 225     List* list, ///< "this" pointer.
 226     ListCell* listCell ///< Pointer to a cell inside "this" list.
 227 );
 228
 229 /**
 230  * @brief Remove data at the beginning of the list.
 231  */
 232 void list_remove_front(
 233     List* list ///< "this" pointer.
 234 );
 235
 236 /**
 237  * @brief Remove data at the end of the list.
 238  */
 239 void list_remove_back(
 240     List* list ///< "this" pointer.
 241 );
 242
 243 /**
 244  * @brief Clear the entire list.
 245  */
 246 void list_clear(
 247     List* list ///< "this" pointer.
 248 );
 249
 250 /**
 251  * @brief Destroy the list: clear it, and free 'list' pointer.
 252  */
 253 void list_destroy(
 254     List* list ///< "this" pointer.
 255 );
 256
 257 ////////////////////
 258 // Iterator logic //
 259 ////////////////////
 260
 261 /**
 262  * @brief Iterator on a double-linked list.
 263  */
 264 typedef struct ListIterator {
 265     List* list; ///< The list to be iterate.
 266     ListCell* current; ///< The current iterated list cell.
 267 } ListIterator;
 268
 269 /**
 270  * @brief Obtain an iterator object, starting at list beginning.
 271  */
 272 ListIterator* list_get_iterator(
 273     List* list ///< Pointer to the list to be iterated over.
 274 );
 275
 276 /**
 277  * @brief (Re)set current position inside list to head.
 278  */
 279 void listI_reset_head(
 280     ListIterator* listI ///< "this" pointer.
 281 );
 282
 283 /**
 284  * @brief (Re)set current position inside list to tail.
 285  */
 286 void listI_reset_tail(
 287     ListIterator* listI ///< "this" pointer.
 288 );
 289
 290 /**
 291  * @brief Tell if there is some data at the current index.
 292  */
 293 bool listI_has_data(
 294     ListIterator* listI ///< "this" pointer.
 295 );
 296
 297 /**
 298  * @brief Return data contained in the current list cell.
 299  * @param listI "this" pointer.
 300  * @param data Data to be assigned.
 301  *
 302  * Usage: void listI_get(ListIterator* listI, void data)
 303  */
 304 #define listI_get(listI, data) \
 305     list_get(listI->current, data)
 306
 307 /**
 308  * @brief Set data at the current iterator position.
 309  * @param listI "this" pointer
 310  * @param data Data to assign.
 311  *
 312  * Usage: void listI_set(ListIterator* listI, void data);
 313  */
 314 #define listI_set(listI, data) \
 315     list_set(listI->list, listI->current, data)
 316
 317 /**
 318  * @brief Add data before current list cell.
 319  * @param listI "this" pointer
 320  * @param data Data to be inserted.
 321  *
 322  * Usage: void listI_insert_before(ListIteratorI* listI, void data)
 323  */
 324 #define listI_insert_before(listI, data) \
 325     list_insert_before(listI->list, listI->current, data)
 326
 327 /**
 328  * @brief Add data after current list cell.
 329  * @param listI "this" pointer
 330  * @param data Data to be inserted.
 331  *
 332  * Usage: void listI_insert_after(ListIteratorI* listI, void data)
 333  */
 334 #define listI_insert_after(listI, data) \
 335     list_insert_after(listI->list, listI->current, data)
 336
 337 /**
 338  * @brief Type to encode a direction (forward / backward).
 339  */
 340 typedef enum {
 341     BACKWARD = -1, ///< Move toward head.
 342     FORWARD = 1 ///< Move toward tail.
 343 } Direction;
 344
 345 /**
 346  * @brief Remove data at the current iterator position.
 347  */
 348 void listI_remove(
 349     ListIterator* listI, ///< "this" pointer.
 350     Direction direction ///< Indicate the position of iterator after removal.
 351 );
 352
 353 /**
 354  * @brief Move current iterator position forward (toward tail).
 355  */
 356 void listI_move_next(
 357     ListIterator* listI ///< "this" pointer.
 358 );
 359
 360 /**
 361  * @brief Move current iterator position backward (toward head).
 362  */
 363 void listI_move_prev(
 364     ListIterator* listI ///< "this" pointer.
 365 );
 366
 367 /**
 368  * @brief Free memory allocated for the iterator.
 369  */
 370 void listI_destroy(
 371     ListIterator* listI ///< "this" pointer.
 372 );
 373
 374 #endif