#include <stdlib.h>

#include <stdio.h>

#define TRUE 1
#define FALSE 0

struct block_s {
    struct block_s *next;
    struct block_s *prev;
    char obj;
};

struct block_pool {
	size_t nblocks;
	void *pool;
	struct block_s *free_pool;
	struct block_s *busy_pool;
};

/*
 * инициализация пула
 */
void pool_init(struct block_pool *bp, size_t nblocks, size_t block_size)
{
	size_t i;

	bp->nblocks = nblocks;

	block_size += 2 * sizeof(struct block_s *);

	bp->pool = (struct block_s *)malloc(nblocks * block_size);

	void *p = bp->pool + block_size,
	     *pmax = p + (nblocks - 2) * block_size;

	for ( ; p < pmax; p += block_size) {
		((struct block_s *)p)->prev = (struct block_s *)(p - block_size);
		((struct block_s *)p)->next = (struct block_s *)(p + block_size);
	}

	((struct block_s *)bp->pool)->prev = NULL;
	((struct block_s *)bp->pool)->next = (struct block_s *)(bp->pool + block_size);

	((struct block_s *)(bp->pool + (nblocks - 1) * block_size))->prev =
		(struct block_s *)(bp->pool + (nblocks - 2) * block_size);
	((struct block_s *)(bp->pool + (nblocks - 1) * block_size))->next = NULL;

	bp->free_pool = (struct block_s *)bp->pool;
	bp->busy_pool = NULL;
}

/*
 * уничтожение пула
 */
void pool_destroy(struct block_pool *bp)
{
	free(bp->pool);
	bp->nblocks = 0;
	bp->pool = bp->free_pool = bp->busy_pool = NULL;
}

/*
 * выдача блока из пула
 */
void *pool_alloc(struct block_pool *bp)
{
	if (!bp->free_pool)
		return NULL;

	bp->free_pool->prev = bp->free_pool->next; // save free_pool->next in free_pool->prev
	
	bp->free_pool->next = bp->busy_pool;

	if (bp->busy_pool)
		bp->busy_pool->prev = bp->free_pool;

	bp->busy_pool = bp->free_pool;

	bp->free_pool = bp->free_pool->prev;
	
	bp->busy_pool->prev = NULL; // saved in free_pool->prev to NULL

	return &bp->busy_pool->obj;
}

/*
 * возвращение блока в пул
 */
void pool_free(struct block_pool *bp, void *p)
{
	if (!p)
		return;

	struct block_s *b1 = (struct block_s *)(p - 2 * sizeof(struct block_s *)),
		       *b2 = b1->next;

	if (b1->prev)
		b1->prev->next = b2;
	if (b2)
		b2->prev = b1->prev;

	if (bp->free_pool) {
		b1->next = bp->free_pool;
		bp->free_pool->prev = b1;
	}
	else
		b1->next = NULL;

	bp->free_pool = b2;

	if (bp->busy_pool == b1)
		bp->busy_pool = b2;
}


struct object_s {
    char val;
};

int main()
{
	unsigned long long i;

	struct block_pool bp;

	size_t nblocks = 0xffffff;

	pool_init(&bp, nblocks, sizeof(struct object_s));
	
	void **mem = malloc(nblocks * sizeof(void *));
	
	for (i = 0; i < nblocks; i++)
		if (!(mem[i] = pool_alloc(&bp))) {
			printf("не удалось выделить память под %lld блок\n", i);
			break;
		}

	for (i = 0; i < nblocks; i++)
		pool_free(&bp, mem[i]);

	free(mem);

	pool_destroy(&bp);

	return 0;
}

