mDNSMacOSX/dnssec_v2/utilities/list/list.h

   1 //
   2 //  list.h
   3 //  mDNSResponder
   4 //
   5 //  Copyright (c) 2020 Apple Inc. All rights reserved.
   6 //
   7
   8 #ifndef LIST_H
   9 #define LIST_H
  10
  11 #pragma mark - Includes
  12 #include <stdint.h>
  13 #include <stdio.h>
  14 #include <AssertMacros.h>       // for require_* macro
  15 #include "mDNSEmbeddedAPI.h"    // for mStatus
  16 #if MDNSRESPONDER_SUPPORTS(APPLE, DNSSECv2)
  17
  18 #pragma mark - Structures
  19
  20
  21
  22 #pragma mark list_node_t
  23 /*!
  24  *      @brief
  25  *              A node in the list_t.
  26  */
  27 typedef struct list_node list_node_t;
  28 struct list_node {
  29         list_node_t *   _Nullable       prev;
  30         list_node_t *   _Nullable       next;
  31         mDNSu8                                          data[0];        // the actual data will be stored starting from data, so list_node_t->data can access it
  32 };
  33
  34 #pragma mark list_t
  35 /*!
  36  *      @brief
  37  *              A structure that represents a generic doublely linked list.
  38  */
  39 typedef struct list list_t;
  40 struct list {
  41         mDNSu32                                         data_size;      // to check if the data put into the list matches the size of actual structure
  42         list_node_t *   _Nullable       head_ptr;
  43         list_node_t *   _Nullable       tail_ptr;
  44         list_node_t                                     head;           // dummy head will be pointed by head_ptr
  45         list_node_t                                     tail;           // dummy tail will be pointed by tail_ptr
  46 };
  47
  48 #pragma mark - Functions
  49
  50
  51
  52 #pragma mark list_init
  53 /*!
  54  *      @brief
  55  *              Initializes list_t, must be called before using the list
  56  *
  57  *      @param list_to_init
  58  *              The pointer to the unintialized list
  59  *
  60  *      @param new_data_size
  61  *              the size of the data that will be put into the list
  62  *
  63  *      @discussion
  64  *              After the list is initialized with "new_data_size", we could only put the same data structure that has the same "data_size" into the list
  65  */
  66 mDNSexport void
  67 list_init(list_t * const _Nonnull list_to_init, const mDNSu32 new_data_size);
  68
  69 #pragma mark list_append_uinitialized
  70 /*!
  71  *      @brief
  72  *              Appends a node at the end of the list, and return a memory pointer that can be used to store the data structure.
  73  *
  74  *      @param list_ptr
  75  *              The pointer to the list.
  76  *
  77  *      @param new_data_size
  78  *              The size of the data structure that will be appended into the list.
  79  *
  80  *      @param out_data_ptr
  81  *              The output pointer to the memory location that can be used to save the data structure.
  82  *
  83  *      @return
  84  *              mStatus_NoError if everything works fine, or other error codes defined in mStatus.
  85
  86  *      @discussion
  87  *              The returned memory pointer can be used to initialize a data structure which will stored in the list.
  88  */
  89 mDNSexport mStatus
  90 list_append_uinitialized(list_t * const _Nonnull list_ptr, const mDNSu32 new_data_size, void * _Nullable * _Nonnull out_data_ptr);
  91
  92 #pragma mark list_prepend_uinitialized
  93 /*!
  94  *      @brief
  95  *              Prepends a node at the start of the list, and return a memory pointer that can be used to store the data structure.
  96  *
  97  *      @param list_ptr
  98  *              The pointer to the list.
  99  *
 100  *      @param new_data_size
 101  *              The size of the data structure that will be appended into the list.
 102  *
 103  *      @param out_data_ptr
 104  *              The output pointer to the memory location that can be used to save the data structure.
 105  *
 106  *      @return
 107  *              mStatus_NoError if everything works fine, or other error codes defined in mStatus.
 108
 109  *      @discussion
 110  *              The returned memory pointer can be used to initialize a data structure which will be stored in the list.
 111  */
 112 mDNSexport mStatus
 113 list_prepend_uinitialized(list_t * const _Nonnull list_ptr, const mDNSu32 new_data_size, void * _Nullable * _Nonnull out_data_ptr);
 114
 115 #pragma mark list_append_node
 116 /*!
 117  *      @brief
 118  *              Given a list_node_t structure, insert it in the end of the list.
 119  *      @param list_ptr
 120  *              The pointer to the list.
 121  *      @param node_ptr
 122  *              The list_node_t structure to be inserted.
 123  */
 124 mDNSexport void
 125 list_append_node(list_t * const _Nonnull list_ptr, list_node_t * const _Nonnull node_ptr);
 126
 127 /*!
 128  *      @brief
 129  *              Given a list_node_t structure, insert it in the start of the list.
 130  *      @param list_ptr
 131  *              The pointer to the list.
 132  *      @param node_ptr
 133  *              The list_node_t structure to be inserted.
 134  */
 135 #pragma mark list_prepend_node
 136 mDNSexport void
 137 list_prepend_node(list_t * const _Nonnull list_ptr, list_node_t * const _Nonnull node_ptr);
 138
 139 #pragma mark list_append_node_at_node
 140 /*!
 141  *      @brief
 142  *              Append the list_node_t after the given node in the list
 143  *      @param original_node
 144  *              The node to be appended after.
 145  *      @param added_node
 146  *              The node to append.
 147  */
 148 mDNSexport void
 149 list_append_node_at_node(list_node_t * const _Nonnull original_node, list_node_t * const _Nonnull added_node);
 150
 151 #pragma mark list_prepend_node_at_node
 152 /*!
 153  *      @brief
 154  *              Prepend the list_node_t before the given node in the list
 155  *      @param original_node
 156  *              The node to be appended after.
 157  *      @param added_node
 158  *              The node to prepend.
 159  */
 160 mDNSexport void
 161 list_prepend_node_at_node(list_node_t * const _Nonnull original_node, list_node_t * const _Nonnull added_node);
 162
 163 #pragma mark list_concatenate
 164 /*!
 165  *      @brief
 166  *              Concatenate two lists together.
 167  *      @param dst_list
 168  *              The list to concatenate with.
 169  *      @param src_list
 170  *              The list to concatenate with.
 171  *      @discussion
 172  *              The concatenation result is the dst_list.
 173  */
 174 mDNSexport void
 175 list_concatenate(list_t * const _Nonnull dst_list, list_t * const _Nonnull src_list);
 176
 177 #pragma mark list_sort_comparator_t
 178 /*!
 179  *      @brief
 180  *              The sort comparator for the list.
 181  *      @param left
 182  *              The list_node_t to be compared.
 183  *      @param right
 184  *              The list_node_t to be compared.
 185  *      @discussion
 186  *              If the comparator returns -1, 0 and 1, -1 means left is less than right, 0 means left is equal to right, 1 means left is greater than right
 187  */
 188 typedef mDNSs8 (* _Nonnull list_sort_comparator_t)(const list_node_t * _Nonnull const left, const list_node_t * _Nonnull const right);
 189
 190 #pragma mark list_sort
 191 /*!
 192  *      @brief
 193  *              Sort the node in the list according to the comparator.
 194  *      @param list_ptr
 195  *              The list to be sorted.
 196  *      @param comparator
 197  *              The list_sort_comparator_t that defines the sort order.
 198  *      @discussion
 199  *              If the comparator returns -1, 0 and 1, -1 means left is less than right, 0 means left is equal to right, 1 means left is greater than right
 200  */
 201 mDNSexport void
 202 list_sort(list_t * const _Nonnull list_ptr, list_sort_comparator_t comparator);
 203
 204 #pragma mark list_node_detach
 205 /*!
 206  *      @brief
 207  *              Detach the list_node_t from the list
 208  *      @param node
 209  *              The node to be detached
 210  *      @discussion
 211  *              It will only seperate the node from the list,  the node itself still exists.
 212  */
 213 mDNSexport void
 214 list_node_detach(list_node_t * const _Nonnull node);
 215
 216 #pragma mark list_node_delete
 217 /*!
 218  *      @brief
 219  *              Delete the current node that is in the list.
 220  *      @param node_ptr
 221  *              The pointer of the node to be deleted.
 222  *      @discussion
 223  *              This function must be used for the node that is in the list.
 224  */
 225 mDNSexport void
 226 list_node_delete(list_node_t * const _Nonnull node_ptr);
 227
 228 #pragma mark list_node_delete_all
 229 /*!
 230  *      @brief
 231  *              Delete all nodes in the list
 232  *      @param list_ptr
 233  *              The pointer to the list.
 234  */
 235 mDNSexport void
 236 list_node_delete_all(list_t * const _Nonnull list_ptr);
 237
 238 #pragma mark list_delete_node_with_data_ptr
 239 /*!
 240  *      @brief
 241  *              Delete the node in the list that contains the data.
 242  *      @param list_ptr
 243  *              The pointer to the list that will delete the node.
 244  *      @param data
 245  *              The pointer to the data that one node in list contains.
 246  *      @return
 247  *              return mStatus_NoError if the node is found and deleted from the list, return mStatus_NoSuchKey if the node does not exist.
 248  *      @discussion
 249  *              The function will scan through the list, compare the data field of node with the "data" parameter.
 250  */
 251 mDNSexport mStatus
 252 list_delete_node_with_data_ptr(list_t * const _Nonnull list_ptr, void * const _Nonnull data);
 253
 254 #pragma mark list_empty
 255 /*!
 256  *      @brief
 257  *              Test if the list is empty or not.
 258  *      @param list_ptr
 259  *              The list to test.
 260  *      @return
 261  *              Returns true if the lis is empty, returns false if the list has nodes inside.
 262  */
 263 mDNSexport mDNSBool
 264 list_empty(const list_t * const _Nonnull list_ptr);
 265
 266 #pragma mark list_count_node
 267 /*!
 268  *      @brief
 269  *              Get the number of nodes in the list.
 270  *      @param list_ptr
 271  *              The list to count node.
 272  *      @return
 273  *              The number of nodes.
 274  */
 275 mDNSexport mDNSu32
 276 list_count_node(const list_t *const _Nonnull list_ptr);
 277
 278 #pragma mark list_get_first
 279 /*!
 280  *      @brief
 281  *              Get the first node in the list.
 282  *      @param list_ptr
 283  *              The pointer to the list.
 284  *      @return
 285  *              The first list_node_t in the list, if the list is empty, NULL is returned.
 286  */
 287 mDNSexport list_node_t * _Nullable
 288 list_get_first(const list_t * const _Nonnull list_ptr);
 289
 290 #pragma mark list_get_last
 291 /*!
 292  *      @brief
 293  *              Get the last node in the list.
 294  *      @param list_ptr
 295  *              The pointer to the list.
 296  *      @return
 297  *              The last list_node_t in the list, if the list is empty, NULL is returned.
 298  */
 299 mDNSexport list_node_t * _Nullable
 300 list_get_last(const list_t * const _Nonnull list_ptr);
 301
 302 #pragma mark list_next
 303 /*!
 304  *      @brief
 305  *              Get the next node of the current node in the list.
 306  *      @param node_ptr
 307  *              The pointer to the current node.
 308  *      @return
 309  *              The next node.
 310  */
 311 mDNSexport list_node_t * _Nonnull
 312 list_next(const list_node_t * const _Nonnull node_ptr);
 313
 314 #pragma mark list_has_ended
 315 /*!
 316  *      @brief
 317  *              Test if the current node has reached the end of the list.
 318  *      @param list_ptr
 319  *              The pointer to the list.
 320  *      @param node_ptr
 321  *              The pointer to the node.
 322  *      @return
 323  *              Returns true if the node_ptr points to the end of the list, returns false if it has more nodes coming next.
 324  */
 325 mDNSexport mDNSBool
 326 list_has_ended(const list_t * const _Nonnull list_ptr, const list_node_t * const _Nullable node_ptr);
 327
 328 #pragma mark list_uninit
 329 /*!
 330  *      @brief
 331  *              Delete all the existing nodes in the list, and untialize the list structure.
 332  *      @param list_ptr
 333  *              The pointer to the list that will be uninitialized.
 334  */
 335 mDNSexport void
 336 list_uninit(list_t * const _Nonnull list_ptr);
 337
 338 #endif // MDNSRESPONDER_SUPPORTS(APPLE, DNSSECv2)
 339 #endif // LIST_H