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 #ifndef _PTR_VECTOR_H
47 #define _PTR_VECTOR_H
48
49 #ifdef __cplusplus
50 extern "C" {
51 #endif
52
53 #include <dnscore/sys_types.h>
54
55 #define PTR_VECTOR_TAG 0x52544356525450 // PTRVCTR
56
57 #define PTR_VECTOR_DEFAULT_SIZE 32
58
59 #define PTR_VECTOR_EMPTY {NULL, -1, 0}
60 #define EMPTY_PTR_VECTOR {NULL, -1, 0} // obsolete
61
62 typedef struct ptr_vector ptr_vector;
63
64 struct ptr_vector
65 {
66 void** data;
67 s32 offset;
68 s32 size;
69 };
70
71 static inline void
ptr_vector_init_empty(ptr_vector * v)72 ptr_vector_init_empty(ptr_vector *v)
73 {
74 v->data = NULL;
75 v->offset = -1;
76 v->size = 0;
77 }
78
79 /**
80 * This tool function wraps an existing (const) array
81 * This is meant as a helper to use ptr_vector functions like search & sort to on statically allocated data.
82 *
83 * @param v
84 * @param data
85 * @param size
86 */
87
88 static inline void
ptr_vector_wrap_const_array(ptr_vector * v,void * data,s32 size)89 ptr_vector_wrap_const_array(ptr_vector *v, void *data, s32 size)
90 {
91 v->data = data;
92 v->offset = size - 1;
93 v->size = size;
94 }
95
96 /**
97 * Initialises a vector structure with a size of PTR_VECTOR_DEFAULT_SIZE entries
98 *
99 * @param v a pointer to the ptr_vector structure to initialise
100 */
101
102 void ptr_vector_init(ptr_vector *v);
103
104 /**
105 * Initialises a vector structure with a size of PTR_VECTOR_DEFAULT_SIZE entries
106 *
107 * @param v a pointer to the ptr_vector structure to initialise
108 * @param initial_capacity the size to allocate to start with
109 */
110
111 void ptr_vector_init_ex(ptr_vector *v, u32 initial_capacity);
112
113 /**
114 * Initialises a vector as a copy as another vector.
115 * The reserved size is the size of the original plus the extra size.
116 *
117 * @param v a pointer to the ptr_vector structure to initialise
118 * @param original the vector to copy
119 * @param extra_size the amount of reserved slots to allocate
120 */
121
122 void ptr_vector_init_copy(ptr_vector *v, const ptr_vector *original, u32 extra_size);
123
124 /**
125 * Initialises a vector as a copy as another vector plus onz item added
126 * The reserved size is the size of the original plus one
127 *
128 * @param v a pointer to the ptr_vector structure to initialise
129 * @param original the vector to copy
130 * @param data an item to add
131 */
132
133 void ptr_vector_init_copy_append(ptr_vector *v, const ptr_vector *original, void *data);
134
135 /**
136 * Initialises a vector as a copy as another vector plus a few items added
137 * The reserved size is the size of the original plus the data size.
138 *
139 * @param v a pointer to the ptr_vector structure to initialise
140 * @param original the vector to copy
141 * @param data is an array of pointers
142 * @param data_size the size of the data array
143 */
144
145 void ptr_vector_init_copy_append_array(ptr_vector *v, const ptr_vector *original, void *data, u32 data_size);
146
147 /**
148 * Calls the callback on every pointer stored in the vector.
149 * Frees the memory used by a vector structure
150 *
151 * @param v a pointer to the ptr_vector structure
152 */
153
154 void ptr_vector_callback_and_destroy(ptr_vector *v, callback_function free_memory);
155
156 /**
157 * Frees the memory used by a vector structure
158 *
159 * @param v a pointer to the ptr_vector structure
160 */
161
162 void ptr_vector_destroy(ptr_vector *v);
163
164 /**
165 * Empties the vector (does not release memory)
166 *
167 * @param v a pointer to the ptr_vector structure
168 */
169
170 void ptr_vector_clear(ptr_vector *v);
171
172 /**
173 * Cuts lose all indexes from the first bad one.
174 * Allows to resize down without tripping an assert.
175 */
176
177 void ptr_vector_remove_from(ptr_vector *v, s32 first_bad_index);
178
179 /**
180 * Cuts lose all indexes after the last good one.
181 * Allows to resize down without tripping an assert.
182 */
183
184 void ptr_vector_remove_after(ptr_vector *v, s32 last_good_index);
185
186 /**
187 * Changes the capacity of a vector to the specified size
188 * The new size MUST be enough to keep the current content
189 * of the vector. Failing to do so will most likely result
190 * into a crash.
191 *
192 * @param v a pointer to the ptr_vector structure
193 * @param newsize the new size of the vector
194 */
195
196 void ptr_vector_resize(ptr_vector *v, s32 newsize);
197
198 /**
199 * Ensures the vector has enough capacity to accommodate a
200 * specified number of items
201 *
202 * @param v a pointer to the ptr_vector structure
203 * @param reqsize the minimum size of the vector
204 */
205
206 void ptr_vector_ensures(ptr_vector *v, s32 reqsize);
207
208 /**
209 * Resizes the capacity so it can at most contain its
210 * current size.
211 *
212 * @param v a pointer to the ptr_vector structure
213 */
214
215 void ptr_vector_shrink(ptr_vector *v);
216
217 /**
218 * Appends the item (pointer) to the vector
219 *
220 * @param v a pointer to the ptr_vector structure
221 * @param data a pointer to the item
222 */
223
224 void ptr_vector_append(ptr_vector *v, void* data);
225
226 /**
227 * Appends the item (pointer) to the vector
228 *
229 * @param v a pointer to the ptr_vector structure
230 * @param datap a pointer to the items
231 * @param data_size the number of items to append
232 */
233
234 void ptr_vector_append_array(ptr_vector *v, void** datap, u32 data_size);
235
236 /**
237 * Appends the item (pointer) to the vector
238 *
239 * @param v a pointer to the ptr_vector structure
240 * @param datap a pointer to the items
241 * @param data_size the number of items to append
242 */
243
244 void ptr_vector_append_vector(ptr_vector *v, ptr_vector *toappend);
245
246
247 /**
248 * Appends the item (pointer) to the vector and try to keep the buffer size at at most
249 * restrictedlimit.
250 * The goal is to avoid a growth of *2 that would go far beyond the restrictedlimit.
251 * The performance is extremely poor when the number of items in the buffer is restrictedlimit or more.
252 *
253 * @param v a pointer to the ptr_vector structure
254 * @param data a pointer to the item
255 * @param restrictedlimit a guideline limit on the size of the vector
256 */
257
258 void ptr_vector_append_restrict_size(ptr_vector *v, void* data, u32 restrictedlimit);
259
260 /**
261 * Removes an item from the back of the vector and returns its reference
262 *
263 * @param v a pointer to the ptr_vector structure
264 * @return a pointer to the removed item
265 */
266
267 void* ptr_vector_pop(ptr_vector *v);
268
269 /**
270 * IMPORTANT NOTE: the callbacks are called with a pointer from the array
271 */
272
273 typedef int ptr_vector_qsort_callback(const void*, const void*);
274
275 /**
276 * IMPORTANT NOTE: the callbacks are called with a pointer from the array
277 */
278
279 typedef int ptr_vector_qsort_r_callback(const void*, const void*, void*);
280
281 /**
282 * Sort the content of the vector using the compare callback
283 *
284 * @param v a pointer to the ptr_vector structure
285 * @param compare comparison callback
286 */
287
288 void ptr_vector_qsort(ptr_vector *v, ptr_vector_qsort_callback compare);
289
290 void ptr_vector_qsort_r(ptr_vector *v, ptr_vector_qsort_r_callback compare, void *compare_context);
291
292 void ptr_vector_insertionsort_r(ptr_vector *v, ptr_vector_qsort_r_callback compare, void *compare_context);
293
294 /**
295 * Empties the vector releasing the item memory first
296 *
297 * @param v a pointer to the ptr_vector structure
298 * @param free_memory item free callback
299 */
300
301 void ptr_vector_callback_and_clear(ptr_vector *v, callback_function free_memory);
302
303 /*
304 * First argument is the key, second one is the item to match with the key
305 *
306 */
307
308 typedef int ptr_vector_search_callback(const void*, const void*);
309
310 /**
311 * Look sequentially in the vector for an item using a key and a comparison function
312 * The callback only needs to tell equal (0) or not equal (anything else)
313 *
314 * @param v a pointer to the ptr_vector structure
315 * @param what the key
316 * @param compare the comparison function
317 *
318 * @return the first matching item or NULL if none has been found
319 */
320
321 void* ptr_vector_linear_search(const ptr_vector *v, const void* what, ptr_vector_search_callback compare);
322
323 s32 ptr_vector_search_ptr_index(const ptr_vector* v, const void* what);
324
325 /**
326 * Look sequentially in the vector for an item using a key and a comparison function, returns the index of the first matching item
327 *
328 * @param v a pointer to the ptr_vector structure
329 * @param what the key
330 * @param compare the comparison function
331 *
332 * @return the first matching item index or -1 if none has been found
333 */
334
335 s32 ptr_vector_index_of(const ptr_vector *v, const void* what, ptr_vector_search_callback compare);
336
337 /**
338 * Look in the vector for an item using a key and a comparison function
339 * The callback needs to tell equal (0) smaller (<0) or bigger (>0)
340 *
341 * @param v a pointer to the ptr_vector structure
342 * @param what the key
343 * @param compare the comparison function
344 *
345 * @return the first matching item or NULL if none has been found
346 */
347
348 void* ptr_vector_search(const ptr_vector *v, const void* what,ptr_vector_search_callback compare);
349
350 s32 ptr_vector_search_index(const ptr_vector* v, const void* what, ptr_vector_search_callback compare);
351
352 /**
353 * Returns a pointer to the item at index
354 * Does NOT checks for the index range.
355 *
356 * @param v
357 * @param idx
358 * @return a pointer to the item at index
359 */
360
ptr_vector_get(const ptr_vector * v,s32 idx)361 static inline void* ptr_vector_get(const ptr_vector *v, s32 idx)
362 {
363 yassert(idx >= 0 && idx <= v->offset);
364 return v->data[idx];
365 }
366
367 /**
368 * Returns a pointer to the item at index, in a circular fashion
369 * Does NOT checks for the index range.
370 * The array must NOT be empty (div0).
371 *
372 * @param v
373 * @param idx
374 * @return a pointer to the item at index
375 */
376
ptr_vector_get_mod(const ptr_vector * v,s32 idx)377 static inline void* ptr_vector_get_mod(const ptr_vector *v, s32 idx)
378 {
379 assert(v->offset >= 0);
380 int m = idx % (v->offset + 1);
381 if(m < 0) { m += v->offset + 1; } // modulo fix
382 return v->data[m];
383 }
384
385 /**
386 * Sets the item at index to value.
387 * Does NOT checks for the index range.
388 * Does NOT grows the vector.
389 *
390 * @param v
391 * @param idx
392 * @param val
393 */
394
ptr_vector_set(ptr_vector * v,s32 idx,void * val)395 static inline void ptr_vector_set(ptr_vector *v, s32 idx, void* val)
396 {
397 v->data[idx] = val;
398 }
399
400 /**
401 * Returns a pointer to the last item in the vector or NULL if the vector is empty.
402 *
403 * @param v
404 * @return a pointer to the last item or NULL if the vector is empty
405 */
406
ptr_vector_last(const ptr_vector * v)407 static inline void *ptr_vector_last(const ptr_vector *v)
408 {
409 void *r = NULL;
410
411 if(v->offset >= 0)
412 {
413 r = v->data[v->offset];
414 }
415
416 return r;
417 }
418
419 /**
420 * Returns the size of the vector
421 *
422 * @param pv
423 * @param idx
424 */
425
ptr_vector_size(const ptr_vector * v)426 static inline s32 ptr_vector_size(const ptr_vector *v)
427 {
428 return v->offset + 1;
429 }
430
431 /**
432 * Returns the index of the last item in the vector
433 * This is useful because of an implementaiton detail :
434 * obtaining the last index is faster than the size.
435 *
436 * @param pv
437 * @param idx
438 * @param val
439 */
440
ptr_vector_last_index(const ptr_vector * v)441 static inline s32 ptr_vector_last_index(const ptr_vector *v)
442 {
443 return v->offset;
444 }
445
446 /**
447 * Returns the capacity of the vector, that is : the number of items it can hold
448 * without growing.
449 *
450 * @param pv
451 * @param idx
452 * @param valp
453 * @param n
454 */
455
ptr_vector_capacity(const ptr_vector * v)456 static inline s32 ptr_vector_capacity(const ptr_vector *v)
457 {
458 return v->size;
459 }
460
ptr_vector_isempty(const ptr_vector * v)461 static inline bool ptr_vector_isempty(const ptr_vector *v)
462 {
463 return (v->offset < 0);
464 }
465
466 /**
467 * Swap the last item of the vector with the one at index idx.
468 *
469 * One typical use of this function is to remove an item and shrink:
470 * If the vector does not need to keep the order of its content, the
471 * item that is not wanted is exchanged with the end, then the size is
472 * shrank of one slot.
473 *
474 * This is certainly much faster than the insert and remove families
475 * that can be found here below.
476 *
477 * @param pv
478 * @param idx
479 */
480
ptr_vector_end_swap(ptr_vector * pv,s32 idx)481 static inline void ptr_vector_end_swap(ptr_vector *pv,s32 idx)
482 {
483 void* tmp = pv->data[idx];
484 pv->data[idx] = pv->data[pv->offset];
485 pv->data[pv->offset] = tmp;
486 }
487
488
489 /**
490 * Reverse the content
491 *
492 * e.g.
493 * 'I' 'I' 'S' 'G'
494 * becomes
495 * 'G' 'S' 'I' 'I'
496 *
497 * @param pv
498 */
499
ptr_vector_reverse(ptr_vector * v)500 static inline void ptr_vector_reverse(ptr_vector *v)
501 {
502 void *temp;
503
504 void **start = v->data;
505 void **end = &v->data[v->offset];
506
507 while (start < end)
508 {
509 temp = *start;
510 *start = *end;
511 *end = temp;
512
513 start++;
514 end--;
515 }
516 }
517
518
519 /**
520 * Inserts a value at position, pushing items from this position up
521 * Potentially very slow.
522 *
523 * @param pv
524 * @param idx
525 */
526
527 void ptr_vector_insert_at(ptr_vector *pv, s32 idx, void *val);
528
529 /**
530 * Inserts multiple values at position, pushing items from this position up
531 * Potentially very slow.
532 *
533 * @param pv
534 * @param idx
535 * @param valp an array of pointers that will be inserted
536 * @param n the size of the array of pointers
537 */
538
539 void ptr_vector_insert_array_at(ptr_vector *pv, s32 idx, void **valp, u32 n);
540
541 /**
542 *
543 * Removes a value at position, pulling items above this position down
544 * Potentially very slow
545 *
546 * @param pv
547 * @param idx
548 * @return the removed value
549 */
550
551 void* ptr_vector_remove_at(ptr_vector *pv, s32 idx);
552
553 typedef int ptr_vector_forall_callback(void*, void*);
554
ptr_vector_forall(ptr_vector * pv,ptr_vector_forall_callback callback,void * args)555 static inline void ptr_vector_forall(ptr_vector *pv, ptr_vector_forall_callback callback, void *args)
556 {
557 intptr *limit = (intptr*)&pv->data[pv->offset];
558 for(intptr *p = (intptr*)pv->data; p <= limit; ++p)
559 {
560 if(callback((void*)*p, args) <= 0)
561 {
562 break;
563 }
564 }
565 }
566
567 int ptr_vector_compare_pointers_callback(const void *a, const void *b);
568
569 #ifdef __cplusplus
570 }
571 #endif
572
573 #endif /* _RR_VECTOR_H */
574
575 /** @} */
576