Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-only
2 : : /*
3 : : * Copyright (c) Meta Platforms, Inc. and affiliates.
4 : : */
5 : :
6 : : #include "bpfilter/core/vector.h"
7 : :
8 : : #include <errno.h>
9 : : #include <stdint.h>
10 : : #include <stdlib.h>
11 : : #include <string.h>
12 : :
13 : : #include "bpfilter/helper.h"
14 : :
15 : : #define _BF_VECTOR_INIT_CAP 8
16 : : // Largest capacity where cap + cap / 2 does not exceed SIZE_MAX.
17 : : #define _BF_VECTOR_MAX_CAP (SIZE_MAX / 3 * 2)
18 : :
19 : 1325 : bf_vector bf_vector_default(size_t elem_size)
20 : : {
21 : : /* This is not a NULL check, but we don't want to let the caller
22 : : * create a vector with elem_size zero. And yet we want to have
23 : : * the API of `bf_vector x = bf_vector_default(y);`. */
24 : : assert(elem_size > 0);
25 : :
26 : 1325 : return (bf_vector) {.elem_size = elem_size};
27 : : }
28 : :
29 : 4 : void bf_vector_init(bf_vector *vec, size_t elem_size)
30 : : {
31 : : assert(vec);
32 : :
33 : 4 : *vec = bf_vector_default(elem_size);
34 : 4 : }
35 : :
36 : 3 : int bf_vector_new(bf_vector **vec, size_t elem_size)
37 : : {
38 : 3 : _free_bf_vector_ bf_vector *_vec = NULL;
39 : :
40 : : assert(vec);
41 : :
42 [ + + ]: 3 : if (!elem_size)
43 : : return -EINVAL;
44 : :
45 : 2 : _vec = calloc(1, sizeof(*_vec));
46 [ + - ]: 2 : if (!_vec)
47 : : return -ENOMEM;
48 : :
49 : 2 : bf_vector_init(_vec, elem_size);
50 : :
51 : 2 : *vec = TAKE_PTR(_vec);
52 : :
53 : 2 : return 0;
54 : : }
55 : :
56 : 7 : void bf_vector_free(bf_vector **vec)
57 : : {
58 : : assert(vec);
59 : :
60 [ + + ]: 7 : if (!*vec)
61 : : return;
62 : :
63 : 2 : bf_vector_clean(*vec);
64 : 2 : BF_FREEP(vec);
65 : : }
66 : :
67 : 1326 : void bf_vector_clean(bf_vector *vec)
68 : : {
69 : : assert(vec);
70 : :
71 : 1326 : BF_FREEP(&vec->data);
72 : 1326 : vec->size = 0;
73 : 1326 : vec->cap = 0;
74 : 1326 : }
75 : :
76 : 59396 : void *bf_vector_get(const bf_vector *vec, size_t index)
77 : : {
78 : : assert(vec);
79 : :
80 [ + + ]: 59396 : if (index >= vec->size)
81 : : return NULL;
82 : :
83 : 59394 : return vec->data + (index * vec->elem_size);
84 : : }
85 : :
86 : 2681 : int bf_vector_set(bf_vector *vec, size_t index, const void *elem)
87 : : {
88 : : assert(vec);
89 : : assert(elem);
90 : :
91 [ + + ]: 2681 : if (index >= vec->size)
92 : : return -EINVAL;
93 : :
94 : 2679 : memcpy(vec->data + (index * vec->elem_size), elem, vec->elem_size);
95 : :
96 : 2679 : return 0;
97 : : }
98 : :
99 : 5 : int bf_vector_remove(bf_vector *vec, size_t index)
100 : : {
101 : : assert(vec);
102 : :
103 [ + + ]: 5 : if (index >= vec->size)
104 : : return -EINVAL;
105 : :
106 : 3 : --vec->size;
107 : :
108 [ + + ]: 3 : if (index < vec->size) {
109 : 2 : memmove(vec->data + (index * vec->elem_size),
110 : 2 : vec->data + ((index + 1) * vec->elem_size),
111 : 2 : (vec->size - index) * vec->elem_size);
112 : : }
113 : :
114 : : return 0;
115 : : }
116 : :
117 : 1364 : static int _bf_vector_resize(bf_vector *vec, size_t new_cap)
118 : : {
119 : : size_t alloc_size;
120 : : int r;
121 : :
122 : : assert(vec);
123 : :
124 [ + - ]: 1364 : if (__builtin_mul_overflow(new_cap, vec->elem_size, &alloc_size))
125 : : return -EOVERFLOW;
126 : :
127 : 1364 : r = bf_realloc(&vec->data, alloc_size);
128 [ + - ]: 1364 : if (r)
129 : : return r;
130 : :
131 : 1364 : vec->cap = new_cap;
132 : :
133 : 1364 : return 0;
134 : : }
135 : :
136 : 296713 : static int _bf_vector_grow(bf_vector *vec, size_t required)
137 : : {
138 : : size_t new_cap;
139 : :
140 : : assert(vec);
141 : :
142 [ + + ]: 296713 : if (required <= vec->cap)
143 : : return 0;
144 : :
145 [ + - ]: 50 : if (vec->cap >= _BF_VECTOR_MAX_CAP)
146 : : return -ENOMEM;
147 : :
148 [ + + ]: 50 : new_cap = vec->cap ? vec->cap + (vec->cap / 2) : _BF_VECTOR_INIT_CAP;
149 : 50 : new_cap = bf_max(new_cap, required);
150 : 50 : new_cap = bf_min(new_cap, _BF_VECTOR_MAX_CAP);
151 : :
152 [ + - ]: 50 : if (new_cap < required)
153 : : return -ENOMEM;
154 : :
155 : 50 : return _bf_vector_resize(vec, new_cap);
156 : : }
157 : :
158 : 296711 : int bf_vector_add(bf_vector *vec, const void *elem)
159 : : {
160 : : size_t required;
161 : : int r;
162 : :
163 : : assert(vec);
164 : : assert(elem);
165 : :
166 [ + - ]: 296711 : if (__builtin_add_overflow(vec->size, 1, &required))
167 : : return -ENOMEM;
168 : :
169 : 296711 : r = _bf_vector_grow(vec, required);
170 [ + - ]: 296711 : if (r)
171 : : return r;
172 : :
173 : 296711 : memcpy(vec->data + (vec->size * vec->elem_size), elem, vec->elem_size);
174 : 296711 : ++vec->size;
175 : :
176 : 296711 : return 0;
177 : : }
178 : :
179 : 3 : int bf_vector_add_many(bf_vector *vec, const void *data, size_t count)
180 : : {
181 : : size_t required;
182 : : int r;
183 : :
184 : : assert(vec);
185 : : assert(data);
186 : :
187 [ + + ]: 3 : if (!count)
188 : : return 0;
189 : :
190 [ + - ]: 2 : if (__builtin_add_overflow(vec->size, count, &required))
191 : : return -ENOMEM;
192 : :
193 : 2 : r = _bf_vector_grow(vec, required);
194 [ + - ]: 2 : if (r)
195 : : return r;
196 : :
197 : 2 : memcpy(vec->data + (vec->size * vec->elem_size), data,
198 : 2 : count * vec->elem_size);
199 : 2 : vec->size += count;
200 : :
201 : 2 : return 0;
202 : : }
203 : :
204 : 1314 : int bf_vector_reserve(bf_vector *vec, size_t cap)
205 : : {
206 : : assert(vec);
207 : :
208 [ + - ]: 1314 : if (cap <= vec->cap)
209 : : return 0;
210 : :
211 [ + - ]: 1314 : if (cap > _BF_VECTOR_MAX_CAP)
212 : : return -ENOMEM;
213 : :
214 : 1314 : return _bf_vector_resize(vec, cap);
215 : : }
216 : :
217 : 2 : void *bf_vector_take(bf_vector *vec)
218 : : {
219 : : assert(vec);
220 : :
221 : 2 : vec->size = 0;
222 : 2 : vec->cap = 0;
223 : :
224 : 2 : return TAKE_PTR(vec->data);
225 : : }
|
