dynamic_array.h (11569B)
1 /* Copyright (C) 2013-2023, 2025 Vincent Forest (vaplv@free.fr) 2 * 3 * The RSys library is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published 5 * by the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * The RSys library is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #if !defined(DARRAY_NAME) && !defined(DARRAY_DATA) 17 #ifndef DYNAMIC_ARRAY_H 18 #define DYNAMIC_ARRAY_H 19 20 #include "math.h" 21 #include "mem_allocator.h" 22 #include "rsys.h" 23 #include <string.h> 24 25 /* Helper macro to quickly access darray internal buffer */ 26 #define DARRAY_BUF(Darray) (Darray)->data 27 28 #endif /* DYNAMIC_ARRAY_H */ 29 #else 30 /* 31 * Generate the dynamic array data type and functions with respect to the 32 * following macros: 33 * - DARRAY_NAME: prefix of the dynamic array functions & types; 34 * - DARRAY_DATA: type of the data registered into the array; 35 * - DARRAY_ALIGNMENT: alignment of the array address. Must be a power of two. 36 * If not defined, used the default system alignment. 37 * - DARRAY_FUNCTOR_INIT: init functor on DARRAY_DATA. If not defined, no 38 * specific treatment is performed on the created data; 39 * - DARRAY_FUNCTOR_COPY: copy functor on DARRAY_DATA. If not defined a 40 * bitwise copy is used instead; 41 * - DARRAY_FUNCTOR_RELEASE: release functor on DARRAY_DATA. If not defined 42 * nothing is done on the release of an element; 43 * - DARRAY_FUNCTOR_COPY_AND_RELEASE: Copy and release of a DARRAY_DATA. If 44 * not defined the copy and the release functors is used. 45 * 46 * The name of the generated type is: struct darray_<DARRAY_NAME> 47 * 48 * while the generated functions are: darray_<DARRAY_NAME>_<FUNCTION_NAME> 49 */ 50 #ifndef DARRAY_NAME 51 #error "Missing the DARRAY_NAME macro defining the structure name" 52 #endif 53 #ifndef DARRAY_DATA 54 #error "Missing the DARRAY_DATA macro defining the array data type" 55 #endif 56 57 #define DARRAY_FUNC__(Func) CONCAT(CONCAT(CONCAT(darray_, DARRAY_NAME),_), Func) 58 #define DARRAY_TYPE__ CONCAT(darray_, DARRAY_NAME) 59 60 #ifndef DARRAY_ALIGNMENT 61 #define DARRAY_ALIGNMENT__ MMAX(ALIGNOF(DARRAY_DATA), 16) 62 #else 63 STATIC_ASSERT(IS_POW2(DARRAY_ALIGNMENT), 64 DARRAY_ALIGNMENT_must_be_a_power_of_2); 65 #define DARRAY_ALIGNMENT__\ 66 MMAX(ALIGNOF(DARRAY_DATA), MMAX(DARRAY_ALIGNMENT, 16)) 67 #endif 68 69 struct DARRAY_TYPE__ { 70 DARRAY_DATA* data; 71 size_t size; 72 size_t capacity; 73 struct mem_allocator* allocator; 74 }; 75 76 /******************************************************************************* 77 * Internal default functors 78 ******************************************************************************/ 79 #ifndef DARRAY_FUNCTOR_INIT 80 static FINLINE void 81 DARRAY_FUNC__(functor_init__)(struct mem_allocator* alloc, DARRAY_DATA* data) 82 { ASSERT(data); (void)alloc, (void)data; } 83 #define DARRAY_FUNCTOR_INIT DARRAY_FUNC__(functor_init__) 84 #endif 85 86 #ifndef DARRAY_FUNCTOR_RELEASE 87 static FINLINE void 88 DARRAY_FUNC__(functor_release__)(DARRAY_DATA* data) 89 { ASSERT(data); (void)data; } 90 #define DARRAY_FUNCTOR_RELEASE DARRAY_FUNC__(functor_release__) 91 #endif 92 93 #ifndef DARRAY_FUNCTOR_COPY 94 static FINLINE res_T 95 DARRAY_FUNC__(functor_cp__)(DARRAY_DATA* dst, DARRAY_DATA const* src) 96 { ASSERT(dst && src); *dst = *src; return RES_OK; } 97 #define DARRAY_FUNCTOR_COPY DARRAY_FUNC__(functor_cp__) 98 #endif 99 100 #ifndef DARRAY_FUNCTOR_COPY_AND_RELEASE 101 static FINLINE res_T 102 DARRAY_FUNC__(functor_cp_and_release__)(DARRAY_DATA* dst, DARRAY_DATA* src) 103 { 104 const res_T res = DARRAY_FUNCTOR_COPY(dst, src); 105 DARRAY_FUNCTOR_RELEASE(src); 106 return res; 107 } 108 #define DARRAY_FUNCTOR_COPY_AND_RELEASE DARRAY_FUNC__(functor_cp_and_release__) 109 #endif 110 111 /******************************************************************************* 112 * Dynamic array API 113 ******************************************************************************/ 114 static INLINE void 115 DARRAY_FUNC__(init) 116 (struct mem_allocator* allocator, /* May be NULL <=> use default allocator */ 117 struct DARRAY_TYPE__* darray) 118 { 119 size_t i; 120 ASSERT(darray); 121 darray->data = NULL; 122 darray->size = 0; 123 darray->capacity = 0; 124 FOR_EACH(i, 0, darray->capacity) 125 DARRAY_FUNCTOR_INIT(allocator, darray->data + i); 126 darray->allocator = allocator ? allocator : &mem_default_allocator; 127 } 128 129 static INLINE void 130 DARRAY_FUNC__(clear)(struct DARRAY_TYPE__* darray) 131 { 132 size_t i; 133 ASSERT(darray); 134 FOR_EACH(i, 0, darray->size) 135 DARRAY_FUNCTOR_RELEASE(darray->data + i); 136 darray->size = 0; 137 } 138 139 static INLINE void 140 DARRAY_FUNC__(release)(struct DARRAY_TYPE__* darray) 141 { 142 ASSERT(darray); 143 DARRAY_FUNC__(clear)(darray); 144 MEM_RM(darray->allocator, darray->data); 145 } 146 147 /* Clean up the array and, unlike the clear function, ensure that the memory 148 * used to store the data is effectively released. */ 149 static INLINE void 150 DARRAY_FUNC__(purge)(struct DARRAY_TYPE__* darray) 151 { 152 struct mem_allocator* allocator; 153 ASSERT(darray); 154 allocator = darray->allocator; 155 DARRAY_FUNC__(release)(darray); 156 DARRAY_FUNC__(init)(allocator, darray); 157 } 158 159 static INLINE res_T 160 DARRAY_FUNC__(reserve)(struct DARRAY_TYPE__* darray, const size_t sz) 161 { 162 DARRAY_DATA* data = NULL; 163 ASSERT(darray); 164 165 if(sz <= darray->capacity) 166 return RES_OK; 167 168 data = (DARRAY_DATA*)MEM_ALLOC_ALIGNED 169 (darray->allocator, sz * sizeof(DARRAY_DATA), DARRAY_ALIGNMENT__); 170 if(!data) return RES_MEM_ERR; 171 172 if(darray->size) { 173 size_t i = 0; 174 FOR_EACH(i, 0, darray->size) { 175 res_T res = 0; 176 DARRAY_FUNCTOR_INIT(darray->allocator, data+i); 177 res = DARRAY_FUNCTOR_COPY_AND_RELEASE(data+i, darray->data+i); 178 if(res != RES_OK) { 179 MEM_RM(darray->allocator, data); 180 return res; 181 } 182 } 183 } 184 MEM_RM(darray->allocator, darray->data); 185 186 darray->data = data; 187 darray->capacity = sz; 188 return RES_OK; 189 } 190 191 static INLINE res_T 192 DARRAY_FUNC__(resize)(struct DARRAY_TYPE__* darray, const size_t sz) 193 { 194 size_t sz_adjusted; 195 size_t i; 196 res_T res; 197 ASSERT(darray); 198 199 if(sz < darray->capacity) { 200 sz_adjusted = sz; 201 } else if(sz < darray->size*2) { 202 sz_adjusted = darray->size*2; 203 } else { 204 sz_adjusted = sz; 205 } 206 207 res = DARRAY_FUNC__(reserve)(darray, sz_adjusted); 208 if(res != RES_OK) return res; 209 210 if(sz < darray->size) { 211 FOR_EACH(i, sz, darray->size) 212 DARRAY_FUNCTOR_RELEASE(darray->data+i); 213 } else if(darray->size < sz) { 214 FOR_EACH(i, darray->size, sz) 215 DARRAY_FUNCTOR_INIT(darray->allocator, darray->data+i); 216 } 217 darray->size = sz; 218 return RES_OK; 219 } 220 221 static INLINE res_T 222 DARRAY_FUNC__(push_back) 223 (struct DARRAY_TYPE__* darray, 224 DARRAY_DATA const* data) 225 { 226 DARRAY_DATA* dst; 227 size_t sz_adjusted; 228 res_T res; 229 ASSERT(darray && data); 230 231 sz_adjusted = darray->size + 1; 232 if(sz_adjusted > darray->capacity) { 233 sz_adjusted = MMAX(darray->capacity*2, 1); 234 } 235 res = DARRAY_FUNC__(reserve)(darray, sz_adjusted); 236 if(res != RES_OK) return res; 237 dst = darray->data + darray->size; 238 DARRAY_FUNCTOR_INIT(darray->allocator, dst); 239 DARRAY_FUNCTOR_COPY(dst, data); 240 ++darray->size; 241 return RES_OK; 242 } 243 244 static INLINE void 245 DARRAY_FUNC__(pop_back)(struct DARRAY_TYPE__* darray) 246 { 247 ASSERT(darray); 248 if(darray->size > 0) { 249 const res_T res = DARRAY_FUNC__(resize)(darray, darray->size - 1); 250 ASSERT(res == RES_OK); (void)res; 251 } 252 } 253 254 static INLINE size_t 255 DARRAY_FUNC__(size_get)(const struct DARRAY_TYPE__* darray) 256 { 257 ASSERT(darray); 258 return darray->size; 259 } 260 261 static INLINE size_t 262 DARRAY_FUNC__(capacity)(const struct DARRAY_TYPE__* darray) 263 { 264 ASSERT(darray); 265 return darray->capacity; 266 } 267 268 static INLINE DARRAY_DATA* 269 DARRAY_FUNC__(data_get)(struct DARRAY_TYPE__* darray) 270 { 271 ASSERT(darray); 272 return darray->data; 273 } 274 275 static INLINE DARRAY_DATA const* 276 DARRAY_FUNC__(cdata_get)(const struct DARRAY_TYPE__* darray) 277 { 278 ASSERT(darray); 279 return darray->data; 280 } 281 282 static INLINE res_T 283 DARRAY_FUNC__(copy)(struct DARRAY_TYPE__* dst, const struct DARRAY_TYPE__* src) 284 { 285 DARRAY_DATA const* src_data = NULL; 286 size_t i, src_sz, dst_sz, sz_adjusted; 287 res_T res; 288 ASSERT(dst && src); 289 290 if(dst == src) 291 return RES_OK; 292 293 DARRAY_FUNC__(clear)(dst); 294 src_sz = DARRAY_FUNC__(size_get)(src); 295 dst_sz = DARRAY_FUNC__(size_get)(dst); 296 297 sz_adjusted = MMAX(src_sz, dst_sz); 298 res = DARRAY_FUNC__(reserve)(dst, sz_adjusted); 299 if(res != RES_OK) return res; 300 301 src_data = DARRAY_FUNC__(cdata_get)(src); 302 FOR_EACH(i, 0, src_sz) 303 DARRAY_FUNC__(push_back)(dst, src_data+i); 304 return RES_OK; 305 } 306 307 static INLINE res_T 308 DARRAY_FUNC__(copy_and_clear) 309 (struct DARRAY_TYPE__* dst, 310 struct DARRAY_TYPE__* src) 311 { 312 res_T res = RES_OK; 313 ASSERT(dst && src); 314 if(dst == src) { 315 DARRAY_FUNC__(clear)(dst); 316 return RES_OK; 317 } 318 319 if(src->allocator == dst->allocator) { 320 /* Give the ownership of src->data to dst */ 321 DARRAY_FUNC__(clear)(dst); 322 MEM_RM(dst->allocator, dst->data); 323 dst->data = src->data; 324 dst->capacity = src->capacity; 325 dst->size = src->size; 326 DARRAY_FUNC__(init)(src->allocator, src); /* Reset src */ 327 } else { 328 DARRAY_DATA* src_data = NULL; 329 DARRAY_DATA* dst_data = NULL; 330 const size_t src_sz = DARRAY_FUNC__(size_get)(src); 331 size_t i = 0; 332 333 DARRAY_FUNC__(clear)(dst); 334 res = DARRAY_FUNC__(resize)(dst, src_sz); 335 if(res != RES_OK) return res; 336 337 src_data = DARRAY_FUNC__(data_get)(src); 338 dst_data = DARRAY_FUNC__(data_get)(dst); 339 FOR_EACH(i, 0, src_sz) { 340 res = DARRAY_FUNCTOR_COPY_AND_RELEASE(dst_data+i, src_data+i); 341 if(res != RES_OK) return res; 342 } 343 src->size = 0; 344 } 345 return res; 346 } 347 348 static INLINE res_T 349 DARRAY_FUNC__(copy_and_release) 350 (struct DARRAY_TYPE__* dst, 351 struct DARRAY_TYPE__* src) 352 { 353 res_T res = RES_OK; 354 ASSERT(dst && src); 355 if(dst == src) { 356 DARRAY_FUNC__(release)(dst); 357 } else { 358 res = DARRAY_FUNC__(copy_and_clear)(dst, src); 359 if(res == RES_OK) 360 DARRAY_FUNC__(release)(src); 361 } 362 return res; 363 } 364 365 static INLINE res_T 366 DARRAY_FUNC__(swap)(struct DARRAY_TYPE__* a, struct DARRAY_TYPE__* b) 367 { 368 res_T res = RES_OK; 369 ASSERT(a && b); 370 371 /* Ensure that `a' point toward the smallest array */ 372 if(DARRAY_FUNC__(size_get)(a) > DARRAY_FUNC__(size_get)(b)) { 373 SWAP(struct DARRAY_TYPE__*, a, b); 374 } 375 376 if(a->allocator != b->allocator) { 377 struct DARRAY_TYPE__ tmp; 378 DARRAY_FUNC__(init)(a->allocator, &tmp); 379 380 res = DARRAY_FUNC__(copy_and_clear)(&tmp, b); 381 if(res != RES_OK) return res; 382 res = DARRAY_FUNC__(copy_and_clear)(b, a); 383 if(res != RES_OK) return res; 384 res = DARRAY_FUNC__(copy_and_release)(a, &tmp); 385 if(res != RES_OK) return res; 386 387 } else { 388 /* Back-up the data of `b' */ 389 DARRAY_DATA* b_data = b->data; 390 const size_t b_capacity = b->capacity; 391 const size_t b_size = b->size; 392 393 /* Reset `b' and copy `a' into `b' */ 394 DARRAY_FUNC__(init)(b->allocator, b); 395 res = DARRAY_FUNC__(copy_and_clear)(b, a); 396 ASSERT(res == RES_OK); 397 398 /* Give the ownership of `b' data to `a' */ 399 a->data = b_data; 400 a->capacity = b_capacity; 401 a->size = b_size; 402 } 403 return RES_OK; 404 } 405 406 #undef DARRAY_ALIGNMENT 407 #undef DARRAY_NAME 408 #undef DARRAY_DATA 409 #undef DARRAY_FUNCTOR_INIT 410 #undef DARRAY_FUNCTOR_RELEASE 411 #undef DARRAY_FUNCTOR_COPY 412 #undef DARRAY_FUNCTOR_COPY_AND_RELEASE 413 #undef DARRAY_ALIGNMENT__ 414 #undef DARRAY_FUNC__ 415 #undef DARRAY_TYPE__ 416 417 #endif /* !DARRAY_NAME || !DARRAY_TYPE */