diff options
Diffstat (limited to 'include/08.heap')
37 files changed, 289 insertions, 147 deletions
diff --git a/include/08.heap/heap00.c b/include/08.heap/deo1 index c45e28b..c45e28b 100644 --- a/include/08.heap/heap00.c +++ b/include/08.heap/deo1 diff --git a/include/08.heap/deo10 b/include/08.heap/deo10 new file mode 100644 index 0000000..fd64ff9 --- /dev/null +++ b/include/08.heap/deo10 @@ -0,0 +1,5 @@ + /* reserve room for bitmap */ + bcnt = (bcnt / bsize) * bsize < bcnt ? bcnt / bsize + 1 : bcnt / bsize; + for (x = 0; x < bcnt; ++x) { + bm[x] = 5; + } diff --git a/include/08.heap/deo11 b/include/08.heap/deo11 new file mode 100644 index 0000000..a61193b --- /dev/null +++ b/include/08.heap/deo11 @@ -0,0 +1,4 @@ + b->lfb = bcnt - 1; + b->used = bcnt; + return 1; +} diff --git a/include/08.heap/deo12 b/include/08.heap/deo12 new file mode 100644 index 0000000..84c5721 --- /dev/null +++ b/include/08.heap/deo12 @@ -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/deo13 b/include/08.heap/deo13 new file mode 100644 index 0000000..369c3f3 --- /dev/null +++ b/include/08.heap/deo13 @@ -0,0 +1,7 @@ +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; diff --git a/include/08.heap/deo14 b/include/08.heap/deo14 new file mode 100644 index 0000000..8bfb6f0 --- /dev/null +++ b/include/08.heap/deo14 @@ -0,0 +1,4 @@ + /* iterate blocks */ + for (b = heap->fblock; b; b = b->next) { + /* check if block has enough room */ + if (b->size - (b->used * b->bsize) >= size) { diff --git a/include/08.heap/deo15 b/include/08.heap/deo15 new file mode 100644 index 0000000..a867821 --- /dev/null +++ b/include/08.heap/deo15 @@ -0,0 +1,3 @@ + bcnt = b->size / b->bsize; + bneed = (size / b->bsize) * b->bsize < size ? size / b->bsize + 1 : size / b->bsize; + bm = (uint8_t*)&b[1]; diff --git a/include/08.heap/deo16 b/include/08.heap/deo16 new file mode 100644 index 0000000..78f4675 --- /dev/null +++ b/include/08.heap/deo16 @@ -0,0 +1,5 @@ + for (x = (b->lfb + 1 >= bcnt ? 0 : b->lfb + 1); x != b->lfb; ++x) { + /* just wrap around */ + if (x >= bcnt) { + x = 0; + } diff --git a/include/08.heap/deo17 b/include/08.heap/deo17 new file mode 100644 index 0000000..d20be4c --- /dev/null +++ b/include/08.heap/deo17 @@ -0,0 +1,3 @@ + if (bm[x] == 0) { + /* count free blocks */ + for (y = 0; bm[x + y] == 0 && y < bneed && (x + y) < bcnt; ++y); diff --git a/include/08.heap/deo18 b/include/08.heap/deo18 new file mode 100644 index 0000000..fed8463 --- /dev/null +++ b/include/08.heap/deo18 @@ -0,0 +1,4 @@ + /* 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]); diff --git a/include/08.heap/deo19 b/include/08.heap/deo19 new file mode 100644 index 0000000..9b49484 --- /dev/null +++ b/include/08.heap/deo19 @@ -0,0 +1,4 @@ + /* allocate by setting id */ + for (z = 0; z < y; ++z) { + bm[x + z] = nid; + } diff --git a/include/08.heap/deo2 b/include/08.heap/deo2 new file mode 100644 index 0000000..2a69314 --- /dev/null +++ b/include/08.heap/deo2 @@ -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/deo20 b/include/08.heap/deo20 new file mode 100644 index 0000000..f141368 --- /dev/null +++ b/include/08.heap/deo20 @@ -0,0 +1,2 @@ + /* optimization */ + b->lfb = (x + bneed) - 2; diff --git a/include/08.heap/deo21 b/include/08.heap/deo21 new file mode 100644 index 0000000..8fd73e2 --- /dev/null +++ b/include/08.heap/deo21 @@ -0,0 +1,2 @@ + /* count used blocks NOT bytes */ + b->used += y; diff --git a/include/08.heap/deo22 b/include/08.heap/deo22 new file mode 100644 index 0000000..98c1157 --- /dev/null +++ b/include/08.heap/deo22 @@ -0,0 +1,2 @@ + return (void*)(x * b->bsize + (uintptr_t)&b[1]); + } diff --git a/include/08.heap/deo23 b/include/08.heap/deo23 new file mode 100644 index 0000000..21aa8c8 --- /dev/null +++ b/include/08.heap/deo23 @@ -0,0 +1,9 @@ + /* x will be incremented by one ONCE more in our FOR loop */ + x += (y - 1); + continue; + } + } + } + } + return 0; +} diff --git a/include/08.heap/deo24 b/include/08.heap/deo24 new file mode 100644 index 0000000..e9c116b --- /dev/null +++ b/include/08.heap/deo24 @@ -0,0 +1,7 @@ +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; diff --git a/include/08.heap/deo25 b/include/08.heap/deo25 new file mode 100644 index 0000000..1a22151 --- /dev/null +++ b/include/08.heap/deo25 @@ -0,0 +1,20 @@ + 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; + } + } diff --git a/include/08.heap/deo26 b/include/08.heap/deo26 new file mode 100644 index 0000000..11a4697 --- /dev/null +++ b/include/08.heap/deo26 @@ -0,0 +1,3 @@ + /* this error needs to be raised or reported somehow */ + return; +} diff --git a/include/08.heap/deo27 b/include/08.heap/deo27 new file mode 100644 index 0000000..6ac75a9 --- /dev/null +++ b/include/08.heap/deo27 @@ -0,0 +1 @@ +KHEAPBM kheap; diff --git a/include/08.heap/deo28 b/include/08.heap/deo28 new file mode 100644 index 0000000..6d7223d --- /dev/null +++ b/include/08.heap/deo28 @@ -0,0 +1,4 @@ +void kheapinit() +{ + k_heapBMInit(&kheap); +} diff --git a/include/08.heap/heap08.c b/include/08.heap/deo29 index 05cf132..de767a2 100644 --- a/include/08.heap/heap08.c +++ b/include/08.heap/deo29 @@ -1,8 +1,3 @@ -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/heap02.c b/include/08.heap/deo3 index e46dc38..d07786d 100644 --- a/include/08.heap/heap02.c +++ b/include/08.heap/deo3 @@ -1,3 +1,3 @@ typedef struct _KHEAPBM { - KHEAPBLOCKBM *fblock; + KHEAPBLOCKBM *fblock; } KHEAPBM; diff --git a/include/08.heap/heap09.c b/include/08.heap/deo30 index 6874578..22972f4 100644 --- a/include/08.heap/heap09.c +++ b/include/08.heap/deo30 @@ -1,9 +1,4 @@ void *kmalloc(uint32_t size) { return k_heapBMAlloc(&kheap,size); - -} -void kfree(void *ptr) -{ - k_heapBMFree(&kheap,ptr); } diff --git a/include/08.heap/deo31 b/include/08.heap/deo31 new file mode 100644 index 0000000..d4d5941 --- /dev/null +++ b/include/08.heap/deo31 @@ -0,0 +1,4 @@ +void kfree(void *ptr) +{ + k_heapBMFree(&kheap,ptr); +} diff --git a/include/08.heap/heap03.c b/include/08.heap/deo4 index 9e2fe89..c2dc3b5 100644 --- a/include/08.heap/heap03.c +++ b/include/08.heap/deo4 @@ -1,3 +1,3 @@ void k_heapBMInit(KHEAPBM *heap) { - heap->fblock = 0; + heap->fblock = 0; } diff --git a/include/08.heap/deo5 b/include/08.heap/deo5 new file mode 100644 index 0000000..8eda156 --- /dev/null +++ b/include/08.heap/deo5 @@ -0,0 +1,5 @@ +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; diff --git a/include/08.heap/deo6 b/include/08.heap/deo6 new file mode 100644 index 0000000..024a09a --- /dev/null +++ b/include/08.heap/deo6 @@ -0,0 +1,3 @@ + b = (KHEAPBLOCKBM*)addr; + b->size = size - sizeof(KHEAPBLOCKBM); + b->bsize = bsize; diff --git a/include/08.heap/deo7 b/include/08.heap/deo7 new file mode 100644 index 0000000..c816b2c --- /dev/null +++ b/include/08.heap/deo7 @@ -0,0 +1,2 @@ + b->next = heap->fblock; + heap->fblock = b; diff --git a/include/08.heap/deo8 b/include/08.heap/deo8 new file mode 100644 index 0000000..3a9ea03 --- /dev/null +++ b/include/08.heap/deo8 @@ -0,0 +1,2 @@ + bcnt = b->size / b->bsize; + bm = (uint8_t*)&b[1]; diff --git a/include/08.heap/deo9 b/include/08.heap/deo9 new file mode 100644 index 0000000..7183948 --- /dev/null +++ b/include/08.heap/deo9 @@ -0,0 +1,4 @@ + /* clear bitmap */ + for (x = 0; x < bcnt; ++x) { + bm[x] = 0; + } diff --git a/include/08.heap/heap.c b/include/08.heap/heap.c new file mode 100644 index 0000000..99d0a37 --- /dev/null +++ b/include/08.heap/heap.c @@ -0,0 +1,166 @@ +#include<types.h> + +typedef struct _KHEAPBLOCKBM { + struct _KHEAPBLOCKBM *next; + uint32_t size; + uint32_t used; + uint32_t bsize; + uint32_t lfb; +} KHEAPBLOCKBM; + +typedef struct _KHEAPBM { + KHEAPBLOCKBM *fblock; +} KHEAPBM; + +void k_heapBMInit(KHEAPBM *heap) { + heap->fblock = 0; +} + +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; +} + +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; +} + +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) { + /* 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]; + + 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; +} + +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; +} + +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); +} + +void *kmalloc(uint32_t size) +{ + return k_heapBMAlloc(&kheap,size); +} + +void kfree(void *ptr) +{ + k_heapBMFree(&kheap,ptr); +} diff --git a/include/08.heap/heap01.c b/include/08.heap/heap01.c deleted file mode 100644 index e7f4f84..0000000 --- a/include/08.heap/heap01.c +++ /dev/null @@ -1,7 +0,0 @@ -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/heap04.c b/include/08.heap/heap04.c deleted file mode 100644 index be39951..0000000 --- a/include/08.heap/heap04.c +++ /dev/null @@ -1,33 +0,0 @@ -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 deleted file mode 100644 index 1856ca5..0000000 --- a/include/08.heap/heap05.c +++ /dev/null @@ -1,5 +0,0 @@ -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 deleted file mode 100644 index 5ad2787..0000000 --- a/include/08.heap/heap06.c +++ /dev/null @@ -1,58 +0,0 @@ -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 deleted file mode 100644 index 5686cd4..0000000 --- a/include/08.heap/heap07.c +++ /dev/null @@ -1,32 +0,0 @@ -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; -} |