Create a gist now

Instantly share code, notes, and snippets.

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include <stdarg.h>
#include <assert.h>
//#define DEBUG
#define MAX_KVAL (26)
#define PADDING (sizeof(double) - 1)
#define RESERVED (1)
#define FREE (0)
typedef struct block_t block_t;
struct block_t {
unsigned status: 1; /* RESERVED / FREE */
size_t kval;
block_t *succ;
char data[];
};
static block_t *blocks[MAX_KVAL + 1];
static char *pool;
static inline void debug(const char *format, ...)
{
#ifdef DEBUG
/* my debug function */
va_list vargs;
va_start(vargs, format);
vfprintf(stderr, format, vargs);
va_end(vargs);
#endif
}
static void *split(size_t order)
{
debug("[%-7s] entered function, order: %zu\n", __func__, order);
size_t i;
block_t *block = NULL;
for (i = order + 1; i <= MAX_KVAL; i++) {
if (blocks[i] != NULL) {
debug("[%-7s] found block at pos: %zu\n", __func__, i);
block = blocks[i];
blocks[i] = block->succ;
block->succ = NULL;
break;
}
}
if (block == NULL)
return NULL;
debug("[%-7s] found block with kval: %zu\n", __func__, block->kval);
if (block->kval > MAX_KVAL || block->kval == 0) {
debug("[%-7s] encountered weird block_t:\n", __func__);
debug(" status: %d\n", block->status);
debug(" kval: %zu\n", block->kval);
return NULL;
}
debug("[%-7s] chosen block->kval: %zu\n", __func__, block->kval);
do {
debug("[%-7s] splitting for order = %zu into two order = %zu\n",
__func__, block->kval, block->kval-1);
block->kval -= 1;
block_t *buddy = (void *)(pool + (((char *)block - pool) ^ (1 << block->kval)));
buddy->kval = block->kval;
buddy->status = FREE;
buddy->succ = blocks[block->kval];
blocks[block->kval] = buddy;
} while (block->kval != order);
debug("[%-7s] done splitting\n", __func__);
block->status = RESERVED;
return block->data;
}
void *malloc(size_t size)
{
debug("[%-7s] entered function, size: %zu\n", __func__, size);
if (pool == NULL) {
char *start = sbrk((1 << MAX_KVAL) + PADDING);
int offset = (uintptr_t)start % sizeof(double);
block_t *init = blocks[MAX_KVAL] = (void *)(start + offset);
pool = (void *)blocks[MAX_KVAL];
init->status = FREE;
init->kval = MAX_KVAL;
init->succ = NULL;
}
size_t order = 2;
while((1 << order) < (size + sizeof(block_t)))
order++;
if (blocks[order] != NULL) {
debug("[%-7s] got order %zu block\n", __func__, order);
block_t *block = blocks[order];
blocks[order] = block->succ;
block->succ = NULL;
block->status = RESERVED;
return block->data;
}
return split(order);
}
void *calloc(size_t nmemb, size_t size)
{
debug("[%-7s] entered function\n", __func__);
size_t total = nmemb * size;
char *alloc = malloc(total);
if (alloc == NULL)
return NULL;
size_t i;
for (i = 0; i < total; i++)
alloc[i] = 0;
return alloc;
}
void *realloc(void *ptr, size_t size)
{
debug("[%-7s] entered function\n", __func__);
size_t i;
block_t *old_alloc = (void*)((char*)ptr - sizeof(block_t));
char *new_alloc = malloc(size);
if (new_alloc == NULL || ptr == NULL)
return NULL;
size_t old_siz = (1 << old_alloc->kval) - sizeof(block_t);
for (i = 0; i < old_siz && i < size; i++)
new_alloc[i] = old_alloc->data[i];
free(ptr);
return new_alloc;
}
static void remove_block(block_t *block)
{
size_t order = block->kval;
block_t *current = blocks[order];
/* element not in list */
if (current == NULL) {
debug("[%-7s] element not found (order: %zu)\n", __func__, order);
return;
}
/* is first in list */
if (current == block) {
blocks[order] = current->succ;
return;
}
/* set current to succ until succ is block */
while (current->succ != block)
current = current->succ;
current->succ = current->succ->succ;
}
void free(void *ptr)
{
debug("[%-7s] entered function\n", __func__);
if (ptr == NULL)
return;
/* check buddy is free and if buddy is same kval */
block_t *block = (char *)ptr - sizeof(block_t);
block_t *buddy = (char *)(pool + (((char *)block - pool) ^ (1 << block->kval)));
debug("[%-7s] block->kval = %zu\n", __func__, block->kval);
/* set current block to free */
block->status = FREE;
/* merge with buddies until buddy found not to be free */
while (block->kval < MAX_KVAL &&
buddy->status == FREE &&
buddy->kval == block->kval) {
remove_block(buddy);
/* we need to that block is the "left" block */
if (block > buddy) {
block_t *tmp = block;
block = buddy;
buddy = block;
}
block->kval += 1;
buddy = (void *)(pool + (((char *)block - pool) ^ (1 << block->kval)));
}
block->succ = blocks[block->kval];
blocks[block->kval] = block;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment