]>
Commit | Line | Data |
---|---|---|
acddc0ed | 1 | // SPDX-License-Identifier: LGPL-2.1-or-later |
74971473 JG |
2 | /* |
3 | * This file is part of the PCEPlib, a PCEP protocol library. | |
4 | * | |
5 | * Copyright (C) 2020 Volta Networks https://voltanet.io/ | |
6 | * | |
74971473 JG |
7 | * Author : Brady Johnson <brady@voltanet.io> |
8 | * | |
9 | */ | |
10 | ||
11 | ||
1f8031f7 DL |
12 | #ifdef HAVE_CONFIG_H |
13 | #include "config.h" | |
14 | #endif | |
15 | ||
74971473 JG |
16 | #include <stdio.h> |
17 | #include <string.h> | |
18 | ||
19 | #include "pcep_utils_logging.h" | |
20 | #include "pcep_utils_memory.h" | |
21 | #include "pcep_utils_ordered_list.h" | |
22 | ||
23 | /* Compare function that simply compares pointers. | |
24 | * return: | |
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 | |
28 | */ | |
29 | int pointer_compare_function(void *list_entry, void *new_entry) | |
30 | { | |
31 | return (char *)new_entry - (char *)list_entry; | |
32 | } | |
33 | ||
34 | ordered_list_handle *ordered_list_initialize(ordered_compare_function func_ptr) | |
35 | { | |
36 | ordered_list_handle *handle = | |
37 | pceplib_malloc(PCEPLIB_INFRA, sizeof(ordered_list_handle)); | |
38 | memset(handle, 0, sizeof(ordered_list_handle)); | |
39 | handle->head = NULL; | |
40 | handle->num_entries = 0; | |
41 | handle->compare_function = func_ptr; | |
42 | ||
43 | return handle; | |
44 | } | |
45 | ||
46 | ||
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. | |
50 | */ | |
51 | void ordered_list_destroy(ordered_list_handle *handle) | |
52 | { | |
53 | if (handle == NULL) { | |
54 | return; | |
55 | } | |
56 | ||
57 | ordered_list_node *node = handle->head; | |
58 | ordered_list_node *next; | |
59 | ||
60 | while (node != NULL) { | |
61 | next = node->next_node; | |
62 | pceplib_free(PCEPLIB_INFRA, node); | |
63 | node = next; | |
64 | } | |
65 | ||
66 | pceplib_free(PCEPLIB_INFRA, handle); | |
67 | } | |
68 | ||
69 | ||
70 | ordered_list_node *ordered_list_add_node(ordered_list_handle *handle, | |
71 | void *data) | |
72 | { | |
73 | if (handle == NULL) { | |
74 | pcep_log( | |
75 | LOG_WARNING, | |
76 | "%s: ordered_list_add_node, the list has not been initialized", | |
77 | __func__); | |
78 | return NULL; | |
79 | } | |
80 | handle->num_entries++; | |
81 | ||
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; | |
87 | ||
88 | /* check if its an empty list */ | |
89 | if (handle->head == NULL) { | |
90 | handle->head = new_node; | |
91 | ||
92 | return new_node; | |
93 | } | |
94 | ||
95 | ordered_list_node *prev_node = handle->head; | |
96 | ordered_list_node *node = prev_node; | |
97 | int compare_result; | |
98 | ||
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; | |
107 | } else { | |
108 | prev_node->next_node = new_node; | |
109 | } | |
110 | ||
111 | return new_node; | |
112 | } | |
113 | ||
114 | /* keep searching with the next node in the list */ | |
115 | prev_node = node; | |
116 | node = node->next_node; | |
117 | } | |
118 | ||
119 | /* at the end of the list, add it here */ | |
120 | prev_node->next_node = new_node; | |
121 | ||
122 | return new_node; | |
123 | } | |
124 | ||
125 | ||
126 | ordered_list_node *ordered_list_find2(ordered_list_handle *handle, void *data, | |
127 | ordered_compare_function compare_func) | |
128 | { | |
129 | if (handle == NULL) { | |
130 | pcep_log( | |
131 | LOG_WARNING, | |
132 | "%s: ordered_list_find2, the list has not been initialized", | |
133 | __func__); | |
134 | return NULL; | |
135 | } | |
136 | ||
137 | ordered_list_node *node = handle->head; | |
138 | int compare_result; | |
139 | ||
140 | while (node != NULL) { | |
141 | compare_result = compare_func(node->data, data); | |
142 | if (compare_result == 0) { | |
143 | return node; | |
144 | } else { | |
145 | node = node->next_node; | |
146 | } | |
147 | } | |
148 | ||
149 | return NULL; | |
150 | } | |
151 | ||
152 | ||
153 | ordered_list_node *ordered_list_find(ordered_list_handle *handle, void *data) | |
154 | { | |
155 | if (handle == NULL) { | |
156 | pcep_log( | |
157 | LOG_WARNING, | |
158 | "%s: ordered_list_find, the list has not been initialized", | |
159 | __func__); | |
160 | return NULL; | |
161 | } | |
162 | ||
163 | return ordered_list_find2(handle, data, handle->compare_function); | |
164 | } | |
165 | ||
166 | ||
167 | void *ordered_list_remove_first_node(ordered_list_handle *handle) | |
168 | { | |
169 | if (handle == NULL) { | |
170 | pcep_log( | |
171 | LOG_WARNING, | |
172 | "%s: ordered_list_remove_first_node, the list has not been initialized", | |
173 | __func__); | |
174 | return NULL; | |
175 | } | |
176 | ||
177 | if (handle->head == NULL) { | |
178 | return NULL; | |
179 | } | |
180 | handle->num_entries--; | |
181 | ||
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; | |
186 | ||
187 | return data; | |
188 | } | |
189 | ||
190 | ||
191 | void * | |
192 | ordered_list_remove_first_node_equals2(ordered_list_handle *handle, void *data, | |
193 | ordered_compare_function compare_func) | |
194 | { | |
195 | if (handle == NULL) { | |
196 | pcep_log( | |
197 | LOG_WARNING, | |
198 | "%s: ordered_list_remove_first_node_equals2, the list has not been initialized", | |
199 | __func__); | |
200 | return NULL; | |
201 | } | |
202 | ||
203 | if (handle->head == NULL) { | |
204 | return NULL; | |
205 | } | |
206 | ||
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; | |
211 | int compare_result; | |
212 | ||
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--; | |
219 | ||
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; | |
224 | } else { | |
225 | prev_node->next_node = node->next_node; | |
226 | } | |
227 | ||
228 | pceplib_free(PCEPLIB_INFRA, node); | |
229 | } else { | |
230 | prev_node = node; | |
231 | node = node->next_node; | |
232 | } | |
233 | } | |
234 | ||
235 | return return_data; | |
236 | } | |
237 | ||
238 | ||
239 | void *ordered_list_remove_first_node_equals(ordered_list_handle *handle, | |
240 | void *data) | |
241 | { | |
242 | if (handle == NULL) { | |
243 | pcep_log( | |
244 | LOG_WARNING, | |
245 | "%s: ordered_list_remove_first_node_equals, the list has not been initialized", | |
246 | __func__); | |
247 | return NULL; | |
248 | } | |
249 | ||
250 | return ordered_list_remove_first_node_equals2(handle, data, | |
251 | handle->compare_function); | |
252 | } | |
253 | ||
254 | ||
255 | void *ordered_list_remove_node(ordered_list_handle *handle, | |
256 | ordered_list_node *prev_node, | |
257 | ordered_list_node *node_toRemove) | |
258 | { | |
259 | if (handle == NULL) { | |
260 | pcep_log( | |
261 | LOG_WARNING, | |
262 | "%s: ordered_list_remove_node, the list has not been initialized", | |
263 | __func__); | |
264 | return NULL; | |
265 | } | |
266 | ||
267 | if (handle->head == NULL) { | |
268 | return NULL; | |
269 | } | |
270 | ||
271 | void *return_data = node_toRemove->data; | |
272 | handle->num_entries--; | |
273 | ||
274 | if (node_toRemove == handle->head) { | |
275 | handle->head = node_toRemove->next_node; | |
276 | } else { | |
277 | prev_node->next_node = node_toRemove->next_node; | |
278 | } | |
279 | ||
280 | pceplib_free(PCEPLIB_INFRA, node_toRemove); | |
281 | ||
282 | return return_data; | |
283 | } | |
284 | ||
285 | void *ordered_list_remove_node2(ordered_list_handle *handle, | |
286 | ordered_list_node *node_to_remove) | |
287 | { | |
288 | if (handle == NULL) { | |
289 | pcep_log( | |
290 | LOG_WARNING, | |
291 | "%s: ordered_list_remove_node2, the list has not been initialized", | |
292 | __func__); | |
293 | return NULL; | |
294 | } | |
295 | ||
296 | if (handle->head == NULL) { | |
297 | return NULL; | |
298 | } | |
299 | ||
300 | ordered_list_node *node = handle->head; | |
301 | ordered_list_node *prev_node = handle->head; | |
302 | ||
303 | while (node != NULL) { | |
304 | if (node == node_to_remove) { | |
305 | return (ordered_list_remove_node(handle, prev_node, | |
306 | node)); | |
307 | } else { | |
308 | prev_node = node; | |
309 | node = node->next_node; | |
310 | } | |
311 | } | |
312 | ||
313 | return NULL; | |
314 | } |