-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathtimelinefx.h
8612 lines (7632 loc) · 398 KB
/
timelinefx.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#ifndef TFX_LIBRARY_HEADER
#define TFX_LIBRARY_HEADER
#define tfxENABLE_PROFILING
#define tfxPROFILER_SAMPLES 60
#define TFX_THREAD_SAFE
#define TFX_EXTRA_DEBUGGING
/*
Timeline FX C++ library
This library is for implementing particle effects into your games and applications.
This library is render agnostic, so you will have to provide your own means to render the particles. There are various API functions in the library that help you do this.
Currently tested on Windows and MacOS, Intel and Mac based ARM processors.
Table of contents
Sections in this header file, you can search for the following keywords to jump to that section:
[Zest_Pocket_Allocator] A single header library for allocating memory from a large pool.
[Header_Includes_and_Typedefs] Just your basic header stuff for setting up typedefs and some #defines
[OS_Specific_Functions] OS specific multithreading and file access
[Pocket_Hasher] XXHasher for the storage map.
[SIMD_defines] Defines for SIMD intrinsics
[Enums] All the definitions for enums and bit flags
[Constants] Various constant definitions
[String_Buffers] Basic string buffers for storing names of things in the library and reading from library files.
[Containers_and_Memory] Container structs and lists and defines for memory is allocated (uses Zest Pocket Allocator by default)
[Multithreading_Work_Queues] Implementation for work queues for threading
[Vector_Math] Vec2/3/4 and Matrix2/3/4 structs including wide vectors for SIMD
[Simplex_Noise] Some setup for implementing simplex noise.
[Profiling] Very basic profiling for internal use
[File_IO] A package manager for reading/writing files such as a tfx library effects file
[Struct_Types] All of the structs used for objects in TimelineFX
[Internal_Functions] Mainly internal functions called only by the library but also the Editor, these are marked either tfxINTERNAL or tfxAPI_EDITOR
[API_Functions] The main functions for use by users of the library
-[Initialisation_functions] Startup and shutdown timelinefx
-[Global_variable_access] Any functions that give you access to global variables relating to timelinefx
-[Library_functions] Functions for loading and accessing timelinefx libraries
-[Particle_Manager_functions] Create and update functions for particle managers where the main work is done to update particles every frame
-[Animation_manager] Animation manager functions for playing pre-recorded effect data
-[Effect_templates] Functions for working with effect templates which help modify effects in the library without actually changing the base effect in the library.
-[General_helpers] General math functions and other helpers.
*/
/* Functions come in 3 flavours:
1) INTERNAL where they're only meant for internal use by the library and not for any use outside it. Note that these functions are declared as static.
2) API where they're meant for access within your games that you're developing. These functions are c compatible.
3) EDITOR where they can be accessed from outside the library but really they're mainly useful for editing the effects such as in in the TimelineFX Editor. These
functions are c++ compatabile only and currently not available if you're including the library in a c project.
All functions in the library will be marked this way for clarity and naturally the API functions will all be properly documented.
*/
#ifdef __cplusplus
#define tfxAPI extern "C"
#else
#define tfxAPI
#endif
#define tfxINTERNAL static
#define tfxAPI_EDITOR
//Override this if you'd prefer a different way to allocate the pools for sub allocation in host memory.
#ifndef tfxALLOCATE_POOL
#define tfxALLOCATE_POOL malloc
#endif
#ifndef tfxMAX_MEMORY_POOLS
#define tfxMAX_MEMORY_POOLS 32
#endif
#ifndef tfxMAX_THREADS
#define tfxMAX_THREADS 64
#endif
//---------------------------------------
/* Zest_Pocket_Allocator, a Two Level Segregated Fit memory allocator
This is my own memory allocator from https://github.com/peterigz/zloc
This is used in TimelineFX to manage memory allocation. A large pool is created and allocated from. New pools are created if it runs out of space
(and you initialised TimelineFX to do so).
*/
//---------------------------------------
#include <assert.h>
#include <stdlib.h>
#include <limits.h>
#include <stddef.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdbool.h>
#include <inttypes.h>
#include <stdint.h>
#include <string.h>
#include <ctype.h>
#define tfx__Min(a, b) (((a) < (b)) ? (a) : (b))
#define tfx__Max(a, b) (((a) > (b)) ? (a) : (b))
#define tfx__Clamp(min, max, v) (v < min) ? min : (v > max) ? max : v
typedef int tfx_index;
typedef unsigned int tfx_sl_bitmap;
typedef unsigned int tfx_uint;
typedef unsigned char tfx_byte;
typedef void *tfx_pool;
#if !defined (TFX_ASSERT)
#define TFX_ASSERT assert
#endif
#define TFX_DEPRECATED assert(0 && "Function is deprecated");
#define TFX_ASSERT_INIT(magic) TFX_ASSERT(magic == tfxINIT_MAGIC)
#define TFX_ASSERT_UNINIT(magic) TFX_ASSERT(magic != tfxINIT_MAGIC)
#define TFX_CHECK_HANDLE(handle) TFX_ASSERT(handle && *((tfxU32*)handle) == tfxINIT_MAGIC)
#define TFX_VALID_HANDLE(handle) (handle && *((tfxU32*)handle) == tfxINIT_MAGIC)
#define tfx__is_pow2(x) ((x) && !((x) & ((x) - 1)))
#define tfx__glue2(x, y) x ## y
#define tfx__glue(x, y) tfx__glue2(x, y)
#define tfx__static_assert(exp) \
typedef char tfx__glue(static_assert, __LINE__) [(exp) ? 1 : -1]
#if (defined(_MSC_VER) && defined(_M_X64)) || defined(__x86_64__)
#define tfx__64BIT
typedef size_t tfx_size;
typedef size_t tfx_fl_bitmap;
typedef int tfxLONG;
#define TFX_ONE 1ULL
#else
typedef size_t tfx_size;
typedef size_t tfx_fl_bitmap;
typedef int tfxLONG;
#define TFX_ONE 1U
#endif
#ifndef MEMORY_ALIGNMENT_LOG2
#if defined(tfx__64BIT)
#define MEMORY_ALIGNMENT_LOG2 3 //64 bit
#else
#define MEMORY_ALIGNMENT_LOG2 2 //32 bit
#endif
#endif
#ifndef TFX_ERROR_NAME
#define TFX_ERROR_NAME "Allocator Error"
#endif
#ifndef TFX_ERROR_COLOR
#define TFX_ERROR_COLOR "\033[31m"
#endif
#ifndef TFX_NOTICE_COLOR
#define TFX_NOTICE_COLOR "\033[0m"
#endif
#ifndef TFX_NOTICE_NAME
#define TFX_NOTICE_NAME "TimelineFX Notice"
#endif
#ifdef TFX_OUTPUT_NOTICE_MESSAGES
#define TFX_PRINT_NOTICE(message_f, ...) printf(message_f"\033[0m", __VA_ARGS__)
#else
#define TFX_PRINT_NOTICE(message_f, ...)
#endif
#ifdef TFX_OUTPUT_ERROR_MESSAGES
#define TFX_PRINT_ERROR(message_f, ...) printf(message_f"\033[0m", __VA_ARGS__)
#else
#define TFX_PRINT_ERROR(message_f, ...)
#endif
#define tfx__KILOBYTE(Value) ((Value) * 1024LL)
#define tfx__MEGABYTE(Value) (tfx__KILOBYTE(Value) * 1024LL)
#define tfx__GIGABYTE(Value) (tfx__MEGABYTE(Value) * 1024LL)
#ifndef TFX_MAX_SIZE_INDEX
#if defined(tfx__64BIT)
#define TFX_MAX_SIZE_INDEX 32
#else
#define TFX_MAX_SIZE_INDEX 30
#endif
#endif
tfx__static_assert(TFX_MAX_SIZE_INDEX < 64);
#ifdef __cplusplus
extern "C" {
#endif
#define tfx__MAXIMUM_BLOCK_SIZE (TFX_ONE << TFX_MAX_SIZE_INDEX)
enum tfx__constants {
tfx__MEMORY_ALIGNMENT = 1 << MEMORY_ALIGNMENT_LOG2,
tfx__SECOND_LEVEL_INDEX_LOG2 = 5,
tfx__FIRST_LEVEL_INDEX_COUNT = TFX_MAX_SIZE_INDEX,
tfx__SECOND_LEVEL_INDEX_COUNT = 1 << tfx__SECOND_LEVEL_INDEX_LOG2,
tfx__BLOCK_POINTER_OFFSET = sizeof(void *) + sizeof(tfx_size),
tfx__MINIMUM_BLOCK_SIZE = 16,
tfx__BLOCK_SIZE_OVERHEAD = sizeof(tfx_size),
tfx__POINTER_SIZE = sizeof(void *),
tfx__SMALLEST_CATEGORY = (1 << (tfx__SECOND_LEVEL_INDEX_LOG2 + MEMORY_ALIGNMENT_LOG2))
};
typedef enum tfx__boundary_tag_flags {
tfx__BLOCK_IS_FREE = 1 << 0,
tfx__PREV_BLOCK_IS_FREE = 1 << 1,
} tfx__boundary_tag_flags;
typedef enum tfx__error_codes {
tfx__OK,
tfx__INVALID_FIRST_BLOCK,
tfx__INVALID_BLOCK_FOUND,
tfx__PHYSICAL_BLOCK_MISALIGNMENT,
tfx__INVALID_SEGRATED_LIST,
tfx__WRONG_BLOCK_SIZE_FOUND_IN_SEGRATED_LIST,
tfx__SECOND_LEVEL_BITMAPS_NOT_INITIALISED
} tfx__error_codes;
/*
Each block has a header that is used only has a pointer to the previous physical block
and the size. If the block is free then the prev and next free blocks are also stored.
*/
typedef struct tfx_header {
struct tfx_header *prev_physical_block;
/* Note that the size is either 4 or 8 bytes aligned so the boundary tag (2 flags denoting
whether this or the previous block is free) can be stored in the first 2 least
significant bits */
tfx_size size;
/*
User allocation will start here when the block is used. When the block is free prev and next
are pointers in a linked list of free blocks within the same class size of blocks
*/
struct tfx_header *prev_free_block;
struct tfx_header *next_free_block;
} tfx_header;
/*
A struct for making snapshots of a memory pool to get used/free memory stats
*/
typedef struct tfx_pool_stats_t {
int used_blocks;
int free_blocks;
tfx_size free_size;
tfx_size used_size;
} tfx_pool_stats_t;
typedef struct tfx_allocator {
/* This is basically a terminator block that free blocks can point to if they're at the end
of a free list. */
tfx_header null_block;
//todo: just make thead safe by default and remove these conditions
#if defined(TFX_THREAD_SAFE)
/* Multithreading protection*/
volatile tfxLONG access;
#endif
tfx_size minimum_allocation_size;
/* Here we store all of the free block data. first_level_bitmap is either a 32bit int
or 64bit depending on whether tfx__64BIT is set. Second_level_bitmaps are an array of 32bit
ints. segregated_lists is a two level array pointing to free blocks or null_block if the list
is empty. */
tfx_fl_bitmap first_level_bitmap;
tfx_sl_bitmap second_level_bitmaps[tfx__FIRST_LEVEL_INDEX_COUNT];
tfx_header *segregated_lists[tfx__FIRST_LEVEL_INDEX_COUNT][tfx__SECOND_LEVEL_INDEX_COUNT];
} tfx_allocator;
#if defined (_MSC_VER) && (_MSC_VER >= 1400) && (defined (_M_IX86) || defined (_M_X64))
/* Microsoft Visual C++ support on x86/X64 architectures. */
#include <intrin.h>
static inline int tfx__scan_reverse(tfx_size bitmap) {
unsigned long index;
#if defined(tfx__64BIT)
return _BitScanReverse64(&index, bitmap) ? index : -1;
#else
return _BitScanReverse(&index, bitmap) ? index : -1;
#endif
}
static inline int tfx__scan_forward(tfx_size bitmap)
{
unsigned long index;
#if defined(tfx__64BIT)
return _BitScanForward64(&index, bitmap) ? index : -1;
#else
return _BitScanForward(&index, bitmap) ? index : -1;
#endif
}
#ifdef _WIN32
#include <Windows.h>
static inline tfxLONG tfx__compare_and_exchange(volatile tfxLONG *target, tfxLONG value, tfxLONG original) {
return InterlockedCompareExchange((volatile LONG *)target, value, original);
}
static inline tfxLONG tfx__exchange(volatile tfxLONG *target, tfxLONG value) {
return InterlockedExchange((volatile LONG *)target, value);
}
static inline unsigned int tfx__increment(unsigned int volatile *target) {
return InterlockedIncrement(target);
}
#endif
#define tfx__strlen strnlen_s
#define tfx__writebarrier _WriteBarrier();
#define tfx__readbarrier _ReadBarrier();
#define tfx__strcpy(dst, size, src) strcpy_s(dst, size, src)
#define tfx__fseek _fseeki64
#define tfx__ftell _ftelli64
#define TFX_ALIGN_AFFIX(v)
#define TFX_PACKED_STRUCT
#elif defined(__GNUC__) && ((__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)) && \
(defined(__i386__) || defined(__x86_64__)) || defined(__clang__)
/* GNU C/C++ or Clang support on x86/x64 architectures. */
static inline int tfx__scan_reverse(tfx_size bitmap)
{
#if defined(tfx__64BIT)
return 64 - __builtin_clzll(bitmap) - 1;
#else
return 32 - __builtin_clz((int)bitmap) - 1;
#endif
}
static inline int tfx__scan_forward(tfx_size bitmap)
{
#if defined(tfx__64BIT)
return __builtin_ffsll(bitmap) - 1;
#else
return __builtin_ffs((int)bitmap) - 1;
#endif
}
static inline tfxLONG tfx__compare_and_exchange(volatile tfxLONG *target, tfxLONG value, tfxLONG original) {
return __sync_val_compare_and_swap(target, original, value);
}
static inline tfxLONG tfx__exchange(volatile tfxLONG *target, tfxLONG value) {
return __sync_lock_test_and_set(target, value);
}
static inline unsigned int tfx__increment(unsigned int volatile *target) {
return __sync_add_and_fetch(target, 1);
}
#define tfx__strlen strnlen
#define tfx__writebarrier __asm__ __volatile__ ("" : : : "memory");
#define tfx__readbarrier __asm__ __volatile__ ("" : : : "memory");
#define tfx__strcpy(dst, size, src) strcpy(dst, src)
#define tfx__fseek fseeko
#define tfx__ftell ftello
#define TFX_ALIGN_AFFIX(v) __attribute__((aligned(v)))
#define TFX_PACKED_STRUCT __attribute__((packed))
#endif
/*
Initialise an allocator. Pass a block of memory that you want to use to store the allocator data. This will not create a pool, only the
necessary data structures to store the allocator.
*/
tfx_allocator *tfx_InitialiseAllocator(void *memory);
/*
Initialise an allocator and a pool at the same time. The data stucture to store the allocator will be stored at the beginning of the memory
you pass to the function and the remaining memory will be used as the pool.
*/
tfx_allocator *tfx_InitialiseAllocatorWithPool(void *memory, tfx_size size, tfx_allocator **allocator);
/*
Add a new memory pool to the allocator. Pools don't have to all be the same size, adding a pool will create the biggest block it can within
the pool and then add that to the segregated list of free blocks in the allocator. All the pools in the allocator will be naturally linked
together in the segregated list because all blocks are linked together with a linked list either as physical neighbours or free blocks in
the segregated list.
*/
tfx_pool *tfx_AddPool(tfx_allocator *allocator, tfx_pool *memory, tfx_size size);
/*
Get the structure size of an allocator. You can use this to take into account the overhead of the allocator when preparing a new allocator
with memory pool.
*/
tfx_size tfx_AllocatorSize(void);
/*
If you initialised an allocator with a pool then you can use this function to get a pointer to the start of the pool. It won't get a pointer
to any other pool in the allocator. You can just get that when you call tfx_AddPool.
*/
tfx_pool *tfx_GetPool(tfx_allocator *allocator);
/*
Allocate some memory within a tfx_allocator of the specified size. Minimum size is 16 bytes.
*/
void *tfx_Allocate(tfx_allocator *allocator, tfx_size size);
/*
Try to reallocate an existing memory block within the allocator. If possible the current block will be merged with the physical neigbouring
block, otherwise a normal tfx_Allocate will take place and the data copied over to the new allocation.
*/
void *tfx_Reallocate(tfx_allocator *allocator, void *ptr, tfx_size size);
/*
Allocate some memory within a tfx_allocator of the specified size. Minimum size is 16 bytes.
*/
void *tfx_AllocateAligned(tfx_allocator *allocator, tfx_size size, tfx_size alignment);
/*
Free an allocation from a tfx_allocator. When freeing a block of memory any adjacent free blocks are merged together to keep on top of
fragmentation as much as possible. A check is also done to confirm that the block being freed is still valid and detect any memory corruption
due to out of bounds writing of this or potentially other blocks.
*/
int tfx_Free(tfx_allocator *allocator, void *allocation);
/*
Remove a pool from an allocator. Note that all blocks in the pool must be free and therefore all merged together into one block (this happens
automatically as all blocks are freed are merged together into bigger blocks.
*/
bool tfx_RemovePool(tfx_allocator *allocator, tfx_pool *pool);
/*
When using an allocator for managing remote memory, you need to set the bytes per block that a block storing infomation about the remote
memory allocation will manage. For example you might set the value to 1MB so if you were to then allocate 4MB of remote memory then 4 blocks
worth of space would be used to allocate that memory. This means that if it were to be freed and then split down to a smaller size they'd be
enough blocks worth of space to do this.
Note that the lower the number the more memory you need to track remote memory blocks but the more granular it will be. It will depend alot
on the size of allocations you will need
*/
void tfx_SetMinimumAllocationSize(tfx_allocator *allocator, tfx_size size);
//--End of user functions
//Private inline functions, user doesn't need to call these
static inline void tfx__map(tfx_size size, tfx_index *fli, tfx_index *sli) {
*fli = tfx__scan_reverse(size);
if (*fli <= tfx__SECOND_LEVEL_INDEX_LOG2) {
*fli = 0;
*sli = (int)size / (tfx__SMALLEST_CATEGORY / tfx__SECOND_LEVEL_INDEX_COUNT);
return;
}
size = size & ~(1 << *fli);
*sli = (tfx_index)(size >> (*fli - tfx__SECOND_LEVEL_INDEX_LOG2)) % tfx__SECOND_LEVEL_INDEX_COUNT;
}
//Read only functions
static inline bool tfx__has_free_block(const tfx_allocator *allocator, tfx_index fli, tfx_index sli) {
return allocator->first_level_bitmap & (TFX_ONE << fli) && allocator->second_level_bitmaps[fli] & (1U << sli);
}
static inline bool tfx__is_used_block(const tfx_header *block) {
return !(block->size & tfx__BLOCK_IS_FREE);
}
static inline bool tfx__is_free_block(const tfx_header *block) {
//Crashing here? The most likely reason is a pointer into the allocation for this block that became invalid but was still written to at some point.
//Most likeyly cause is a tfx_vector_t or similar being resized and allocated elsewhere but you didn't account for this happening and update the pointer. Just index
//into the array instead to fix these issues.
//Another reason is simply that you're trying to free something that isn't actually a block of memory in the allocator, maybe you're just trying to free a struct or
//other object?
return block->size & tfx__BLOCK_IS_FREE;
}
static inline bool tfx__prev_is_free_block(const tfx_header *block) {
return block->size & tfx__PREV_BLOCK_IS_FREE;
}
static inline void *tfx__align_ptr(const void *ptr, tfx_size align) {
ptrdiff_t aligned = (((ptrdiff_t)ptr) + (align - 1)) & ~(align - 1);
TFX_ASSERT(0 == (align & (align - 1)) && "must align to a power of two");
return (void *)aligned;
}
static inline bool tfx__is_aligned(tfx_size size, tfx_size alignment) {
return (size % alignment) == 0;
}
static inline bool tfx__ptr_is_aligned(void *ptr, tfx_size alignment) {
uintptr_t address = (uintptr_t)ptr;
return (address % alignment) == 0;
}
static inline tfx_size tfx__align_size_down(tfx_size size, tfx_size alignment) {
return size - (size % alignment);
}
static inline tfx_size tfx__align_size_up(tfx_size size, tfx_size alignment) {
tfx_size remainder = size % alignment;
if (remainder != 0) {
size += alignment - remainder;
}
return size;
}
static inline tfx_size tfx__adjust_size(tfx_size size, tfx_size minimum_size, tfx_size alignment) {
return tfx__Min(tfx__Max(tfx__align_size_up(size, alignment), minimum_size), tfx__MAXIMUM_BLOCK_SIZE);
}
static inline tfx_size tfx__block_size(const tfx_header *block) {
return block->size & ~(tfx__BLOCK_IS_FREE | tfx__PREV_BLOCK_IS_FREE);
}
static inline tfx_header *tfx__block_from_allocation(const void *allocation) {
return (tfx_header *)((char *)allocation - tfx__BLOCK_POINTER_OFFSET);
}
static inline tfx_header *tfx__null_block(tfx_allocator *allocator) {
return &allocator->null_block;
}
static inline void *tfx__block_user_ptr(const tfx_header *block) {
return (char *)block + tfx__BLOCK_POINTER_OFFSET;
}
static inline tfx_header *tfx__first_block_in_pool(const tfx_pool *pool) {
return (tfx_header *)((char *)pool - tfx__POINTER_SIZE);
}
static inline tfx_header *tfx__next_physical_block(const tfx_header *block) {
return (tfx_header *)((char *)tfx__block_user_ptr(block) + tfx__block_size(block));
}
static inline bool tfx__next_block_is_free(const tfx_header *block) {
return tfx__is_free_block(tfx__next_physical_block(block));
}
static inline tfx_header *tfx__allocator_first_block(tfx_allocator *allocator) {
return (tfx_header *)((char *)allocator + tfx_AllocatorSize() - tfx__POINTER_SIZE);
}
static inline bool tfx__is_last_block_in_pool(const tfx_header *block) {
return tfx__block_size(block) == 0;
}
static inline tfx_index tfx__find_next_size_up(tfx_fl_bitmap map, tfx_uint start) {
//Mask out all bits up to the start point of the scan
map &= (~0ULL << (start + 1));
return tfx__scan_forward(map);
}
//Debug tool to make sure that if a first level bitmap has a bit set, then the corresponding second level index should contain a value
//It also checks that the blocks in the list are valid.
//The most common cause of asserts here is where memory has been written to the wrong address. Check for buffers where they where resized
//but the buffer pointer that was being written too was not updated after the resize for example.
static inline void tfx__verify_lists(tfx_allocator *allocator) {
for (int fli = 0; fli != tfx__FIRST_LEVEL_INDEX_COUNT; ++fli) {
if (allocator->first_level_bitmap & (1ULL << fli)) {
//bit in first level is set but according to the second level bitmap array there are no blocks so the first level
//bitmap bit should have been 0
TFX_ASSERT(allocator->second_level_bitmaps[fli] > 0);
int sli = -1;
sli = tfx__find_next_size_up(allocator->second_level_bitmaps[fli], sli);
while (sli != -1) {
tfx_header *block = allocator->segregated_lists[fli][sli];
bool is_free = tfx__is_free_block(block);
TFX_ASSERT(is_free); //The block should be marked as free
TFX_ASSERT(block->prev_free_block == &allocator->null_block); //The first block in in the list should have a prev_free_block that points to the null block in the allocator
sli = tfx__find_next_size_up(allocator->second_level_bitmaps[fli], sli);
}
}
}
}
//Write functions
#if defined(TFX_THREAD_SAFE)
#define tfx__lock_thread_access(alloc) \
do { \
} while (0 != tfx__compare_and_exchange(&alloc->access, 1, 0)); \
TFX_ASSERT(alloc->access != 0);
#define tfx__unlock_thread_access(alloc) alloc->access = 0;
#else
#define tfx__lock_thread_access
#define tfx__unlock_thread_access
#endif
static inline void tfx__set_block_size(tfx_header *block, tfx_size size) {
tfx_size boundary_tag = block->size & (tfx__BLOCK_IS_FREE | tfx__PREV_BLOCK_IS_FREE);
block->size = size | boundary_tag;
}
static inline void tfx__set_prev_physical_block(tfx_header *block, tfx_header *prev_block) {
block->prev_physical_block = prev_block;
}
static inline void tfx__zero_block(tfx_header *block) {
block->prev_physical_block = 0;
block->size = 0;
}
static inline void tfx__mark_block_as_used(tfx_header *block) {
block->size &= ~tfx__BLOCK_IS_FREE;
tfx_header *next_block = tfx__next_physical_block(block);
next_block->size &= ~tfx__PREV_BLOCK_IS_FREE;
}
static inline void tfx__mark_block_as_free(tfx_header *block) {
block->size |= tfx__BLOCK_IS_FREE;
tfx_header *next_block = tfx__next_physical_block(block);
next_block->size |= tfx__PREV_BLOCK_IS_FREE;
}
static inline void tfx__block_set_used(tfx_header *block) {
block->size &= ~tfx__BLOCK_IS_FREE;
}
static inline void tfx__block_set_free(tfx_header *block) {
block->size |= tfx__BLOCK_IS_FREE;
}
static inline void tfx__block_set_prev_used(tfx_header *block) {
block->size &= ~tfx__PREV_BLOCK_IS_FREE;
}
static inline void tfx__block_set_prev_free(tfx_header *block) {
block->size |= tfx__PREV_BLOCK_IS_FREE;
}
/*
Push a block onto the segregated list of free blocks. Called when tfx_Free is called. Generally blocks are
merged if possible before this is called
*/
static inline void tfx__push_block(tfx_allocator *allocator, tfx_header *block) {
tfx_index fli;
tfx_index sli;
//Get the size class of the block
tfx__map(tfx__block_size(block), &fli, &sli);
tfx_header *current_block_in_free_list = allocator->segregated_lists[fli][sli];
//If you hit this assert then it's likely that at somepoint in your code you're trying to free an allocation
//that was already freed.
TFX_ASSERT(block != current_block_in_free_list);
//Insert the block into the list by updating the next and prev free blocks of
//this and the current block in the free list. The current block in the free
//list may well be the null_block in the allocator so this just means that this
//block will be added as the first block in this class of free blocks.
block->next_free_block = current_block_in_free_list;
block->prev_free_block = &allocator->null_block;
current_block_in_free_list->prev_free_block = block;
allocator->segregated_lists[fli][sli] = block;
//Flag the bitmaps to mark that this size class now contains a free block
allocator->first_level_bitmap |= TFX_ONE << fli;
allocator->second_level_bitmaps[fli] |= 1U << sli;
if (allocator->first_level_bitmap & (TFX_ONE << fli)) {
TFX_ASSERT(allocator->second_level_bitmaps[fli] > 0);
}
tfx__mark_block_as_free(block);
#ifdef TFX_EXTRA_DEBUGGING
tfx__verify_lists(allocator);
#endif
}
/*
Remove a block from the segregated list in the allocator and return it. If there is a next free block in the size class
then move it down the list, otherwise unflag the bitmaps as necessary. This is only called when we're trying to allocate
some memory with tfx_Allocate and we've determined that there's a suitable free block in segregated_lists.
*/
static inline tfx_header *tfx__pop_block(tfx_allocator *allocator, tfx_index fli, tfx_index sli) {
tfx_header *block = allocator->segregated_lists[fli][sli];
//If the block in the segregated list is actually the null_block then something went very wrong.
//Somehow the segregated lists had the end block assigned but the first or second level bitmaps
//did not have the masks assigned
TFX_ASSERT(block != &allocator->null_block);
if (block->next_free_block && block->next_free_block != &allocator->null_block) {
//If there are more free blocks in this size class then shift the next one down and terminate the prev_free_block
allocator->segregated_lists[fli][sli] = block->next_free_block;
allocator->segregated_lists[fli][sli]->prev_free_block = tfx__null_block(allocator);
} else {
//There's no more free blocks in this size class so flag the second level bitmap for this class to 0.
allocator->segregated_lists[fli][sli] = tfx__null_block(allocator);
allocator->second_level_bitmaps[fli] &= ~(1U << sli);
if (allocator->second_level_bitmaps[fli] == 0) {
//And if the second level bitmap is 0 then the corresponding bit in the first lebel can be zero'd too.
allocator->first_level_bitmap &= ~(TFX_ONE << fli);
}
}
if (allocator->first_level_bitmap & (TFX_ONE << fli)) {
TFX_ASSERT(allocator->second_level_bitmaps[fli] > 0);
}
tfx__mark_block_as_used(block);
#ifdef TFX_EXTRA_DEBUGGING
tfx__verify_lists(allocator);
#endif
return block;
}
/*
Remove a block from the segregated list. This is only called when we're merging blocks together. The block is
just removed from the list and marked as used and then merged with an adjacent block.
*/
static inline void tfx__remove_block_from_segregated_list(tfx_allocator *allocator, tfx_header *block) {
tfx_index fli, sli;
//Get the size class
tfx__map(tfx__block_size(block), &fli, &sli);
tfx_header *prev_block = block->prev_free_block;
tfx_header *next_block = block->next_free_block;
TFX_ASSERT(prev_block);
TFX_ASSERT(next_block);
next_block->prev_free_block = prev_block;
prev_block->next_free_block = next_block;
if (allocator->segregated_lists[fli][sli] == block) {
allocator->segregated_lists[fli][sli] = next_block;
if (next_block == tfx__null_block(allocator)) {
allocator->second_level_bitmaps[fli] &= ~(1U << sli);
if (allocator->second_level_bitmaps[fli] == 0) {
allocator->first_level_bitmap &= ~(1ULL << fli);
}
}
}
if (allocator->first_level_bitmap & (TFX_ONE << fli)) {
TFX_ASSERT(allocator->second_level_bitmaps[fli] > 0);
}
tfx__mark_block_as_used(block);
#ifdef TFX_EXTRA_DEBUGGING
tfx__verify_lists(allocator);
#endif
}
/*
This function is called when tfx_Allocate is called. Once a free block is found then it will be split
if the size + header overhead + the minimum block size (16b) is greater then the size of the free block.
If not then it simply returns the free block as it is without splitting.
If split then the trimmed amount is added back to the segregated list of free blocks.
*/
static inline tfx_header *tfx__maybe_split_block(tfx_allocator *allocator, tfx_header *block, tfx_size size, tfx_size remote_size) {
TFX_ASSERT(!tfx__is_last_block_in_pool(block));
tfx_size size_plus_overhead = size + tfx__BLOCK_POINTER_OFFSET;
if (size_plus_overhead + tfx__MINIMUM_BLOCK_SIZE >= tfx__block_size(block)) {
return block;
}
tfx_header *trimmed = (tfx_header *)((char *)tfx__block_user_ptr(block) + size);
trimmed->size = 0;
tfx__set_block_size(trimmed, tfx__block_size(block) - size_plus_overhead);
tfx_header *next_block = tfx__next_physical_block(block);
tfx__set_prev_physical_block(next_block, trimmed);
tfx__set_prev_physical_block(trimmed, block);
tfx__set_block_size(block, size);
tfx__push_block(allocator, trimmed);
return block;
}
//For splitting blocks when allocating to a specific memory alignment
static inline tfx_header *tfx__split_aligned_block(tfx_allocator *allocator, tfx_header *block, tfx_size size) {
TFX_ASSERT(!tfx__is_last_block_in_pool(block));
tfx_size size_minus_overhead = size - tfx__BLOCK_POINTER_OFFSET;
tfx_header *trimmed = (tfx_header *)((char *)tfx__block_user_ptr(block) + size_minus_overhead);
trimmed->size = 0;
tfx__set_block_size(trimmed, tfx__block_size(block) - size);
tfx_header *next_block = tfx__next_physical_block(block);
tfx__set_prev_physical_block(next_block, trimmed);
tfx__set_prev_physical_block(trimmed, block);
tfx__set_block_size(block, size_minus_overhead);
tfx__push_block(allocator, block);
return trimmed;
}
/*
This function is called when tfx_Free is called and the previous physical block is free. If that's the case
then this function will merge the block being freed with the previous physical block then add that back into
the segregated list of free blocks. Note that that happens in the tfx_Free function after attempting to merge
both ways.
*/
static inline tfx_header *tfx__merge_with_prev_block(tfx_allocator *allocator, tfx_header *block) {
TFX_ASSERT(!tfx__is_last_block_in_pool(block));
tfx_header *prev_block = block->prev_physical_block;
tfx__remove_block_from_segregated_list(allocator, prev_block);
tfx__set_block_size(prev_block, tfx__block_size(prev_block) + tfx__block_size(block) + tfx__BLOCK_POINTER_OFFSET);
tfx_header *next_block = tfx__next_physical_block(block);
tfx__set_prev_physical_block(next_block, prev_block);
tfx__zero_block(block);
return prev_block;
}
/*
This function might be called when tfx_Free is called to free a block. If the block being freed is not the last
physical block then this function is called and if the next block is free then it will be merged.
*/
static inline void tfx__merge_with_next_block(tfx_allocator *allocator, tfx_header *block) {
tfx_header *next_block = tfx__next_physical_block(block);
TFX_ASSERT(next_block->prev_physical_block == block); //could be potentional memory corruption. Check that you're not writing outside the boundary of the block size
TFX_ASSERT(!tfx__is_last_block_in_pool(next_block));
tfx__remove_block_from_segregated_list(allocator, next_block);
tfx__set_block_size(block, tfx__block_size(next_block) + tfx__block_size(block) + tfx__BLOCK_POINTER_OFFSET);
tfx_header *block_after_next = tfx__next_physical_block(next_block);
tfx__set_prev_physical_block(block_after_next, block);
tfx__zero_block(next_block);
}
static inline tfx_header *tfx__find_free_block(tfx_allocator *allocator, tfx_size size, tfx_size remote_size) {
tfx_index fli;
tfx_index sli;
tfx__map(size, &fli, &sli);
//Note that there may well be an appropriate size block in the class but that block may not be at the head of the list
//In this situation we could opt to loop through the list of the size class to see if there is an appropriate size but instead
//we stick to the paper and just move on to the next class up to keep a O1 speed at the cost of some extra fragmentation
if (tfx__has_free_block(allocator, fli, sli) && tfx__block_size(allocator->segregated_lists[fli][sli]) >= size) {
tfx_header *block = tfx__pop_block(allocator, fli, sli);
tfx__unlock_thread_access(allocator);
return block;
}
if (sli == tfx__SECOND_LEVEL_INDEX_COUNT - 1) {
sli = -1;
} else {
sli = tfx__find_next_size_up(allocator->second_level_bitmaps[fli], sli);
}
if (sli == -1) {
fli = tfx__find_next_size_up(allocator->first_level_bitmap, fli);
if (fli > -1) {
sli = tfx__scan_forward(allocator->second_level_bitmaps[fli]);
tfx_header *block = tfx__pop_block(allocator, fli, sli);
tfx_header *split_block = tfx__maybe_split_block(allocator, block, size, 0);
tfx__unlock_thread_access(allocator);
return split_block;
}
} else {
tfx_header *block = tfx__pop_block(allocator, fli, sli);
tfx_header *split_block = tfx__maybe_split_block(allocator, block, size, 0);
tfx__unlock_thread_access(allocator);
return split_block;
}
return 0;
}
//--End of internal functions
//--End of header declarations
//Implementation
#if defined(TFX_ALLOCATOR_IMPLEMENTATION)
//Definitions
void *tfx_BlockUserExtensionPtr(const tfx_header *block) {
return (char *)block + sizeof(tfx_header);
}
void *tfx_AllocationFromExtensionPtr(const void *block) {
return (void *)((char *)block - tfx__MINIMUM_BLOCK_SIZE);
}
tfx_allocator *tfx_InitialiseAllocator(void *memory) {
if (!memory) {
TFX_PRINT_ERROR(TFX_ERROR_COLOR"%s: The memory pointer passed in to the initialiser was NULL, did it allocate properly?\n", TFX_ERROR_NAME);
return 0;
}
tfx_allocator *allocator = (tfx_allocator *)memory;
memset(allocator, 0, sizeof(tfx_allocator));
allocator->null_block.next_free_block = &allocator->null_block;
allocator->null_block.prev_free_block = &allocator->null_block;
allocator->minimum_allocation_size = tfx__MINIMUM_BLOCK_SIZE;
//Point all of the segregated list array pointers to the empty block
for (tfx_uint i = 0; i < tfx__FIRST_LEVEL_INDEX_COUNT; i++) {
for (tfx_uint j = 0; j < tfx__SECOND_LEVEL_INDEX_COUNT; j++) {
allocator->segregated_lists[i][j] = &allocator->null_block;
}
}
return allocator;
}
tfx_allocator *tfx_InitialiseAllocatorWithPool(void *memory, tfx_size size, tfx_allocator **allocator) {
tfx_size array_offset = sizeof(tfx_allocator);
if (size < array_offset + tfx__MEMORY_ALIGNMENT) {
TFX_PRINT_ERROR(TFX_ERROR_COLOR"%s: Tried to initialise allocator with a memory allocation that is too small. Must be at least: %zi bytes\n", TFX_ERROR_NAME, array_offset + tfx__MEMORY_ALIGNMENT);
return 0;
}
*allocator = tfx_InitialiseAllocator(memory);
if (!allocator) {
return 0;
}
tfx_AddPool(*allocator, tfx_GetPool(*allocator), size - tfx_AllocatorSize());
return *allocator;
}
tfx_size tfx_AllocatorSize(void) {
return sizeof(tfx_allocator);
}
void tfx_SetMinimumAllocationSize(tfx_allocator *allocator, tfx_size size) {
TFX_ASSERT(allocator->minimum_allocation_size == tfx__MINIMUM_BLOCK_SIZE); //You cannot change this once set
TFX_ASSERT(tfx__is_pow2(size)); //Size must be a power of 2
allocator->minimum_allocation_size = tfx__Max(tfx__MINIMUM_BLOCK_SIZE, size);
}
tfx_pool *tfx_GetPool(tfx_allocator *allocator) {
return (tfx_pool *)((char *)allocator + tfx_AllocatorSize());
}
tfx_pool *tfx_AddPool(tfx_allocator *allocator, tfx_pool *memory, tfx_size size) {
tfx__lock_thread_access(allocator);
//Offset it back by the pointer size, we don't need the prev_physical block pointer as there is none
//for the first block in the pool
tfx_header *block = tfx__first_block_in_pool(memory);
block->size = 0;
//Leave room for an end block
tfx__set_block_size(block, size - (tfx__BLOCK_POINTER_OFFSET)-tfx__BLOCK_SIZE_OVERHEAD);
//Make sure it aligns
tfx__set_block_size(block, tfx__align_size_down(tfx__block_size(block), tfx__MEMORY_ALIGNMENT));
TFX_ASSERT(tfx__block_size(block) > tfx__MINIMUM_BLOCK_SIZE);
tfx__block_set_free(block);
tfx__block_set_prev_used(block);
//Add a 0 sized block at the end of the pool to cap it off
tfx_header *last_block = tfx__next_physical_block(block);
last_block->size = 0;
tfx__block_set_used(last_block);
last_block->prev_physical_block = block;
tfx__push_block(allocator, block);
tfx__unlock_thread_access(allocator);
return memory;
}
bool tfx_RemovePool(tfx_allocator *allocator, tfx_pool *pool) {
tfx__lock_thread_access(allocator);
tfx_header *block = tfx__first_block_in_pool(pool);
if (tfx__is_free_block(block) && !tfx__next_block_is_free(block) && tfx__is_last_block_in_pool(tfx__next_physical_block(block))) {
tfx__remove_block_from_segregated_list(allocator, block);
tfx__unlock_thread_access(allocator);
return 1;
}
#if defined(TFX_THREAD_SAFE)
tfx__unlock_thread_access(allocator);
TFX_PRINT_ERROR(TFX_ERROR_COLOR"%s: In order to remove a pool there must be only 1 free block in the pool. Was possibly freed by another thread\n", TFX_ERROR_NAME);
#else
TFX_PRINT_ERROR(TFX_ERROR_COLOR"%s: In order to remove a pool there must be only 1 free block in the pool.\n", TFX_ERROR_NAME);
#endif
return 0;
}
void *tfx_Allocate(tfx_allocator *allocator, tfx_size size) {
tfx_size remote_size = 0;
tfx__lock_thread_access(allocator);
size = tfx__adjust_size(size, tfx__MINIMUM_BLOCK_SIZE, tfx__MEMORY_ALIGNMENT);
tfx_header *block = tfx__find_free_block(allocator, size, remote_size);
if (block) {
return tfx__block_user_ptr(block);
}
//Out of memory;
TFX_PRINT_ERROR(TFX_ERROR_COLOR"%s: Not enough memory in pool to allocate %zu bytes\n", TFX_ERROR_NAME, size);
tfx__unlock_thread_access(allocator);
return 0;
}
void *tfx_Reallocate(tfx_allocator *allocator, void *ptr, tfx_size size) {
tfx__lock_thread_access(allocator);
if (ptr && size == 0) {
tfx__unlock_thread_access(allocator);
tfx_Free(allocator, ptr);
}
if (!ptr) {
tfx__unlock_thread_access(allocator);
return tfx_Allocate(allocator, size);
}
tfx_header *block = tfx__block_from_allocation(ptr);
tfx_header *next_block = tfx__next_physical_block(block);
void *allocation = 0;
tfx_size current_size = tfx__block_size(block);
tfx_size adjusted_size = tfx__adjust_size(size, allocator->minimum_allocation_size, tfx__MEMORY_ALIGNMENT);
tfx_size combined_size = current_size + tfx__block_size(next_block);
if ((!tfx__next_block_is_free(block) || adjusted_size > combined_size) && adjusted_size > current_size) {
tfx_header *block = tfx__find_free_block(allocator, adjusted_size, 0);
if (block) {
allocation = tfx__block_user_ptr(block);
}
if (allocation) {
tfx_size smallest_size = tfx__Min(current_size, size);
memcpy(allocation, ptr, smallest_size);
tfx_Free(allocator, ptr);
}
} else {
//Reallocation is possible
if (adjusted_size > current_size)
{
tfx__merge_with_next_block(allocator, block);
tfx__mark_block_as_used(block);
}
tfx_header *split_block = tfx__maybe_split_block(allocator, block, adjusted_size, 0);
allocation = tfx__block_user_ptr(split_block);
}
tfx__unlock_thread_access(allocator);
return allocation;
}