/*
* heap.c
* Copyright (c) 2021 Jon Santmyer <jon@jonsantmyer.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
/**
* File : heap.c
* Author : Jon Santmyer <jon@jonsantmyer.com>
* Date : 10.12.2021
*/
#include "heap.h"
#include <string.h>
int
heap_create(struct heap *heap, uintptr_t at, size_t len)
{
struct crate *firstcrate = NULL;
struct bucket *cratebucket = NULL;
struct bucket *freebucket = NULL;
memset(heap, 0, sizeof(struct heap));
heap->start = at;
heap->size = len;
/*check if heap can fit crate*/
if(len < HEAP_CRATE_SIZE) return -1;
/*Populate first crate*/
heap->crates_tail = heap->crates_head = firstcrate = (struct crate*)at;
cratebucket = &firstcrate->buckets[0];
heap->used = HEAP_CRATE_SIZE;
memset(firstcrate, 0, HEAP_CRATE_SIZE);
/*Allocate first bucket for crate*/
heap->buckets_tail = heap->buckets_head = cratebucket;
cratebucket->address = (uintptr_t)firstcrate;
cratebucket->sizetaken = HEAP_CRATE_SIZE | 1;
/*Set buckets after 1 to link to free list*/
for(size_t i = 2; i < HEAP_CRATE_BUCKETS; i++) {
struct bucket *prev = &firstcrate->buckets[i - 1];
struct bucket *bucket = &firstcrate->buckets[i];
prev->next = bucket;
bucket->prev = prev;
}
heap->buckets_unused_tail = &firstcrate->buckets[1];
return 0;
}
struct bucket*
__heap_bucket_findbest(struct heap *heap, size_t size)
{
struct bucket *best = NULL;
for(struct bucket *bucket = heap->buckets_tail;
bucket != NULL;
bucket = bucket->next)
{
if(HEAP_BUCKET_TAKEN(bucket)) continue;
if(bucket->sizetaken < size) continue;
if(best == NULL) best = bucket;
if(best->sizetaken > bucket->sizetaken) best = bucket;
}
return best;
}
struct bucket*
__heap_crate_create(struct heap *heap)
{
size_t remaining = heap->size - heap->used;
struct bucket *head = heap->buckets_head;
struct bucket *crate_bucket = NULL;
struct crate *crate = NULL;
/*Check for room in heap*/
if(remaining < HEAP_CRATE_SIZE) {
return NULL;
}
/*Take crate bucket from crate head*/
crate_bucket = &heap->crates_head->reserved;
/*Populate crate bucket*/
crate_bucket->address = heap->start + heap->used;
crate_bucket->sizetaken = HEAP_CRATE_SIZE | 1;
crate_bucket->prev = heap->buckets_head;
heap->buckets_head = crate_bucket;
/*Populate crate, linking buckets together*/
crate = (struct crate*)crate_bucket->address;
memset(crate, 0, HEAP_CRATE_SIZE);
for(size_t i = 0; i < HEAP_CRATE_BUCKETS; i++) {
struct bucket *bucket = &crate->buckets[i];
struct bucket *prev = &crate->buckets[i-1];
bucket->prev = prev;
prev->next = bucket;
}
/*Set unused tail to first bucket*/
heap->buckets_unused_tail = &crate->buckets[0];
/*Add crate to crate list*/
heap->crates_head->next = crate;
heap->crates_head = crate;
/*Add used memory to heap info*/
heap->used += HEAP_CRATE_SIZE;
return heap->buckets_unused_tail;
}
struct bucket*
__heap_bucket_append(struct heap *heap, struct bucket *bucket, size_t size)
{
/*Get free bucket from crate*/
struct bucket *free = heap->buckets_unused_tail;
if(free == NULL) {
free = __heap_crate_create(heap);
if(free == NULL) return NULL;
}
heap->buckets_unused_tail = heap->buckets_unused_tail->next;
/*Append free to bucket chain*/
free->prev = bucket;
free->next = bucket->next;
if(free->next != NULL) free->next->prev = free;
bucket->next = free;
/*Fix heap buckets_head*/
if(free->next == NULL) heap->buckets_head = free;
/*Populate free bucket*/
free->address = bucket->address + bucket->sizetaken;
free->sizetaken = size;
return free;
}
void
__heap_bucket_release(struct heap *heap, struct bucket *bucket)
{
/*Disconnect bucket from main chain*/
if(bucket->prev != NULL) {
bucket->prev->next = bucket->next;
}else{
heap->buckets_tail = bucket->next;
}
if(bucket->next != NULL) {
bucket->next->prev = bucket->prev;
}else{
heap->buckets_head = bucket->prev;
}
/*Attach bucket to unused list*/
bucket->next = heap->buckets_unused_tail;
bucket->prev = NULL;
heap->buckets_unused_tail = bucket;
}
void
__heap_bucket_split(struct heap *heap, struct bucket *bucket, size_t size)
{
/*Check if split is required*/
intmax_t diff = bucket->sizetaken - size;
if(diff <= 0) return;
/*Shrink bucket to required size*/
bucket->sizetaken = size;
/*Create new bucket with remainder*/
__heap_bucket_append(heap, bucket, diff);
}
void
__heap_bucket_merge(struct heap *heap, struct bucket *bucket)
{
struct bucket *prev = bucket->prev;
struct bucket *next = bucket->next;
/*Merge bucket with prev*/
if(prev != NULL) {
if(!HEAP_BUCKET_TAKEN(prev)) {
prev->sizetaken += bucket->sizetaken;
__heap_bucket_release(heap, bucket);
__heap_bucket_merge(heap, prev);
return;
}
}
/*Merge bucket with next*/
if(next != NULL) {
if(!HEAP_BUCKET_TAKEN(next)) {
bucket->sizetaken += next->sizetaken;
__heap_bucket_release(heap, next);
__heap_bucket_merge(heap, bucket);
}
}
}
void*
heap_alloc(struct heap *heap, size_t size)
{
struct bucket *bestfit = NULL;
size_t remaining = heap->size - heap->used;
if(size == 0) return NULL;
/*Check for room in heap*/
if(remaining < size) return NULL;
/*Resize to fit with granularity*/
size = ((size + (HEAP_ALLOC_GRAN - 1)) / HEAP_ALLOC_GRAN) * HEAP_ALLOC_GRAN;
bestfit = __heap_bucket_findbest(heap, size);
if(bestfit == NULL) {
if(!HEAP_BUCKET_TAKEN(heap->buckets_head)) {
/*Expand empty head to fit*/
heap->buckets_head->sizetaken = size;
bestfit = heap->buckets_head;
}else{
/*Append new bucket to list*/
bestfit = __heap_bucket_append(heap, heap->buckets_head, size);
}
if(bestfit == NULL) return NULL; /*Heap ran out of space*/
}
/*Split bucket into perfectly sized piece*/
__heap_bucket_split(heap, bestfit, size);
/*Take memory in heap, mark bucket as taken*/
heap->used += bestfit->sizetaken;
bestfit->sizetaken |= 1;
return (void*)bestfit->address;
}
int
heap_free(struct heap *heap, void *ptr)
{
uintptr_t addr = (uintptr_t)ptr;
for(struct bucket *bucket = heap->buckets_tail;
bucket != NULL;
bucket = bucket->next)
{
if(bucket->address == addr) {
bucket->sizetaken &= ~1;
__heap_bucket_merge(heap, bucket);
return 0;
}
}
return -1;
}