main.c (19415B)
1 #include <gs/gs.h> 2 3 // comment out this line to disable bit field 4 //#define GS_BUCKET_ARRAY_BIT_FIELD 5 6 7 #define GS_BUCKET_ARRAY_INVALID_HANDLE UINT32_MAX 8 9 #define __gs_bucket_array_raw(__T) \ 10 struct \ 11 { \ 12 uint32_t bucket_size; \ 13 uint32_t top; \ 14 gs_dyn_array(int64_t) bit_field; \ 15 gs_dyn_array(__T*) data; \ 16 __T tmp; \ 17 } 18 19 #define gs_bucket_array(__T)\ 20 __gs_bucket_array_raw(__T)* 21 22 #define gs_bucket_array_new(__T, __AMOUNT)\ 23 __gs_bucket_array_new(__AMOUNT, sizeof(__gs_bucket_array_raw(__T))) 24 25 gs_force_inline void* 26 __gs_bucket_array_new(uint32_t amount, size_t struct_size) 27 { 28 void* ret = malloc(struct_size); 29 memset(ret, 0, struct_size); 30 uint32_t* i = ret; 31 i[0] = amount; 32 return ret; 33 } 34 35 #define gs_bucket_array_bucket_size(__BA) ((__BA)->bucket_size) 36 #define gs_bucket_array_bucket_count(__BA) (gs_dyn_array_size((__BA)->data)) 37 #define gs_bucket_array_capacity(__BA) ((__BA)->bucket_size * gs_dyn_array_size((__BA)->data)) 38 #define gs_bucket_array_size(__BA) ((__BA)->top) 39 40 #define gs_bucket_array_get(__BA, __HNDL)\ 41 (__BA)->data[(__HNDL) / (__BA)->bucket_size][(__HNDL) - (__HNDL) / (__BA)->bucket_size * (__BA)->bucket_size] 42 43 #define gs_bucket_array_getp(__BA, __HNDL) &gs_bucket_array_get(__BA, __HNDL) 44 45 #define gs_bucket_array_push(__BA, __VAL)\ 46 ((__BA)->tmp = __VAL, \ 47 __gs_bucket_array_push_func((void***)&((__BA)->data), (__BA)->bucket_size, \ 48 &(__BA)->tmp, sizeof((__BA)->tmp), &(__BA)->top)) 49 50 #define gs_bucket_array_reserve(__BA, __NUM_BUCKETS)\ 51 (__gs_bucket_array_reserve_func((void***)&((__BA)->data), (__BA)->bucket_size, sizeof((__BA)->tmp), __NUM_BUCKETS)) 52 53 gs_force_inline void 54 __gs_bucket_array_reserve_func(void*** dynarr, uint32_t bucket_size, uint32_t element_size, uint32_t num_buckets) 55 { 56 while (num_buckets--) { 57 void* ptr = malloc(element_size * bucket_size); 58 gs_dyn_array_push_data((void**)dynarr, &ptr, sizeof(ptr)); 59 } 60 } 61 62 gs_force_inline void 63 __gs_bucket_array_push_func(void*** dynarr, uint32_t bucket_size, 64 void* element, size_t element_size, uint32_t* top) 65 { 66 uint32_t sz = gs_dyn_array_size(*dynarr); 67 void* ptr; 68 if (!sz || *top >= bucket_size * sz) { 69 ptr = malloc(element_size * bucket_size); 70 gs_dyn_array_push_data((void**)dynarr, &ptr, sizeof(ptr)); 71 } else { 72 const uint32_t major = *top / bucket_size; 73 ptr = (char*)dynarr[0][major] + ((*top - major * bucket_size) * element_size); 74 } 75 *top += 1; 76 memcpy(ptr, element, element_size); 77 } 78 79 80 81 #ifdef GS_BUCKET_ARRAY_BIT_FIELD 82 // optional bit field functions 83 84 #define gs_bucket_array_bf_exists(__BA, __HNDL)\ 85 (__HNDL / (__BA)->bucket_size > gs_dyn_array_size((__BA)->data) ? false : \ 86 __gs_bucket_array_check((__BA)->bit_field, __HNDL) ? \ 87 true : false) 88 89 #define gs_bucket_array_bf_insert(__BA, __VAL)\ 90 ((__BA)->tmp = __VAL, \ 91 __gs_bucket_array_insert_into_any_bucket((void***)&((__BA)->data), &(__BA)->bit_field, (__BA)->bucket_size, \ 92 &(__BA)->tmp, sizeof((__BA)->tmp), &(__BA)->top)) 93 94 #define gs_bucket_array_bf_erase(__BA, __HNDL)\ 95 __gs_bucket_array_clear_bucket((__BA)->bit_field, __HNDL) 96 97 gs_force_inline bool32_t 98 __gs_bucket_array_check(int64_t* bit_field, uint32_t index) 99 { 100 uint32_t bit_field_index = index / 64; 101 uint32_t bit = index - bit_field_index * 64; 102 103 return bit_field[bit_field_index] & (1L << bit) ? true : false; 104 } 105 106 gs_force_inline void 107 __gs_bucket_array_clear_bucket(int64_t* bit_field, uint32_t index) 108 { 109 uint32_t bit_field_index = index / 64; 110 uint32_t bit = index - bit_field_index * 64; 111 112 bit_field[bit_field_index] &= ~(1L << bit); 113 } 114 115 gs_force_inline uint32_t 116 __gs_bucket_array_insert_into_any_bucket(void*** dynarr, int64_t** bit_field_dynarr, uint32_t bucket_size, 117 void* element, size_t element_size, uint32_t* top) 118 { 119 uint32_t index; 120 uint32_t bit_sz = gs_dyn_array_size(*bit_field_dynarr); 121 uint32_t sz = gs_dyn_array_size(*dynarr); 122 123 if (bit_sz) { 124 for (uint32_t i = bit_sz - 1; i != UINT32_MAX; i--) { 125 int pos = ffsll(~bit_field_dynarr[0][i]); 126 if (pos) { 127 index = pos - 1 + i * 64; 128 if (index >= sz * bucket_size) continue; 129 130 const uint32_t bucket_index = index - index / bucket_size * bucket_size; 131 void* p = (char*)dynarr[0][index / bucket_size] + bucket_index * element_size; 132 memcpy(p, element, element_size); 133 bit_field_dynarr[0][i] |= 1L << (pos - 1); 134 return index; 135 } 136 } 137 } 138 139 void* tmp_ptr = malloc(element_size * bucket_size); 140 memcpy(tmp_ptr, element, element_size); 141 gs_dyn_array_push_data((void**)dynarr, &tmp_ptr, sizeof(tmp_ptr)); 142 143 index = bucket_size * sz; 144 uint32_t last_field_end = index + ((index % 64) ? (64 - index % 64) : 0); 145 146 uint32_t index_end = index + bucket_size; 147 *top = index_end; 148 uint32_t new_index_field_end = index_end + ((index_end % 64) ? (64 - index_end % 64) : 0); 149 150 uint32_t new_bit_size = (new_index_field_end - last_field_end) / 64; 151 int64_t tmp = 0; 152 for (uint32_t i = 0; i < new_bit_size; i++) 153 gs_dyn_array_push(*bit_field_dynarr, tmp); 154 155 bit_field_dynarr[0][index / 64] |= 1L << (index - index / 64 * 64); 156 157 return sz * bucket_size; 158 } 159 160 #define gs_bucket_array_bf_reserve(__BA, __NUM_BUCKETS)\ 161 (__gs_bucket_array_bf_reserve_func((void***)&((__BA)->data), (__BA)->bucket_size, sizeof((__BA)->tmp),\ 162 __NUM_BUCKETS, &(__BA)->bit_field, &(__BA)->top)) 163 164 gs_force_inline void 165 __gs_bucket_array_bf_reserve_func(void*** dynarr, uint32_t bucket_size, uint32_t element_size, 166 uint32_t num_buckets, int64_t** bit_field_dynarr, uint32_t* top) 167 { 168 uint32_t sz = gs_dyn_array_size(*dynarr); 169 170 __gs_bucket_array_reserve_func(dynarr, bucket_size, element_size, num_buckets); 171 172 uint32_t index = bucket_size * sz; 173 uint32_t last_field_end = index + ((index % 64) ? (64 - index % 64) : 0); 174 175 uint32_t index_end = index + bucket_size * num_buckets; 176 *top = index_end; 177 uint32_t new_index_field_end = index_end + ((index_end % 64) ? (64 - index_end % 64) : 0); 178 179 uint32_t new_bit_size = (new_index_field_end - last_field_end) / 64; 180 int64_t tmp = 0; 181 for (uint32_t i = 0; i < new_bit_size; i++) 182 gs_dyn_array_push(*bit_field_dynarr, tmp); 183 } 184 185 // bit field iter 186 // the iter is a hndl into the bit field / array 187 #define gs_bucket_array_iter_bf uint32_t 188 #define gs_bucket_array_iter_bf_new(__BA) __gs_bucket_array_iter_bf_new_func((__BA)->bit_field, (__BA)->bucket_size * gs_bucket_array_bucket_count(__BA)) 189 #define gs_bucket_array_iter_bf_valid(__BA, __IT) (__IT != GS_BUCKET_ARRAY_INVALID_HANDLE) 190 #define gs_bucket_array_iter_bf_advance(__BA, __IT) __gs_bucket_array_bf_advance_func((__BA)->bit_field, &__IT, (__BA)->bucket_size * gs_bucket_array_bucket_count(__BA)) 191 192 gs_force_inline uint32_t 193 __gs_bucket_array_iter_bf_new_func(int64_t* bit_field, uint32_t max_index) 194 { 195 uint32_t res = 1; 196 uint32_t idx = 0; 197 do { 198 if (!res) idx++; 199 if (idx >= max_index) { 200 idx = GS_BUCKET_ARRAY_INVALID_HANDLE; 201 break; 202 } 203 res = __gs_bucket_array_check(bit_field, idx); 204 } while (!res); 205 return idx; 206 } 207 208 gs_force_inline void 209 __gs_bucket_array_bf_advance_func(int64_t* bit_field, uint32_t* index, uint32_t max_index) 210 { 211 uint32_t res = 0; 212 do { 213 *index += 1; 214 if (*index >= max_index) { 215 *index = GS_BUCKET_ARRAY_INVALID_HANDLE; 216 return; 217 } 218 res = __gs_bucket_array_check(bit_field, *index); 219 } while (!res); 220 } 221 222 #endif // GS_BUCKET_ARRAY_BIT_FIELD 223 224 225 // normal iter 226 typedef struct gs_bucket_array_iter_s { 227 uint32_t major; 228 uint32_t minor; 229 } gs_bucket_array_iter; 230 231 #define gs_bucket_array_iter_new(__BA) gs_default_val() 232 #define gs_bucket_array_iter_valid(__BA, __IT) (__IT.major * (__BA)->bucket_size + __IT.minor < (__BA)->top) 233 #define gs_bucket_array_iter_advance(__BA, __IT) __gs_bucket_array_advance_func(&__IT, (__BA)->bucket_size) 234 235 gs_force_inline void 236 __gs_bucket_array_advance_func(gs_bucket_array_iter* it, uint32_t bucket_size) 237 { 238 it->minor += 1; 239 if (it->minor >= bucket_size) { 240 it->minor = 0; 241 it->major += 1; 242 } 243 } 244 #define gs_bucket_array_iter_get(__BA, __IT)\ 245 (__BA)->data[__IT.major][__IT.minor] 246 247 #define gs_bucket_array_iter_getp(__BA, __IT)\ 248 &gs_bucket_array_iter_get(__BA, __IT) 249 250 #define gs_bucket_array_iter_get_hndl(__BA, __IT)\ 251 (__IT.major * (__BA)->bucket_size + __IT.minor) 252 253 254 // clear and free 255 #define gs_bucket_array_clear(__BA)\ 256 memset((__BA)->bit_field, 0, gs_dyn_array_size((__BA)->bit_field) * sizeof(int64_t)); 257 258 259 #define gs_bucket_array_free(__BA)\ 260 do { \ 261 if (__BA) { \ 262 if ((__BA)->bit_field) \ 263 gs_dyn_array_free((__BA)->bit_field); \ 264 for (uint32_t __BA_IT = 0; __BA_IT < gs_dyn_array_size((__BA)->data); __BA_IT++) \ 265 gs_free((__BA)->data[__BA_IT]); \ 266 gs_dyn_array_free((__BA)->data); \ 267 gs_free(__BA); \ 268 __BA = NULL; \ 269 } \ 270 } while (0) 271 272 273 /* 274 275 gs_bucket_array: 276 277 NOTE: 278 > Unlike the other gunslinger containers, the gs_bucket_array needs initialization. 279 > It is NOT allocated on use. 280 281 Bucket arrays are internally a list of pointers to fixed-size arrays; 282 This means that there are no realloc's, and all your pointers will remain valid. 283 284 Due to the nature of this container it's very handy for managing both stuff that are 285 "constant" and dynamic in a singular place. 286 The major drawback of this is slower insertion and iteration. 287 288 The guts look somewhat like: 289 290 gs_dyn_array(Type[bucket_size]) your_data; 291 292 Standard initializatoin would look like: 293 294 gs_bucket_array(float) arr = gs_bucket_array_new(float, 100); // Bucket array with internal 'float' data, where each bucket is 100 floats 295 gs_bucket_array_push(arr, 3.145f); // Pushes 3.145 into the array 296 float* val_p = gs_bucket_array_getp(arr, index); 297 float val = gs_bucket_array_get(arr, index); 298 299 The bucket array provides iterators: 300 301 for ( 302 gs_bucket_array_iter it = gs_bucket_array_iter_new(ba); 303 gs_bucket_array_iter_valid(ba, it); 304 gs_bucket_array_iter_advance(ba, it) 305 ) { 306 float v = gs_bucket_array_iter_get(ba, it); // Get value using iterator 307 float* vp = gs_bucket_array_iter_getp(ba, it); // Get value pointer using iterator 308 } 309 310 Internally the iterator is just struct {uint32_t major; uint32_t minor;} 311 312 Bucket array usage: 313 314 gs_bucket_array(float) ba = gs_bucket_array_new(float, 100); // Bucket array with internal 'float' data, where each bucket is 100 floats 315 gs_bucket_array_reserve(ba, 2); // Reserves 2 buckets 316 gs_bucket_array_push(ba, 3.145f); // Pushes 3.145 onto the end of the bucket array 317 float* val_p = gs_bucket_array_getp(ba, index); // Returns a pointer to your data 318 float val = gs_bucket_array_get(ba, index); // Dereferences your data as well 319 320 uint32_t bs = gs_bucket_array_bucket_size(ba) // Returns initialized bucket size 321 uint32_t bc = gs_bucket_array_bucket_count(ba) // Returns the amount of buckets allocated 322 uint32_t ba_cap = gs_bucket_array_capacity(ba) // Returns bucket_size * bucket_count 323 uint32_t ba_size = gs_bucket_array_size(ba) // returns index+1 of the last element 324 gs_bucket_array_free(ba) // Free's the entire array, make sure your own elements are free'd first 325 326 327 Additionally, you may choose to use the provided bit field. 328 This allows usage of discarded slots, and iteration through just the valid elements. 329 The bit field uses compiler specific intrinsics (ffsll), and is not portable. 330 331 In the case where you use the bit field, you must NEVER use the following functions: 332 333 gs_bucket_array_push(); 334 gs_bucket_array_reserve(); 335 336 Instead use: 337 338 gs_bucket_array_bf_insert(); 339 gs_bucket_array_bf_reserve(); 340 341 Bucket array with bit field usage: 342 343 gs_bucket_array(float) ba = gs_bucket_array_new(float, 100); // Bucket array with internal 'float' data, where each bucket is 100 floats 344 gs_bucket_array_bf_reserve(ba, 2); // Reserves 2 buckets 345 uitn32_t index = gs_bucket_array_bf_insert(ba, 3.145f); // Inserts 3.145 to some new or discarded place in ba 346 float* val_p = gs_bucket_array_getp(ba, index); // Returns a pointer to your data 347 float val = gs_bucket_array_get(ba, index); // Dereferences your data as well 348 349 uint32_t bs = gs_bucket_array_bucket_size(ba) // Returns initialized bucket size 350 uint32_t bc = gs_bucket_array_bucket_count(ba) // Returns the amount of buckets allocated 351 uint32_t ba_cap = gs_bucket_array_capacity(ba) // Returns bucket_size * bucket_count 352 uint32_t ba_size = gs_bucket_array_size(ba) // returns the same as capacity 353 gs_bucket_array_clear(ba) // invalidates all existing elements 354 gs_bucket_array_free(ba) // Free's the entire array, make sure your own elements are free'd first 355 356 The bucket array with bit fields also has iterators: 357 358 for ( 359 gs_bucket_array_bf_iter it = gs_bucket_array_iter_bf_new(ba); 360 gs_bucket_array_bf_iter_valid(ba, it); 361 gs_bucket_array_bf_iter_advance(ba, it) 362 ) { 363 float v = gs_bucket_array_get(ba, it); // Get value using iterator 364 float* vp = gs_bucket_array_getp(ba, it); // Get value pointer using iterator 365 } 366 367 */ 368 369 370 int main() 371 { 372 gs_bucket_array(int) foo = gs_bucket_array_new(int, 99); 373 gs_println("foo has a bucket size of %d", gs_bucket_array_bucket_size(foo)); 374 375 #ifdef GS_BUCKET_ARRAY_BIT_FIELD 376 gs_bucket_array_bf_reserve(foo, 2); 377 #else // ! GS_BUCKET_ARRAY_BIT_FIELD 378 gs_bucket_array_reserve(foo, 2); 379 #endif // GS_BUCKET_ARRAY_BIT_FIELD 380 381 uint32_t element_inserts = 400; 382 gs_println("---- inserting %d elements", element_inserts); 383 for (int i = 0; i < element_inserts; i++) { 384 #ifdef GS_BUCKET_ARRAY_BIT_FIELD 385 gs_println("got hndl %3d for %3d : bucket count %2d", gs_bucket_array_bf_insert(foo, i), i, gs_bucket_array_bucket_count(foo)); 386 #else // ! GS_BUCKET_ARRAY_BIT_FIELD 387 gs_bucket_array_push(foo, i + 1); 388 gs_println("%3d has %3d : bucket count %2d", i, gs_bucket_array_get(foo, i), gs_bucket_array_bucket_count(foo)); 389 #endif // GS_BUCKET_ARRAY_BIT_FIELD 390 } 391 392 const int start = element_inserts + 5 - 20; 393 const int end = start + 20; 394 395 396 397 #ifdef GS_BUCKET_ARRAY_BIT_FIELD 398 for (int i = start + 5; i < start + 10; i++) 399 gs_bucket_array_bf_erase(foo, i); 400 401 gs_println("---- checking the elements %d -> %d", start, end); 402 for (int i = start; i < end; i++) { 403 if (gs_bucket_array_bf_exists(foo, i)) { 404 gs_println("element %d: exists and has value %d", i, gs_bucket_array_get(foo, i)); 405 } else { 406 gs_println("element %d: does not exist", i); 407 } 408 } 409 410 for (int i = 2; i < 100; i++) 411 gs_bucket_array_bf_erase(foo, i); 412 413 414 int loops = 0; 415 for (gs_bucket_array_iter_bf it = gs_bucket_array_iter_bf_new(foo); 416 gs_bucket_array_iter_bf_valid(foo, it); 417 gs_bucket_array_iter_bf_advance(foo, it) 418 ) { 419 int test = gs_bucket_array_get(foo, it); 420 int* testp = gs_bucket_array_getp(foo, it); 421 loops++; 422 if (test == 250) { 423 gs_println("element with value 250 found after %d loops, iterator is now %d", loops, it); 424 break; 425 } 426 } 427 428 gs_bucket_array_clear(foo); 429 430 for (gs_bucket_array_iter_bf it = gs_bucket_array_iter_bf_new(foo); 431 gs_bucket_array_iter_bf_valid(foo, it); 432 gs_bucket_array_iter_bf_advance(foo, it) 433 ) { 434 // will never print because of previous clear. 435 gs_println("element %d:%d", it, gs_bucket_array_get(foo, it)); 436 } 437 #endif // GS_BUCKET_ARRAY_BIT_FIELD 438 439 440 441 for (gs_bucket_array_iter it = gs_bucket_array_iter_new(foo); 442 gs_bucket_array_iter_valid(foo, it); 443 gs_bucket_array_iter_advance(foo, it) 444 ) { 445 int i = gs_bucket_array_iter_get(foo, it); 446 uint32_t hndl = gs_bucket_array_iter_get_hndl(foo, it); 447 gs_println("element %d:%d", hndl, i); 448 } 449 450 gs_bucket_array_free(foo); 451 452 return 0; 453 }