/*Реализовать набор из следующих функций и показать их работоспособность:
- void* myMalloc(size_t size) – аналог функции malloc;
- void myFree(void* ptr) – аналог функции free;
- void* myRealloc(void* ptr, size_t size) – аналог функции realloc;
- void init() – вспомогательная функция, инициализирующая необходимые структуры данных;
В функции init() происходит выделение большой области динамической памяти штатными средствами.
Выделение памяти в реализуемых функциях должно происходить в этой области.
За пределами функции init() нельзя использовать функции malloc, realloc и free.*/

/* менеджер памяти создать
Который пользователю по запросам отдаёт память, потом освобождает
Если надо увеличивает/уменьшает длину */

/* идея: есть массив байтов из которого мы будем выделять по нужде байты. # сделано
Есть массив "контроля" в 4 раза меньше # сделано
В нём каждая ячейка отвечает 4 ячейкам исходного массива # сделано
И говорит, сколько блоков справа от этого заняты (включая текущий) # сделано
В функции free будет происходит обнуление блоков и потом проверка не надо ли сдвинуть налево что-нибудь # сделано
В функции realloc будет происходить сдвиг налево если там есть место
И сдвиг всего, что не даёт влезать области, направо
В функции malloc происходит выделение самой левой памяти
При этом во всех случаях считается, что справа уже всё так как и должно быть */

/*проблемы
проверить на +/- 1
проверить логику
с указателями разобраться. Правильно ли я ссылаюсь по массивам
ускорить поиск, за счёт того, что у меня хранится в buferstat, вместо +1 делать +buferstat[ptr]
Где вопросы, там я не уверен
Ещё что-нибудь
*/

//#include "manager.h"
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define ull unsigned long long
#define uc unsigned char
#define max(x, y) x > y ? x : y
#define min(x, y) x < y ? x : y

char* memory_block;
char* buferstat;
ull size_using_memory, memory_size = 16;
ull first_adress, last_adress;
ull control_block_size;

ull find_size(ull index_block)
{
	char prev_size = buferstat[index_block];
	ull curr_block = index_block + 1;
	char size = buferstat[curr_block];
	ull i = 0;
	while (size == prev_size && size == 255)
	{
		prev_size = buferstat[curr_block];
		curr_block++;
		size = buferstat[curr_block];
		i++;
	}
	return i + prev_size;
}

void my_free(void* ptr)
{
	ull first_byte = (ull)((ull)ptr - first_adress);
	ull curr_block = first_byte / 4;
	ull size_deleted_block = find_size(curr_block);
	ull i = 0;
	for (i; i < size_deleted_block; i++)
		buferstat[curr_block + i] = 0;
	curr_block += i;
	return;
}

void* my_malloc(size_t size)
{
	ull right_size = ((ull)size + 3) / 4 * 4;
	ull remaining_blocks = right_size / 4;
	ull first_free_block = 0;
	while (first_free_block != control_block_size)
	{
		if (buferstat[first_free_block] == 0)
		{
			ull available_size = 4;
			ull curr_block = first_free_block + 1;
			while (buferstat[curr_block] == 0 && available_size < right_size && curr_block != control_block_size)
			{
				available_size += 4;
				curr_block++;
			}
			if (curr_block == control_block_size && available_size < right_size)
				return NULL;
			if (available_size < right_size)
			{
				continue;
				first_free_block = curr_block;
			}
			curr_block = 0;
			while (remaining_blocks != 0)
			{
				buferstat[first_free_block + curr_block] = min(remaining_blocks, 255);
				remaining_blocks--;
				curr_block++;
			}
			return (void*)&memory_block[first_free_block * 4];
		}
		first_free_block++;
	}
}

void* my_realloc(void* ptr, size_t size)
{
	if (size == 0)
	{
		my_free(ptr);
		return;
	}
	if (ptr == NULL)
		return my_malloc(size);
	size_t remaining_size_in_blocks = size / 4;
	ull first_byte = (ull)((ull)ptr - first_adress);
	ull relocate_block = first_byte / 4;
	ull first_free_block = relocate_block - 1;
	while (buferstat[first_free_block] == 0 && first_free_block > -1)
		first_free_block--;
	first_free_block++;
	ull i = 0;
	ull size_relocate_block = find_size(relocate_block);
	ull curr_block = 0;
	while (buferstat[relocate_block + size_relocate_block + curr_block] == 0 && relocate_block + size_relocate_block + curr_block != control_block_size)
		curr_block++;
	ull available_size = size_relocate_block * 4 + (relocate_block - first_free_block) * 4 + curr_block * 4;
	int* pointer;
	if (size <= available_size)
	{
		pointer = &memory_block[first_free_block * 4];
		while (remaining_size_in_blocks != 0)
		{
			buferstat[first_free_block] = min(remaining_size_in_blocks, 255);
			remaining_size_in_blocks--;
			for (char j = 0; j < 4; j++)
				memory_block[first_free_block * 4 + j] = memory_block[relocate_block * 4 + j];
			buferstat[relocate_block] = 0;
			relocate_block++;
			first_free_block++;
			i++;
		}
		while (i < relocate_block + size_relocate_block)
		{
			buferstat[i] = 0;
			i++;
		}
	}
	else
	{
		curr_block = relocate_block + size_relocate_block; // +- 1?
		ull last_busy = 0;
		ull available_size_after_last_busy = 0;
		while (buferstat[curr_block] != 0)
			curr_block++;
		curr_block--;
		if (curr_block == relocate_block + size_relocate_block - 1)
			curr_block = 0;
		last_busy = curr_block;
		curr_block++;
		while (curr_block != control_block_size)
		{
			available_size_after_last_busy += 4;
			curr_block++;
		}
		if (available_size_after_last_busy < size)
			return NULL;
		curr_block = 0;
		pointer = &memory_block[(last_busy + 1) * 4];
		while (remaining_size_in_blocks != 0)
		{
			for (char j = 0; j < 4; j++)
				memory_block[(last_busy + curr_block + 1) * 4 + j] = memory_block[(relocate_block + curr_block) * 4 + j];
			buferstat[last_busy + curr_block] = buferstat[relocate_block + curr_block];
			remaining_size_in_blocks--;
			curr_block++;
		}
		my_free((void*)(&memory_block[relocate_block * 4]));
	}
	return (void*)pointer;
}

void init()
{
	memory_size = ((memory_size + 3) / 4) * 4;
	memory_block = (char*)malloc(sizeof(char) * memory_size);
	first_adress = memory_block;
	control_block_size = memory_size / 4;
	buferstat = (uc*)calloc(control_block_size, sizeof(uc));
	size_using_memory = memory_size;
}

int main()
{
	init();
	int amount = 2;
	int* number;
	printf("%d\n", sizeof(int) * amount);
	number = (int*)my_malloc(sizeof(int) * amount);
	if (number == NULL)
	{
		printf("NULL1");
		return 0;
	}
	number[0] = 1;
	number[1] = 2;
	printf("%d %d\n", number[0], number[1]);
	printf("QQ1\n");
	my_free(number);
	amount--;
	int* number2;
	printf("QQ2\n");
	number = my_realloc(NULL, sizeof(int) * amount);
	printf("QQ3\n");
	number2 = (int*)my_malloc(sizeof(int) * amount);
	printf("QQ4\n");
	if (number == NULL)
	{
		printf("NULL2");
		return 0;
	}
	if (number2 == NULL)
	{
		printf("NULL3");
		return 0;
	}
	number[0] = 1;
	number2[0] = 10;
	printf("%d %d\n", number[0], number2[0]);
	printf("%d %d\n", number, number2);
	amount++;
	number = my_realloc(number, sizeof(int) * amount);
	number[1] = 2;
	printf("%d %d %d\n", number[0], number[1], number2[0]);
	return 0;
}