/src/gnutls/gl/gl_anylinked_list2.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* Sequential list data type implemented by a linked list. |
2 | | Copyright (C) 2006-2025 Free Software Foundation, Inc. |
3 | | Written by Bruno Haible <bruno@clisp.org>, 2006. |
4 | | |
5 | | This file is free software: you can redistribute it and/or modify |
6 | | it under the terms of the GNU Lesser General Public License as |
7 | | published by the Free Software Foundation; either version 2.1 of the |
8 | | License, or (at your option) any later version. |
9 | | |
10 | | This file is distributed in the hope that it will be useful, |
11 | | but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 | | GNU Lesser General Public License for more details. |
14 | | |
15 | | You should have received a copy of the GNU Lesser General Public License |
16 | | along with this program. If not, see <https://www.gnu.org/licenses/>. */ |
17 | | |
18 | | /* Common code of gl_linked_list.c and gl_linkedhash_list.c. */ |
19 | | |
20 | | /* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such |
21 | | a way that a gl_list_t data structure may be used from within a signal |
22 | | handler. The operations allowed in the signal handler are: |
23 | | gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free. |
24 | | The list and node fields that are therefore accessed from the signal handler |
25 | | are: |
26 | | list->root, node->next, node->value. |
27 | | We are careful to make modifications to these fields only in an order |
28 | | that maintains the consistency of the list data structure at any moment, |
29 | | and we use 'volatile' assignments to prevent the compiler from reordering |
30 | | such assignments. */ |
31 | | #ifdef SIGNAL_SAFE_LIST |
32 | | # define ASYNCSAFE(type) *(type volatile *)& |
33 | | #else |
34 | | # define ASYNCSAFE(type) |
35 | | #endif |
36 | | |
37 | | /* -------------------------- gl_list_t Data Type -------------------------- */ |
38 | | |
39 | | static gl_list_t |
40 | | gl_linked_nx_create_empty (gl_list_implementation_t implementation, |
41 | | gl_listelement_equals_fn equals_fn, |
42 | | gl_listelement_hashcode_fn hashcode_fn, |
43 | | gl_listelement_dispose_fn dispose_fn, |
44 | | bool allow_duplicates) |
45 | 20 | { |
46 | 20 | struct gl_list_impl *list = |
47 | 20 | (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); |
48 | | |
49 | 20 | if (list == NULL) |
50 | 0 | return NULL; |
51 | | |
52 | 20 | list->base.vtable = implementation; |
53 | 20 | list->base.equals_fn = equals_fn; |
54 | 20 | list->base.hashcode_fn = hashcode_fn; |
55 | 20 | list->base.dispose_fn = dispose_fn; |
56 | 20 | list->base.allow_duplicates = allow_duplicates; |
57 | 20 | #if WITH_HASHTABLE |
58 | 20 | list->table_size = 11; |
59 | 20 | list->table = |
60 | 20 | (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); |
61 | 20 | if (list->table == NULL) |
62 | 0 | goto fail; |
63 | 20 | #endif |
64 | 20 | list->root.next = &list->root; |
65 | 20 | list->root.prev = &list->root; |
66 | 20 | list->count = 0; |
67 | | |
68 | 20 | return list; |
69 | | |
70 | 0 | #if WITH_HASHTABLE |
71 | 0 | fail: |
72 | 0 | free (list); |
73 | 0 | return NULL; |
74 | 20 | #endif |
75 | 20 | } |
76 | | |
77 | | static gl_list_t |
78 | | gl_linked_nx_create (gl_list_implementation_t implementation, |
79 | | gl_listelement_equals_fn equals_fn, |
80 | | gl_listelement_hashcode_fn hashcode_fn, |
81 | | gl_listelement_dispose_fn dispose_fn, |
82 | | bool allow_duplicates, |
83 | | size_t count, const void **contents) |
84 | 0 | { |
85 | 0 | struct gl_list_impl *list = |
86 | 0 | (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); |
87 | 0 | gl_list_node_t tail; |
88 | |
|
89 | 0 | if (list == NULL) |
90 | 0 | return NULL; |
91 | | |
92 | 0 | list->base.vtable = implementation; |
93 | 0 | list->base.equals_fn = equals_fn; |
94 | 0 | list->base.hashcode_fn = hashcode_fn; |
95 | 0 | list->base.dispose_fn = dispose_fn; |
96 | 0 | list->base.allow_duplicates = allow_duplicates; |
97 | 0 | #if WITH_HASHTABLE |
98 | 0 | { |
99 | 0 | size_t estimate = xsum (count, count / 2); /* 1.5 * count */ |
100 | 0 | if (estimate < 10) |
101 | 0 | estimate = 10; |
102 | 0 | list->table_size = next_prime (estimate); |
103 | 0 | if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t)))) |
104 | 0 | goto fail1; |
105 | 0 | list->table = |
106 | 0 | (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); |
107 | 0 | if (list->table == NULL) |
108 | 0 | goto fail1; |
109 | 0 | } |
110 | 0 | #endif |
111 | 0 | list->count = count; |
112 | 0 | tail = &list->root; |
113 | 0 | for (; count > 0; contents++, count--) |
114 | 0 | { |
115 | 0 | gl_list_node_t node = |
116 | 0 | (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); |
117 | |
|
118 | 0 | if (node == NULL) |
119 | 0 | goto fail2; |
120 | | |
121 | 0 | node->value = *contents; |
122 | 0 | #if WITH_HASHTABLE |
123 | 0 | node->h.hashcode = |
124 | 0 | (list->base.hashcode_fn != NULL |
125 | 0 | ? list->base.hashcode_fn (node->value) |
126 | 0 | : (size_t)(uintptr_t) node->value); |
127 | | |
128 | | /* Add node to the hash table. */ |
129 | 0 | if (add_to_bucket (list, node) < 0) |
130 | 0 | { |
131 | 0 | free (node); |
132 | 0 | goto fail2; |
133 | 0 | } |
134 | 0 | #endif |
135 | | |
136 | | /* Add node to the list. */ |
137 | 0 | node->prev = tail; |
138 | 0 | tail->next = node; |
139 | 0 | tail = node; |
140 | 0 | } |
141 | 0 | tail->next = &list->root; |
142 | 0 | list->root.prev = tail; |
143 | |
|
144 | 0 | return list; |
145 | | |
146 | 0 | fail2: |
147 | 0 | { |
148 | 0 | gl_list_node_t node; |
149 | |
|
150 | 0 | for (node = tail; node != &list->root; ) |
151 | 0 | { |
152 | 0 | gl_list_node_t prev = node->prev; |
153 | |
|
154 | 0 | free (node); |
155 | 0 | node = prev; |
156 | 0 | } |
157 | 0 | } |
158 | 0 | #if WITH_HASHTABLE |
159 | 0 | free (list->table); |
160 | 0 | fail1: |
161 | 0 | #endif |
162 | 0 | free (list); |
163 | 0 | return NULL; |
164 | 0 | } |
165 | | |
166 | | static size_t _GL_ATTRIBUTE_PURE |
167 | | gl_linked_size (gl_list_t list) |
168 | 0 | { |
169 | 0 | return list->count; |
170 | 0 | } |
171 | | |
172 | | static const void * _GL_ATTRIBUTE_PURE |
173 | | gl_linked_node_value (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list, |
174 | | gl_list_node_t node) |
175 | 0 | { |
176 | 0 | return node->value; |
177 | 0 | } |
178 | | |
179 | | static int |
180 | | gl_linked_node_nx_set_value (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list, |
181 | | gl_list_node_t node, |
182 | | const void *elt) |
183 | 0 | { |
184 | 0 | #if WITH_HASHTABLE |
185 | 0 | if (elt != node->value) |
186 | 0 | { |
187 | 0 | size_t new_hashcode = |
188 | 0 | (list->base.hashcode_fn != NULL |
189 | 0 | ? list->base.hashcode_fn (elt) |
190 | 0 | : (size_t)(uintptr_t) elt); |
191 | |
|
192 | 0 | if (new_hashcode != node->h.hashcode) |
193 | 0 | { |
194 | 0 | remove_from_bucket (list, node); |
195 | 0 | node->value = elt; |
196 | 0 | node->h.hashcode = new_hashcode; |
197 | 0 | if (add_to_bucket (list, node) < 0) |
198 | 0 | { |
199 | | /* Out of memory. We removed node from a bucket but cannot add |
200 | | it to another bucket. In order to avoid inconsistencies, we |
201 | | must remove node entirely from the list. */ |
202 | 0 | gl_list_node_t before_removed = node->prev; |
203 | 0 | gl_list_node_t after_removed = node->next; |
204 | 0 | ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed; |
205 | 0 | after_removed->prev = before_removed; |
206 | 0 | list->count--; |
207 | 0 | free (node); |
208 | 0 | return -1; |
209 | 0 | } |
210 | 0 | } |
211 | 0 | else |
212 | 0 | node->value = elt; |
213 | 0 | } |
214 | | #else |
215 | | node->value = elt; |
216 | | #endif |
217 | 0 | return 0; |
218 | 0 | } |
219 | | |
220 | | static gl_list_node_t _GL_ATTRIBUTE_PURE |
221 | | gl_linked_next_node (gl_list_t list, gl_list_node_t node) |
222 | 0 | { |
223 | 0 | return (node->next != &list->root ? node->next : NULL); |
224 | 0 | } |
225 | | |
226 | | static gl_list_node_t _GL_ATTRIBUTE_PURE |
227 | | gl_linked_previous_node (gl_list_t list, gl_list_node_t node) |
228 | 0 | { |
229 | 0 | return (node->prev != &list->root ? node->prev : NULL); |
230 | 0 | } |
231 | | |
232 | | static gl_list_node_t _GL_ATTRIBUTE_PURE |
233 | | gl_linked_first_node (gl_list_t list) |
234 | 0 | { |
235 | 0 | if (list->count > 0) |
236 | 0 | return list->root.next; |
237 | 0 | else |
238 | 0 | return NULL; |
239 | 0 | } |
240 | | |
241 | | static gl_list_node_t _GL_ATTRIBUTE_PURE |
242 | | gl_linked_last_node (gl_list_t list) |
243 | 0 | { |
244 | 0 | if (list->count > 0) |
245 | 0 | return list->root.prev; |
246 | 0 | else |
247 | 0 | return NULL; |
248 | 0 | } |
249 | | |
250 | | static const void * _GL_ATTRIBUTE_PURE |
251 | | gl_linked_get_at (gl_list_t list, size_t position) |
252 | 0 | { |
253 | 0 | size_t count = list->count; |
254 | 0 | gl_list_node_t node; |
255 | |
|
256 | 0 | if (!(position < count)) |
257 | | /* Invalid argument. */ |
258 | 0 | abort (); |
259 | | /* Here we know count > 0. */ |
260 | 0 | if (position <= ((count - 1) / 2)) |
261 | 0 | { |
262 | 0 | node = list->root.next; |
263 | 0 | for (; position > 0; position--) |
264 | 0 | node = node->next; |
265 | 0 | } |
266 | 0 | else |
267 | 0 | { |
268 | 0 | position = count - 1 - position; |
269 | 0 | node = list->root.prev; |
270 | 0 | for (; position > 0; position--) |
271 | 0 | node = node->prev; |
272 | 0 | } |
273 | 0 | return node->value; |
274 | 0 | } |
275 | | |
276 | | static gl_list_node_t |
277 | | gl_linked_nx_set_at (gl_list_t list, size_t position, const void *elt) |
278 | 0 | { |
279 | 0 | size_t count = list->count; |
280 | 0 | gl_list_node_t node; |
281 | |
|
282 | 0 | if (!(position < count)) |
283 | | /* Invalid argument. */ |
284 | 0 | abort (); |
285 | | /* Here we know count > 0. */ |
286 | 0 | if (position <= ((count - 1) / 2)) |
287 | 0 | { |
288 | 0 | node = list->root.next; |
289 | 0 | for (; position > 0; position--) |
290 | 0 | node = node->next; |
291 | 0 | } |
292 | 0 | else |
293 | 0 | { |
294 | 0 | position = count - 1 - position; |
295 | 0 | node = list->root.prev; |
296 | 0 | for (; position > 0; position--) |
297 | 0 | node = node->prev; |
298 | 0 | } |
299 | 0 | #if WITH_HASHTABLE |
300 | 0 | if (elt != node->value) |
301 | 0 | { |
302 | 0 | size_t new_hashcode = |
303 | 0 | (list->base.hashcode_fn != NULL |
304 | 0 | ? list->base.hashcode_fn (elt) |
305 | 0 | : (size_t)(uintptr_t) elt); |
306 | |
|
307 | 0 | if (new_hashcode != node->h.hashcode) |
308 | 0 | { |
309 | 0 | remove_from_bucket (list, node); |
310 | 0 | node->value = elt; |
311 | 0 | node->h.hashcode = new_hashcode; |
312 | 0 | if (add_to_bucket (list, node) < 0) |
313 | 0 | { |
314 | | /* Out of memory. We removed node from a bucket but cannot add |
315 | | it to another bucket. In order to avoid inconsistencies, we |
316 | | must remove node entirely from the list. */ |
317 | 0 | gl_list_node_t before_removed = node->prev; |
318 | 0 | gl_list_node_t after_removed = node->next; |
319 | 0 | ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed; |
320 | 0 | after_removed->prev = before_removed; |
321 | 0 | list->count--; |
322 | 0 | free (node); |
323 | 0 | return NULL; |
324 | 0 | } |
325 | 0 | } |
326 | 0 | else |
327 | 0 | node->value = elt; |
328 | 0 | } |
329 | | #else |
330 | | node->value = elt; |
331 | | #endif |
332 | 0 | return node; |
333 | 0 | } |
334 | | |
335 | | static gl_list_node_t _GL_ATTRIBUTE_PURE |
336 | | gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index, |
337 | | const void *elt) |
338 | 0 | { |
339 | 0 | size_t count = list->count; |
340 | |
|
341 | 0 | if (!(start_index <= end_index && end_index <= count)) |
342 | | /* Invalid arguments. */ |
343 | 0 | abort (); |
344 | 0 | { |
345 | 0 | #if WITH_HASHTABLE |
346 | 0 | size_t hashcode = |
347 | 0 | (list->base.hashcode_fn != NULL |
348 | 0 | ? list->base.hashcode_fn (elt) |
349 | 0 | : (size_t)(uintptr_t) elt); |
350 | 0 | size_t bucket = hashcode % list->table_size; |
351 | 0 | gl_listelement_equals_fn equals = list->base.equals_fn; |
352 | |
|
353 | 0 | if (!list->base.allow_duplicates) |
354 | 0 | { |
355 | | /* Look for the first match in the hash bucket. */ |
356 | 0 | gl_list_node_t found = NULL; |
357 | 0 | gl_list_node_t node; |
358 | |
|
359 | 0 | for (node = (gl_list_node_t) list->table[bucket]; |
360 | 0 | node != NULL; |
361 | 0 | node = (gl_list_node_t) node->h.hash_next) |
362 | 0 | if (node->h.hashcode == hashcode |
363 | 0 | && (equals != NULL |
364 | 0 | ? equals (elt, node->value) |
365 | 0 | : elt == node->value)) |
366 | 0 | { |
367 | 0 | found = node; |
368 | 0 | break; |
369 | 0 | } |
370 | 0 | if (start_index > 0) |
371 | | /* Look whether found's index is < start_index. */ |
372 | 0 | for (node = list->root.next; ; node = node->next) |
373 | 0 | { |
374 | 0 | if (node == found) |
375 | 0 | return NULL; |
376 | 0 | if (--start_index == 0) |
377 | 0 | break; |
378 | 0 | } |
379 | 0 | if (end_index < count) |
380 | | /* Look whether found's index is >= end_index. */ |
381 | 0 | { |
382 | 0 | end_index = count - end_index; |
383 | 0 | for (node = list->root.prev; ; node = node->prev) |
384 | 0 | { |
385 | 0 | if (node == found) |
386 | 0 | return NULL; |
387 | 0 | if (--end_index == 0) |
388 | 0 | break; |
389 | 0 | } |
390 | 0 | } |
391 | 0 | return found; |
392 | 0 | } |
393 | 0 | else |
394 | 0 | { |
395 | | /* Look whether there is more than one match in the hash bucket. */ |
396 | 0 | bool multiple_matches = false; |
397 | 0 | gl_list_node_t first_match = NULL; |
398 | 0 | gl_list_node_t node; |
399 | |
|
400 | 0 | for (node = (gl_list_node_t) list->table[bucket]; |
401 | 0 | node != NULL; |
402 | 0 | node = (gl_list_node_t) node->h.hash_next) |
403 | 0 | if (node->h.hashcode == hashcode |
404 | 0 | && (equals != NULL |
405 | 0 | ? equals (elt, node->value) |
406 | 0 | : elt == node->value)) |
407 | 0 | { |
408 | 0 | if (first_match == NULL) |
409 | 0 | first_match = node; |
410 | 0 | else |
411 | 0 | { |
412 | 0 | multiple_matches = true; |
413 | 0 | break; |
414 | 0 | } |
415 | 0 | } |
416 | 0 | if (multiple_matches) |
417 | 0 | { |
418 | | /* We need the match with the smallest index. But we don't have |
419 | | a fast mapping node -> index. So we have to walk the list. */ |
420 | 0 | end_index -= start_index; |
421 | 0 | node = list->root.next; |
422 | 0 | for (; start_index > 0; start_index--) |
423 | 0 | node = node->next; |
424 | |
|
425 | 0 | for (; |
426 | 0 | end_index > 0; |
427 | 0 | node = node->next, end_index--) |
428 | 0 | if (node->h.hashcode == hashcode |
429 | 0 | && (equals != NULL |
430 | 0 | ? equals (elt, node->value) |
431 | 0 | : elt == node->value)) |
432 | 0 | return node; |
433 | | /* The matches must have all been at indices < start_index or |
434 | | >= end_index. */ |
435 | 0 | return NULL; |
436 | 0 | } |
437 | 0 | else |
438 | 0 | { |
439 | 0 | if (start_index > 0) |
440 | | /* Look whether first_match's index is < start_index. */ |
441 | 0 | for (node = list->root.next; node != &list->root; node = node->next) |
442 | 0 | { |
443 | 0 | if (node == first_match) |
444 | 0 | return NULL; |
445 | 0 | if (--start_index == 0) |
446 | 0 | break; |
447 | 0 | } |
448 | 0 | if (end_index < list->count) |
449 | | /* Look whether first_match's index is >= end_index. */ |
450 | 0 | { |
451 | 0 | end_index = list->count - end_index; |
452 | 0 | for (node = list->root.prev; ; node = node->prev) |
453 | 0 | { |
454 | 0 | if (node == first_match) |
455 | 0 | return NULL; |
456 | 0 | if (--end_index == 0) |
457 | 0 | break; |
458 | 0 | } |
459 | 0 | } |
460 | 0 | return first_match; |
461 | 0 | } |
462 | 0 | } |
463 | | #else |
464 | | gl_listelement_equals_fn equals = list->base.equals_fn; |
465 | | gl_list_node_t node = list->root.next; |
466 | | |
467 | | end_index -= start_index; |
468 | | for (; start_index > 0; start_index--) |
469 | | node = node->next; |
470 | | |
471 | | if (equals != NULL) |
472 | | { |
473 | | for (; end_index > 0; node = node->next, end_index--) |
474 | | if (equals (elt, node->value)) |
475 | | return node; |
476 | | } |
477 | | else |
478 | | { |
479 | | for (; end_index > 0; node = node->next, end_index--) |
480 | | if (elt == node->value) |
481 | | return node; |
482 | | } |
483 | | return NULL; |
484 | | #endif |
485 | 0 | } |
486 | 0 | } |
487 | | |
488 | | static size_t _GL_ATTRIBUTE_PURE |
489 | | gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, |
490 | | const void *elt) |
491 | 0 | { |
492 | 0 | size_t count = list->count; |
493 | |
|
494 | 0 | if (!(start_index <= end_index && end_index <= count)) |
495 | | /* Invalid arguments. */ |
496 | 0 | abort (); |
497 | 0 | { |
498 | 0 | #if WITH_HASHTABLE |
499 | | /* Here the hash table doesn't help much. It only allows us to minimize |
500 | | the number of equals() calls, by looking up first the node and then |
501 | | its index. */ |
502 | 0 | size_t hashcode = |
503 | 0 | (list->base.hashcode_fn != NULL |
504 | 0 | ? list->base.hashcode_fn (elt) |
505 | 0 | : (size_t)(uintptr_t) elt); |
506 | 0 | size_t bucket = hashcode % list->table_size; |
507 | 0 | gl_listelement_equals_fn equals = list->base.equals_fn; |
508 | 0 | gl_list_node_t node; |
509 | | |
510 | | /* First step: Look up the node. */ |
511 | 0 | if (!list->base.allow_duplicates) |
512 | 0 | { |
513 | | /* Look for the first match in the hash bucket. */ |
514 | 0 | for (node = (gl_list_node_t) list->table[bucket]; |
515 | 0 | node != NULL; |
516 | 0 | node = (gl_list_node_t) node->h.hash_next) |
517 | 0 | if (node->h.hashcode == hashcode |
518 | 0 | && (equals != NULL |
519 | 0 | ? equals (elt, node->value) |
520 | 0 | : elt == node->value)) |
521 | 0 | break; |
522 | 0 | } |
523 | 0 | else |
524 | 0 | { |
525 | | /* Look whether there is more than one match in the hash bucket. */ |
526 | 0 | bool multiple_matches = false; |
527 | 0 | gl_list_node_t first_match = NULL; |
528 | |
|
529 | 0 | for (node = (gl_list_node_t) list->table[bucket]; |
530 | 0 | node != NULL; |
531 | 0 | node = (gl_list_node_t) node->h.hash_next) |
532 | 0 | if (node->h.hashcode == hashcode |
533 | 0 | && (equals != NULL |
534 | 0 | ? equals (elt, node->value) |
535 | 0 | : elt == node->value)) |
536 | 0 | { |
537 | 0 | if (first_match == NULL) |
538 | 0 | first_match = node; |
539 | 0 | else |
540 | 0 | { |
541 | 0 | multiple_matches = true; |
542 | 0 | break; |
543 | 0 | } |
544 | 0 | } |
545 | 0 | if (multiple_matches) |
546 | 0 | { |
547 | | /* We need the match with the smallest index. But we don't have |
548 | | a fast mapping node -> index. So we have to walk the list. */ |
549 | 0 | size_t index; |
550 | |
|
551 | 0 | index = start_index; |
552 | 0 | node = list->root.next; |
553 | 0 | for (; start_index > 0; start_index--) |
554 | 0 | node = node->next; |
555 | |
|
556 | 0 | for (; |
557 | 0 | index < end_index; |
558 | 0 | node = node->next, index++) |
559 | 0 | if (node->h.hashcode == hashcode |
560 | 0 | && (equals != NULL |
561 | 0 | ? equals (elt, node->value) |
562 | 0 | : elt == node->value)) |
563 | 0 | return index; |
564 | | /* The matches must have all been at indices < start_index or |
565 | | >= end_index. */ |
566 | 0 | return (size_t)(-1); |
567 | 0 | } |
568 | 0 | node = first_match; |
569 | 0 | } |
570 | | |
571 | | /* Second step: Look up the index of the node. */ |
572 | 0 | if (node == NULL) |
573 | 0 | return (size_t)(-1); |
574 | 0 | else |
575 | 0 | { |
576 | 0 | size_t index = 0; |
577 | |
|
578 | 0 | for (; node->prev != &list->root; node = node->prev) |
579 | 0 | index++; |
580 | |
|
581 | 0 | if (index >= start_index && index < end_index) |
582 | 0 | return index; |
583 | 0 | else |
584 | 0 | return (size_t)(-1); |
585 | 0 | } |
586 | | #else |
587 | | gl_listelement_equals_fn equals = list->base.equals_fn; |
588 | | size_t index = start_index; |
589 | | gl_list_node_t node = list->root.next; |
590 | | |
591 | | for (; start_index > 0; start_index--) |
592 | | node = node->next; |
593 | | |
594 | | if (equals != NULL) |
595 | | { |
596 | | for (; |
597 | | index < end_index; |
598 | | node = node->next, index++) |
599 | | if (equals (elt, node->value)) |
600 | | return index; |
601 | | } |
602 | | else |
603 | | { |
604 | | for (; |
605 | | index < end_index; |
606 | | node = node->next, index++) |
607 | | if (elt == node->value) |
608 | | return index; |
609 | | } |
610 | | return (size_t)(-1); |
611 | | #endif |
612 | 0 | } |
613 | 0 | } |
614 | | |
615 | | static gl_list_node_t |
616 | | gl_linked_nx_add_first (gl_list_t list, const void *elt) |
617 | 0 | { |
618 | 0 | gl_list_node_t node = |
619 | 0 | (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); |
620 | |
|
621 | 0 | if (node == NULL) |
622 | 0 | return NULL; |
623 | | |
624 | 0 | ASYNCSAFE(const void *) node->value = elt; |
625 | 0 | #if WITH_HASHTABLE |
626 | 0 | node->h.hashcode = |
627 | 0 | (list->base.hashcode_fn != NULL |
628 | 0 | ? list->base.hashcode_fn (node->value) |
629 | 0 | : (size_t)(uintptr_t) node->value); |
630 | | |
631 | | /* Add node to the hash table. */ |
632 | 0 | if (add_to_bucket (list, node) < 0) |
633 | 0 | { |
634 | 0 | free (node); |
635 | 0 | return NULL; |
636 | 0 | } |
637 | 0 | #endif |
638 | | |
639 | | /* Add node to the list. */ |
640 | 0 | node->prev = &list->root; |
641 | 0 | ASYNCSAFE(gl_list_node_t) node->next = list->root.next; |
642 | 0 | node->next->prev = node; |
643 | 0 | ASYNCSAFE(gl_list_node_t) list->root.next = node; |
644 | 0 | list->count++; |
645 | |
|
646 | 0 | #if WITH_HASHTABLE |
647 | 0 | hash_resize_after_add (list); |
648 | 0 | #endif |
649 | |
|
650 | 0 | return node; |
651 | 0 | } |
652 | | |
653 | | static gl_list_node_t |
654 | | gl_linked_nx_add_last (gl_list_t list, const void *elt) |
655 | 0 | { |
656 | 0 | gl_list_node_t node = |
657 | 0 | (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); |
658 | |
|
659 | 0 | if (node == NULL) |
660 | 0 | return NULL; |
661 | | |
662 | 0 | ASYNCSAFE(const void *) node->value = elt; |
663 | 0 | #if WITH_HASHTABLE |
664 | 0 | node->h.hashcode = |
665 | 0 | (list->base.hashcode_fn != NULL |
666 | 0 | ? list->base.hashcode_fn (node->value) |
667 | 0 | : (size_t)(uintptr_t) node->value); |
668 | | |
669 | | /* Add node to the hash table. */ |
670 | 0 | if (add_to_bucket (list, node) < 0) |
671 | 0 | { |
672 | 0 | free (node); |
673 | 0 | return NULL; |
674 | 0 | } |
675 | 0 | #endif |
676 | | |
677 | | /* Add node to the list. */ |
678 | 0 | ASYNCSAFE(gl_list_node_t) node->next = &list->root; |
679 | 0 | node->prev = list->root.prev; |
680 | 0 | ASYNCSAFE(gl_list_node_t) node->prev->next = node; |
681 | 0 | list->root.prev = node; |
682 | 0 | list->count++; |
683 | |
|
684 | 0 | #if WITH_HASHTABLE |
685 | 0 | hash_resize_after_add (list); |
686 | 0 | #endif |
687 | |
|
688 | 0 | return node; |
689 | 0 | } |
690 | | |
691 | | static gl_list_node_t |
692 | | gl_linked_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) |
693 | 0 | { |
694 | 0 | gl_list_node_t new_node = |
695 | 0 | (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); |
696 | |
|
697 | 0 | if (new_node == NULL) |
698 | 0 | return NULL; |
699 | | |
700 | 0 | ASYNCSAFE(const void *) new_node->value = elt; |
701 | 0 | #if WITH_HASHTABLE |
702 | 0 | new_node->h.hashcode = |
703 | 0 | (list->base.hashcode_fn != NULL |
704 | 0 | ? list->base.hashcode_fn (new_node->value) |
705 | 0 | : (size_t)(uintptr_t) new_node->value); |
706 | | |
707 | | /* Add new_node to the hash table. */ |
708 | 0 | if (add_to_bucket (list, new_node) < 0) |
709 | 0 | { |
710 | 0 | free (new_node); |
711 | 0 | return NULL; |
712 | 0 | } |
713 | 0 | #endif |
714 | | |
715 | | /* Add new_node to the list. */ |
716 | 0 | ASYNCSAFE(gl_list_node_t) new_node->next = node; |
717 | 0 | new_node->prev = node->prev; |
718 | 0 | ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node; |
719 | 0 | node->prev = new_node; |
720 | 0 | list->count++; |
721 | |
|
722 | 0 | #if WITH_HASHTABLE |
723 | 0 | hash_resize_after_add (list); |
724 | 0 | #endif |
725 | |
|
726 | 0 | return new_node; |
727 | 0 | } |
728 | | |
729 | | static gl_list_node_t |
730 | | gl_linked_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) |
731 | 0 | { |
732 | 0 | gl_list_node_t new_node = |
733 | 0 | (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); |
734 | |
|
735 | 0 | if (new_node == NULL) |
736 | 0 | return NULL; |
737 | | |
738 | 0 | ASYNCSAFE(const void *) new_node->value = elt; |
739 | 0 | #if WITH_HASHTABLE |
740 | 0 | new_node->h.hashcode = |
741 | 0 | (list->base.hashcode_fn != NULL |
742 | 0 | ? list->base.hashcode_fn (new_node->value) |
743 | 0 | : (size_t)(uintptr_t) new_node->value); |
744 | | |
745 | | /* Add new_node to the hash table. */ |
746 | 0 | if (add_to_bucket (list, new_node) < 0) |
747 | 0 | { |
748 | 0 | free (new_node); |
749 | 0 | return NULL; |
750 | 0 | } |
751 | 0 | #endif |
752 | | |
753 | | /* Add new_node to the list. */ |
754 | 0 | new_node->prev = node; |
755 | 0 | ASYNCSAFE(gl_list_node_t) new_node->next = node->next; |
756 | 0 | new_node->next->prev = new_node; |
757 | 0 | ASYNCSAFE(gl_list_node_t) node->next = new_node; |
758 | 0 | list->count++; |
759 | |
|
760 | 0 | #if WITH_HASHTABLE |
761 | 0 | hash_resize_after_add (list); |
762 | 0 | #endif |
763 | |
|
764 | 0 | return new_node; |
765 | 0 | } |
766 | | |
767 | | static gl_list_node_t |
768 | | gl_linked_nx_add_at (gl_list_t list, size_t position, const void *elt) |
769 | 0 | { |
770 | 0 | size_t count = list->count; |
771 | 0 | gl_list_node_t new_node; |
772 | |
|
773 | 0 | if (!(position <= count)) |
774 | | /* Invalid argument. */ |
775 | 0 | abort (); |
776 | | |
777 | 0 | new_node = (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); |
778 | 0 | if (new_node == NULL) |
779 | 0 | return NULL; |
780 | | |
781 | 0 | ASYNCSAFE(const void *) new_node->value = elt; |
782 | 0 | #if WITH_HASHTABLE |
783 | 0 | new_node->h.hashcode = |
784 | 0 | (list->base.hashcode_fn != NULL |
785 | 0 | ? list->base.hashcode_fn (new_node->value) |
786 | 0 | : (size_t)(uintptr_t) new_node->value); |
787 | | |
788 | | /* Add new_node to the hash table. */ |
789 | 0 | if (add_to_bucket (list, new_node) < 0) |
790 | 0 | { |
791 | 0 | free (new_node); |
792 | 0 | return NULL; |
793 | 0 | } |
794 | 0 | #endif |
795 | | |
796 | | /* Add new_node to the list. */ |
797 | 0 | if (position <= (count / 2)) |
798 | 0 | { |
799 | 0 | gl_list_node_t node; |
800 | |
|
801 | 0 | node = &list->root; |
802 | 0 | for (; position > 0; position--) |
803 | 0 | node = node->next; |
804 | 0 | new_node->prev = node; |
805 | 0 | ASYNCSAFE(gl_list_node_t) new_node->next = node->next; |
806 | 0 | new_node->next->prev = new_node; |
807 | 0 | ASYNCSAFE(gl_list_node_t) node->next = new_node; |
808 | 0 | } |
809 | 0 | else |
810 | 0 | { |
811 | 0 | gl_list_node_t node; |
812 | |
|
813 | 0 | position = count - position; |
814 | 0 | node = &list->root; |
815 | 0 | for (; position > 0; position--) |
816 | 0 | node = node->prev; |
817 | 0 | ASYNCSAFE(gl_list_node_t) new_node->next = node; |
818 | 0 | new_node->prev = node->prev; |
819 | 0 | ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node; |
820 | 0 | node->prev = new_node; |
821 | 0 | } |
822 | 0 | list->count++; |
823 | |
|
824 | 0 | #if WITH_HASHTABLE |
825 | 0 | hash_resize_after_add (list); |
826 | 0 | #endif |
827 | |
|
828 | 0 | return new_node; |
829 | 0 | } |
830 | | |
831 | | static bool |
832 | | gl_linked_remove_node (gl_list_t list, gl_list_node_t node) |
833 | 0 | { |
834 | 0 | gl_list_node_t prev; |
835 | 0 | gl_list_node_t next; |
836 | |
|
837 | 0 | #if WITH_HASHTABLE |
838 | | /* Remove node from the hash table. */ |
839 | 0 | remove_from_bucket (list, node); |
840 | 0 | #endif |
841 | | |
842 | | /* Remove node from the list. */ |
843 | 0 | prev = node->prev; |
844 | 0 | next = node->next; |
845 | |
|
846 | 0 | ASYNCSAFE(gl_list_node_t) prev->next = next; |
847 | 0 | next->prev = prev; |
848 | 0 | list->count--; |
849 | |
|
850 | 0 | if (list->base.dispose_fn != NULL) |
851 | 0 | list->base.dispose_fn (node->value); |
852 | 0 | free (node); |
853 | 0 | return true; |
854 | 0 | } |
855 | | |
856 | | static bool |
857 | | gl_linked_remove_at (gl_list_t list, size_t position) |
858 | 0 | { |
859 | 0 | size_t count = list->count; |
860 | 0 | gl_list_node_t removed_node; |
861 | |
|
862 | 0 | if (!(position < count)) |
863 | | /* Invalid argument. */ |
864 | 0 | abort (); |
865 | | /* Here we know count > 0. */ |
866 | 0 | if (position <= ((count - 1) / 2)) |
867 | 0 | { |
868 | 0 | gl_list_node_t node; |
869 | 0 | gl_list_node_t after_removed; |
870 | |
|
871 | 0 | node = &list->root; |
872 | 0 | for (; position > 0; position--) |
873 | 0 | node = node->next; |
874 | 0 | removed_node = node->next; |
875 | 0 | after_removed = node->next->next; |
876 | 0 | ASYNCSAFE(gl_list_node_t) node->next = after_removed; |
877 | 0 | after_removed->prev = node; |
878 | 0 | } |
879 | 0 | else |
880 | 0 | { |
881 | 0 | gl_list_node_t node; |
882 | 0 | gl_list_node_t before_removed; |
883 | |
|
884 | 0 | position = count - 1 - position; |
885 | 0 | node = &list->root; |
886 | 0 | for (; position > 0; position--) |
887 | 0 | node = node->prev; |
888 | 0 | removed_node = node->prev; |
889 | 0 | before_removed = node->prev->prev; |
890 | 0 | node->prev = before_removed; |
891 | 0 | ASYNCSAFE(gl_list_node_t) before_removed->next = node; |
892 | 0 | } |
893 | 0 | #if WITH_HASHTABLE |
894 | 0 | remove_from_bucket (list, removed_node); |
895 | 0 | #endif |
896 | 0 | list->count--; |
897 | |
|
898 | 0 | if (list->base.dispose_fn != NULL) |
899 | 0 | list->base.dispose_fn (removed_node->value); |
900 | 0 | free (removed_node); |
901 | 0 | return true; |
902 | 0 | } |
903 | | |
904 | | static bool |
905 | | gl_linked_remove (gl_list_t list, const void *elt) |
906 | 0 | { |
907 | 0 | gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt); |
908 | |
|
909 | 0 | if (node != NULL) |
910 | 0 | return gl_linked_remove_node (list, node); |
911 | 0 | else |
912 | 0 | return false; |
913 | 0 | } |
914 | | |
915 | | static void |
916 | | gl_linked_list_free (gl_list_t list) |
917 | 0 | { |
918 | 0 | gl_listelement_dispose_fn dispose = list->base.dispose_fn; |
919 | 0 | gl_list_node_t node; |
920 | |
|
921 | 0 | for (node = list->root.next; node != &list->root; ) |
922 | 0 | { |
923 | 0 | gl_list_node_t next = node->next; |
924 | 0 | if (dispose != NULL) |
925 | 0 | dispose (node->value); |
926 | 0 | free (node); |
927 | 0 | node = next; |
928 | 0 | } |
929 | 0 | #if WITH_HASHTABLE |
930 | 0 | free (list->table); |
931 | 0 | #endif |
932 | 0 | free (list); |
933 | 0 | } |
934 | | |
935 | | /* --------------------- gl_list_iterator_t Data Type --------------------- */ |
936 | | |
937 | | static gl_list_iterator_t _GL_ATTRIBUTE_PURE |
938 | | gl_linked_iterator (gl_list_t list) |
939 | 0 | { |
940 | 0 | gl_list_iterator_t result; |
941 | |
|
942 | 0 | result.vtable = list->base.vtable; |
943 | 0 | result.list = list; |
944 | 0 | result.p = list->root.next; |
945 | 0 | result.q = &list->root; |
946 | | #if defined GCC_LINT || defined lint |
947 | | result.i = 0; |
948 | | result.j = 0; |
949 | | result.count = 0; |
950 | | #endif |
951 | |
|
952 | 0 | return result; |
953 | 0 | } |
954 | | |
955 | | static gl_list_iterator_t _GL_ATTRIBUTE_PURE |
956 | | gl_linked_iterator_from_to (gl_list_t list, |
957 | | size_t start_index, size_t end_index) |
958 | 0 | { |
959 | 0 | gl_list_iterator_t result; |
960 | 0 | size_t n1, n2, n3; |
961 | |
|
962 | 0 | if (!(start_index <= end_index && end_index <= list->count)) |
963 | | /* Invalid arguments. */ |
964 | 0 | abort (); |
965 | 0 | result.vtable = list->base.vtable; |
966 | 0 | result.list = list; |
967 | 0 | n1 = start_index; |
968 | 0 | n2 = end_index - start_index; |
969 | 0 | n3 = list->count - end_index; |
970 | | /* Find the maximum among n1, n2, n3, so as to reduce the number of |
971 | | loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */ |
972 | 0 | if (n1 > n2 && n1 > n3) |
973 | 0 | { |
974 | | /* n1 is the maximum, use n2 and n3. */ |
975 | 0 | gl_list_node_t node; |
976 | 0 | size_t i; |
977 | |
|
978 | 0 | node = &list->root; |
979 | 0 | for (i = n3; i > 0; i--) |
980 | 0 | node = node->prev; |
981 | 0 | result.q = node; |
982 | 0 | for (i = n2; i > 0; i--) |
983 | 0 | node = node->prev; |
984 | 0 | result.p = node; |
985 | 0 | } |
986 | 0 | else if (n2 > n3) |
987 | 0 | { |
988 | | /* n2 is the maximum, use n1 and n3. */ |
989 | 0 | gl_list_node_t node; |
990 | 0 | size_t i; |
991 | |
|
992 | 0 | node = list->root.next; |
993 | 0 | for (i = n1; i > 0; i--) |
994 | 0 | node = node->next; |
995 | 0 | result.p = node; |
996 | |
|
997 | 0 | node = &list->root; |
998 | 0 | for (i = n3; i > 0; i--) |
999 | 0 | node = node->prev; |
1000 | 0 | result.q = node; |
1001 | 0 | } |
1002 | 0 | else |
1003 | 0 | { |
1004 | | /* n3 is the maximum, use n1 and n2. */ |
1005 | 0 | gl_list_node_t node; |
1006 | 0 | size_t i; |
1007 | |
|
1008 | 0 | node = list->root.next; |
1009 | 0 | for (i = n1; i > 0; i--) |
1010 | 0 | node = node->next; |
1011 | 0 | result.p = node; |
1012 | 0 | for (i = n2; i > 0; i--) |
1013 | 0 | node = node->next; |
1014 | 0 | result.q = node; |
1015 | 0 | } |
1016 | |
|
1017 | | #if defined GCC_LINT || defined lint |
1018 | | result.i = 0; |
1019 | | result.j = 0; |
1020 | | result.count = 0; |
1021 | | #endif |
1022 | |
|
1023 | 0 | return result; |
1024 | 0 | } |
1025 | | |
1026 | | static bool |
1027 | | gl_linked_iterator_next (gl_list_iterator_t *iterator, |
1028 | | const void **eltp, gl_list_node_t *nodep) |
1029 | 0 | { |
1030 | 0 | if (iterator->p != iterator->q) |
1031 | 0 | { |
1032 | 0 | gl_list_node_t node = (gl_list_node_t) iterator->p; |
1033 | 0 | *eltp = node->value; |
1034 | 0 | if (nodep != NULL) |
1035 | 0 | *nodep = node; |
1036 | 0 | iterator->p = node->next; |
1037 | 0 | return true; |
1038 | 0 | } |
1039 | 0 | else |
1040 | 0 | return false; |
1041 | 0 | } |
1042 | | |
1043 | | static void |
1044 | | gl_linked_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_iterator_t *iterator) |
1045 | 0 | { |
1046 | 0 | } |
1047 | | |
1048 | | /* ---------------------- Sorted gl_list_t Data Type ---------------------- */ |
1049 | | |
1050 | | static gl_list_node_t _GL_ATTRIBUTE_PURE |
1051 | | gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, |
1052 | | const void *elt) |
1053 | 0 | { |
1054 | 0 | gl_list_node_t node; |
1055 | |
|
1056 | 0 | for (node = list->root.next; node != &list->root; node = node->next) |
1057 | 0 | { |
1058 | 0 | int cmp = compar (node->value, elt); |
1059 | |
|
1060 | 0 | if (cmp > 0) |
1061 | 0 | break; |
1062 | 0 | if (cmp == 0) |
1063 | 0 | return node; |
1064 | 0 | } |
1065 | 0 | return NULL; |
1066 | 0 | } |
1067 | | |
1068 | | static gl_list_node_t _GL_ATTRIBUTE_PURE |
1069 | | gl_linked_sortedlist_search_from_to (gl_list_t list, |
1070 | | gl_listelement_compar_fn compar, |
1071 | | size_t low, size_t high, |
1072 | | const void *elt) |
1073 | 0 | { |
1074 | 0 | size_t count = list->count; |
1075 | |
|
1076 | 0 | if (!(low <= high && high <= list->count)) |
1077 | | /* Invalid arguments. */ |
1078 | 0 | abort (); |
1079 | | |
1080 | 0 | high -= low; |
1081 | 0 | if (high > 0) |
1082 | 0 | { |
1083 | | /* Here we know low < count. */ |
1084 | 0 | size_t position = low; |
1085 | 0 | gl_list_node_t node; |
1086 | |
|
1087 | 0 | if (position <= ((count - 1) / 2)) |
1088 | 0 | { |
1089 | 0 | node = list->root.next; |
1090 | 0 | for (; position > 0; position--) |
1091 | 0 | node = node->next; |
1092 | 0 | } |
1093 | 0 | else |
1094 | 0 | { |
1095 | 0 | position = count - 1 - position; |
1096 | 0 | node = list->root.prev; |
1097 | 0 | for (; position > 0; position--) |
1098 | 0 | node = node->prev; |
1099 | 0 | } |
1100 | |
|
1101 | 0 | do |
1102 | 0 | { |
1103 | 0 | int cmp = compar (node->value, elt); |
1104 | |
|
1105 | 0 | if (cmp > 0) |
1106 | 0 | break; |
1107 | 0 | if (cmp == 0) |
1108 | 0 | return node; |
1109 | 0 | node = node->next; |
1110 | 0 | } |
1111 | 0 | while (--high > 0); |
1112 | 0 | } |
1113 | 0 | return NULL; |
1114 | 0 | } |
1115 | | |
1116 | | static size_t _GL_ATTRIBUTE_PURE |
1117 | | gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, |
1118 | | const void *elt) |
1119 | 0 | { |
1120 | 0 | gl_list_node_t node; |
1121 | 0 | size_t index; |
1122 | |
|
1123 | 0 | for (node = list->root.next, index = 0; |
1124 | 0 | node != &list->root; |
1125 | 0 | node = node->next, index++) |
1126 | 0 | { |
1127 | 0 | int cmp = compar (node->value, elt); |
1128 | |
|
1129 | 0 | if (cmp > 0) |
1130 | 0 | break; |
1131 | 0 | if (cmp == 0) |
1132 | 0 | return index; |
1133 | 0 | } |
1134 | 0 | return (size_t)(-1); |
1135 | 0 | } |
1136 | | |
1137 | | static size_t _GL_ATTRIBUTE_PURE |
1138 | | gl_linked_sortedlist_indexof_from_to (gl_list_t list, |
1139 | | gl_listelement_compar_fn compar, |
1140 | | size_t low, size_t high, |
1141 | | const void *elt) |
1142 | 0 | { |
1143 | 0 | size_t count = list->count; |
1144 | |
|
1145 | 0 | if (!(low <= high && high <= list->count)) |
1146 | | /* Invalid arguments. */ |
1147 | 0 | abort (); |
1148 | | |
1149 | 0 | high -= low; |
1150 | 0 | if (high > 0) |
1151 | 0 | { |
1152 | | /* Here we know low < count. */ |
1153 | 0 | size_t index = low; |
1154 | 0 | size_t position = low; |
1155 | 0 | gl_list_node_t node; |
1156 | |
|
1157 | 0 | if (position <= ((count - 1) / 2)) |
1158 | 0 | { |
1159 | 0 | node = list->root.next; |
1160 | 0 | for (; position > 0; position--) |
1161 | 0 | node = node->next; |
1162 | 0 | } |
1163 | 0 | else |
1164 | 0 | { |
1165 | 0 | position = count - 1 - position; |
1166 | 0 | node = list->root.prev; |
1167 | 0 | for (; position > 0; position--) |
1168 | 0 | node = node->prev; |
1169 | 0 | } |
1170 | |
|
1171 | 0 | do |
1172 | 0 | { |
1173 | 0 | int cmp = compar (node->value, elt); |
1174 | |
|
1175 | 0 | if (cmp > 0) |
1176 | 0 | break; |
1177 | 0 | if (cmp == 0) |
1178 | 0 | return index; |
1179 | 0 | node = node->next; |
1180 | 0 | index++; |
1181 | 0 | } |
1182 | 0 | while (--high > 0); |
1183 | 0 | } |
1184 | 0 | return (size_t)(-1); |
1185 | 0 | } |
1186 | | |
1187 | | static gl_list_node_t |
1188 | | gl_linked_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, |
1189 | | const void *elt) |
1190 | 0 | { |
1191 | 0 | gl_list_node_t node; |
1192 | |
|
1193 | 0 | for (node = list->root.next; node != &list->root; node = node->next) |
1194 | 0 | if (compar (node->value, elt) >= 0) |
1195 | 0 | return gl_linked_nx_add_before (list, node, elt); |
1196 | 0 | return gl_linked_nx_add_last (list, elt); |
1197 | 0 | } |
1198 | | |
1199 | | static bool |
1200 | | gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, |
1201 | | const void *elt) |
1202 | 0 | { |
1203 | 0 | gl_list_node_t node; |
1204 | |
|
1205 | 0 | for (node = list->root.next; node != &list->root; node = node->next) |
1206 | 0 | { |
1207 | 0 | int cmp = compar (node->value, elt); |
1208 | |
|
1209 | 0 | if (cmp > 0) |
1210 | 0 | break; |
1211 | 0 | if (cmp == 0) |
1212 | 0 | return gl_linked_remove_node (list, node); |
1213 | 0 | } |
1214 | 0 | return false; |
1215 | 0 | } |