Skip to content

Instantly share code, notes, and snippets.

@felixmulder
Created April 29, 2015 13:22
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save felixmulder/86e11e3a73297c7f7f90 to your computer and use it in GitHub Desktop.
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#define PADDING (sizeof(block_t) + sizeof(double) - 1)
#define MINSLICE (sizeof(block_t) + sizeof(double) + 1)
//#define DEBUG
#ifdef DEBUG
#define DPRINTF(arg) fprintf(stderr, arg)
#else
#define DPRINTF(args) if (0) {}
#endif
typedef struct block_t block_t;
struct block_t {
int prepad; /* padding added before block_t to align */
size_t size;
block_t *prev;
block_t *next;
char data[];
};
static block_t *available = NULL;
static void insert_avail(block_t *block)
{
if (block == NULL)
return;
if (available == NULL) {
available = block;
available->next = available;
available->prev = available;
} else {
bool merged = false;
block_t *curr = available;
do {
char *end_curr = curr->data + curr->size;
char *begin_blk = (char *)block - block->prepad;
if (end_curr == begin_blk) {
curr->size += block->prepad + sizeof(block_t) + block->size;
merged = true;
break;
}
} while (curr != available);
if (!merged) {
block_t *last = available->prev;
last->next = block;
available->prev = block;
block->prev = last;
block->next = available;
} else {
DPRINTF("DID MERGE!\n");
}
}
}
static void remove_avail(block_t *block)
{
if (block == NULL || available == NULL)
return;
/* removing last item */
if (block->next == block && block->next == block) {
available = NULL;
} else {
block_t *prev = block->prev;
block_t *next = block->next;
/* only one item left or removing item pointed to by available */
if (prev == next || block == available)
available = prev;
prev->next = next;
next->prev = prev;
block->next = block;
block->prev = block;
}
}
static block_t *slice(block_t *block, size_t size)
{
if (block->size - size < sizeof(block_t) + sizeof(double))
return NULL;
DPRINTF("SLICING\n");
size_t old_size = block->size;
block->size = size;
remove_avail(block);
char *start_new = block->data + size;
int offset = (uintptr_t)start_new % sizeof(double);
size_t new_size = old_size - size - offset - sizeof(block_t);
block_t *new_block = start_new + offset;
new_block->prepad = offset;
new_block->size = new_size;
new_block->next = new_block;
new_block->prev = new_block;
insert_avail(new_block);
return block;
}
static block_t *find_available(size_t size)
{
if (available == NULL)
return NULL;
block_t *curr = available;
do {
if (curr->size == size) {
DPRINTF("same size!\n");
remove_avail(curr);
return curr;
} else if (curr->size > size) {
DPRINTF("larger size!\n");
return slice(curr, size);
}
curr = curr->next;
} while (curr != available && curr != NULL);
return NULL;
}
void *malloc(size_t size)
{
if (size < 1)
return NULL;
//fprintf(stderr, "malloc : %zu\n", size);
block_t *block = find_available(size);
if (block == NULL) {
char *start = sbrk(size + PADDING);
int offset = (uintptr_t)start % sizeof(double);
block = (void *)(start + offset);
char *end = sbrk(0);
if (block == (void*)-1)
return NULL;
block->prepad = offset;
block->size = size;
block->prev = block;
block->next = block;
}
return block->data;
}
void *calloc(size_t nmemb, size_t size)
{
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)
{
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;
for (i = 0; i < old_alloc->size && i < size; i++)
new_alloc[i] = old_alloc->data[i];
free(ptr);
return new_alloc;
}
void free(void *ptr)
{
if (ptr == NULL)
return;
block_t *block = (void *)((char *)ptr - sizeof(block_t));
char *end = sbrk(0);
/* This block is allocated at the end of the heap!
* As such, the program break can be decreased.
*/
if ((char *)ptr + block->size == end) {
sbrk(-(block->size + PADDING));
return;
}
insert_avail(block);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment