diff options
Diffstat (limited to 'pceplib/pcep_utils_ordered_list.c')
-rw-r--r-- | pceplib/pcep_utils_ordered_list.c | 326 |
1 files changed, 326 insertions, 0 deletions
diff --git a/pceplib/pcep_utils_ordered_list.c b/pceplib/pcep_utils_ordered_list.c new file mode 100644 index 0000000..81eb614 --- /dev/null +++ b/pceplib/pcep_utils_ordered_list.c @@ -0,0 +1,326 @@ +/* + * This file is part of the PCEPlib, a PCEP protocol library. + * + * Copyright (C) 2020 Volta Networks https://voltanet.io/ + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <https://www.gnu.org/licenses/>. + * + * Author : Brady Johnson <brady@voltanet.io> + * + */ + + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <stdio.h> +#include <string.h> + +#include "pcep_utils_logging.h" +#include "pcep_utils_memory.h" +#include "pcep_utils_ordered_list.h" + +/* Compare function that simply compares pointers. + * return: + * < 0 if new_entry < list_entry + * == 0 if new_entry == list_entry (new_entry will be inserted after + * list_entry) > 0 if new_entry > list_entry + */ +int pointer_compare_function(void *list_entry, void *new_entry) +{ + return (char *)new_entry - (char *)list_entry; +} + +ordered_list_handle *ordered_list_initialize(ordered_compare_function func_ptr) +{ + ordered_list_handle *handle = + pceplib_malloc(PCEPLIB_INFRA, sizeof(ordered_list_handle)); + memset(handle, 0, sizeof(ordered_list_handle)); + handle->head = NULL; + handle->num_entries = 0; + handle->compare_function = func_ptr; + + return handle; +} + + +/* free all the ordered_list_node resources and the ordered_list_handle. + * it is assumed that the user is responsible fore freeing the data + * pointed to by the nodes. + */ +void ordered_list_destroy(ordered_list_handle *handle) +{ + if (handle == NULL) { + return; + } + + ordered_list_node *node = handle->head; + ordered_list_node *next; + + while (node != NULL) { + next = node->next_node; + pceplib_free(PCEPLIB_INFRA, node); + node = next; + } + + pceplib_free(PCEPLIB_INFRA, handle); +} + + +ordered_list_node *ordered_list_add_node(ordered_list_handle *handle, + void *data) +{ + if (handle == NULL) { + pcep_log( + LOG_WARNING, + "%s: ordered_list_add_node, the list has not been initialized", + __func__); + return NULL; + } + handle->num_entries++; + + ordered_list_node *new_node = + pceplib_malloc(PCEPLIB_INFRA, sizeof(ordered_list_node)); + memset(new_node, 0, sizeof(ordered_list_node)); + new_node->data = data; + new_node->next_node = NULL; + + /* check if its an empty list */ + if (handle->head == NULL) { + handle->head = new_node; + + return new_node; + } + + ordered_list_node *prev_node = handle->head; + ordered_list_node *node = prev_node; + int compare_result; + + while (node != NULL) { + compare_result = handle->compare_function(node->data, data); + if (compare_result < 0) { + /* insert the node */ + new_node->next_node = node; + if (handle->head == node) { + /* add it at the beginning of the list */ + handle->head = new_node; + } else { + prev_node->next_node = new_node; + } + + return new_node; + } + + /* keep searching with the next node in the list */ + prev_node = node; + node = node->next_node; + } + + /* at the end of the list, add it here */ + prev_node->next_node = new_node; + + return new_node; +} + + +ordered_list_node *ordered_list_find2(ordered_list_handle *handle, void *data, + ordered_compare_function compare_func) +{ + if (handle == NULL) { + pcep_log( + LOG_WARNING, + "%s: ordered_list_find2, the list has not been initialized", + __func__); + return NULL; + } + + ordered_list_node *node = handle->head; + int compare_result; + + while (node != NULL) { + compare_result = compare_func(node->data, data); + if (compare_result == 0) { + return node; + } else { + node = node->next_node; + } + } + + return NULL; +} + + +ordered_list_node *ordered_list_find(ordered_list_handle *handle, void *data) +{ + if (handle == NULL) { + pcep_log( + LOG_WARNING, + "%s: ordered_list_find, the list has not been initialized", + __func__); + return NULL; + } + + return ordered_list_find2(handle, data, handle->compare_function); +} + + +void *ordered_list_remove_first_node(ordered_list_handle *handle) +{ + if (handle == NULL) { + pcep_log( + LOG_WARNING, + "%s: ordered_list_remove_first_node, the list has not been initialized", + __func__); + return NULL; + } + + if (handle->head == NULL) { + return NULL; + } + handle->num_entries--; + + void *data = handle->head->data; + ordered_list_node *next_node = handle->head->next_node; + pceplib_free(PCEPLIB_INFRA, handle->head); + handle->head = next_node; + + return data; +} + + +void * +ordered_list_remove_first_node_equals2(ordered_list_handle *handle, void *data, + ordered_compare_function compare_func) +{ + if (handle == NULL) { + pcep_log( + LOG_WARNING, + "%s: ordered_list_remove_first_node_equals2, the list has not been initialized", + __func__); + return NULL; + } + + if (handle->head == NULL) { + return NULL; + } + + ordered_list_node *prev_node = handle->head; + ordered_list_node *node = prev_node; + bool keep_walking = true; + void *return_data = NULL; + int compare_result; + + while (node != NULL && keep_walking) { + compare_result = compare_func(node->data, data); + if (compare_result == 0) { + return_data = node->data; + keep_walking = false; + handle->num_entries--; + + /* adjust the corresponding pointers accordingly */ + if (handle->head == node) { + /* its the first node in the list */ + handle->head = node->next_node; + } else { + prev_node->next_node = node->next_node; + } + + pceplib_free(PCEPLIB_INFRA, node); + } else { + prev_node = node; + node = node->next_node; + } + } + + return return_data; +} + + +void *ordered_list_remove_first_node_equals(ordered_list_handle *handle, + void *data) +{ + if (handle == NULL) { + pcep_log( + LOG_WARNING, + "%s: ordered_list_remove_first_node_equals, the list has not been initialized", + __func__); + return NULL; + } + + return ordered_list_remove_first_node_equals2(handle, data, + handle->compare_function); +} + + +void *ordered_list_remove_node(ordered_list_handle *handle, + ordered_list_node *prev_node, + ordered_list_node *node_toRemove) +{ + if (handle == NULL) { + pcep_log( + LOG_WARNING, + "%s: ordered_list_remove_node, the list has not been initialized", + __func__); + return NULL; + } + + if (handle->head == NULL) { + return NULL; + } + + void *return_data = node_toRemove->data; + handle->num_entries--; + + if (node_toRemove == handle->head) { + handle->head = node_toRemove->next_node; + } else { + prev_node->next_node = node_toRemove->next_node; + } + + pceplib_free(PCEPLIB_INFRA, node_toRemove); + + return return_data; +} + +void *ordered_list_remove_node2(ordered_list_handle *handle, + ordered_list_node *node_to_remove) +{ + if (handle == NULL) { + pcep_log( + LOG_WARNING, + "%s: ordered_list_remove_node2, the list has not been initialized", + __func__); + return NULL; + } + + if (handle->head == NULL) { + return NULL; + } + + ordered_list_node *node = handle->head; + ordered_list_node *prev_node = handle->head; + + while (node != NULL) { + if (node == node_to_remove) { + return (ordered_list_remove_node(handle, prev_node, + node)); + } else { + prev_node = node; + node = node->next_node; + } + } + + return NULL; +} |