オレオレallocとfree

main.c

#include <stdalign.h>
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>

char mem[1024];
void* last_pointer = mem;

typedef struct {
  uint8_t isUsing;
  uint32_t size;
} PointerInfo;

void* alloc(uint32_t size) {
  if (size == 0) return 0;

  PointerInfo* info = last_pointer;
  if (info->isUsing == 0) {
    // 空きが足りないなら後ろにある空きと統合
    if (info->size > 0 && size > info->size) {
      PointerInfo* nextInfo = last_pointer + sizeof(uint32_t) * 2 + info->size;

      while (1) {
          printf("-- find available pointer %p - %d\n", nextInfo, nextInfo->isUsing);
        if (nextInfo->isUsing == 0) {
          if (nextInfo->size == 0) break;

          printf("-- marge pointer %p to %p\n", nextInfo, last_pointer);

          // ポインタの空きを統合する
          info->size += nextInfo->size;
          printf("-- marged size: %d\n", info->size);

          nextInfo += sizeof(uint32_t) * 2 + nextInfo->size;
          nextInfo->size = 0;
          continue;
        }

        break;
      }

      // 統合しても足りないならエラー あとで前のポインタも統合できるように変更したい
      if (size > info->size) {
        return 0;
      }
    }

    info->isUsing = 1;
    void* res = last_pointer += sizeof(uint32_t) * 2;

    last_pointer += size;

    // 利用可能サイズより少なく使う場合は、空きポインタを２つに分割
    if (info->size > size) {
      ((uint32_t*)last_pointer)[1] = info->size - size;
    }

    info->size = size;

    return res;
  }

  return 0;
}

void free(void* p) {
  void* pointer = p - sizeof(uint32_t) * 2;
  last_pointer = pointer;

  // ポインタの利用状況を取る
  uint8_t* isUsing = (uint8_t*)pointer;
  if (*isUsing != 0) {
    *isUsing = 0;
    uint32_t* size = ((uint32_t*)pointer) + 1;

    // ポインタの内容を消す
    for (uint32_t i = 0; i < *size; i++) {
      ((char*)p)[i] = 0;
    }

    // 後ろに空きポインタがある場合は統合する
    void* next_pointer = p + *size;

    while (1) {
      printf("-- find available pointer %p - %u\n", next_pointer, ((uint8_t*)next_pointer)[0]);
      if (((uint8_t*)next_pointer)[0] == 0) {
        uint32_t* next_size = ((uint32_t*)next_pointer) + 1;
        if (*next_size == 0) break;

        printf("-- marge pointer %p to %p, size: %u\n", next_pointer, p, *next_size);
        // ポインタの空きを統合する
        *size += *next_size;
        printf("-- marged size: %u\n", *size);

        next_pointer += sizeof(uint32_t) * 2 + *next_size;
        *next_size = 0;
        continue;
      }

      break;
    }
  }
}

void printIntArray(char* name, int* arr, uint32_t len) {
  if (arr == 0) {
    printf("error: array %s is null!\n", name);
    return;
  }

  printf("name: %s, size: %dbyte, pos: %p\n", name, arr[-1] / (int)sizeof(int), arr);

  printf("content:\n");
  for (uint32_t i = 0; i < len; i++) {
    printf("  [%d]: %d\n", i, arr[i]);
  }
}

void assignIntArray(int* arr, uint32_t lne) {
  printf("assign: %p\n", arr);
  for (uint32_t i = 0; i < 4; i++) {
    printf("  [%d] <- %d\n", i, i * 2);
    arr[i] = i * 2;
  }
}

int main() {
  for (uint32_t i = 0; i < 1024; i++) {
    mem[i] = 0;
  }

  printf("mem root: %p\n", mem);

  int* arr1 = (void*)(alloc(sizeof(int) * 4));

  printIntArray("arr1", arr1, 4);
  assignIntArray(arr1, 4);

  printf("free: arr1\n");
  free(arr1);

  int* arr2 = (void*)(alloc(sizeof(int) * 2));

  printIntArray("arr2", arr2, 2);

  printf("\nassert: arr1 == arr2 is %d\n\n", arr1 == arr2);

  int* arr3 = (void*)(alloc(sizeof(int) * 2));

  printIntArray("arr3", arr3, 2);

  int* arr4 = (void*)(alloc(sizeof(int) * 2));

  printIntArray("arr4", arr4, 2);

  // 統合できるように開放する
  printf("free: arr3\n");
  free(arr3);
  printf("free: arr2\n");
  free(arr2);

  printf("free completed: arr2, arr3\n");

  int* arr5 = (void*)(alloc(sizeof(int) * 4));
  printIntArray("arr5", arr5, 2);

  printf("\nassert: arr5 == arr2 is %d\n\n", arr5 == arr2);


  return 0;
}