Line | Branch | Exec | Source |
---|---|---|---|
1 | #include <errno.h> | ||
2 | #include <string.h> | ||
3 | #include "ptr-array.h" | ||
4 | |||
5 | 13509 | static void ptr_array_grow(PointerArray *array) | |
6 | { | ||
7 | 13509 | BUG_ON(array->alloc < array->count); | |
8 | 13509 | const size_t alloc_min = 8; | |
9 |
2/2✓ Branch 0 (4→5) taken 470 times.
✓ Branch 1 (4→6) taken 13039 times.
|
13509 | size_t alloc = MAX((array->alloc * 3) / 2, alloc_min); |
10 |
1/2✗ Branch 0 (6→7) not taken.
✓ Branch 1 (6→8) taken 13509 times.
|
13509 | if (unlikely(alloc <= array->count)) { |
11 | − | fatal_error(__func__, EOVERFLOW); | |
12 | } | ||
13 | 13509 | array->ptrs = xrenew(array->ptrs, alloc); | |
14 | 13509 | array->alloc = alloc; | |
15 | 13509 | } | |
16 | |||
17 | // This is separate from ptr_array_append(), to allow the hot path to be | ||
18 | // inlined. It also duplicates the append operation so as to allow tail | ||
19 | // calling, which appears to improve code generation. | ||
20 | 13509 | void ptr_array_grow_and_append(PointerArray *array, void *ptr) | |
21 | { | ||
22 | 13509 | ptr_array_grow(array); | |
23 | 13509 | array->ptrs[array->count++] = ptr; | |
24 | 13509 | } | |
25 | |||
26 | // Move a pointer from one index to another | ||
27 | 34 | void ptr_array_move(PointerArray *array, size_t from, size_t to) | |
28 | { | ||
29 | 34 | BUG_ON(from >= array->count); | |
30 | 34 | BUG_ON(to >= array->count); | |
31 |
2/2✓ Branch 0 (6→7) taken 24 times.
✓ Branch 1 (6→17) taken 10 times.
|
34 | if (unlikely(from == to)) { |
32 | return; | ||
33 | } | ||
34 | |||
35 | 24 | void **p = array->ptrs; | |
36 | 24 | bool up = (from < to); | |
37 |
2/2✓ Branch 0 (7→8) taken 8 times.
✓ Branch 1 (7→9) taken 16 times.
|
24 | void *dest = up ? p + from : p + to + 1; |
38 |
2/2✓ Branch 0 (10→11) taken 8 times.
✓ Branch 1 (10→12) taken 16 times.
|
24 | void *src = up ? p + from + 1 : p + to; |
39 |
2/2✓ Branch 0 (13→14) taken 8 times.
✓ Branch 1 (13→15) taken 16 times.
|
24 | size_t difference = up ? to - from : from - to; |
40 | |||
41 | 24 | void *tmp = p[from]; | |
42 | 24 | memmove(dest, src, difference * sizeof(void*)); | |
43 | 24 | p[to] = tmp; | |
44 | } | ||
45 | |||
46 | 12 | void ptr_array_insert(PointerArray *array, void *ptr, size_t idx) | |
47 | { | ||
48 | 12 | size_t last = array->count; | |
49 | 12 | BUG_ON(idx > last); | |
50 | 12 | ptr_array_append(array, ptr); // last is now array->count - 1 | |
51 | 12 | ptr_array_move(array, last, idx); | |
52 | 12 | } | |
53 | |||
54 | // Free and remove and all pointers, without freeing the array itself | ||
55 | 14970 | void ptr_array_clear(PointerArray *array, FreeFunction free_ptr) | |
56 | { | ||
57 |
2/2✓ Branch 0 (5→3) taken 45688 times.
✓ Branch 1 (5→6) taken 14970 times.
|
60658 | for (size_t i = 0, n = array->count; i < n; i++) { |
58 | 45688 | do_free_value(free_ptr, array->ptrs[i]); | |
59 | 45688 | array->ptrs[i] = NULL; | |
60 | } | ||
61 | 14970 | array->count = 0; | |
62 | 14970 | } | |
63 | |||
64 | 14970 | void ptr_array_free_cb(PointerArray *array, FreeFunction free_ptr) | |
65 | { | ||
66 | 14970 | ptr_array_clear(array, free_ptr); | |
67 | 14970 | ptr_array_free_array(array); | |
68 | 14970 | } | |
69 | |||
70 | 254 | size_t ptr_array_remove(PointerArray *array, void *ptr) | |
71 | { | ||
72 | 254 | size_t idx = ptr_array_index(array, ptr); | |
73 | 254 | ptr_array_remove_index(array, idx); | |
74 | 254 | return idx; | |
75 | } | ||
76 | |||
77 | 2176 | void *ptr_array_remove_index(PointerArray *array, size_t idx) | |
78 | { | ||
79 | 2176 | BUG_ON(idx >= array->count); | |
80 | 2176 | void **ptrs = array->ptrs + idx; | |
81 | 2176 | void *removed = *ptrs; | |
82 | 2176 | memmove(ptrs, ptrs + 1, (--array->count - idx) * sizeof(void*)); | |
83 | 2176 | return removed; | |
84 | } | ||
85 | |||
86 | // Return the first array index found to contain `ptr`, or SIZE_MAX | ||
87 | // if not found. See also: ptr_array_xindex(), ptr_array_bsearch(). | ||
88 | 2165 | size_t ptr_array_index(const PointerArray *array, const void *ptr) | |
89 | { | ||
90 |
1/2✓ Branch 0 (5→3) taken 8216 times.
✗ Branch 1 (5→6) not taken.
|
8216 | for (size_t i = 0, n = array->count; i < n; i++) { |
91 |
2/2✓ Branch 0 (3→4) taken 6051 times.
✓ Branch 1 (3→6) taken 2165 times.
|
8216 | if (array->ptrs[i] == ptr) { |
92 | return i; | ||
93 | } | ||
94 | } | ||
95 | |||
96 | // If `ptr` isn't found in the array, return -1 (SIZE_MAX). Callers | ||
97 | // should check that the returned index is less than `array->count` | ||
98 | // before indexing `array->ptrs` with it or use ptr_array_xindex() | ||
99 | // instead, if applicable. | ||
100 | return -1; | ||
101 | } | ||
102 | |||
103 | // Trim all leading NULLs and all but one trailing NULL (if any) | ||
104 | 1895 | void ptr_array_trim_nulls(PointerArray *array) | |
105 | { | ||
106 | 1895 | size_t n = array->count; | |
107 |
2/2✓ Branch 0 (2→3) taken 1894 times.
✓ Branch 1 (2→17) taken 1 times.
|
1895 | if (n == 0) { |
108 | return; | ||
109 | } | ||
110 | |||
111 | 1894 | void **ptrs = array->ptrs; | |
112 |
4/4✓ Branch 0 (4→5) taken 3789 times.
✓ Branch 1 (4→6) taken 2 times.
✓ Branch 2 (5→4) taken 1897 times.
✓ Branch 3 (5→6) taken 1892 times.
|
3791 | while (n > 0 && ptrs[n - 1] == NULL) { |
113 | n--; | ||
114 | } | ||
115 | |||
116 |
1/2✓ Branch 0 (6→7) taken 1894 times.
✗ Branch 1 (6→8) not taken.
|
1894 | if (n != array->count) { |
117 | // Leave 1 trailing NULL | ||
118 | 1894 | n++; | |
119 | } | ||
120 | |||
121 |
3/4✓ Branch 0 (8→9) taken 1894 times.
✗ Branch 1 (8→10) not taken.
✓ Branch 2 (9→10) taken 1891 times.
✓ Branch 3 (9→12) taken 3 times.
|
1894 | if (n == 0 || ptrs[0] != NULL) { |
122 | // No leading NULLs; simply adjust count and return early | ||
123 | 1891 | array->count = n; | |
124 | 1891 | return; | |
125 | } | ||
126 | |||
127 | size_t i = 0; | ||
128 |
4/4✓ Branch 0 (12→13) taken 5 times.
✓ Branch 1 (12→14) taken 2 times.
✓ Branch 2 (13→11) taken 4 times.
✓ Branch 3 (13→14) taken 1 times.
|
7 | while (i < n && ptrs[i] == NULL) { |
129 | 4 | i++; | |
130 | } | ||
131 | |||
132 | 3 | BUG_ON(i == 0); | |
133 | 3 | n -= i; | |
134 | 3 | array->count = n; | |
135 | 3 | memmove(ptrs, ptrs + i, n * sizeof(void*)); | |
136 | } | ||
137 |