]>
Commit | Line | Data |
---|---|---|
74971473 JG |
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 | ||
1f8031f7 DL |
24 | #ifdef HAVE_CONFIG_H |
25 | #include "config.h" | |
26 | #endif | |
27 | ||
74971473 JG |
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 | } |