1 // SPDX-License-Identifier: LGPL-2.1-or-later
3 * This file is part of the PCEPlib, a PCEP protocol library.
5 * Copyright (C) 2020 Volta Networks https://voltanet.io/
7 * Author : Brady Johnson <brady@voltanet.io>
19 #include "pcep_utils_logging.h"
20 #include "pcep_utils_memory.h"
21 #include "pcep_utils_ordered_list.h"
23 /* Compare function that simply compares pointers.
25 * < 0 if new_entry < list_entry
26 * == 0 if new_entry == list_entry (new_entry will be inserted after
27 * list_entry) > 0 if new_entry > list_entry
29 int pointer_compare_function(void *list_entry
, void *new_entry
)
31 return (char *)new_entry
- (char *)list_entry
;
34 ordered_list_handle
*ordered_list_initialize(ordered_compare_function func_ptr
)
36 ordered_list_handle
*handle
=
37 pceplib_malloc(PCEPLIB_INFRA
, sizeof(ordered_list_handle
));
38 memset(handle
, 0, sizeof(ordered_list_handle
));
40 handle
->num_entries
= 0;
41 handle
->compare_function
= func_ptr
;
47 /* free all the ordered_list_node resources and the ordered_list_handle.
48 * it is assumed that the user is responsible fore freeing the data
49 * pointed to by the nodes.
51 void ordered_list_destroy(ordered_list_handle
*handle
)
57 ordered_list_node
*node
= handle
->head
;
58 ordered_list_node
*next
;
60 while (node
!= NULL
) {
61 next
= node
->next_node
;
62 pceplib_free(PCEPLIB_INFRA
, node
);
66 pceplib_free(PCEPLIB_INFRA
, handle
);
70 ordered_list_node
*ordered_list_add_node(ordered_list_handle
*handle
,
76 "%s: ordered_list_add_node, the list has not been initialized",
80 handle
->num_entries
++;
82 ordered_list_node
*new_node
=
83 pceplib_malloc(PCEPLIB_INFRA
, sizeof(ordered_list_node
));
84 memset(new_node
, 0, sizeof(ordered_list_node
));
85 new_node
->data
= data
;
86 new_node
->next_node
= NULL
;
88 /* check if its an empty list */
89 if (handle
->head
== NULL
) {
90 handle
->head
= new_node
;
95 ordered_list_node
*prev_node
= handle
->head
;
96 ordered_list_node
*node
= prev_node
;
99 while (node
!= NULL
) {
100 compare_result
= handle
->compare_function(node
->data
, data
);
101 if (compare_result
< 0) {
102 /* insert the node */
103 new_node
->next_node
= node
;
104 if (handle
->head
== node
) {
105 /* add it at the beginning of the list */
106 handle
->head
= new_node
;
108 prev_node
->next_node
= new_node
;
114 /* keep searching with the next node in the list */
116 node
= node
->next_node
;
119 /* at the end of the list, add it here */
120 prev_node
->next_node
= new_node
;
126 ordered_list_node
*ordered_list_find2(ordered_list_handle
*handle
, void *data
,
127 ordered_compare_function compare_func
)
129 if (handle
== NULL
) {
132 "%s: ordered_list_find2, the list has not been initialized",
137 ordered_list_node
*node
= handle
->head
;
140 while (node
!= NULL
) {
141 compare_result
= compare_func(node
->data
, data
);
142 if (compare_result
== 0) {
145 node
= node
->next_node
;
153 ordered_list_node
*ordered_list_find(ordered_list_handle
*handle
, void *data
)
155 if (handle
== NULL
) {
158 "%s: ordered_list_find, the list has not been initialized",
163 return ordered_list_find2(handle
, data
, handle
->compare_function
);
167 void *ordered_list_remove_first_node(ordered_list_handle
*handle
)
169 if (handle
== NULL
) {
172 "%s: ordered_list_remove_first_node, the list has not been initialized",
177 if (handle
->head
== NULL
) {
180 handle
->num_entries
--;
182 void *data
= handle
->head
->data
;
183 ordered_list_node
*next_node
= handle
->head
->next_node
;
184 pceplib_free(PCEPLIB_INFRA
, handle
->head
);
185 handle
->head
= next_node
;
192 ordered_list_remove_first_node_equals2(ordered_list_handle
*handle
, void *data
,
193 ordered_compare_function compare_func
)
195 if (handle
== NULL
) {
198 "%s: ordered_list_remove_first_node_equals2, the list has not been initialized",
203 if (handle
->head
== NULL
) {
207 ordered_list_node
*prev_node
= handle
->head
;
208 ordered_list_node
*node
= prev_node
;
209 bool keep_walking
= true;
210 void *return_data
= NULL
;
213 while (node
!= NULL
&& keep_walking
) {
214 compare_result
= compare_func(node
->data
, data
);
215 if (compare_result
== 0) {
216 return_data
= node
->data
;
217 keep_walking
= false;
218 handle
->num_entries
--;
220 /* adjust the corresponding pointers accordingly */
221 if (handle
->head
== node
) {
222 /* its the first node in the list */
223 handle
->head
= node
->next_node
;
225 prev_node
->next_node
= node
->next_node
;
228 pceplib_free(PCEPLIB_INFRA
, node
);
231 node
= node
->next_node
;
239 void *ordered_list_remove_first_node_equals(ordered_list_handle
*handle
,
242 if (handle
== NULL
) {
245 "%s: ordered_list_remove_first_node_equals, the list has not been initialized",
250 return ordered_list_remove_first_node_equals2(handle
, data
,
251 handle
->compare_function
);
255 void *ordered_list_remove_node(ordered_list_handle
*handle
,
256 ordered_list_node
*prev_node
,
257 ordered_list_node
*node_toRemove
)
259 if (handle
== NULL
) {
262 "%s: ordered_list_remove_node, the list has not been initialized",
267 if (handle
->head
== NULL
) {
271 void *return_data
= node_toRemove
->data
;
272 handle
->num_entries
--;
274 if (node_toRemove
== handle
->head
) {
275 handle
->head
= node_toRemove
->next_node
;
277 prev_node
->next_node
= node_toRemove
->next_node
;
280 pceplib_free(PCEPLIB_INFRA
, node_toRemove
);
285 void *ordered_list_remove_node2(ordered_list_handle
*handle
,
286 ordered_list_node
*node_to_remove
)
288 if (handle
== NULL
) {
291 "%s: ordered_list_remove_node2, the list has not been initialized",
296 if (handle
->head
== NULL
) {
300 ordered_list_node
*node
= handle
->head
;
301 ordered_list_node
*prev_node
= handle
->head
;
303 while (node
!= NULL
) {
304 if (node
== node_to_remove
) {
305 return (ordered_list_remove_node(handle
, prev_node
,
309 node
= node
->next_node
;