1 /*------------------------------------------------------------------------------
2 *
3 * Copyright (c) 2011-2021, EURid vzw. All rights reserved.
4 * The YADIFA TM software product is provided under the BSD 3-clause license:
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * * Neither the name of EURid nor the names of its contributors may be
16 * used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 *
31 *------------------------------------------------------------------------------
32 *
33 */
34
35 /** @defgroup collections Generic collections functions
36 * @ingroup dnscore
37 * @brief A dynamic-sized array of pointers
38 *
39 * A dynamic-sized array of pointers
40 *
41 * Used for resource record canonization and such.
42 *
43 * @{
44 */
45
46 #include "dnscore/dnscore-config.h"
47 #include "dnscore/ptr_vector.h"
48
49 #define PTR_QSORT_SMALL 50
50 #define PTR_QSORT_PIVOT_CHOSE 1
51 #define PTR_QSORT_DERECURSE 1
52 #define PTR_QSORT_DERECURSE_DEPTH 64
53
54 #define PTR_VECTOR_RESTRICTED_SIZE_INCREASE 16
55
56 #if PTR_VECTOR_RESTRICTED_SIZE_INCREASE <= 0
57 #error "PTR_VECTOR_RESTRICTED_SIZE_INCREASE must be > 0"
58 #endif
59
60 /**
61 * Initialises a vector structure with a size of PTR_VECTOR_DEFAULT_SIZE entries
62 *
63 * @param v a pointer to the ptr_vector structure to initialise
64 */
65
66 void
ptr_vector_init(ptr_vector * v)67 ptr_vector_init(ptr_vector* v)
68 {
69 v->size = PTR_VECTOR_DEFAULT_SIZE;
70 MALLOC_OR_DIE(void**, v->data, v->size * sizeof(void*), PTR_VECTOR_TAG);
71 v->offset = -1;
72 }
73
74 /**
75 * Initialises a vector structure with a size of PTR_VECTOR_DEFAULT_SIZE entries
76 *
77 * @param v a pointer to the ptr_vector structure to initialise
78 * @param initial_capacity the size to allocate to start with
79 */
80
81 void
ptr_vector_init_ex(ptr_vector * v,u32 initial_capacity)82 ptr_vector_init_ex(ptr_vector* v, u32 initial_capacity)
83 {
84 v->size = initial_capacity;
85 if(initial_capacity > 0)
86 {
87 MALLOC_OR_DIE(void**, v->data, v->size * sizeof(void*), PTR_VECTOR_TAG);
88 }
89 else
90 {
91 v->data = NULL;
92 }
93 v->offset = -1;
94 }
95
96 /**
97 * Initialises a vector as a copy as another vector.
98 * The reserved size is the size of the original plus the extra size.
99 *
100 * @param v a pointer to the ptr_vector structure to initialise
101 * @param original the vector to copy
102 * @param extra_size the amount of reserved slots to allocate
103 */
104
105 void
ptr_vector_init_copy(ptr_vector * v,const ptr_vector * original,u32 extra_size)106 ptr_vector_init_copy(ptr_vector* v, const ptr_vector* original, u32 extra_size)
107 {
108 assert(ptr_vector_size(original) >= 0);
109
110 ptr_vector_init_ex(v, ptr_vector_size(original) + extra_size);
111 if(ptr_vector_last_index(original) >= 0) // => size > 0 => v->data != NULL
112 {
113 assert(original->data != NULL && v->data != NULL);
114 memcpy(v->data, original->data, ptr_vector_size(original) * sizeof(void*)); // scan-build false positive
115 }
116 v->offset = original->offset;
117 }
118
119 /**
120 * Initialises a vector as a copy as another vector plus onz item added
121 * The reserved size is the size of the original plus one
122 *
123 * @param v a pointer to the ptr_vector structure to initialise
124 * @param original the vector to copy
125 * @param data an item to add
126 */
127
128 void
ptr_vector_init_copy_append(ptr_vector * v,const ptr_vector * original,void * data)129 ptr_vector_init_copy_append(ptr_vector* v, const ptr_vector* original, void *data)
130 {
131 assert(ptr_vector_size(original) >= 0);
132
133 ptr_vector_init_ex(v, ptr_vector_size(original) + 1);
134 if(ptr_vector_last_index(original) >= 0)
135 {
136 assert(original->data != NULL && v->data != NULL);
137 memcpy(v->data, original->data, ptr_vector_size(original) * sizeof(void*));
138 }
139 v->offset = original->offset;
140 ptr_vector_append(v, data);
141 }
142
143 /**
144 * Initialises a vector as a copy as another vector plus a few items added
145 * The reserved size is the size of the original plus the data size.
146 *
147 * @param v a pointer to the ptr_vector structure to initialise
148 * @param original the vector to copy
149 * @param data an array of pointers
150 * @param data_size the size of the data array
151 */
152
153 void
ptr_vector_init_copy_append_array(ptr_vector * v,const ptr_vector * original,void * data,u32 data_size)154 ptr_vector_init_copy_append_array(ptr_vector* v, const ptr_vector* original, void *data, u32 data_size)
155 {
156 ptr_vector_init_ex(v, ptr_vector_size(original) + data_size);
157
158 if(ptr_vector_last_index(original) >= 0) // A faster way to test if size > 0 => v->data != NULL
159 {
160 assert(original->data != NULL && v->data != NULL);
161 memcpy(v->data, original->data, ptr_vector_size(original) * sizeof(void*)); // scan-build false positive: v->data is not NULL
162 }
163 v->offset = original->offset;
164 ptr_vector_append_array(v, data, data_size);
165 }
166
167 /**
168 * Calls the callback on every pointer stored in the vector.
169 * Frees the memory used by a vector structure
170 *
171 * @param v a pointer to the ptr_vector structure
172 */
173
174 void
ptr_vector_callback_and_destroy(ptr_vector * v,callback_function free_memory)175 ptr_vector_callback_and_destroy(ptr_vector *v, callback_function free_memory)
176 {
177 ptr_vector_callback_and_clear(v, free_memory);
178 v->size = -1;
179 free(v->data);
180 v->data = NULL;
181 }
182
183 /**
184 * Frees the memory used by a vector structure (not the vector structure itself)
185 *
186 * @param v a pointer to the ptr_vector structure
187 */
188
189 void
ptr_vector_destroy(ptr_vector * v)190 ptr_vector_destroy(ptr_vector* v)
191 {
192 v->size = -1;
193 v->offset = -1;
194 free(v->data);
195 v->data = NULL;
196 }
197
198 /**
199 * Empties the vector (does not release memory)
200 *
201 * @param v a pointer to the ptr_vector structure
202 */
203
204 void
ptr_vector_clear(ptr_vector * v)205 ptr_vector_clear(ptr_vector* v)
206 {
207 v->offset = -1;
208 }
209
210 /**
211 * Changes the capacity of a vector to the specified size
212 * The new size SHOULD be enough to keep the current content
213 * of the vector. Failing to do so will most likely result
214 * into a crash or a leak of the pointers lost in the operation.
215 *
216 * Note that when shrinking, the capacity is not really changed.
217 *
218 *
219 * @param v a pointer to the ptr_vector structure
220 * @param newsize
221 */
222
223 void
ptr_vector_resize(ptr_vector * v,s32 newsize)224 ptr_vector_resize(ptr_vector*v, s32 newsize)
225 {
226 void** data;
227 assert(newsize >= 0);
228 assert(v->offset >= -1);
229 assert(v->size >= 0);
230
231 if(v->offset >= 0)
232 {
233 if(newsize > v->offset + 1)
234 {
235 MALLOC_OR_DIE(void**, data, newsize * sizeof(void*), PTR_VECTOR_TAG);
236
237 /* Only the data up to v->offset (included) is relevant */
238 MEMCOPY(data, v->data, (v->offset + 1) * sizeof(void*));
239 #if DEBUG
240 if(v->data != NULL)
241 {
242 memset(v->data, 0xff, v->size * sizeof(void*));
243 }
244 #endif
245 free(v->data);
246 v->data = data;
247 v->size = newsize;
248 }
249 else
250 {
251 v->offset = newsize - 1;
252 }
253 }
254 else
255 {
256 if(newsize != v->size)
257 {
258 free(v->data);
259
260 if(newsize > 0)
261 {
262 MALLOC_OR_DIE(void**, data, newsize * sizeof(void*), PTR_VECTOR_TAG);
263 }
264 else
265 {
266 #if DEBUG
267 #pragma message ("this should actually set data to NULL and keep newsize to 0 but scan-build coudln't handle it")
268 MALLOC_OR_DIE(void**, data, sizeof(void*), PTR_VECTOR_TAG);
269 newsize = 1;
270 #else
271 data = NULL;
272 newsize = 0;
273 #endif
274 }
275 v->data = data;
276 v->size = newsize;
277 }
278 }
279 }
280
281 /**
282 * Ensures the vector has enough capacity to accommodate a
283 * specified number of items
284 *
285 * @param v a pointer to the ptr_vector structure
286 * @param reqsize the minimum size of the vector
287 */
288
289 void
ptr_vector_ensures(ptr_vector * v,s32 reqsize)290 ptr_vector_ensures(ptr_vector*v, s32 reqsize)
291 {
292 if(v->size >= 0)
293 {
294 if(v->size < reqsize)
295 {
296 ptr_vector_resize(v, reqsize);
297 }
298 }
299 else
300 {
301 ptr_vector_init_ex(v, reqsize);
302 }
303 }
304
305 void
ptr_vector_remove_from(ptr_vector * v,s32 first_bad_index)306 ptr_vector_remove_from(ptr_vector *v, s32 first_bad_index)
307 {
308 assert((first_bad_index >= 0) && (first_bad_index <= v->offset));
309 v->offset = first_bad_index - 1;
310 }
311
312 void
ptr_vector_remove_after(ptr_vector * v,s32 last_good_index)313 ptr_vector_remove_after(ptr_vector *v, s32 last_good_index)
314 {
315 assert((last_good_index >= -1) && (last_good_index <= v->offset));
316 v->offset = last_good_index;
317 }
318
319 /**
320 * Resizes the capacity so it can at most contain its
321 * current size.
322 *
323 * @param v a pointer to the ptr_vector structure
324 */
325
326 void
ptr_vector_shrink(ptr_vector * v)327 ptr_vector_shrink(ptr_vector*v)
328 {
329 if(v->size != (v->offset + 1))
330 {
331 ptr_vector_resize(v, v->offset + 1);
332 }
333 }
334
335 /**
336 * Appends the item (pointer) to the vector
337 *
338 * @param v a pointer to the ptr_vector structure
339 * @param data a pointer to the item
340 */
341
342 void
ptr_vector_append(ptr_vector * v,void * data)343 ptr_vector_append(ptr_vector* v, void* data)
344 {
345 if(v->offset + 1 >= v->size)
346 {
347 if(v->size == 0)
348 {
349 v->size = PTR_VECTOR_DEFAULT_SIZE;
350 }
351 ptr_vector_resize(v, v->size * 2);
352 }
353
354 assert(v->data != NULL);
355 v->data[++v->offset] = data;
356 }
357
358 /**
359 * Appends the item (pointer) to the vector
360 *
361 * @param v a pointer to the ptr_vector structure
362 * @param datap a pointer to the items
363 * @param data_size the number of items to append
364 */
365
366 void
ptr_vector_append_array(ptr_vector * v,void ** datap,u32 data_size)367 ptr_vector_append_array(ptr_vector* v, void** datap, u32 data_size)
368 {
369 if(data_size > 0)
370 {
371 while((u32)(v->offset + data_size) >= (u32)v->size)
372 {
373 if(v->size == 0)
374 {
375 v->size = PTR_VECTOR_DEFAULT_SIZE;
376 }
377 ptr_vector_resize(v, v->size * 2);
378 }
379 assert(v->data != NULL);
380 assert(datap != NULL);
381 memcpy(&v->data[++v->offset], datap, data_size * sizeof(void*)); // scan-build false positive: v->data can only be null if data_size is 0, which is not possible
382 }
383 }
384
ptr_vector_append_vector(ptr_vector * v,ptr_vector * toappend)385 void ptr_vector_append_vector(ptr_vector *v, ptr_vector *toappend)
386 {
387 ptr_vector_append_array(v, toappend->data, toappend->offset + 1);
388 }
389
390 /**
391 * Appends the item (pointer) to the vector and try to keep the buffer size at at most
392 * restrictedlimit.
393 * The goal is to avoid a growth of *2 that would go far beyond the restrictedlimit.
394 * The performance is extremely poor when the number of items in the buffer is restrictedlimit or more.
395 *
396 * @param v a pointer to the ptr_vector structure
397 * @param data a pointer to the item
398 * @param restrictedlimit a guideline limit on the size of the vector
399 */
400
401 void
ptr_vector_append_restrict_size(ptr_vector * v,void * data,u32 restrictedlimit)402 ptr_vector_append_restrict_size(ptr_vector* v, void* data, u32 restrictedlimit)
403 {
404 assert((v->size >= 0) && (v->offset < v->size) && (v->offset >= -1));
405
406 u32 next_offset = (u32)(v->offset + 1); // >= 0
407
408 if(next_offset >= (u32)v->size) // size has to be > next_offset
409 {
410 u32 size = (u32)v->size; // unsigned
411
412 // if the size is not 0 prepare to double it, else set it to a reasonable minimum
413 if(size != 0) // size > 0
414 {
415 size <<= 1;
416
417 // if the size is bigger than the restriction, set it to the maximum between the restriction and what we actually need
418
419 if(size > restrictedlimit)
420 {
421 size = MAX(MIN(restrictedlimit, PTR_VECTOR_DEFAULT_SIZE), next_offset + PTR_VECTOR_RESTRICTED_SIZE_INCREASE); // worst case size = MAX(>0, 0)
422 }
423 }
424 else
425 {
426 size = PTR_VECTOR_DEFAULT_SIZE; // size > 0
427 }
428
429 ptr_vector_resize(v, size);
430 }
431
432 v->data[++v->offset] = data; // scan-build false positive, can only happen if resize called with size = 0, which is impossible
433 }
434
435 /**
436 * Appends the item (pointer) to the vector
437 *
438 * @param v a pointer to the ptr_vector structure
439 * @param data a pointer to the item
440 */
441
442 void*
ptr_vector_pop(ptr_vector * v)443 ptr_vector_pop(ptr_vector* v)
444 {
445 if(v->offset >= 0)
446 {
447 return v->data[v->offset--];
448 }
449 else
450 {
451 return NULL;
452 }
453 }
454
455 static int
ptr_sort_heap_parent(int index)456 ptr_sort_heap_parent(int index)
457 {
458 assert(index > 0);
459 return (index - 1) / 2;
460 }
461
462 static int
ptr_sort_heap_leftchild(int index)463 ptr_sort_heap_leftchild(int index)
464 {
465 return (index * 2) + 1;
466 }
467
468 static void
ptr_sort_siftdown(void ** base,int from,size_t n,ptr_vector_qsort_r_callback * cmp,void * data)469 ptr_sort_siftdown(void** base, int from, size_t n, ptr_vector_qsort_r_callback *cmp, void *data)
470 {
471 int root = from;
472 int child;
473 while((child = ptr_sort_heap_leftchild(root)) <= (int)n)
474 {
475 int swp = root;
476 if(cmp(base[swp], base[child], data) < 0)
477 {
478 swp = child;
479 }
480 if((child + 1 <= (int)n) && (cmp(base[swp], base[child + 1], data) < 0))
481 {
482 swp = child + 1;
483 }
484 if(swp == root)
485 {
486 break;
487 }
488
489 void **tmp = base[swp];
490 base[swp] = base[root];
491 base[root] = tmp;
492
493 root = swp;
494 }
495 }
496
497 static void
ptr_sort_heapify(void ** base,size_t n,ptr_vector_qsort_r_callback * cmp,void * data)498 ptr_sort_heapify(void **base, size_t n, ptr_vector_qsort_r_callback *cmp, void *data)
499 {
500 int start = ptr_sort_heap_parent(n - 1);
501
502 while(start >= 0)
503 {
504 ptr_sort_siftdown(base, start, n - 1, cmp, data);
505 --start;
506 }
507 }
508
509 void
ptr_sort_heapsort(void ** base,size_t n,ptr_vector_qsort_r_callback * cmp,void * data)510 ptr_sort_heapsort(void **base, size_t n, ptr_vector_qsort_r_callback *cmp, void *data)
511 {
512 if(n > 2)
513 {
514 ptr_sort_heapify(base, n, cmp, data);
515
516 size_t end = n - 1;
517 while(end > 0)
518 {
519 void **tmp = base[0];
520 base[0] = base[end];
521 base[end] = tmp;
522
523 --end;
524
525 ptr_sort_siftdown(base, 0, end, cmp, data);
526 }
527 }
528 else if(n == 2)
529 {
530 if(cmp(base[0], base[1], data) > 0)
531 {
532 void **tmp = base[0];
533 base[0] = base[1];
534 base[1] = tmp;
535 }
536 }
537 }
538
539 void
ptr_sort_insertion(void ** base,size_t n,ptr_vector_qsort_r_callback * cmp,void * data)540 ptr_sort_insertion(void **base, size_t n, ptr_vector_qsort_r_callback *cmp, void *data)
541 {
542 for(ssize_t i = 1; i < (ssize_t)n; ++i)
543 {
544 void **tmp = base[i];
545 ssize_t j = i - 1;
546 for(; (j >= 0) && (cmp(base[j], tmp, data) > 0); --j)
547 {
548 base[j + 1] = base[j];
549 }
550 base[j + 1] = tmp;
551 }
552 }
553
554 void
ptr_sort3_bubble(void ** base,size_t n,ptr_vector_qsort_r_callback * cmp,void * data)555 ptr_sort3_bubble(void **base, size_t n, ptr_vector_qsort_r_callback *cmp, void *data)
556 {
557 for(size_t i = 0; i < n; ++i)
558 {
559 for(size_t j = i + 1; j < n; ++j)
560 {
561 if(cmp(base[i], base[j], data) > 0)
562 {
563 void **tmp = base[j];
564 base[j] = base[i];
565 base[i] = tmp;
566 }
567 }
568 }
569 }
570
571 struct ptr_sort3_quicksort2_stack_cell
572 {
573 void **base;
574 void **limit;
575 };
576 static void
ptr_sort_quicksort(void ** base,size_t n,ptr_vector_qsort_callback * cmp)577 ptr_sort_quicksort(void **base, size_t n, ptr_vector_qsort_callback *cmp)
578 {
579 void **limit = &base[n];
580 ssize_t sp = -1;
581
582 struct ptr_sort3_quicksort2_stack_cell stack[PTR_QSORT_DERECURSE_DEPTH];
583
584 //ssize_t msp = -1;
585
586 for(;;)
587 {
588 if(limit - base <= PTR_QSORT_SMALL)
589 {
590 //ptr_sort_insertion(base, limit - base, cmp);
591
592 for(void **ip = base + 1; ip < limit; ++ip) //for(ssize_t i = 1; i < (ssize_t)n; ++i)
593 {
594 void *tmp = *ip;
595 void **jp = ip - 1;
596 for(; (jp >= base) && (cmp(*jp, tmp) > 0); --jp)
597 {
598 jp[1] = *jp; // base[j + 1] = base[j];
599 }
600 jp[1] = tmp; //base[j + 1] = tmp;
601 }
602
603 if(sp >= 0)
604 {
605 //if(sp > msp) msp = sp;
606
607 base = stack[sp].base;
608 limit = stack[sp--].limit;
609 continue;
610 }
611
612 return;
613 }
614
615 // choose a good enough pivot
616 // doing this, start sorting
617
618 void **hip = limit - 1;
619 void **lop = base;
620 void *pivot;
621
622 {
623 void **middlep = &base[(limit - base) >> 1];
624
625 // A B C
626
627 // A > B ?
628
629 if(cmp(*lop, *middlep) > 0)
630 {
631 // A > C ?
632
633 if(cmp(*lop, *hip) > 0)
634 {
635 // A is the highest: ? ? A
636
637 if(cmp(*middlep, *hip) > 0)
638 {
639 // C is the smallest: C B A
640
641 register void *tmp = *lop; // t = A
642 *lop = *hip; // A = C
643 *hip = tmp; // C = t
644 }
645 else
646 {
647 // B is the smallest: B C A
648
649 register void *tmp = *lop; // t = A
650 *lop = *middlep; // A = B
651 *middlep = *hip; // B = C
652 *hip = tmp; // C = t
653 }
654 }
655 else // A <= C
656 {
657 // B A C
658
659 register void *tmp = *lop; // t = A
660 *lop = *middlep; // A = B
661 *middlep = tmp; // B = t
662 }
663 } // A <= B
664 else
665 {
666 // B > C ?
667
668 if(cmp(*middlep, *hip) > 0)
669 {
670 // B is the highest: ? ? B
671
672 if(cmp(*lop, *hip) > 0)
673 {
674 // C is the smallest: C A B
675
676 register void *tmp = *lop; // t = A
677 *lop = *hip; // A = C
678 *hip = *middlep; // C = B
679 *middlep = tmp; // B = t
680 }
681 else
682 {
683 // A is the smallest: A C B
684
685 register void *tmp = *middlep; // t = B
686 *middlep = *hip; // B = C
687 *hip = tmp; // C = t
688 }
689 }
690 else // B <= C
691 {
692 // A B C
693 }
694 }
695
696 pivot = *middlep;
697 }
698
699 // 0 is already < pivot
700 // last is already > pivot
701 // continue from there
702
703 ++lop;
704 --hip;
705
706 for(;;)
707 {
708 while(cmp(*lop, pivot) < 0) // while smaller than pivot
709 {
710 ++lop;
711 }
712
713 while(cmp(*hip, pivot) > 0) // while bigger than pivot
714 {
715 --hip;
716 }
717
718 ssize_t d = hip - lop;
719
720 if(d <= 1)
721 {
722 if(d > 0)
723 {
724 register void *tmp = *lop;
725 *lop = *hip;
726 *hip = tmp;
727 }
728 else
729 {
730 hip = lop;
731 }
732 break;
733 }
734
735 // exchange two values (<= pivot with >= pivot)
736
737 register void *tmp = *lop;
738 *lop = *hip;
739 *hip = tmp;
740
741 ++lop;
742 --hip;
743 }
744
745 size_t first = hip - base;
746 size_t second = limit - hip;
747
748 assert(sp < PTR_QSORT_DERECURSE_DEPTH);
749
750 if(first > second)
751 {
752 stack[++sp].base = base;
753 stack[sp].limit = hip;
754
755 base = hip;
756 }
757 else
758 {
759 stack[++sp].base = hip;
760 stack[sp].limit = limit;
761
762 limit = hip;
763 }
764 }
765 }
766
767 /**
768 * Sort the content of the vector using the compare callback
769 *
770 * @param v a pointer to the ptr_vector structure
771 * @param compare comparison callback
772 */
773
774 void
ptr_vector_qsort(ptr_vector * v,ptr_vector_qsort_callback compare)775 ptr_vector_qsort(ptr_vector* v, ptr_vector_qsort_callback compare)
776 {
777 if(v->offset > 0) /* at least 2 items */
778 {
779 ptr_sort_quicksort(v->data, v->offset + 1, compare);
780 }
781 }
782
783 static void
ptr_sort_quicksort_r(void ** base,size_t n,ptr_vector_qsort_r_callback * cmp,void * data)784 ptr_sort_quicksort_r(void **base, size_t n, ptr_vector_qsort_r_callback *cmp, void *data)
785 {
786 void **limit = &base[n];
787 ssize_t sp = -1;
788
789 struct ptr_sort3_quicksort2_stack_cell stack[PTR_QSORT_DERECURSE_DEPTH];
790
791 //ssize_t msp = -1;
792
793 for(;;)
794 {
795 if(limit - base <= PTR_QSORT_SMALL)
796 {
797 //ptr_sort_insertion(base, limit - base, cmp, data);
798
799 for(void **ip = base + 1; ip < limit; ++ip) //for(ssize_t i = 1; i < (ssize_t)n; ++i)
800 {
801 void *tmp = *ip;
802 void **jp = ip - 1;
803 for(; (jp >= base) && (cmp(*jp, tmp, data) > 0); --jp)
804 {
805 jp[1] = *jp; // base[j + 1] = base[j];
806 }
807 jp[1] = tmp; //base[j + 1] = tmp;
808 }
809
810 if(sp >= 0)
811 {
812 //if(sp > msp) msp = sp;
813
814 base = stack[sp].base;
815 limit = stack[sp--].limit;
816 continue;
817 }
818
819 return;
820 }
821
822 // choose a good enough pivot
823 // doing this, start sorting
824
825 void **hip = limit - 1;
826 void **lop = base;
827 void *pivot;
828
829 {
830 void **middlep = &base[(limit - base) >> 1];
831
832 // A B C
833
834 // A > B ?
835
836 if(cmp(*lop, *middlep, data) > 0)
837 {
838 // A > C ?
839
840 if(cmp(*lop, *hip, data) > 0)
841 {
842 // A is the highest: ? ? A
843
844 if(cmp(*middlep, *hip, data) > 0)
845 {
846 // C is the smallest: C B A
847
848 register void *tmp = *lop; // t = A
849 *lop = *hip; // A = C
850 *hip = tmp; // C = t
851 }
852 else
853 {
854 // B is the smallest: B C A
855
856 register void *tmp = *lop; // t = A
857 *lop = *middlep; // A = B
858 *middlep = *hip; // B = C
859 *hip = tmp; // C = t
860 }
861 }
862 else // A <= C
863 {
864 // B A C
865
866 register void *tmp = *lop; // t = A
867 *lop = *middlep; // A = B
868 *middlep = tmp; // B = t
869 }
870 } // A <= B
871 else
872 {
873 // B > C ?
874
875 if(cmp(*middlep, *hip, data) > 0)
876 {
877 // B is the highest: ? ? B
878
879 if(cmp(*lop, *hip, data) > 0)
880 {
881 // C is the smallest: C A B
882
883 register void *tmp = *lop; // t = A
884 *lop = *hip; // A = C
885 *hip = *middlep; // C = B
886 *middlep = tmp; // B = t
887 }
888 else
889 {
890 // A is the smallest: A C B
891
892 register void *tmp = *middlep; // t = B
893 *middlep = *hip; // B = C
894 *hip = tmp; // C = t
895 }
896 }
897 else // B <= C
898 {
899 // A B C
900 }
901 }
902
903 pivot = *middlep;
904 }
905
906 // 0 is already < pivot
907 // last is already > pivot
908 // continue from there
909
910 ++lop;
911 --hip;
912
913 for(;;)
914 {
915 while(cmp(*lop, pivot, data) < 0) // while smaller than pivot
916 {
917 ++lop;
918 }
919
920 while(cmp(*hip, pivot, data) > 0) // while bigger than pivot
921 {
922 --hip;
923 }
924
925 ssize_t d = hip - lop;
926
927 if(d <= 1)
928 {
929 if(d > 0)
930 {
931 register void *tmp = *lop;
932 *lop = *hip;
933 *hip = tmp;
934 }
935 else
936 {
937 hip = lop;
938 }
939 break;
940 }
941
942 // exchange two values (<= pivot with >= pivot)
943
944 register void *tmp = *lop;
945 *lop = *hip;
946 *hip = tmp;
947
948 ++lop;
949 --hip;
950 }
951
952 size_t first = hip - base;
953 size_t second = limit - hip;
954
955 assert(sp < PTR_QSORT_DERECURSE_DEPTH);
956
957 if(first > second)
958 {
959 stack[++sp].base = base;
960 stack[sp].limit = hip;
961
962 base = hip;
963 }
964 else
965 {
966 stack[++sp].base = hip;
967 stack[sp].limit = limit;
968
969 limit = hip;
970 }
971 }
972 }
973
974 void
ptr_vector_qsort_r(ptr_vector * v,ptr_vector_qsort_r_callback compare,void * compare_context)975 ptr_vector_qsort_r(ptr_vector *v, ptr_vector_qsort_r_callback compare, void *compare_context)
976 {
977 if(v->offset > 0) /* at least 2 items */
978 {
979 ptr_sort_quicksort_r(v->data, v->offset + 1, compare, compare_context);
980 }
981 }
982
983 void
ptr_vector_insertionsort_r(ptr_vector * v,ptr_vector_qsort_r_callback compare,void * compare_context)984 ptr_vector_insertionsort_r(ptr_vector *v, ptr_vector_qsort_r_callback compare, void *compare_context)
985 {
986 if(v->offset > 0) /* at least 2 items */
987 {
988 ptr_sort_insertion(v->data, v->offset + 1, compare, compare_context);
989 }
990 }
991
992 /**
993 * Empties the vector releasing the item memory first
994 *
995 * @param v a pointer to the ptr_vector structure
996 * @param free_memory item free callback
997 */
998
999 void
ptr_vector_callback_and_clear(ptr_vector * v,callback_function free_memory)1000 ptr_vector_callback_and_clear(ptr_vector* v, callback_function free_memory)
1001 {
1002 int n = v->offset;
1003 int i;
1004 for(i = 0; i <= n; i++)
1005 {
1006 free_memory(v->data[i]);
1007 #if DEBUG
1008 v->data[i] = NULL;
1009 #endif
1010 }
1011 v->offset = -1;
1012 }
1013
1014 /**
1015 * Look sequentially in the vector for an item using a key and a comparison function
1016 *
1017 * @param v a pointer to the ptr_vector structure
1018 * @param what the key
1019 * @param compare the comparison function
1020 *
1021 * @return the first matching item or NULL if none has been found
1022 */
1023
1024 void*
ptr_vector_linear_search(const ptr_vector * v,const void * what,ptr_vector_search_callback compare)1025 ptr_vector_linear_search(const ptr_vector* v, const void* what, ptr_vector_search_callback compare)
1026 {
1027 int last = v->offset;
1028 int i;
1029
1030 for(i = 0; i <= last; i++)
1031 {
1032 void* data = v->data[i];
1033
1034 if(compare(what, data) == 0)
1035 {
1036 return data;
1037 }
1038 }
1039
1040 return NULL;
1041 }
1042
1043 s32
ptr_vector_search_ptr_index(const ptr_vector * v,const void * what)1044 ptr_vector_search_ptr_index(const ptr_vector* v, const void* what)
1045 {
1046 int last = v->offset;
1047 int i;
1048
1049 for(i = 0; i <= last; i++)
1050 {
1051 void* data = v->data[i];
1052
1053 if(what == data)
1054 {
1055 return i;
1056 }
1057 }
1058
1059 return -1;
1060 }
1061
1062 /**
1063 * Look sequentially in the vector for an item using a key and a comparison function, returns the index of the first matching item
1064 *
1065 * @param v a pointer to the ptr_vector structure
1066 * @param what the key
1067 * @param compare the comparison function
1068 *
1069 * @return the first matching item index or -1 if none has been found
1070 */
1071
1072 s32
ptr_vector_index_of(const ptr_vector * v,const void * what,ptr_vector_search_callback compare)1073 ptr_vector_index_of(const ptr_vector* v, const void* what, ptr_vector_search_callback compare)
1074 {
1075 s32 last = v->offset;
1076 s32 i;
1077
1078 for(i = 0; i <= last; i++)
1079 {
1080 void* data = v->data[i];
1081
1082 if(compare(what, data) == 0)
1083 {
1084 return i;
1085 }
1086 }
1087
1088 return -1;
1089 }
1090
1091 /**
1092 * Look in the SORTED vector for an item using a key and a comparison function
1093 * The callback needs to tell equal (0) smaller (<0) or bigger (>0)
1094 *
1095 * @param v a pointer to the ptr_vector structure
1096 * @param what the key
1097 * @param compare the comparison function
1098 *
1099 * @return the first matching item or NULL if none has been found
1100 */
1101
1102 void*
ptr_vector_search(const ptr_vector * v,const void * what,ptr_vector_search_callback compare)1103 ptr_vector_search(const ptr_vector* v, const void* what, ptr_vector_search_callback compare)
1104 {
1105 int first = 0;
1106 int last = v->offset;
1107
1108 /*
1109 * NOTE: for small intervals, a linear search may be faster
1110 *
1111 */
1112
1113 while(first < last)
1114 {
1115
1116 int pivot = (last + first) >> 1;
1117
1118 void *item = v->data[pivot];
1119
1120 int cmp = compare(what, item);
1121
1122 if(cmp == 0)
1123 {
1124 return item;
1125 }
1126
1127 if(cmp < 0)
1128 {
1129 last = pivot - 1;
1130 }
1131 else
1132 {
1133 first = pivot + 1;
1134 }
1135 }
1136
1137 if(first == last)
1138 {
1139 void *item = v->data[first];
1140
1141 if(compare(what, item) == 0)
1142 {
1143 return item;
1144 }
1145 }
1146
1147 return NULL;
1148 }
1149
1150 /**
1151 * Look in the SORTED vector for an item using a key and a comparison function
1152 * The callback needs to tell equal (0) smaller (<0) or bigger (>0)
1153 *
1154 * @param v a pointer to the ptr_vector structure
1155 * @param what the key
1156 * @param compare the comparison function
1157 *
1158 * @return the first matching item or NULL if none has been found
1159 */
1160
1161 s32
ptr_vector_search_index(const ptr_vector * v,const void * what,ptr_vector_search_callback compare)1162 ptr_vector_search_index(const ptr_vector* v, const void* what, ptr_vector_search_callback compare)
1163 {
1164 int first = 0;
1165 int last = v->offset;
1166
1167 /*
1168 * NOTE: for small intervals, a linear search may be faster
1169 *
1170 */
1171
1172 while(first < last)
1173 {
1174
1175 int pivot = (last + first) >> 1;
1176
1177 void *item = v->data[pivot];
1178
1179 int cmp = compare(what, item);
1180
1181 if(cmp == 0)
1182 {
1183 return pivot;
1184 }
1185
1186 if(cmp < 0)
1187 {
1188 last = pivot - 1;
1189 }
1190 else
1191 {
1192 first = pivot + 1;
1193 }
1194 }
1195
1196 if(first == last)
1197 {
1198 void *item = v->data[first];
1199
1200 if(compare(what, item) == 0)
1201 {
1202 return first;
1203 }
1204 }
1205
1206 return -1;
1207 }
1208
1209 /**
1210 * Inserts a value at position, pushing items from this position up
1211 * Potentially very slow.
1212 *
1213 * @param pv
1214 * @param idx
1215 */
1216
1217 void
ptr_vector_insert_at(ptr_vector * pv,s32 idx,void * val)1218 ptr_vector_insert_at(ptr_vector *pv, s32 idx, void *val)
1219 {
1220 assert(idx >= 0);
1221
1222 if(idx <= pv->offset)
1223 {
1224 ptr_vector_ensures(pv, pv->offset + 1);
1225 memmove(&pv->data[idx + 1], &pv->data[idx], (pv->offset - idx) * sizeof(void*)); // scan-build false positive as ensures is called with size > 0 and thus data cannot be NULL
1226 pv->data[idx] = val;
1227 }
1228 else
1229 {
1230 ptr_vector_ensures(pv, idx + 1);
1231 memset(&pv->data[pv->offset + 1], 0, &pv->data[idx] - &pv->data[pv->offset + 1]); // scan-build false positive as ensures is called with size > 0 and thus data cannot be NULL
1232 pv->data[idx] = val;
1233 pv->offset = idx;
1234 }
1235 }
1236
1237 /**
1238 * Inserts multiple values at position, pushing items from this position up
1239 * Potentially very slow.
1240 *
1241 * @param pv
1242 * @param idx
1243 * @param valp an array of pointers that will be inserted
1244 * @param n the size of the array of pointers
1245 */
1246
1247 void
ptr_vector_insert_array_at(ptr_vector * pv,s32 idx,void ** valp,u32 n)1248 ptr_vector_insert_array_at(ptr_vector *pv, s32 idx, void **valp, u32 n)
1249 {
1250 assert(idx >= 0);
1251 assert(pv->offset >= -1);
1252 if(n > 0)
1253 {
1254 if(idx <= pv->offset)
1255 {
1256 ptr_vector_ensures(pv, pv->offset + n);
1257 memmove(&pv->data[idx + n], &pv->data[idx], (pv->offset - idx + n) * sizeof(void*)); // scan-build false positive as ensures is called with size > 0 and thus data cannot be NULL
1258 memcpy(&pv->data[idx], valp, n);
1259 }
1260 else
1261 {
1262 ptr_vector_ensures(pv, idx + n);
1263 memset(&pv->data[pv->offset + n], 0, &pv->data[idx] - &pv->data[pv->offset + n]); // scan-build false positive as ensures is called with size > 0 and thus data cannot be NULL
1264 memcpy(&pv->data[idx], valp, n);
1265 pv->offset = idx + n - 1;
1266 }
1267 }
1268 }
1269
1270 /**
1271 *
1272 * Removes a value at position, pulling items above this position down
1273 * Potentially very slow
1274 *
1275 * @param pv
1276 * @param idx
1277 * @return the removed value
1278 */
1279
1280 void*
ptr_vector_remove_at(ptr_vector * pv,s32 idx)1281 ptr_vector_remove_at(ptr_vector *pv, s32 idx)
1282 {
1283 void *data = pv->data[idx];
1284
1285 if(idx <= pv->offset)
1286 {
1287 memmove(&pv->data[idx], &pv->data[idx + 1], (pv->offset - idx) * sizeof(void*));
1288 --pv->offset;
1289 }
1290
1291 return data;
1292 }
1293
1294 int
ptr_vector_compare_pointers_callback(const void * a,const void * b)1295 ptr_vector_compare_pointers_callback(const void *a, const void *b)
1296 {
1297 intptr va = (intptr)a;
1298 intptr vb = (intptr)b;
1299 return va - vb;
1300 }
1301
1302 /** @} */
1303