1 /* radare - LGPL - Copyright 2017-2020 - maskray, thestr4ng3r */
2
3 #include "r_vector.h"
4
5 // Optimize memory usage on glibc
6 #if __WORDSIZE == 32
7 // Chunk size 24, minus 4 (chunk header), minus 8 for capacity and len, 12 bytes remaining for 3 void *
8 #define INITIAL_VECTOR_LEN 3
9 #else
10 // For __WORDSIZE == 64
11 // Chunk size 48, minus 8 (chunk header), minus 8 for capacity and len, 32 bytes remaining for 4 void *
12 #define INITIAL_VECTOR_LEN 4
13 #endif
14
15 #define NEXT_VECTOR_CAPACITY (vec->capacity < INITIAL_VECTOR_LEN \
16 ? INITIAL_VECTOR_LEN \
17 : vec->capacity <= 12 ? vec->capacity * 2 \
18 : vec->capacity + (vec->capacity >> 1))
19
20 #define RESIZE_OR_RETURN_NULL(next_capacity) do { \
21 size_t new_capacity = next_capacity; \
22 void **new_a = realloc (vec->a, vec->elem_size * new_capacity); \
23 if (!new_a) { \
24 return NULL; \
25 } \
26 vec->a = new_a; \
27 vec->capacity = new_capacity; \
28 } while (0)
29
r_vector_init(RVector * vec,size_t elem_size,RVectorFree free,void * free_user)30 R_API void r_vector_init(RVector *vec, size_t elem_size, RVectorFree free, void *free_user) {
31 r_return_if_fail (vec);
32 vec->a = NULL;
33 vec->capacity = vec->len = 0;
34 vec->elem_size = elem_size;
35 vec->free = free;
36 vec->free_user = free_user;
37 }
38
r_vector_new(size_t elem_size,RVectorFree free,void * free_user)39 R_API RVector *r_vector_new(size_t elem_size, RVectorFree free, void *free_user) {
40 RVector *vec = R_NEW (RVector);
41 if (!vec) {
42 return NULL;
43 }
44 r_vector_init (vec, elem_size, free, free_user);
45 return vec;
46 }
47
vector_free_elems(RVector * vec)48 static void vector_free_elems(RVector *vec) {
49 if (vec->free) {
50 while (vec->len > 0) {
51 vec->free (r_vector_index_ptr (vec, --vec->len), vec->free_user);
52 }
53 } else {
54 vec->len = 0;
55 }
56 }
57
r_vector_fini(RVector * vec)58 R_API void r_vector_fini(RVector *vec) {
59 r_return_if_fail (vec);
60 r_vector_clear (vec);
61 vec->free = NULL;
62 vec->free_user = NULL;
63 }
64
r_vector_clear(RVector * vec)65 R_API void r_vector_clear(RVector *vec) {
66 r_return_if_fail (vec);
67 vector_free_elems (vec);
68 R_FREE (vec->a);
69 vec->capacity = 0;
70 }
71
r_vector_free(RVector * vec)72 R_API void r_vector_free(RVector *vec) {
73 if (vec) {
74 r_vector_fini (vec);
75 free (vec);
76 }
77 }
78
vector_clone(RVector * dst,RVector * src)79 static bool vector_clone(RVector *dst, RVector *src) {
80 r_return_val_if_fail (dst && src, false);
81 dst->capacity = src->capacity;
82 dst->len = src->len;
83 dst->elem_size = src->elem_size;
84 dst->free = src->free;
85 dst->free_user = src->free_user;
86 if (!dst->len) {
87 dst->a = NULL;
88 } else {
89 dst->a = malloc (src->elem_size * src->capacity);
90 if (!dst->a) {
91 return false;
92 }
93 memcpy (dst->a, src->a, src->elem_size * src->len);
94 }
95 return true;
96 }
97
r_vector_clone(RVector * vec)98 R_API RVector *r_vector_clone(RVector *vec) {
99 r_return_val_if_fail (vec, NULL);
100 RVector *ret = R_NEW (RVector);
101 if (!ret) {
102 return NULL;
103 }
104 if (!vector_clone (ret, vec)) {
105 free (ret);
106 return NULL;
107 }
108 return ret;
109 }
110
r_vector_assign(RVector * vec,void * p,void * elem)111 R_API void r_vector_assign(RVector *vec, void *p, void *elem) {
112 r_return_if_fail (vec && p && elem);
113 memcpy (p, elem, vec->elem_size);
114 }
115
r_vector_assign_at(RVector * vec,size_t index,void * elem)116 R_API void *r_vector_assign_at(RVector *vec, size_t index, void *elem) {
117 void *p = r_vector_index_ptr (vec, index);
118 if (elem) {
119 r_vector_assign (vec, p, elem);
120 }
121 return p;
122 }
123
r_vector_remove_at(RVector * vec,size_t index,void * into)124 R_API void r_vector_remove_at(RVector *vec, size_t index, void *into) {
125 r_return_if_fail (vec);
126 void *p = r_vector_index_ptr (vec, index);
127 if (into) {
128 r_vector_assign (vec, into, p);
129 }
130 vec->len--;
131 if (index < vec->len) {
132 memmove (p, (char *)p + vec->elem_size, vec->elem_size * (vec->len - index));
133 }
134 }
135
r_vector_insert(RVector * vec,size_t index,void * x)136 R_API void *r_vector_insert(RVector *vec, size_t index, void *x) {
137 r_return_val_if_fail (vec && index <= vec->len, NULL);
138 if (vec->len >= vec->capacity) {
139 RESIZE_OR_RETURN_NULL (NEXT_VECTOR_CAPACITY);
140 }
141 void *p = r_vector_index_ptr (vec, index);
142 if (index < vec->len) {
143 memmove ((char *)p + vec->elem_size, p, vec->elem_size * (vec->len - index));
144 }
145 vec->len++;
146 if (x) {
147 r_vector_assign (vec, p, x);
148 }
149 return p;
150 }
151
r_vector_insert_range(RVector * vec,size_t index,void * first,size_t count)152 R_API void *r_vector_insert_range(RVector *vec, size_t index, void *first, size_t count) {
153 r_return_val_if_fail (vec && index <= vec->len, NULL);
154 if (vec->len + count > vec->capacity) {
155 RESIZE_OR_RETURN_NULL (R_MAX (NEXT_VECTOR_CAPACITY, vec->len + count));
156 }
157 size_t sz = count * vec->elem_size;
158 void *p = r_vector_index_ptr (vec, index);
159 if (index < vec->len) {
160 memmove ((char *)p + sz, p, vec->elem_size * (vec->len - index));
161 }
162 vec->len += count;
163 if (first) {
164 memcpy (p, first, sz);
165 }
166 return p;
167 }
168
r_vector_pop(RVector * vec,void * into)169 R_API void r_vector_pop(RVector *vec, void *into) {
170 r_return_if_fail (vec);
171 if (into) {
172 r_vector_assign (vec, into, r_vector_index_ptr (vec, vec->len - 1));
173 }
174 vec->len--;
175 }
176
r_vector_pop_front(RVector * vec,void * into)177 R_API void r_vector_pop_front(RVector *vec, void *into) {
178 r_return_if_fail (vec);
179 r_vector_remove_at (vec, 0, into);
180 }
181
r_vector_push(RVector * vec,void * x)182 R_API void *r_vector_push(RVector *vec, void *x) {
183 r_return_val_if_fail (vec, NULL);
184 if (vec->len >= vec->capacity) {
185 RESIZE_OR_RETURN_NULL (NEXT_VECTOR_CAPACITY);
186 }
187 void *p = r_vector_index_ptr (vec, vec->len++);
188 if (x) {
189 r_vector_assign (vec, p, x);
190 }
191 return p;
192 }
193
r_vector_push_front(RVector * vec,void * x)194 R_API void *r_vector_push_front(RVector *vec, void *x) {
195 r_return_val_if_fail (vec, NULL);
196 return r_vector_insert (vec, 0, x);
197 }
198
r_vector_reserve(RVector * vec,size_t capacity)199 R_API void *r_vector_reserve(RVector *vec, size_t capacity) {
200 r_return_val_if_fail (vec, NULL);
201 if (vec->capacity < capacity) {
202 RESIZE_OR_RETURN_NULL (capacity);
203 }
204 return vec->a;
205 }
206
r_vector_shrink(RVector * vec)207 R_API void *r_vector_shrink(RVector *vec) {
208 r_return_val_if_fail (vec, NULL);
209 if (vec->len < vec->capacity) {
210 RESIZE_OR_RETURN_NULL (vec->len);
211 }
212 return vec->a;
213 }
214
215 // pvector
216
pvector_free_elem(void * e,void * user)217 static void pvector_free_elem(void *e, void *user) {
218 void *p = *((void **)e);
219 RPVectorFree elem_free = (RPVectorFree)user;
220 elem_free (p);
221 }
222
r_pvector_init(RPVector * vec,RPVectorFree free)223 R_API void r_pvector_init(RPVector *vec, RPVectorFree free) {
224 r_vector_init (&vec->v, sizeof (void *), free ? pvector_free_elem : NULL, free);
225 }
226
r_pvector_new(RPVectorFree free)227 R_API RPVector *r_pvector_new(RPVectorFree free) {
228 RPVector *v = R_NEW (RPVector);
229 if (!v) {
230 return NULL;
231 }
232 r_pvector_init (v, free);
233 return v;
234 }
235
r_pvector_new_with_len(RPVectorFree free,size_t length)236 R_API RPVector *r_pvector_new_with_len(RPVectorFree free, size_t length) {
237 RPVector *v = r_pvector_new (free);
238 if (!v) {
239 return NULL;
240 }
241 void** p = r_pvector_reserve (v, length);
242 if (!p) {
243 r_pvector_free (v);
244 return NULL;
245 }
246 memset (p, 0, v->v.elem_size * v->v.capacity);
247 v->v.len = length;
248 return v;
249 }
250
r_pvector_clear(RPVector * vec)251 R_API void r_pvector_clear(RPVector *vec) {
252 r_return_if_fail (vec);
253 r_vector_clear (&vec->v);
254 }
255
r_pvector_fini(RPVector * vec)256 R_API void r_pvector_fini(RPVector *vec) {
257 r_return_if_fail (vec);
258 r_vector_fini (&vec->v);
259 }
260
r_pvector_free(RPVector * vec)261 R_API void r_pvector_free(RPVector *vec) {
262 if (!vec) {
263 return;
264 }
265 r_vector_fini (&vec->v);
266 free (vec);
267 }
268
r_pvector_contains(RPVector * vec,void * x)269 R_API void **r_pvector_contains(RPVector *vec, void *x) {
270 r_return_val_if_fail (vec, NULL);
271 size_t i;
272 for (i = 0; i < vec->v.len; i++) {
273 if (((void **)vec->v.a)[i] == x) {
274 return &((void **)vec->v.a)[i];
275 }
276 }
277 return NULL;
278 }
279
r_pvector_remove_at(RPVector * vec,size_t index)280 R_API void *r_pvector_remove_at(RPVector *vec, size_t index) {
281 r_return_val_if_fail (vec, NULL);
282 void *r = r_pvector_at (vec, index);
283 r_vector_remove_at (&vec->v, index, NULL);
284 return r;
285 }
286
r_pvector_remove_data(RPVector * vec,void * x)287 R_API void r_pvector_remove_data(RPVector *vec, void *x) {
288 void **el = r_pvector_contains (vec, x);
289 if (!el) {
290 return;
291 }
292
293 size_t index = el - (void **)vec->v.a;
294 r_vector_remove_at (&vec->v, index, NULL);
295 }
296
r_pvector_pop(RPVector * vec)297 R_API void *r_pvector_pop(RPVector *vec) {
298 r_return_val_if_fail (vec, NULL);
299 void *r = r_pvector_at (vec, vec->v.len - 1);
300 r_vector_pop (&vec->v, NULL);
301 return r;
302 }
303
r_pvector_pop_front(RPVector * vec)304 R_API void *r_pvector_pop_front(RPVector *vec) {
305 r_return_val_if_fail (vec, NULL);
306 void *r = r_pvector_at (vec, 0);
307 r_vector_pop_front (&vec->v, NULL);
308 return r;
309 }
310
311 // CLRS Quicksort. It is slow, but simple.
quick_sort(void ** a,size_t n,RPVectorComparator cmp)312 static void quick_sort(void **a, size_t n, RPVectorComparator cmp) {
313 if (n <= 1) {
314 return;
315 }
316 size_t i = rand() % n, j = 0;
317 void *t, *pivot = a[i];
318 a[i] = a[n - 1];
319 for (i = 0; i < n - 1; i++) {
320 if (cmp (a[i], pivot) < 0) {
321 t = a[i];
322 a[i] = a[j];
323 a[j] = t;
324 j++;
325 }
326 }
327 a[n - 1] = a[j];
328 a[j] = pivot;
329 quick_sort (a, j, cmp);
330 quick_sort (a + j + 1, n - j - 1, cmp);
331 }
332
r_pvector_sort(RPVector * vec,RPVectorComparator cmp)333 R_API void r_pvector_sort(RPVector *vec, RPVectorComparator cmp) {
334 r_return_if_fail (vec && cmp);
335 quick_sort (vec->v.a, vec->v.len, cmp);
336 }
337