pceplib/pcep_utils_ordered_list.c

   1 /*
   2  * This file is part of the PCEPlib, a PCEP protocol library.
   3  *
   4  * Copyright (C) 2020 Volta Networks https://voltanet.io/
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
  18  *
  19  * Author : Brady Johnson <brady@voltanet.io>
  20  *
  21  */
  22
  23
  24 #ifdef HAVE_CONFIG_H
  25 #include "config.h"
  26 #endif
  27
  28 #include <stdio.h>
  29 #include <string.h>
  30
  31 #include "pcep_utils_logging.h"
  32 #include "pcep_utils_memory.h"
  33 #include "pcep_utils_ordered_list.h"
  34
  35 /* Compare function that simply compares pointers.
  36  * return:
  37  *   < 0  if new_entry  < list_entry
  38  *   == 0 if new_entry == list_entry (new_entry will be inserted after
  39  * list_entry) > 0  if new_entry  > list_entry
  40  */
  41 int pointer_compare_function(void *list_entry, void *new_entry)
  42 {
  43         return (char *)new_entry - (char *)list_entry;
  44 }
  45
  46 ordered_list_handle *ordered_list_initialize(ordered_compare_function func_ptr)
  47 {
  48         ordered_list_handle *handle =
  49                 pceplib_malloc(PCEPLIB_INFRA, sizeof(ordered_list_handle));
  50         memset(handle, 0, sizeof(ordered_list_handle));
  51         handle->head = NULL;
  52         handle->num_entries = 0;
  53         handle->compare_function = func_ptr;
  54
  55         return handle;
  56 }
  57
  58
  59 /* free all the ordered_list_node resources and the ordered_list_handle.
  60  * it is assumed that the user is responsible fore freeing the data
  61  * pointed to by the nodes.
  62  */
  63 void ordered_list_destroy(ordered_list_handle *handle)
  64 {
  65         if (handle == NULL) {
  66                 return;
  67         }
  68
  69         ordered_list_node *node = handle->head;
  70         ordered_list_node *next;
  71
  72         while (node != NULL) {
  73                 next = node->next_node;
  74                 pceplib_free(PCEPLIB_INFRA, node);
  75                 node = next;
  76         }
  77
  78         pceplib_free(PCEPLIB_INFRA, handle);
  79 }
  80
  81
  82 ordered_list_node *ordered_list_add_node(ordered_list_handle *handle,
  83                                          void *data)
  84 {
  85         if (handle == NULL) {
  86                 pcep_log(
  87                         LOG_WARNING,
  88                         "%s: ordered_list_add_node, the list has not been initialized",
  89                         __func__);
  90                 return NULL;
  91         }
  92         handle->num_entries++;
  93
  94         ordered_list_node *new_node =
  95                 pceplib_malloc(PCEPLIB_INFRA, sizeof(ordered_list_node));
  96         memset(new_node, 0, sizeof(ordered_list_node));
  97         new_node->data = data;
  98         new_node->next_node = NULL;
  99
 100         /* check if its an empty list */
 101         if (handle->head == NULL) {
 102                 handle->head = new_node;
 103
 104                 return new_node;
 105         }
 106
 107         ordered_list_node *prev_node = handle->head;
 108         ordered_list_node *node = prev_node;
 109         int compare_result;
 110
 111         while (node != NULL) {
 112                 compare_result = handle->compare_function(node->data, data);
 113                 if (compare_result < 0) {
 114                         /* insert the node */
 115                         new_node->next_node = node;
 116                         if (handle->head == node) {
 117                                 /* add it at the beginning of the list */
 118                                 handle->head = new_node;
 119                         } else {
 120                                 prev_node->next_node = new_node;
 121                         }
 122
 123                         return new_node;
 124                 }
 125
 126                 /* keep searching with the next node in the list */
 127                 prev_node = node;
 128                 node = node->next_node;
 129         }
 130
 131         /* at the end of the list, add it here */
 132         prev_node->next_node = new_node;
 133
 134         return new_node;
 135 }
 136
 137
 138 ordered_list_node *ordered_list_find2(ordered_list_handle *handle, void *data,
 139                                       ordered_compare_function compare_func)
 140 {
 141         if (handle == NULL) {
 142                 pcep_log(
 143                         LOG_WARNING,
 144                         "%s: ordered_list_find2, the list has not been initialized",
 145                         __func__);
 146                 return NULL;
 147         }
 148
 149         ordered_list_node *node = handle->head;
 150         int compare_result;
 151
 152         while (node != NULL) {
 153                 compare_result = compare_func(node->data, data);
 154                 if (compare_result == 0) {
 155                         return node;
 156                 } else {
 157                         node = node->next_node;
 158                 }
 159         }
 160
 161         return NULL;
 162 }
 163
 164
 165 ordered_list_node *ordered_list_find(ordered_list_handle *handle, void *data)
 166 {
 167         if (handle == NULL) {
 168                 pcep_log(
 169                         LOG_WARNING,
 170                         "%s: ordered_list_find, the list has not been initialized",
 171                         __func__);
 172                 return NULL;
 173         }
 174
 175         return ordered_list_find2(handle, data, handle->compare_function);
 176 }
 177
 178
 179 void *ordered_list_remove_first_node(ordered_list_handle *handle)
 180 {
 181         if (handle == NULL) {
 182                 pcep_log(
 183                         LOG_WARNING,
 184                         "%s: ordered_list_remove_first_node, the list has not been initialized",
 185                         __func__);
 186                 return NULL;
 187         }
 188
 189         if (handle->head == NULL) {
 190                 return NULL;
 191         }
 192         handle->num_entries--;
 193
 194         void *data = handle->head->data;
 195         ordered_list_node *next_node = handle->head->next_node;
 196         pceplib_free(PCEPLIB_INFRA, handle->head);
 197         handle->head = next_node;
 198
 199         return data;
 200 }
 201
 202
 203 void *
 204 ordered_list_remove_first_node_equals2(ordered_list_handle *handle, void *data,
 205                                        ordered_compare_function compare_func)
 206 {
 207         if (handle == NULL) {
 208                 pcep_log(
 209                         LOG_WARNING,
 210                         "%s: ordered_list_remove_first_node_equals2, the list has not been initialized",
 211                         __func__);
 212                 return NULL;
 213         }
 214
 215         if (handle->head == NULL) {
 216                 return NULL;
 217         }
 218
 219         ordered_list_node *prev_node = handle->head;
 220         ordered_list_node *node = prev_node;
 221         bool keep_walking = true;
 222         void *return_data = NULL;
 223         int compare_result;
 224
 225         while (node != NULL && keep_walking) {
 226                 compare_result = compare_func(node->data, data);
 227                 if (compare_result == 0) {
 228                         return_data = node->data;
 229                         keep_walking = false;
 230                         handle->num_entries--;
 231
 232                         /* adjust the corresponding pointers accordingly */
 233                         if (handle->head == node) {
 234                                 /* its the first node in the list */
 235                                 handle->head = node->next_node;
 236                         } else {
 237                                 prev_node->next_node = node->next_node;
 238                         }
 239
 240                         pceplib_free(PCEPLIB_INFRA, node);
 241                 } else {
 242                         prev_node = node;
 243                         node = node->next_node;
 244                 }
 245         }
 246
 247         return return_data;
 248 }
 249
 250
 251 void *ordered_list_remove_first_node_equals(ordered_list_handle *handle,
 252                                             void *data)
 253 {
 254         if (handle == NULL) {
 255                 pcep_log(
 256                         LOG_WARNING,
 257                         "%s: ordered_list_remove_first_node_equals, the list has not been initialized",
 258                         __func__);
 259                 return NULL;
 260         }
 261
 262         return ordered_list_remove_first_node_equals2(handle, data,
 263                                                       handle->compare_function);
 264 }
 265
 266
 267 void *ordered_list_remove_node(ordered_list_handle *handle,
 268                                ordered_list_node *prev_node,
 269                                ordered_list_node *node_toRemove)
 270 {
 271         if (handle == NULL) {
 272                 pcep_log(
 273                         LOG_WARNING,
 274                         "%s: ordered_list_remove_node, the list has not been initialized",
 275                         __func__);
 276                 return NULL;
 277         }
 278
 279         if (handle->head == NULL) {
 280                 return NULL;
 281         }
 282
 283         void *return_data = node_toRemove->data;
 284         handle->num_entries--;
 285
 286         if (node_toRemove == handle->head) {
 287                 handle->head = node_toRemove->next_node;
 288         } else {
 289                 prev_node->next_node = node_toRemove->next_node;
 290         }
 291
 292         pceplib_free(PCEPLIB_INFRA, node_toRemove);
 293
 294         return return_data;
 295 }
 296
 297 void *ordered_list_remove_node2(ordered_list_handle *handle,
 298                                 ordered_list_node *node_to_remove)
 299 {
 300         if (handle == NULL) {
 301                 pcep_log(
 302                         LOG_WARNING,
 303                         "%s: ordered_list_remove_node2, the list has not been initialized",
 304                         __func__);
 305                 return NULL;
 306         }
 307
 308         if (handle->head == NULL) {
 309                 return NULL;
 310         }
 311
 312         ordered_list_node *node = handle->head;
 313         ordered_list_node *prev_node = handle->head;
 314
 315         while (node != NULL) {
 316                 if (node == node_to_remove) {
 317                         return (ordered_list_remove_node(handle, prev_node,
 318                                                          node));
 319                 } else {
 320                         prev_node = node;
 321                         node = node->next_node;
 322                 }
 323         }
 324
 325         return NULL;
 326 }