1  /*-
  2   * Copyright(c) 2024-2025 Baptiste Daroussin <bapt@FreeBSD.org>
  3   *
  4   * SPDX-License-Identifier: BSD-2-Clause
  5   */
  6  
  7  #ifndef VEC_H
  8  #define VEC_H
  9  
 10  #include <stdbool.h>
 11  #include <stdlib.h>
 12  #include <stddef.h>
 13  
 14  #define vec_t(Type) \
 15    struct { Type *d; size_t len, cap; }
 16  
 17  #define vec_init() \
 18  	{ .d = NULL, .len = 0, .cap = 0 }
 19  
 20  #define vec_foreach(list, __i) \
 21  	for (size_t __i = 0; __i < (list).len; __i++)
 22  
 23  /* ssize_t because the value can be negative */
 24  #define vec_rforeach(list, __i) \
 25  	for (ssize_t __i = ((ssize_t)(list).len) -1 ; __i >= 0; __i--)
 26  
 27  #define vec_free(v) \
 28  	do { \
 29  		free((v)->d); \
 30  		memset((v), 0, sizeof(*(v))); \
 31  	} while (0)
 32  
 33  #define vec_free_and_free(v, free_func)        \
 34  	do {                                   \
 35  		vec_foreach(*(v), _i) {        \
 36  			free_func((v)->d[_i]); \
 37  			(v)->d[_i] = NULL;     \
 38  		}                              \
 39  		vec_free((v));                 \
 40  	} while(0)
 41  
 42  #define vec_first(v) \
 43  	(v)->d[0]
 44  
 45  #define vec_last(v) \
 46  	(v)->d[(v)->len -1]
 47  
 48  #define vec_clear(v) \
 49  	(v)->len = 0
 50  
 51  #define vec_clear_and_free(v, free_func)       \
 52  	do {                                   \
 53  		vec_foreach(*(v), _i) {        \
 54  			free_func((v)->d[_i]); \
 55  			(v)->d[_i] = NULL;     \
 56  		}                              \
 57  		(v)->len = 0;                  \
 58  	} while (0)
 59  
 60  #define vec_push(v, _d)                                            \
 61  	do {                                                          \
 62  		if ((v)->len >= (v)->cap) {                            \
 63  			if ((v)->cap == 0)                              \
 64  				(v)->cap = 1;                          \
 65  			else                                          \
 66  				(v)->cap *=2;                           \
 67  			(v)->d = realloc((v)->d, (v)->cap * sizeof(*(v)->d)); \
 68  			if ((v)->d == NULL)                             \
 69  				abort();                              \
 70  		}                                                     \
 71  		(v)->d[(v)->len++] = (_d);                                  \
 72  	} while (0)                                                   \
 73  
 74  #define vec_pop(v) \
 75  	(v)->d[--(v)->len]
 76  
 77  #define vec_remove(v, cnt) \
 78  	do {                                                    \
 79  		for (size_t _i = cnt; _i < (v)->len - 1; _i++) {    \
 80  			(v)->d[_i] = (v)->d[_i + 1];            \
 81  		}                                               \
 82  		(v)->len--;                                     \
 83  	} while (0)
 84  
 85  #define vec_remove_and_free(v, cnt, free_func) \
 86  	do {                                                    \
 87  		free_func((v)->d[cnt]);                         \
 88  		vec_remove(v, cnt);                             \
 89  	} while (0)
 90  
 91  /*
 92   * Remove the element at the given index and replace it with the last
 93   * element in the vec. Does not preserve order, but is O(1).
 94   */
 95  #define vec_swap_remove(v, index)                    \
 96  	do {                                         \
 97  		assert((index) < (v)->len);          \
 98  		assert((v)->len > 0);                \
 99  		if ((index) < (v)->len - 1) {        \
100  			(v)->d[index] = vec_last(v); \
101  		}                                    \
102  		(v)->len--;                          \
103  	} while (0)
104  
105  #define vec_len(v) \
106  	(v)->len
107  
108  #define DEFINE_VEC_INSERT_SORTED_PROTO(type, name, element_type) \
109  	element_type *name##_insert_sorted(type *v, element_type el)
110  
111  #define DEFINE_VEC_INSERT_SORTED_FUNC(type, _name, element_type, compare_func) \
112  	element_type *_name##_insert_sorted(type *v, element_type el) { \
113  		/* Verify if the element already exists */ \
114  		if (v->len > 0) { \
115  			element_type *found = bsearch(&el, v->d, v->len, sizeof(element_type), compare_func); \
116  			if (found != NULL){ \
117  				return (found); \
118  			} \
119  		} \
120  		if (v->len >= v->cap) { \
121  			v->cap = (v->cap == 0) ? 1 : v->cap * 2; \
122  			v->d = realloc(v->d, v->cap * sizeof(element_type)); \
123  			if (v->d == NULL) \
124  				abort(); \
125  		} \
126  		/* Find where to insert */ \
127  		size_t i; \
128  		for (i = v->len; i > 0 && compare_func(&v->d[i - 1], &el) > 0; i--) { \
129  			v->d[i] = v->d[i - 1]; \
130  		} \
131  		v->d[i] = el; \
132  		v->len++; \
133  		return (NULL); \
134  	}
135  
136  typedef vec_t(char *) charv_t;
137  typedef vec_t(const char *) c_charv_t;
138  
139  #endif