1 #ifndef CORE_ARRAY_H
2 #define CORE_ARRAY_H
3 
4 #include <stdlib.h>
5 #include <string.h>
6 
7 /**
8  * Creates an array structure
9  * @param T The type of item that the array holds
10  */
11 #define array(T) \
12 struct { \
13     T **items; \
14     int size; \
15     int blocks; \
16     int block_offset; \
17     int bit_offset; \
18     void (*constructor)(T *, int); \
19     int (*in_use)(const T *); \
20 }
21 
22 /**
23  * Initiates an array
24  * @param a The array structure
25  * @param size The size of each block of items
26  * @param new_item_callback A function to run when a new item is added to an array. Can be null.
27  *        Items are are always zeroed before the function is called.
28  *        The function should have the following signature:
29  *        void(<item> *, int position). <item> is the new array item, position is its index.
30  * @param in_use_callback A function to check if the current position has a valid item. Can be null.
31  *        If null, it is assumed that every item in the array is valid.
32  *        The function should have the following signature:
33  *        int(<item> *). <item> is the current array item. Should return 1 if the item is being used.
34  * @return Whether memory was properly allocated.
35  */
36 #define array_init(a, size, new_item_callback, in_use_callback) \
37 ( \
38     array_free((void **)(a).items, (a).blocks), \
39     memset(&(a), 0, sizeof(a)), \
40     (a).constructor = new_item_callback, \
41     (a).in_use = in_use_callback, \
42     (a).block_offset = array_next_power_of_two(size) - 1, \
43     (a).bit_offset = array_active_bit(array_next_power_of_two(size)), \
44     array_create_blocks(a, 1) \
45 )
46 
47 /**
48  * Creates a new item for the array, either by finding an available empty item or by expanding the array.
49  * @param a The array structure
50  * @param index The index upon which to start searching for a free slot. If index is greater than the arrray size,
51  *        the array will be expanded.
52  * @param ptr A pointer that will get the new item. Will be null if there was a memory allocation error.
53  */
54 #define array_new_item(a, index, ptr) \
55 { \
56     ptr = 0; \
57     int error = 0; \
58     while ((a).size < index) { \
59         if (!array_advance(a)) { \
60             error = 1; \
61             break; \
62         } \
63     } \
64     if (!error && (a).in_use) { \
65         for (int i = index; i < (a).size; i++) { \
66             if (!(a).in_use(array_item(a, i))) { \
67                 ptr = array_item(a, i); \
68                 memset(ptr, 0, sizeof(**(a).items)); \
69                 if ((a).constructor) { \
70                     (a).constructor(ptr, i); \
71                 } \
72                 break; \
73             } \
74         } \
75     } \
76     if (!error && !ptr) { \
77         ptr = array_advance(a); \
78     } \
79 }
80 
81 /**
82  * Advances an array, creating a new item, incrementing size and increasing the memory buffer if needed
83  * @param a The array structure
84  * @return A pointer to the newest item of the array, or 0 if there was a memory allocation error
85  */
86 #define array_advance(a) \
87 ( \
88     (a).size >> (a).bit_offset < (a).blocks || \
89     array_create_blocks(a, 1) ? \
90     array_next(a) : 0 \
91 )
92 
93 /**
94  * Gets the array item at the specified position
95  * @param a The array structure
96  * @param position The position to fetch
97  * @return A pointer to the item at the requested position
98  */
99 #define array_item(a, position) \
100 ( \
101     &(a).items[(position) >> (a).bit_offset][(position) & (a).block_offset] \
102 )
103 
104 /**
105  * Returns the first item of the array, or 0 if the array has no items
106  * @param a The array structure
107  * @return A pointer to the first item of the array, or 0 if the array has no items
108  */
109 #define array_first(a) \
110     ( (a).size > 0 ? (a).items[0] : 0 )
111 
112 /**
113  * Returns the last item of the array, or 0 if the array has no items
114  * @param a The array structure
115  * @return A pointer to the last item of the array, or 0 if the array has no items
116  */
117 #define array_last(a) \
118     ( (a).size > 0 ? array_item(a, (a).size - 1) : 0 )
119 
120 /**
121  * Iterates through an array
122  * @param a The array structure
123  * @param item A pointer to the array item that will be used to traverse the structure
124  */
125 #define array_foreach(a, item) \
126     for(int i = 0; i < (a).size && ((item) = array_item(a, i)); i++)
127 
128 /**
129  * Trims an array, removing its latest items that aren't being used until the first one is used.
130  * The first item of the array is always kept.
131  * @param a The array structure
132  */
133 #define array_trim(a) \
134 { \
135     if ((a).size > 1 && (a).in_use) { \
136         while ((a).size - 1 && !(a).in_use(array_item(a, (a).size - 1))) { \
137             (a).size--; \
138         } \
139     } \
140 }
141 
142 /**
143  * Expands an array to fit the specified amount of items. The array may become larger than size, but never smaller.
144  * @param a The array structure
145  * @param Size The size that the array should at least expand into
146  * @return Whether memory was properly allocated.
147  */
148 #define array_expand(a, size) \
149 ( \
150     array_create_blocks(a, (size) > 0 ? (((size) - 1) >> (a).bit_offset) + 1 - (a).blocks : 0) \
151 )
152 
153 /**
154  * Gets the next item of the array without checking for memory bounds.
155  * ONLY use when you're SURE the array memory bounds won't be exceeded!
156  * @param a The array structure
157  * @return A pointer to the newest item of the array, or 0 if there was a memory allocation error
158  */
159 #define array_next(a) \
160 ( \
161     memset(array_item(a, (a).size), 0, sizeof(**(a).items)), \
162     (a).constructor ? (a).constructor(array_item(a, (a).size), (a).size) : 0, \
163     (a).size++, \
164     array_item(a, (a).size - 1) \
165 )
166 
167 /**
168  * This definition is private and should not be used
169  */
170 #define array_create_blocks(a, num_blocks) \
171 ( \
172     array_add_blocks((void ***)&(a).items, &(a).blocks, (a).block_offset + 1, sizeof(**(a).items), num_blocks) \
173 )
174 
175 /**
176  * This function is private and should not be used
177  */
178 int array_add_blocks(void ***data, int *blocks, int items_per_block, int item_size, int num_blocks);
179 
180 /**
181  * This function is private and should not be used
182  */
183 void array_free(void **data, int blocks);
184 
185 /**
186  * Private helper compile-time functions for finding the next power of two into which a number fits
187  */
188 #define array_next_power_of_two_0(v) ((v) - 1)
189 #define array_next_power_of_two_1(v) (array_next_power_of_two_0(v) | array_next_power_of_two_0(v) >> 1)
190 #define array_next_power_of_two_2(v) (array_next_power_of_two_1(v) | array_next_power_of_two_1(v) >> 2)
191 #define array_next_power_of_two_3(v) (array_next_power_of_two_2(v) | array_next_power_of_two_2(v) >> 4)
192 #define array_next_power_of_two_4(v) (array_next_power_of_two_3(v) | array_next_power_of_two_3(v) >> 8)
193 #define array_next_power_of_two_5(v) (array_next_power_of_two_4(v) | array_next_power_of_two_4(v) >> 16)
194 #define array_next_power_of_two(v) (((v) < 1) ? 1 : array_next_power_of_two_5(v) + 1)
195 
196 /**
197  * Private helper compile-time functions for finding the which bit is active on a power of two
198  */
199 #define array_active_bit_1(n) (((n) >= 2) ? 1 : 0)
200 #define array_active_bit_2(n) (((n) >= 1 << 2) ? (2 + array_active_bit_1((n) >> 2)) : array_active_bit_1(n))
201 #define array_active_bit_3(n) (((n) >= 1 << 4) ? (4 + array_active_bit_2((n) >> 4)) : array_active_bit_2(n))
202 #define array_active_bit_4(n) (((n) >= 1 << 8) ? (8 + array_active_bit_3((n) >> 8)) : array_active_bit_3(n))
203 #define array_active_bit(n)   (((n) >= 1 << 16) ? (16 + array_active_bit_4((n) >> 16)) : array_active_bit_4(n))
204 
205 #endif // CORE_ARRAY_H
206