include <assert.h>
#include <stdio.h>
#include <stdbool.h>
#include <unistd.h>
#include <stdlib.h>

#define ALIGN4(s)       (((((s) - 1) >> 2) << 2) + 4)
#define BLOCK_DATA(b)    ((b))
#define BLOCK_HEADER(ptr) ((struct _block *)(ptr))

void *calloc(size_t nmemb, size_t size);
void *realloc(void *ptr, size_t size);

static int atexit_registered = 0;
static int num_mallocs    = 0;
static int num_frees       = 0;
static int num_reuses    = 0;
static int num_grows       = 0;
static int num_splits    = 0;
static int num_coalesces = 0;
static int num_blocks    = 0;
static int num_requested = 0;
static int max_heap       = 0;

struct _block *freeList = NULL; /* Free list to track the _blocks available */

struct _block
{
size_t size;       /* Size of the allocated _block of memory in bytes */
struct _block *prev; /* Pointer to the previous _block of allcated memory */
struct _block *next; /* Pointer to the next _block of allcated memory */
bool free;       /* Is this _block free?                   */
char padding[3];
};

/*
* \brief printStatistics
*
* \param none
*
* Prints the heap statistics upon process exit. Registered
* via atexit()
*
* \return none
*/
void printStatistics( void )
{

struct _block *curr = freeList;
num_blocks = 0;
max_heap = 0;
while (curr != NULL) {
   if(curr->free == true) {
   num_blocks++;
   }
// printf("Pointer:\t%p, size:\t%d, free:\t%d\n", curr,
   // curr->size, curr->free );
   max_heap += curr->size;
   curr = curr->next;
}

printf("\nheap management statistics\n");
printf("mallocs:\t%d\n", num_mallocs );
printf("frees:\t\t%d\n", num_frees );
printf("reuses:\t\t%d\n", num_reuses );
printf("grows:\t\t%d\n", num_grows );
printf("splits:\t\t%d\n", num_splits );
printf("coalesces:\t%d\n", num_coalesces );
printf("blocks:\t\t%d\n", num_blocks );
printf("requested:\t%d\n", num_requested );
printf("max heap:\t%d\n", max_heap );
}

/*
* \brief findFreeBlock
*
* \param last pointer to the linked list of free _blocks
* \param size size of the _block needed in bytes
*
* \return a _block that fits the request or NULL if no free _block matches
*
* \TODO Implement Next Fit
* \TODO Implement Best Fit
* \TODO Implement Worst Fit
*/
struct _block *findFreeBlock(struct _block **last, size_t size)
{
struct _block *curr = freeList;

#if defined FIT && FIT == 0
/* First fit */
while (curr && !(curr->free && curr->size >= size))
{
   *last = curr;
   curr = curr->next;
}
#endif

#if defined BEST && BEST == 0
size_t min_size = (size_t)-1;
struct _block *minBlock = NULL;
while (curr!= NULL)
{
   *last = curr;
   if(curr->free && curr->size >= size && curr->size < min_size) {
   min_size = curr->size;
   minBlock = curr;
   }
   curr = curr->next;
}
curr = minBlock;
#endif

#if defined WORST && WORST == 0
size_t max_size = 0;
struct _block *maxBlock = NULL;
while (curr !=NULL)
{
   *last = curr;
   if(curr->free && curr->size >= size && curr->size > max_size) {
   max_size = curr->size;
   maxBlock = curr;
   }
   curr = curr->next;
}
curr = maxBlock;
#endif

#if defined NEXT && NEXT == 0
curr = *last;
if(curr != NULL) {
curr = curr->next;
}
while (curr && !(curr->free && curr->size >= size))
{
   *last = curr;
   curr = curr->next

The Minix operating system uses a microkernel architectural approac...