From e2b78d20b80d89321d8d9df3ab8ade8407642dfc Mon Sep 17 00:00:00 2001 From: Aleksa Vučković Date: Sun, 2 Jan 2022 22:56:02 +0100 Subject: Adding code --- include/08.heap/heap00.c | 1 + include/08.heap/heap01.c | 7 ++++++ include/08.heap/heap02.c | 3 +++ include/08.heap/heap03.c | 3 +++ include/08.heap/heap04.c | 33 +++++++++++++++++++++++++++ include/08.heap/heap05.c | 5 +++++ include/08.heap/heap06.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++ include/08.heap/heap07.c | 32 ++++++++++++++++++++++++++ include/08.heap/heap08.c | 9 ++++++++ include/08.heap/heap09.c | 9 ++++++++ 10 files changed, 160 insertions(+) create mode 100644 include/08.heap/heap00.c create mode 100644 include/08.heap/heap01.c create mode 100644 include/08.heap/heap02.c create mode 100644 include/08.heap/heap03.c create mode 100644 include/08.heap/heap04.c create mode 100644 include/08.heap/heap05.c create mode 100644 include/08.heap/heap06.c create mode 100644 include/08.heap/heap07.c create mode 100644 include/08.heap/heap08.c create mode 100644 include/08.heap/heap09.c (limited to 'include/08.heap') diff --git a/include/08.heap/heap00.c b/include/08.heap/heap00.c new file mode 100644 index 0000000..c45e28b --- /dev/null +++ b/include/08.heap/heap00.c @@ -0,0 +1 @@ +#include diff --git a/include/08.heap/heap01.c b/include/08.heap/heap01.c new file mode 100644 index 0000000..e7f4f84 --- /dev/null +++ b/include/08.heap/heap01.c @@ -0,0 +1,7 @@ +typedef struct _KHEAPBLOCKBM { + struct _KHEAPBLOCKBM *next; + uint32_t size; + uint32_t used; + uint32_t bsize; + uint32_t lfb; +} KHEAPBLOCKBM; diff --git a/include/08.heap/heap02.c b/include/08.heap/heap02.c new file mode 100644 index 0000000..e46dc38 --- /dev/null +++ b/include/08.heap/heap02.c @@ -0,0 +1,3 @@ +typedef struct _KHEAPBM { + KHEAPBLOCKBM *fblock; +} KHEAPBM; diff --git a/include/08.heap/heap03.c b/include/08.heap/heap03.c new file mode 100644 index 0000000..9e2fe89 --- /dev/null +++ b/include/08.heap/heap03.c @@ -0,0 +1,3 @@ +void k_heapBMInit(KHEAPBM *heap) { + heap->fblock = 0; +} diff --git a/include/08.heap/heap04.c b/include/08.heap/heap04.c new file mode 100644 index 0000000..be39951 --- /dev/null +++ b/include/08.heap/heap04.c @@ -0,0 +1,33 @@ +int k_heapBMAddBlock(KHEAPBM *heap, uintptr_t addr, uint32_t size, uint32_t bsize) { + KHEAPBLOCKBM *b; + uint32_t bcnt; + uint32_t x; + uint8_t *bm; + + b = (KHEAPBLOCKBM*)addr; + b->size = size - sizeof(KHEAPBLOCKBM); + b->bsize = bsize; + + b->next = heap->fblock; + heap->fblock = b; + + bcnt = b->size / b->bsize; + bm = (uint8_t*)&b[1]; + + /* clear bitmap */ + for (x = 0; x < bcnt; ++x) { + bm[x] = 0; + } + + /* reserve room for bitmap */ + bcnt = (bcnt / bsize) * bsize < bcnt ? bcnt / bsize + 1 : bcnt / bsize; + for (x = 0; x < bcnt; ++x) { + bm[x] = 5; + } + + b->lfb = bcnt - 1; + + b->used = bcnt; + + return 1; +} diff --git a/include/08.heap/heap05.c b/include/08.heap/heap05.c new file mode 100644 index 0000000..1856ca5 --- /dev/null +++ b/include/08.heap/heap05.c @@ -0,0 +1,5 @@ +static uint8_t k_heapBMGetNID(uint8_t a, uint8_t b) { + uint8_t c; + for (c = a + 1; c == b || c == 0; ++c); + return c; +} diff --git a/include/08.heap/heap06.c b/include/08.heap/heap06.c new file mode 100644 index 0000000..5ad2787 --- /dev/null +++ b/include/08.heap/heap06.c @@ -0,0 +1,58 @@ +void *k_heapBMAlloc(KHEAPBM *heap, uint32_t size) { + KHEAPBLOCKBM *b; + uint8_t *bm; + uint32_t bcnt; + uint32_t x, y, z; + uint32_t bneed; + uint8_t nid; + + /* iterate blocks */ + for (b = heap->fblock; b; b = b->next) { + //printf("size:%d,used:%d,bsize:%d,lfb:%d\n",b->size,b->used,b->bsize,b->lfb); + /* check if block has enough room */ + if (b->size - (b->used * b->bsize) >= size) { + + bcnt = b->size / b->bsize; + bneed = (size / b->bsize) * b->bsize < size ? size / b->bsize + 1 : size / b->bsize; + bm = (uint8_t*)&b[1]; + //printf("bcnt:%d,bneed:%d,bm:%d\n",bcnt,bneed,bm); + + for (x = (b->lfb + 1 >= bcnt ? 0 : b->lfb + 1); x != b->lfb; ++x) { + /* just wrap around */ + if (x >= bcnt) { + x = 0; + } + + if (bm[x] == 0) { + /* count free blocks */ + for (y = 0; bm[x + y] == 0 && y < bneed && (x + y) < bcnt; ++y); + + /* we have enough, now allocate them */ + if (y == bneed) { + /* find ID that does not match left or right */ + nid = k_heapBMGetNID(bm[x - 1], bm[x + y]); + + /* allocate by setting id */ + for (z = 0; z < y; ++z) { + bm[x + z] = nid; + } + + /* optimization */ + b->lfb = (x + bneed) - 2; + + /* count used blocks NOT bytes */ + b->used += y; + + return (void*)(x * b->bsize + (uintptr_t)&b[1]); + } + + /* x will be incremented by one ONCE more in our FOR loop */ + x += (y - 1); + continue; + } + } + } + } + + return 0; +} diff --git a/include/08.heap/heap07.c b/include/08.heap/heap07.c new file mode 100644 index 0000000..5686cd4 --- /dev/null +++ b/include/08.heap/heap07.c @@ -0,0 +1,32 @@ +void k_heapBMFree(KHEAPBM *heap, void *ptr) { + KHEAPBLOCKBM *b; + uintptr_t ptroff; + uint32_t bi, x; + uint8_t *bm; + uint8_t id; + uint32_t max; + + for (b = heap->fblock; b; b = b->next) { + if ((uintptr_t)ptr > (uintptr_t)b && (uintptr_t)ptr < (uintptr_t)b + sizeof(KHEAPBLOCKBM) + b->size) { + /* found block */ + ptroff = (uintptr_t)ptr - (uintptr_t)&b[1]; /* get offset to get block */ + /* block offset in BM */ + bi = ptroff / b->bsize; + /* .. */ + bm = (uint8_t*)&b[1]; + /* clear allocation */ + id = bm[bi]; + /* oddly.. GCC did not optimize this */ + max = b->size / b->bsize; + for (x = bi; bm[x] == id && x < max; ++x) { + bm[x] = 0; + } + /* update free block count */ + b->used -= x - bi; + return; + } + } + + /* this error needs to be raised or reported somehow */ + return; +} diff --git a/include/08.heap/heap08.c b/include/08.heap/heap08.c new file mode 100644 index 0000000..05cf132 --- /dev/null +++ b/include/08.heap/heap08.c @@ -0,0 +1,9 @@ +KHEAPBM kheap; +void kheapinit() +{ + k_heapBMInit(&kheap); +} +int kheapaddblock(uintptr_t addr,uint32_t size,uint32_t bsize) +{ + return k_heapBMAddBlock(&kheap,addr,size,bsize); +} diff --git a/include/08.heap/heap09.c b/include/08.heap/heap09.c new file mode 100644 index 0000000..6874578 --- /dev/null +++ b/include/08.heap/heap09.c @@ -0,0 +1,9 @@ +void *kmalloc(uint32_t size) +{ + return k_heapBMAlloc(&kheap,size); + +} +void kfree(void *ptr) +{ + k_heapBMFree(&kheap,ptr); +} -- cgit v1.2.3