mDNSMacOSX/dnssec_v2/utilities/list/list.c

   1 //
   2 //  list.c
   3 //  mDNSResponder
   4 //
   5 //  Copyright (c) 2020 Apple Inc. All rights reserved.
   6 //
   7
   8 #pragma mark - Includes
   9 #include "mDNSEmbeddedAPI.h"
  10 #if MDNSRESPONDER_SUPPORTS(APPLE, DNSSECv2)
  11 #include "list.h"
  12
  13 #pragma mark - list_init
  14 mDNSexport void
  15 list_init(list_t * const _Nonnull list_to_init, const mDNSu32 new_data_size) {
  16         // use dummy head and tail to handle the corner case such as adding node to empty list
  17         list_to_init->head_ptr                  = &(list_to_init->head);
  18         list_to_init->tail_ptr                  = &(list_to_init->tail);
  19         list_to_init->head_ptr->next    = list_to_init->tail_ptr;
  20         list_to_init->tail_ptr->prev    = list_to_init->head_ptr;
  21         // data size is used to prevent from adding different structures into list
  22         list_to_init->data_size                 = new_data_size;
  23 }
  24
  25 #pragma mark - list_append_uinitialized
  26 mDNSexport mStatus
  27 list_append_uinitialized(list_t * const _Nonnull list_ptr, const mDNSu32 new_data_size, void * _Nullable * _Nonnull out_data_ptr) {
  28         mStatus                 error           = mStatus_NoError;
  29         list_node_t *   node_ptr        = mDNSNULL;
  30         list_node_t *   real_tail       = mDNSNULL;
  31
  32         require_action(list_ptr->data_size == new_data_size, exit, error = mStatus_BadParamErr);
  33
  34         node_ptr = malloc(offsetof(list_node_t, data) + new_data_size);
  35         require_action(node_ptr != mDNSNULL, exit, error = mStatus_NoMemoryErr);
  36
  37         *out_data_ptr = &node_ptr->data;
  38
  39         real_tail                                       = list_ptr->tail_ptr->prev;
  40         real_tail->next                         = node_ptr;
  41         node_ptr->prev                          = real_tail;
  42         node_ptr->next                          = list_ptr->tail_ptr;
  43         list_ptr->tail_ptr->prev        = node_ptr;
  44
  45 exit:
  46         if (error != mStatus_NoError && node_ptr != mDNSNULL) free(node_ptr);
  47         return error;
  48 }
  49
  50 #pragma mark - list_prepend_uinitialized
  51 mDNSexport mStatus
  52 list_prepend_uinitialized(list_t * const _Nonnull list_ptr, const mDNSu32 new_data_size, void * _Nullable * _Nonnull out_data_ptr) {
  53         mStatus                 error           = mStatus_NoError;
  54         list_node_t *   node_ptr        = mDNSNULL;
  55         list_node_t *   real_head       = mDNSNULL;
  56
  57         require_action(list_ptr->data_size == new_data_size, exit, error = mStatus_BadParamErr);
  58
  59         node_ptr = malloc(offsetof(list_node_t, data) + new_data_size);
  60         require_action(node_ptr != mDNSNULL, exit, error = mStatus_NoMemoryErr);
  61
  62         *out_data_ptr = &node_ptr->data;
  63
  64         real_head                                       = list_ptr->head_ptr->next;
  65         real_head->prev                         = node_ptr;
  66         node_ptr->next                          = real_head;
  67         node_ptr->prev                          = list_ptr->head_ptr;
  68         list_ptr->head_ptr->next        = node_ptr;
  69
  70 exit:
  71         if (error != mDNSNULL && node_ptr != mDNSNULL) free(node_ptr);
  72         return error;
  73 }
  74
  75 #pragma mark - list_append_node
  76 mDNSexport void
  77 list_append_node(list_t * const _Nonnull list_ptr, list_node_t * const _Nonnull node_ptr) {
  78         node_ptr->prev                                  = list_ptr->head_ptr;
  79         node_ptr->next                                  = list_ptr->head_ptr->next;
  80         list_ptr->head_ptr->next->prev  = node_ptr;
  81         list_ptr->head_ptr->next                = node_ptr;
  82 }
  83
  84 #pragma mark - list_prepend_node
  85 mDNSexport void
  86 list_prepend_node(list_t *const _Nonnull list_ptr, list_node_t * const _Nonnull node_ptr) {
  87         node_ptr->prev                                  = list_ptr->tail_ptr->prev;
  88         node_ptr->next                                  = list_ptr->tail_ptr;
  89         list_ptr->tail_ptr->prev->next  = node_ptr;
  90         list_ptr->tail_ptr->prev                = node_ptr;
  91 }
  92
  93 #pragma mark - list_append_node_at_node
  94 mDNSexport void
  95 list_append_node_at_node(list_node_t * const _Nonnull original_node, list_node_t * const _Nonnull added_node) {
  96         list_node_t * const original_next = original_node->next;
  97
  98         added_node->prev        = original_node;
  99         added_node->next        = original_next;
 100         original_node->next     = added_node;
 101         original_next->prev     = added_node;
 102 }
 103
 104 #pragma mark - list_prepend_node_at_node
 105 mDNSexport void
 106 list_prepend_node_at_node(list_node_t * const _Nonnull original_node, list_node_t * const _Nonnull added_node) {
 107         list_node_t * const original_prev = original_node->prev;
 108
 109         added_node->prev        = original_prev;
 110         added_node->next        = original_node;
 111         original_prev->next     = added_node;
 112         original_node->prev     = added_node;
 113 }
 114
 115 #pragma mark - list_concatenate
 116 mDNSexport void
 117 list_concatenate(list_t * const _Nonnull dst_list, list_t * const _Nonnull src_list) {
 118         list_node_t *dst_last_node      = dst_list->tail_ptr->prev;
 119         list_node_t *src_first_node     = src_list->head_ptr->next;
 120         list_node_t *src_last_node      = src_list->tail_ptr->prev;
 121
 122         if (list_empty(src_list)) {
 123                 return;
 124         }
 125
 126         src_list->head_ptr->next        = src_list->tail_ptr;
 127         src_list->tail_ptr->prev        = src_list->head_ptr;
 128
 129         dst_last_node->next                     = src_first_node;
 130         src_first_node->prev            = dst_last_node;
 131         src_last_node->next                     = dst_list->tail_ptr;
 132         dst_list->tail_ptr->prev        = src_last_node;
 133 }
 134
 135 #pragma mark - node_list_sort
 136 mDNSlocal void
 137 node_list_sort(list_node_t * _Nullable * const _Nonnull in_out_list_ptr, list_sort_comparator_t comparator);
 138
 139 #pragma mark - node_list_tail
 140 mDNSlocal list_node_t *
 141 node_list_tail(list_node_t * _Nonnull list_ptr);
 142
 143 #pragma mark - list_sort
 144 mDNSexport void
 145 list_sort(list_t * const _Nonnull list_ptr, list_sort_comparator_t comparator) {
 146         list_node_t *real_head = list_ptr->head_ptr->next;
 147
 148         if (list_empty(list_ptr)) {
 149                 return;
 150         }
 151
 152         list_ptr->tail_ptr->prev->next  = mDNSNULL;
 153         list_ptr->head_ptr->next                = list_ptr->tail_ptr;
 154         list_ptr->tail_ptr->prev                = list_ptr->head_ptr;
 155
 156         node_list_sort(&real_head, comparator);
 157
 158         list_ptr->head_ptr->next                = real_head;
 159         list_ptr->tail_ptr->prev                = node_list_tail(real_head);
 160         real_head->prev                                 = list_ptr->head_ptr;
 161         list_ptr->tail_ptr->prev->next  = list_ptr->tail_ptr;
 162 }
 163
 164 #pragma mark - front_back_split
 165 mDNSlocal void
 166 front_back_split(list_node_t * const _Nonnull list_ptr, list_node_t **out_front, list_node_t **out_back);
 167
 168 #pragma mark - sorted_merge
 169 mDNSlocal list_node_t *
 170 sorted_merge(list_node_t * _Nullable left, list_node_t * _Nullable right, list_sort_comparator_t comparator);
 171
 172 #pragma mark - node_list_sort
 173 mDNSlocal void
 174 node_list_sort(list_node_t * _Nullable * const _Nonnull in_out_list_ptr, list_sort_comparator_t comparator) {
 175         list_node_t *list_ptr = *in_out_list_ptr;
 176         list_node_t *front_half;
 177         list_node_t *back_half;
 178
 179         if (list_ptr == mDNSNULL || list_ptr->next == mDNSNULL)
 180                 return;
 181
 182         front_back_split(list_ptr, &front_half, &back_half);
 183
 184         node_list_sort(&front_half, comparator);
 185         node_list_sort(&back_half, comparator);
 186
 187         *in_out_list_ptr = sorted_merge(front_half, back_half, comparator);
 188 }
 189
 190 #pragma mark - front_back_split
 191 mDNSlocal void
 192 front_back_split(
 193         list_node_t * const _Nonnull        list_ptr,
 194         list_node_t * _Nullable * _Nonnull  out_front,
 195         list_node_t * _Nullable * _Nonnull  out_back) {
 196
 197         list_node_t *fast = list_ptr->next;
 198         list_node_t *slow = list_ptr;
 199
 200         while (fast != mDNSNULL) {
 201                 fast = fast->next;
 202                 if (fast != mDNSNULL) {
 203                         slow = slow->next;
 204                         fast = fast->next;
 205                 }
 206         }
 207
 208         *out_front      = list_ptr;
 209         *out_back       = slow->next;
 210         slow->next      = mDNSNULL;
 211 }
 212
 213 #pragma mark - sorted_merge
 214 mDNSlocal list_node_t *
 215 sorted_merge(list_node_t * _Nullable left, list_node_t * _Nullable right, list_sort_comparator_t comparator) {
 216         list_node_t *sorted_list;
 217         list_node_t *tail;
 218         mDNSs8 cmp_result;
 219
 220         if (left == mDNSNULL) {
 221                 return right;
 222         } else if (right == mDNSNULL) {
 223                 return left;
 224         }
 225
 226         cmp_result = comparator(left, right);
 227         if (cmp_result <= 0) {
 228                 sorted_list = left;
 229                 tail            = left;
 230                 left            = left->next;
 231         } else {
 232                 // cmp_result > 0
 233                 sorted_list     = right;
 234                 tail            = right;
 235                 right           = right->next;
 236         }
 237
 238         while (left != mDNSNULL && right != mDNSNULL) {
 239                 cmp_result = comparator(left, right);
 240                 if (cmp_result <= 0) {
 241                         tail->next      = left;
 242                         tail            = left;
 243                         left            = left->next;
 244                 } else {
 245                         // cmp_result > 0
 246                         tail->next      = right;
 247                         tail            = right;
 248                         right           = right->next;
 249                 }
 250         }
 251
 252         if (left != mDNSNULL) {
 253                 tail->next = left;
 254         } else {
 255                 tail->next = right;
 256         }
 257
 258         return sorted_list;
 259 }
 260
 261 #pragma mark - node_list_tail
 262 mDNSlocal list_node_t *
 263 node_list_tail(list_node_t * _Nonnull list_ptr) {
 264         while (list_ptr->next != mDNSNULL) {
 265                 list_ptr = list_ptr->next;
 266         }
 267
 268         return list_ptr;
 269 }
 270
 271 #pragma mark - list_node_detach
 272 mDNSexport void
 273 list_node_detach(list_node_t * const _Nonnull node) {
 274         list_node_t *prev = node->prev;
 275         list_node_t *next = node->next;
 276         prev->next = next;
 277         next->prev = prev;
 278 }
 279
 280 #pragma mark - list_node_delete
 281 mDNSexport void
 282 list_node_delete(list_node_t * const _Nonnull node_ptr) {
 283         list_node_t *prev;
 284         list_node_t *next;
 285
 286         prev = node_ptr->prev;
 287         next = node_ptr->next;
 288
 289         prev->next = next;
 290         next->prev = prev;
 291
 292         free(node_ptr);
 293 }
 294
 295 #pragma mark - list_node_delete_all
 296 mDNSexport void
 297 list_node_delete_all(list_t * const _Nonnull list_ptr) {
 298         list_node_t *next_node;
 299         for (list_node_t * node = list_get_first(list_ptr); !list_has_ended(list_ptr, node); node = next_node) {
 300                 next_node = list_next(node);
 301                 list_node_delete(node);
 302         }
 303 }
 304
 305 #pragma mark - list_delete_node_with_data_ptr
 306 mDNSexport mStatus
 307 list_delete_node_with_data_ptr(list_t * const _Nonnull list_ptr, void * const _Nonnull data) {
 308         mStatus error = mStatus_NoSuchKey;
 309
 310         for (list_node_t *ptr = list_get_first(list_ptr); !list_has_ended(list_ptr, ptr); ptr = list_next(ptr)) {
 311                 if (data == &ptr->data) {
 312                         list_node_delete(ptr);
 313                         error = mStatus_NoError;
 314                         break;
 315                 }
 316         }
 317
 318         return error;
 319 }
 320
 321 #pragma mark - list_empty
 322 mDNSexport mDNSBool
 323 list_empty(const list_t * const _Nonnull list_ptr) {
 324         return list_ptr->head_ptr->next == list_ptr->tail_ptr;
 325 }
 326
 327 #pragma mark - list_count_node
 328 mDNSexport mDNSu32
 329 list_count_node(const list_t *const _Nonnull list_ptr) {
 330         mDNSu32 count = 0;
 331
 332         if (list_empty(list_ptr)) {
 333                 return 0;
 334         }
 335
 336         for (list_node_t *ptr = list_get_first(list_ptr); !list_has_ended(list_ptr, ptr); ptr = list_next(ptr)) {
 337                 count++;
 338         }
 339
 340         return count;
 341 }
 342
 343 #pragma mark - list_get_first
 344 mDNSexport list_node_t * _Nullable
 345 list_get_first(const list_t * const _Nonnull list_ptr) {
 346         if (list_empty(list_ptr)) {
 347                 return mDNSNULL;
 348         }
 349
 350         return list_ptr->head_ptr->next;
 351 }
 352
 353 #pragma mark - list_get_last
 354 mDNSexport list_node_t * _Nullable
 355 list_get_last(const list_t * const _Nonnull list_ptr) {
 356         if (list_empty(list_ptr)) {
 357                 return mDNSNULL;
 358         }
 359
 360         return list_ptr->tail_ptr->prev;
 361 }
 362
 363 #pragma mark - list_next
 364 mDNSexport list_node_t * _Nonnull
 365 list_next(const list_node_t * const _Nonnull node_ptr) {
 366         return node_ptr->next;
 367 }
 368
 369 #pragma mark - list_has_ended
 370 mDNSexport mDNSBool
 371 list_has_ended(const list_t * const _Nonnull list_ptr, const list_node_t * const _Nullable node_ptr) {
 372         if (node_ptr == mDNSNULL) {
 373                 return mDNStrue;
 374         }
 375         return node_ptr == list_ptr->tail_ptr;
 376 }
 377
 378 #pragma mark - list_uninit
 379 mDNSexport void
 380 list_uninit(list_t * const _Nonnull list_ptr) {
 381         list_node_delete_all(list_ptr);
 382
 383         list_ptr->data_size                     = 0;
 384         list_ptr->head_ptr->next        = mDNSNULL;
 385         list_ptr->tail_ptr->prev        = mDNSNULL;
 386         list_ptr->head_ptr                      = mDNSNULL;
 387         list_ptr->tail_ptr                      = mDNSNULL;
 388 }
 389
 390 #endif // MDNSRESPONDER_SUPPORTS(APPLE, DNSSECv2)