malloc/free

自分用

```c
// followings are usually applied in other include files.
#if 1
// #include <stdint.h>
typedef unsigned char uint8_t;
typedef unsigned long int uintptr_t;

// #include <stddef.h>
#define NULL (void*)0
typedef unsigned int size_t;

// #include <assert.h>
static void assert(int condition) {
    while(!(condition));
}
#endif


#define HEAP_SIZE (1024 * 2)
#define MAX_ALLOC_SIZE 0xffff
#define ALIGN(p, s) \
    (((p) % (s)) ? (p) + (s) - ((p) % (s)) : (p))

#define USE(p) (*(uint8_t*)(p) |= 1)
#define UNUSE(p) (*(uint8_t*)(p) &= 0xfe)
#define USED(p) (*(uint8_t*)(p) & 1)
#define GE(p, s) (((uintptr_t)((heap_t*)(p))->end - (uintptr_t)((heap_t*)(p))->start) >= s)

typedef struct str_heap
{
    uint8_t *end;
    uint8_t *bef;
    uint8_t start[];
} heap_t;

static uint8_t heap[HEAP_SIZE];

void heap_init(void)
{
    heap_t *p = (heap_t*) heap;
    p->bef = NULL;
    p->end = &heap[HEAP_SIZE];
    UNUSE(p);
}

void* heap_malloc(size_t _size)
{
    heap_t *p, *p2;
    size_t size;

    size = ALIGN(_size, sizeof(uint8_t*));
    if (!size)
        return NULL;
    if (size > MAX_ALLOC_SIZE)
        return NULL;

    p = (heap_t*) heap;
    while (heap <= (uint8_t*) p && p <= (heap_t*) &heap[HEAP_SIZE])
    {
        if (USED(p))
            goto next;
        if (!GE(p, size))
            goto next;
        p2 = (heap_t*) &p->start[size];
        if ((p->end < heap) || (p->end > &heap[HEAP_SIZE]))
        {
            assert(0);
        }
        if ((p->end - p->start - size) > sizeof(heap_t))
        {
            p2->end = p->end;
            p2->bef = (uint8_t*) p;
            p->end = (uint8_t*) p2;
        }
        USE(p);
        return p->start;

        next: p = (heap_t*) p->end;
        p = (heap_t*) ((((uintptr_t) p) >> 1) << 1);
        if (p < (heap_t*) heap || p > (heap_t*) &heap[HEAP_SIZE])
        {
            assert(0);
        }
    }
    return NULL;
}

void heap_free(void *buf)
{
    heap_t *p;

    if (buf == NULL)
    {
        return;
    }
    p = (heap_t*) ((uint8_t*) buf - (uint8_t*) ((heap_t*) 0)->start);
    if (!USED(p))
    {
        return;
    }

    UNUSE(p);
    if ((heap < p->end) && (p->end < &heap[HEAP_SIZE]) && !USED((heap_t* )p->end))
    {
        p->end = ((heap_t*) p->end)->end;
    }
    if (p->end < heap || &heap[HEAP_SIZE] < p->end)
    {
        assert(0);
    }

    if ((heap < (uint8_t*) p) && (p <= (heap_t*) &heap[HEAP_SIZE]) && !USED((heap_t* )(p->bef)))
    {
        ((heap_t*) p->bef)->end = p->end;
    }
}

```

<details><summary>ライブラリのテスト</summary>

```c
#ifndef __HEAP_MEMORY_H__
#define __HEAP_MEMORY_H__

#define HEAP_SIZE (1024 * 1024 * 4)
void heap_init(void);
void* heap_malloc(size_t size);
void heap_free(void *buf);

#endif
```

```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


int main(void) {
    int i, j;
    size_t size;
    int offset;
    void *p; 
#define LOOP 10000
    void *p2[LOOP] = {NULL};

// テスト用にメモリを汚す
    srand(time(NULL));
    for(i=0;i<HEAP_SIZE;i++) {
        heap[i] = (rand() % 0x100);
    }   

    heap_init();

// LOOP 回数テスト
    for(i=0;i<LOOP;i++) {
        if (rand() % 2) {
            size = rand() % 0x100;
            p = heap_malloc(size);
            if (p == NULL ) { 
                printf("malloc error NULL\n");
                continue;
            }
            for (j=0;j<LOOP;j++){
                if (!p2[j]) {
                    p2[j] = p;
                    break;
                }
            }
        } else {
            offset = rand() % LOOP;
            for (j=0;j<LOOP;j++) {
                if (p2[(offset + j) % LOOP]) {
                    heap_free(p2[(offset + j) % LOOP]);
                    p2[(offset + j) % LOOP] = NULL;
                    break;
                }
            }
        }
    }   
    printf("test done\n");
    return 0;
}

```
</details>