#include <stdlib.h>
#include <stdio.h>

#define HASH_SIZE	131

/*This type defines a memory allocation*/
typedef struct mem_alloc
{
	/*The address of the pointer to the memory block*/
	void		*address;
	/*Number of bytes held by this allocation*/
	unsigned	size;
} memory_allocation;

/*This type defines a memory allocation node to be stored in the allocation table*/
typedef struct mem_alloc_node
{
	memory_allocation		allocation;
	struct mem_alloc_node	*next;
	struct mem_alloc_node	*pre;
} memory_allocation_node;

typedef struct memory_pool_bucket
{
	memory_allocation_node *head;
	memory_allocation_node *tail;
} bucket;

/*The memory pool*/
typedef bucket memory_pool[HASH_SIZE];

void *mcalloc(size_t nobj,size_t size,memory_pool *my_memory_pool);
void *mmalloc(size_t size,memory_pool *my_memory_pool);
void *mrealloc(void *p,size_t size,memory_pool *my_memory_pool);
void mfree(void *p);

/*Search for an allocation in memory pool*/
memory_allocation_node *search_allocation(void *p,memory_pool *my_memory_pool);

/*The memory pool is implemented as a chained hash table 
(the chaining is done with doubly linked lists)
Init all memory pool buckets to 'NULL'.*/
void		init_memory_pool(memory_pool *my_memory_pool);
/*Free all allocations stored in the memory pool*/
void		free_memory_pool(memory_pool *my_memory_pool,FILE *destination); 
/*Calculate the sum of all allocations in memory pool. Return the result in bytes.*/
unsigned	get_memory_pool_size(memory_pool *my_memory_pool);
/*Print memory pool*/
void		print_memory_pool(memory_pool *my_memory_pool,FILE *destination);
/*Add allocation to memory pool*/
void		add_allocation_to_memory_pool(memory_allocation_node *new_allocation
										  ,memory_pool *my_memory_pool);
/*Remove allocation from memory pool*/
void		remove_allocation_from_memory_pool(memory_allocation_node *the_allocation
											   ,memory_pool *my_memory_pool);

/*Robert Jenkins' 32 bit Mix Function with the following modification :
The returend value is the key calculated by the original function, modulo HASH_SIZE*/
unsigned int inthash(unsigned int key);

#include "memory_handling.h"

int main()
{
	int *p,*j,*k;
	memory_pool my_memory_pool;
	j = malloc(sizeof(int));
	init_memory_pool(&my_memory_pool);

	p = mmalloc(20,&my_memory_pool);
	j = mrealloc(p,25,&my_memory_pool);
	print_memory_pool(&my_memory_pool,stdout);
}

void *mmalloc(size_t size,memory_pool *my_memory_pool)
{
	void *result = NULL;
	/*Allocate memory*/
	result = malloc(size);
	if (result == NULL)
	{
		fprintf(stderr,"<malloc> Couldn't allocate memory.\n");
	}
	else
	{
		memory_allocation_node *new_allocation;
		new_allocation = malloc(sizeof(memory_allocation_node));
		/*If we can't allocate memory for memory pool allocation, 
		there will be a possible memory leak ! therefor, this is equal to 
		general memory allocation failure.*/
		if (new_allocation == NULL)
		{
			void *dummy = result;
			fprintf(stderr,"<malloc> Couldn't allocate memory.\n");
			free(dummy);
			result = NULL;
		}
		else
		{
			/*Memory allocation success. Add allocation to memory pool*/
			new_allocation->allocation.address = result;
			new_allocation->allocation.size = size;
			new_allocation->pre = NULL;
			add_allocation_to_memory_pool(new_allocation,my_memory_pool);
		}
	}
	return (result);
}

void *mcalloc(size_t nobj,size_t size,memory_pool *my_memory_pool)
{
	void *result = NULL;
	/*Allocate memory*/
	result = calloc(nobj,size);
	if (result == NULL)
	{
		fprintf(stderr,"<calloc> Couldn't allocate memory.\n");
	}
	else
	{
		memory_allocation_node *new_allocation;
		new_allocation = malloc(sizeof(memory_allocation_node));
		/*If we can't allocate memory for memory pool allocation, 
		there will be a possible memory leak ! therefor, this is equal to 
		general memory allocation failure.*/
		if (new_allocation == NULL)
		{
			void *dummy = result;
			fprintf(stderr,"<malloc> Couldn't allocate memory.\n");
			free(dummy);
			result = NULL;
		}
		else
		{
			/*Memory allocation success. Add allocation to memory pool*/
			new_allocation->allocation.address = result;
			new_allocation->allocation.size = nobj * size;
			new_allocation->pre = NULL;
			add_allocation_to_memory_pool(new_allocation,my_memory_pool);
		}
	}
	return (result);
}

void *mrealloc(void *p,size_t size,memory_pool *my_memory_pool)
{
	void *result;
	/*Allocate memory*/
	result = realloc(p,size);
	if (result == NULL)
	{
		fprintf(stderr,"<realloc> Couldn't (re)allocate memory.\n");
	}
	else
	{
		/*Create the new allocation*/
		memory_allocation_node *new_allocation;
		new_allocation = malloc(sizeof(memory_allocation_node));
		if (new_allocation == NULL)
		{
			fprintf(stderr,"<malloc> Couldn't allocate memory.\n");
			result = NULL;
		}
		else
		{
			memory_allocation_node *old_allocation;
			new_allocation->allocation.address = result;
			new_allocation->allocation.size = size;
			new_allocation->pre = NULL;
			/*Remove old allocation from memory pool*/
			old_allocation = search_allocation(p,my_memory_pool);
			if (old_allocation == NULL)
			{
				result = NULL;
			}
			else
			{
				remove_allocation_from_memory_pool(old_allocation,my_memory_pool);
				add_allocation_to_memory_pool(new_allocation,my_memory_pool);
			}
			
		}
	}
	return (result);
}

void		init_memory_pool(memory_pool *my_memory_pool)
{
	unsigned i;

	for (i = 0;i < HASH_SIZE;i++)
	{
		(*my_memory_pool)[i].head = NULL;
		(*my_memory_pool)[i].tail = NULL;
	}
}

void		free_memory_pool(memory_pool *my_memory_pool,FILE *destination)
{
	memory_allocation_node *iterator,*dummy;
	unsigned current_bucket;
	unsigned allocations_counter = 0;
	unsigned bytes_counter = 0;

	for (current_bucket = 0;current_bucket < HASH_SIZE;current_bucket++)
	{
		for (iterator = (*my_memory_pool)[current_bucket].head;iterator != NULL;iterator = dummy)
		{
			allocations_counter++;
			bytes_counter += iterator->allocation.size;
			
			dummy = iterator->next;
			fprintf(destination,"Releasing %-8u bytes starting from address 0x%X,memory pool bucket #%u\n",iterator->allocation.size,
					iterator->allocation.address,current_bucket);
			free(iterator);
		}
	}
	fprintf(destination,"Total allocations released : %u\n",allocations_counter);
	fprintf(destination,"Total bytes released : %u\n",bytes_counter);
	init_memory_pool(my_memory_pool);
}

unsigned	get_memory_pool_size(memory_pool *my_memory_pool)
{
	unsigned result = 0;
	unsigned i;
	memory_allocation_node *iterator;
	
	for (i = 0;i < HASH_SIZE; i++)
	{
		iterator = (*my_memory_pool)[i].head;
		while (iterator != NULL)
		{
			result += iterator->allocation.size;
			iterator = iterator->next;
		}
	}

	return (result);
}

void		print_memory_pool(memory_pool *my_memory_pool,FILE *destination)
{
	memory_allocation_node *iterator;
	unsigned current_bucket;
	for (current_bucket = 0;current_bucket < HASH_SIZE;current_bucket++)
	{
		fprintf(destination,"Bucket #%u\n",current_bucket);
		iterator = (*my_memory_pool)[current_bucket].head;
		while (iterator != NULL)
		{
			fprintf(destination,"Address :0x%.8X\tAllocation size :%u \tbytes\n",iterator->allocation.address,iterator->allocation.size);
			iterator = iterator->next;
		}
	}
}

void		add_allocation_to_memory_pool(memory_allocation_node *new_allocation
										  ,memory_pool *my_memory_pool)
{
	unsigned memory_pool_bucket;
	memory_pool_bucket = inthash((unsigned int)new_allocation->allocation.address);
	if ((*my_memory_pool)[memory_pool_bucket].head == NULL)
	{
		/*Insert memory allocation as the first allocation in the bucket*/
		new_allocation->next = NULL;
		(*my_memory_pool)[memory_pool_bucket].head = new_allocation;
		(*my_memory_pool)[memory_pool_bucket].tail = new_allocation;
	}
	else
	{
		/*Insert memory allocation at the head of the bucket*/
		new_allocation->next = (*my_memory_pool)[memory_pool_bucket].head;
		(*my_memory_pool)[memory_pool_bucket].head->pre = new_allocation;
		(*my_memory_pool)[memory_pool_bucket].head = new_allocation;
	}
}

void		remove_allocation_from_memory_pool(memory_allocation_node *the_allocation
											   ,memory_pool *my_memory_pool)
{
	bucket *the_list;
	unsigned bucket_index;
	bucket_index = inthash((unsigned int)the_allocation->allocation.address) % HASH_SIZE;
	the_list = my_memory_pool[bucket_index];
	if (the_allocation->next == NULL && the_allocation->pre == NULL)
	{
		the_list->head = NULL;
	}
	else if (the_allocation->next == NULL && the_allocation->pre != NULL)
	{
		the_allocation->pre->next = NULL;	
	}
	else if (the_allocation->next != NULL && the_allocation->pre == NULL)
	{
		the_allocation->next->pre = NULL;
		the_list->head = the_allocation->next;
	}
	else if (the_allocation->next != NULL && the_allocation->pre != NULL)
	{
		the_allocation->pre->next = the_allocation->next;
		the_allocation->next->pre = the_allocation->pre;
	}
}

memory_allocation_node *search_allocation(void *p,memory_pool *my_memory_pool)
{
	memory_allocation_node *result = NULL;
	memory_allocation_node *iterator;
	unsigned current_bucket;
	
	for (current_bucket = 0;(current_bucket < HASH_SIZE) && (result == NULL);current_bucket++)
	{
			iterator = (*my_memory_pool)[current_bucket].head;
			while ((iterator != NULL) && (result == NULL))
			{
				if (iterator->allocation.address == p)
				{
					result = iterator;
				}
				iterator = iterator->next;
			}
	}
	return (result);
}

unsigned int inthash(unsigned int key)
{
  key += (key << 12);
  key ^= (key >> 22);
  key += (key << 4);
  key ^= (key >> 9);
  key += (key << 10);
  key ^= (key >> 2);
  key += (key << 7);
  key ^= (key >> 12);
  return (key % HASH_SIZE);
}

void *mrealloc(void *p,size_t size,memory_pool *my_memory_pool)
{
.
.
.
  result = realloc(p,size); /* <<< Note 1 */
.
.
.
    new_allocation = malloc(sizeof(memory_allocation_node)); /* <<< Note 2 */
.
.
.
      old_allocation = search_allocation(p,my_memory_pool);
        remove_allocation_from_memory_pool(old_allocation,my_memory_pool); /* <<< Note 3 */
.
.
.
}