46#define KEY_TYPE struct freelist_header
47#define KEY_IS_STRICTLY_LESS(a, b) ((a).curr_block_size < (b).curr_block_size)
48#define KEY_MEMBER_IS_FIRST
49#define ALLOW_DUPLICATES
65static inline struct freetree_node *internal_freetree_search_best_block(
struct freetree_node **rootptr_ptr,
66 const size_t block_size);
72static inline struct freelist_header freelist_header_from(const bool is_freed, const size_t prev_size,
73 const size_t curr_size)
75 return (
struct freelist_header){.__prev_block_size_w_freed_bit = prev_size + (is_freed ? 1 : 0),
80static inline size_t freelist_header_prev_size(
const struct freelist_header *header)
86static inline bool freelist_header_is_freed(
const struct freelist_header *header)
94 const size_t prev_size = freelist_header_prev_size(header);
96 return prev_size == 0 ? NULL : (
struct freelist_header *)((
char *)header - prev_size);
101 const struct freelist *freelist_ptr)
104 const bool is_end = next >= (
char *)freelist_ptr->buf_ptr + freelist_ptr->buf_len;
110static inline bool freelist_header_should_be_in_freetree(
const struct freelist_header *header)
112 return freelist_header_is_freed(header) && header->
curr_block_size >=
sizeof(
struct freetree_node);
116static inline void freelist_deallocate_all(
struct freelist *self)
120 struct freetree_node *node = (
struct freetree_node *)self->
buf_ptr;
122 freetree_node_init(node, freelist_header_from(
true, 0, self->buf_len));
124 self->buf_used = self->buf_len - node->key.curr_block_size;
125 self->rb_rootptr = node;
126 self->head = &node->key;
130static inline void freelist_init(
struct freelist *self,
const size_t len,
unsigned char *backing_buf)
137 assert(len >=
sizeof(
struct freetree_node) + padding);
139 self->
buf_ptr = &backing_buf[padding];
142 freelist_deallocate_all(self);
146static inline void *internal_freelist_init_block(
struct freelist *self,
char *block_ptr,
struct freelist_header *next,
147 const size_t prev_size,
const size_t block_size,
148 const size_t remaining_size)
150 if (remaining_size > 0) {
152 *remaining_header = freelist_header_from(
true, block_size, remaining_size);
155 *next = freelist_header_from(freelist_header_is_freed(next), remaining_size, next->
curr_block_size);
158 if (freelist_header_should_be_in_freetree(remaining_header)) {
159 struct freetree_node *new_node = (
struct freetree_node *)remaining_header;
160 freetree_node_init(new_node, *remaining_header);
161 freetree_insert_node(&self->
rb_rootptr, new_node);
165 *curr_header = freelist_header_from(
false, prev_size, block_size);
170static inline size_t internal_freelist_calc_block_size(
size_t requested_size)
173 block_size = block_size >=
sizeof(
struct freetree_node) ? block_size : sizeof(struct freetree_node);
181static inline void *freelist_allocate(struct freelist *self, const size_t requested_size)
184 assert(requested_size != 0);
186 const size_t block_size = internal_freelist_calc_block_size(requested_size);
188 struct freetree_node *node = internal_freetree_search_best_block(&self->
rb_rootptr, block_size);
194 freetree_delete_node(&self->
rb_rootptr, node);
198 return internal_freelist_init_block(self, (
char *)node, freelist_header_next(&node->key, self),
199 freelist_header_prev_size(&node->key), block_size,
200 node->key.curr_block_size - block_size);
204static inline void freelist_deallocate(
struct freelist *self,
void *ptr)
206 assert(self->
buf_ptr <= (
unsigned char *)ptr && (
unsigned char *)ptr < &self->buf_ptr[self->
buf_len]);
210 assert(!freelist_header_is_freed(header) &&
"double free detected!");
214 internal_freelist_coalescence(self, header);
218static inline void *freelist_reallocate(
struct freelist *self,
void *ptr,
const size_t new_size)
221 assert(new_size != 0);
222 assert(&self->
buf_ptr[0] <= (
unsigned char *)ptr && (
unsigned char *)ptr < &self->buf_ptr[self->
buf_len]);
225 const size_t prev_size = freelist_header_prev_size(header);
228 assert(freelist_header_is_freed(header) &&
"reallocating freed block!");
230 if (new_size <= old_size) {
231 const size_t block_size = internal_freelist_calc_block_size(new_size);
236 return internal_freelist_init_block(self, (
char *)header, freelist_header_next(header, self), prev_size,
242 while (bytes_acc < new_size && next != NULL && !freelist_header_is_freed(next)) {
244 next = freelist_header_next(next, self);
247 if (bytes_acc >= new_size) {
248 return internal_freelist_init_block(self, (
char *)header, next, prev_size, new_size, bytes_acc - new_size);
251 void *ptr_new = freelist_allocate(self, new_size);
256 memcpy(ptr_new, ptr, old_size);
258 freelist_deallocate(self, ptr);
264static inline struct freetree_node *internal_freetree_search_best_block(
struct freetree_node **rootptr_ptr,
265 const size_t block_size)
267 assert(rootptr_ptr != NULL);
269 struct freetree_node *prev_ptr = NULL;
270 struct freetree_node *curr_ptr = *rootptr_ptr;
272 while (curr_ptr != NULL) {
273 if (block_size > curr_ptr->key.curr_block_size) {
274 curr_ptr = curr_ptr->right_ptr;
278 curr_ptr = curr_ptr->left_ptr;
296 if (prev && freelist_header_is_freed(prev)) {
301 if (freelist_header_should_be_in_freetree(prev)) {
302 freetree_delete_node(&self->
rb_rootptr, (
struct freetree_node *)prev);
305 if (next && freelist_header_is_freed(next)) {
307 header_next = freelist_header_next(next, self);
309 if (freelist_header_should_be_in_freetree(next)) {
310 freetree_delete_node(&self->
rb_rootptr, (
struct freetree_node *)next);
314 *header_next = freelist_header_from(freelist_header_is_freed(header_next), header_new.
curr_block_size,
318 assert(freelist_header_should_be_in_freetree(&header_new));
320 struct freetree_node *node_addr = (
struct freetree_node *)header_addr;
321 freetree_node_init(node_addr, header_new);
322 freetree_insert_node(&self->
rb_rootptr, node_addr);
static uintptr_t calc_alignment_padding(const size_t alignment, const uintptr_t ptr)
Calculate the alignment padding required to align a pointer.
Definition align.h:91
#define CALC_ALIGNMENT_PADDING(alignment, ptr)
compile time calc_alignment_padding.
Definition align.h:105
Intrusive red-black tree.
Freelist struct definition.
Definition freelist.h:56
struct freetree_node * rb_rootptr
Header of freetree (freed memory blocks)
Definition freelist.h:60
unsigned char * buf_ptr
Underlying buffer.
Definition freelist.h:61
size_t buf_used
Number of bytes used of buffer.
Definition freelist.h:58
struct freelist_header * head
Header of freelist headers (all memory blocks)
Definition freelist.h:59
size_t buf_len
Buffer length.
Definition freelist.h:57