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