diff options
Diffstat (limited to 'heap.c')
| -rw-r--r-- | heap.c | 276 |
1 files changed, 276 insertions, 0 deletions
@@ -0,0 +1,276 @@ +/* + * 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; +} |