2 * This file is part of the PCEPlib, a PCEP protocol library.
4 * Copyright (C) 2020 Volta Networks https://voltanet.io/
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.
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.
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/>.
19 * Author : Brady Johnson <brady@voltanet.io>
31 #include "pcep_utils_logging.h"
32 #include "pcep_utils_memory.h"
33 #include "pcep_utils_ordered_list.h"
35 /* Compare function that simply compares pointers.
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
41 int pointer_compare_function(void *list_entry
, void *new_entry
)
43 return (char *)new_entry
- (char *)list_entry
;
46 ordered_list_handle
*ordered_list_initialize(ordered_compare_function func_ptr
)
48 ordered_list_handle
*handle
=
49 pceplib_malloc(PCEPLIB_INFRA
, sizeof(ordered_list_handle
));
50 memset(handle
, 0, sizeof(ordered_list_handle
));
52 handle
->num_entries
= 0;
53 handle
->compare_function
= func_ptr
;
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.
63 void ordered_list_destroy(ordered_list_handle
*handle
)
69 ordered_list_node
*node
= handle
->head
;
70 ordered_list_node
*next
;
72 while (node
!= NULL
) {
73 next
= node
->next_node
;
74 pceplib_free(PCEPLIB_INFRA
, node
);
78 pceplib_free(PCEPLIB_INFRA
, handle
);
82 ordered_list_node
*ordered_list_add_node(ordered_list_handle
*handle
,
88 "%s: ordered_list_add_node, the list has not been initialized",
92 handle
->num_entries
++;
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
;
100 /* check if its an empty list */
101 if (handle
->head
== NULL
) {
102 handle
->head
= new_node
;
107 ordered_list_node
*prev_node
= handle
->head
;
108 ordered_list_node
*node
= prev_node
;
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
;
120 prev_node
->next_node
= new_node
;
126 /* keep searching with the next node in the list */
128 node
= node
->next_node
;
131 /* at the end of the list, add it here */
132 prev_node
->next_node
= new_node
;
138 ordered_list_node
*ordered_list_find2(ordered_list_handle
*handle
, void *data
,
139 ordered_compare_function compare_func
)
141 if (handle
== NULL
) {
144 "%s: ordered_list_find2, the list has not been initialized",
149 ordered_list_node
*node
= handle
->head
;
152 while (node
!= NULL
) {
153 compare_result
= compare_func(node
->data
, data
);
154 if (compare_result
== 0) {
157 node
= node
->next_node
;
165 ordered_list_node
*ordered_list_find(ordered_list_handle
*handle
, void *data
)
167 if (handle
== NULL
) {
170 "%s: ordered_list_find, the list has not been initialized",
175 return ordered_list_find2(handle
, data
, handle
->compare_function
);
179 void *ordered_list_remove_first_node(ordered_list_handle
*handle
)
181 if (handle
== NULL
) {
184 "%s: ordered_list_remove_first_node, the list has not been initialized",
189 if (handle
->head
== NULL
) {
192 handle
->num_entries
--;
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
;
204 ordered_list_remove_first_node_equals2(ordered_list_handle
*handle
, void *data
,
205 ordered_compare_function compare_func
)
207 if (handle
== NULL
) {
210 "%s: ordered_list_remove_first_node_equals2, the list has not been initialized",
215 if (handle
->head
== NULL
) {
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
;
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
--;
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
;
237 prev_node
->next_node
= node
->next_node
;
240 pceplib_free(PCEPLIB_INFRA
, node
);
243 node
= node
->next_node
;
251 void *ordered_list_remove_first_node_equals(ordered_list_handle
*handle
,
254 if (handle
== NULL
) {
257 "%s: ordered_list_remove_first_node_equals, the list has not been initialized",
262 return ordered_list_remove_first_node_equals2(handle
, data
,
263 handle
->compare_function
);
267 void *ordered_list_remove_node(ordered_list_handle
*handle
,
268 ordered_list_node
*prev_node
,
269 ordered_list_node
*node_toRemove
)
271 if (handle
== NULL
) {
274 "%s: ordered_list_remove_node, the list has not been initialized",
279 if (handle
->head
== NULL
) {
283 void *return_data
= node_toRemove
->data
;
284 handle
->num_entries
--;
286 if (node_toRemove
== handle
->head
) {
287 handle
->head
= node_toRemove
->next_node
;
289 prev_node
->next_node
= node_toRemove
->next_node
;
292 pceplib_free(PCEPLIB_INFRA
, node_toRemove
);
297 void *ordered_list_remove_node2(ordered_list_handle
*handle
,
298 ordered_list_node
*node_to_remove
)
300 if (handle
== NULL
) {
303 "%s: ordered_list_remove_node2, the list has not been initialized",
308 if (handle
->head
== NULL
) {
312 ordered_list_node
*node
= handle
->head
;
313 ordered_list_node
*prev_node
= handle
->head
;
315 while (node
!= NULL
) {
316 if (node
== node_to_remove
) {
317 return (ordered_list_remove_node(handle
, prev_node
,
321 node
= node
->next_node
;