1 #ifndef R2_VECTOR_H
2 #define R2_VECTOR_H
3
4 #include <r_types.h>
5 #include <r_util/r_assert.h>
6 #ifdef __cplusplus
7 extern "C" {
8 #endif
9
10 /*
11 * RVector can contain arbitrarily sized elements.
12 * RPVector uses RVector internally and always contains void *s
13 *
14 * Thus, for storing pointers it is highly encouraged to always use RPVector
15 * as it is specifically made for this purpose and is more consistent with RList,
16 * while RVector can be used as, for example, a flat array of a struct.
17 *
18 * Notable differences between RVector and RPVector:
19 * -------------------------------------------------
20 * When RVector expects an element to be inserted, for example in r_vector_push(..., void *x),
21 * this void * value is interpreted as a pointer to the actual data for the element.
22 * => If you use RVector as a dynamic replacement for (struct SomeStruct)[], you will
23 * pass a struct SomeStruct * to these functions.
24 *
25 * Because RPVector only handles pointers, the given void * is directly interpreted as the
26 * actual pointer to be inserted.
27 * => If you use RPVector as a dynamic replacement for (SomeType *)[], you will pass
28 * SomeType * directly to these functions.
29 *
30 * The same differentiation goes for the free functions:
31 * - The element parameter in RVectorFree is a pointer to the element inside the array.
32 * - The element parameter in RPVectorFree is the actual pointer stored in the array.
33 *
34 * General Hint:
35 * -------------
36 * remove/pop functions do not reduce the capacity.
37 * Call r_(p)vector_shrink explicitly if desired.
38 */
39
40 typedef int (*RPVectorComparator)(const void *a, const void *b);
41 typedef void (*RVectorFree)(void *e, void *user);
42 typedef void (*RPVectorFree)(void *e);
43
44 typedef struct r_vector_t {
45 void *a;
46 size_t len;
47 size_t capacity;
48 size_t elem_size;
49 RVectorFree free;
50 void *free_user;
51 } RVector;
52
53 // RPVector directly wraps RVector for type safety
54 typedef struct r_pvector_t { RVector v; } RPVector;
55
56
57 // RVector
58
59 R_API void r_vector_init(RVector *vec, size_t elem_size, RVectorFree free, void *free_user);
60
61 R_API RVector *r_vector_new(size_t elem_size, RVectorFree free, void *free_user);
62
63 // clears the vector and calls vec->free on every element if set.
64 R_API void r_vector_fini(RVector *vec);
65
66 // frees the vector and calls vec->free on every element if set.
67 R_API void r_vector_free(RVector *vec);
68
69 // the returned vector will have the same capacity as vec.
70 R_API RVector *r_vector_clone(RVector *vec);
71
r_vector_empty(const RVector * vec)72 static inline bool r_vector_empty(const RVector *vec) {
73 r_return_val_if_fail (vec, false);
74 return vec->len == 0;
75 }
76
77 R_API void r_vector_clear(RVector *vec);
78
79 // returns the length of the vector
r_vector_len(const RVector * vec)80 static inline size_t r_vector_len(const RVector *vec) {
81 r_return_val_if_fail (vec, 0);
82 return vec->len;
83 }
84
85 // returns a pointer to the offset inside the array where the element of the index lies.
r_vector_index_ptr(RVector * vec,size_t index)86 static inline void *r_vector_index_ptr(RVector *vec, size_t index) {
87 r_return_val_if_fail (vec && index < vec->capacity, NULL);
88 return (char *)vec->a + vec->elem_size * index;
89 }
90
91 // helper function to assign an element of size vec->elem_size from elem to p.
92 // elem is a pointer to the actual data to assign!
93 R_API void r_vector_assign(RVector *vec, void *p, void *elem);
94
95 // assign the value of size vec->elem_size at elem to vec at the given index.
96 // elem is a pointer to the actual data to assign!
97 R_API void *r_vector_assign_at(RVector *vec, size_t index, void *elem);
98
99 // remove the element at the given index and write the content to into.
100 // It is the caller's responsibility to free potential resources associated with the element.
101 R_API void r_vector_remove_at(RVector *vec, size_t index, void *into);
102
103 // insert the value of size vec->elem_size at x at the given index.
104 // x is a pointer to the actual data to assign!
105 R_API void *r_vector_insert(RVector *vec, size_t index, void *x);
106
107 // insert count values of size vec->elem_size into vec starting at the given index.
108 R_API void *r_vector_insert_range(RVector *vec, size_t index, void *first, size_t count);
109
110 // like r_vector_remove_at for the last element
111 R_API void r_vector_pop(RVector *vec, void *into);
112
113 // like r_vector_remove_at for the first element
114 R_API void r_vector_pop_front(RVector *vec, void *into);
115
116 // like r_vector_insert for the end of vec
117 R_API void *r_vector_push(RVector *vec, void *x);
118
119 // like r_vector_insert for the beginning of vec
120 R_API void *r_vector_push_front(RVector *vec, void *x);
121
122 // make sure the capacity is at least capacity.
123 R_API void *r_vector_reserve(RVector *vec, size_t capacity);
124
125 // shrink capacity to len.
126 R_API void *r_vector_shrink(RVector *vec);
127
128 /*
129 * example:
130 *
131 * RVector *v = ...; // <contains MyStruct>
132 * MyStruct *it;
133 * r_vector_foreach (v, it) {
134 * // Do something with it
135 * }
136 */
137 #define r_vector_foreach(vec, it) \
138 if (!r_vector_empty (vec)) \
139 for (it = (void *)(vec)->a; (char *)it != (char *)(vec)->a + ((vec)->len * (vec)->elem_size); it = (void *)((char *)it + (vec)->elem_size))
140
141 #define r_vector_foreach_prev(vec, it) \
142 if (!r_vector_empty (vec)) \
143 for (it = (void *)((char *)(vec)->a + (((vec)->len - 1)* (vec)->elem_size)); (char *)it != (char *)(vec)->a; it = (void *)((char *)it - (vec)->elem_size))
144
145 #define r_vector_enumerate(vec, it, i) \
146 if (!r_vector_empty (vec)) \
147 for (it = (void *)(vec)->a, i = 0; i < (vec)->len; it = (void *)((char *)it + (vec)->elem_size), i++)
148
149 /*
150 * example:
151 *
152 * RVector *v = ...; // contains {(st64)0, (st64)2, (st64)4, (st64)6, (st64)8};
153 * size_t l;
154 * #define CMP(x, y) x - (*(st64 *)y)
155 * r_vector_lower_bound (v, 3, l, CMP);
156 * // l == 2
157 */
158 #define r_vector_lower_bound(vec, x, i, cmp) \
159 do { \
160 size_t h = (vec)->len, m; \
161 for (i = 0; i < h; ) { \
162 m = i + ((h - i) >> 1); \
163 if ((cmp (x, ((char *)(vec)->a + (vec)->elem_size * m))) > 0) { \
164 i = m + 1; \
165 } else { \
166 h = m; \
167 } \
168 } \
169 } while (0) \
170
171 #define r_vector_upper_bound(vec, x, i, cmp) \
172 do { \
173 size_t h = (vec)->len, m; \
174 for (i = 0; i < h; ) { \
175 m = i + ((h - i) >> 1); \
176 if ((cmp (x, ((char *)(vec)->a + (vec)->elem_size * m))) < 0) { \
177 h = m; \
178 } else { \
179 i = m + 1; \
180 } \
181 } \
182 } while (0) \
183
184 // RPVector
185
186 R_API void r_pvector_init(RPVector *vec, RPVectorFree free);
187 R_API void r_pvector_fini(RPVector *vec);
188
189 R_API RPVector *r_pvector_new(RPVectorFree free);
190
191 R_API RPVector *r_pvector_new_with_len(RPVectorFree free, size_t length);
192
193 // clear the vector and call vec->v.free on every element.
194 R_API void r_pvector_clear(RPVector *vec);
195
196 // free the vector and call vec->v.free on every element.
197 R_API void r_pvector_free(RPVector *vec);
198
r_pvector_len(const RPVector * vec)199 static inline size_t r_pvector_len(const RPVector *vec) {
200 r_return_val_if_fail (vec, 0);
201 return vec->v.len;
202 }
203
r_pvector_at(const RPVector * vec,size_t index)204 static inline void *r_pvector_at(const RPVector *vec, size_t index) {
205 r_return_val_if_fail (vec && index < vec->v.len, NULL);
206 return ((void **)vec->v.a)[index];
207 }
208
r_pvector_set(RPVector * vec,size_t index,void * e)209 static inline void r_pvector_set(RPVector *vec, size_t index, void *e) {
210 r_return_if_fail (vec && index < vec->v.len);
211 ((void **)vec->v.a)[index] = e;
212 }
213
r_pvector_empty(RPVector * vec)214 static inline bool r_pvector_empty(RPVector *vec) {
215 return r_pvector_len (vec) == 0;
216 }
217
218 // returns a pointer to the offset inside the array where the element of the index lies.
r_pvector_index_ptr(RPVector * vec,size_t index)219 static inline void **r_pvector_index_ptr(RPVector *vec, size_t index) {
220 r_return_val_if_fail (vec && index < vec->v.capacity, NULL);
221 return ((void **)vec->v.a) + index;
222 }
223
224 // same as r_pvector_index_ptr(<vec>, 0)
r_pvector_data(RPVector * vec)225 static inline void **r_pvector_data(RPVector *vec) {
226 r_return_val_if_fail (vec, NULL);
227 return (void **)vec->v.a;
228 }
229
230 // returns the respective pointer inside the vector if x is found or NULL otherwise.
231 R_API void **r_pvector_contains(RPVector *vec, void *x);
232
233 // removes and returns the pointer at the given index. Does not call free.
234 R_API void *r_pvector_remove_at(RPVector *vec, size_t index);
235
236 // removes the element x, if present. Does not call free.
237 R_API void r_pvector_remove_data(RPVector *vec, void *x);
238
239 // like r_vector_insert, but the pointer x is the actual data to be inserted.
r_pvector_insert(RPVector * vec,size_t index,void * x)240 static inline void **r_pvector_insert(RPVector *vec, size_t index, void *x) {
241 return (void **)r_vector_insert (&vec->v, index, &x);
242 }
243
244 // like r_vector_insert_range.
r_pvector_insert_range(RPVector * vec,size_t index,void ** first,size_t count)245 static inline void **r_pvector_insert_range(RPVector *vec, size_t index, void **first, size_t count) {
246 return (void **)r_vector_insert_range (&vec->v, index, first, count);
247 }
248
249 // like r_vector_pop, but returns the pointer directly.
250 R_API void *r_pvector_pop(RPVector *vec);
251
252 // like r_vector_pop_front, but returns the pointer directly.
253 R_API void *r_pvector_pop_front(RPVector *vec);
254
255 // like r_vector_push, but the pointer x is the actual data to be inserted.
r_pvector_push(RPVector * vec,void * x)256 static inline void **r_pvector_push(RPVector *vec, void *x) {
257 return (void **)r_vector_push (&vec->v, &x);
258 }
259
260 // like r_vector_push_front, but the pointer x is the actual data to be inserted.
r_pvector_push_front(RPVector * vec,void * x)261 static inline void **r_pvector_push_front(RPVector *vec, void *x) {
262 return (void **)r_vector_push_front (&vec->v, &x);
263 }
264
265 // sort vec using quick sort.
266 R_API void r_pvector_sort(RPVector *vec, RPVectorComparator cmp);
267
r_pvector_reserve(RPVector * vec,size_t capacity)268 static inline void **r_pvector_reserve(RPVector *vec, size_t capacity) {
269 return (void **)r_vector_reserve (&vec->v, capacity);
270 }
271
r_pvector_shrink(RPVector * vec)272 static inline void **r_pvector_shrink(RPVector *vec) {
273 return (void **)r_vector_shrink (&vec->v);
274 }
275
276 /*
277 * example:
278 *
279 * RVector *v = ...;
280 * void **it;
281 * r_pvector_foreach (v, it) {
282 * void *p = *it;
283 * // Do something with p
284 * }
285 */
286 #define r_pvector_foreach(vec, it) \
287 for (it = (void **)(vec)->v.a; it != (void **)(vec)->v.a + (vec)->v.len; it++)
288
289 // like r_pvector_foreach() but inverse
290 #define r_pvector_foreach_prev(vec, it) \
291 for (it = ((vec)->v.len == 0 ? NULL : (void **)(vec)->v.a + (vec)->v.len - 1); it != NULL && it != (void **)(vec)->v.a - 1; it--)
292
293 /*
294 * example:
295 *
296 * RPVector *v = ...; // contains {(void*)0, (void*)2, (void*)4, (void*)6, (void*)8};
297 * size_t index;
298 * #define CMP(x, y) x - y
299 * r_pvector_lower_bound (v, (void *)3, index, CMP);
300 * // index == 2
301 */
302 #define r_pvector_lower_bound(vec, x, i, cmp) \
303 do { \
304 size_t h = (vec)->v.len, m; \
305 for (i = 0; i < h; ) { \
306 m = i + ((h - i) >> 1); \
307 if ((cmp ((x), ((void **)(vec)->v.a)[m])) > 0) { \
308 i = m + 1; \
309 } else { \
310 h = m; \
311 } \
312 } \
313 } while (0) \
314
315 #ifdef __cplusplus
316 }
317 #endif
318
319 #endif
320