#include <stdint.h>
#include <unistd.h>
#include <string.h>

/*                 ┌──────────────────────────────────────────────────────────────────┐
   free list ─────┐|┌──┐┌────────────────────┐┌──────────────────────┐┌────┐┌────┐┌───┘
────────┬────────┬▼▼│┬─▼│┬────────┬────────┬─▼│─┬─────────┬────────┬─▼│─┬──▼│──┬─▼│─┬────────
....... │ In use |   |   | In use | In use |    | ....... | In use |    |      |    |
────────┴────────┴───┴───┴────────┴────────┴────┴─────────┴────────┴────┴──────┴────┴────────
┌────────┐                         ┌────────┐
|        |  Free, owned by malloc  | In use |  In use, owned by malloc
└────────┘                         └────────┘
┌────────┐
| ...... |  Not owned by malloc
└────────┘
*/

/* Header:
  ┌───────► (ptr) Points to next free block
┌─|─┬──────┬────────
│ ● | size |
└───┴──────┴▲───────
            └──── Address returned to user
*/

struct header {         /* Block header: */
  struct header *ptr;   /* Next block if on free list */
  uint64_t size;        /* Size of this block (in header units) */
};

typedef struct header Header;

static Header base;             /* Empty list to get started */
static Header *freep = NULL;    /* Start of free list */

void *my_malloc(uint64_t nbytes);
static Header *morecore(uint64_t nu);
void my_free(void *ap);

/* malloc: General-purpose storage allocator */
void *my_malloc(uint64_t nbytes)
{
  Header *p, *prevp;
  Header *morecore(uint64_t);
  uint64_t nunits;

  nunits = (nbytes + sizeof(Header) -1) / sizeof(Header) + 1;

  if ((prevp = freep) == NULL) {        /* No free list yet */
    base.ptr = freep = prevp = &base;
    base.size = 0;
  }

  for(p = prevp->ptr; ; prevp = p, p = p->ptr) {
    if (p->size >= nunits) {            /* Big enough */
      if (p->size == nunits)            /* Exactly */
        prevp->ptr = p->ptr;
      else {            /* Allocate tail end */
        p->size -= nunits;
        p += p->size;
        p->size = nunits;
      }
      freep = prevp;
      return (void *)(p+1);
    }
    if (p == freep)     /* Wrapped around free list */
      if ((p = morecore(nunits)) == NULL)
        return NULL;    /* None left */
  }
}

#define NALLOC  1024

/* morecore: Ask system for more memory */
static Header *morecore(uint64_t nu)
{
  char *cp;
  Header *up;

  if (nu < NALLOC)
    nu = NALLOC;
  cp = sbrk(nu * sizeof(Header));
  if (cp == (char *) -1)        /* No space at all. */
    return NULL;
  up = (Header *)cp;
  up->size = nu;
  my_free((void *)(up+1));
  return freep;
}

/* free: Put block ap in free list */
void my_free(void *ap)
{
  Header *bp, *p;

  bp = (Header *)ap - 1;                /* Point to block header */
  for(p = freep; !(bp > p && bp < p->ptr); p = p->ptr)
    if (p >= p->ptr && (bp > p || bp < p->ptr))
      break;    /* Freed block at start or end of arena */

  if (bp + bp->size == p->ptr) {        /* Join to upper nbr */
    bp->size += p->ptr->size;
    bp->ptr = p->ptr->ptr;
  } else
    bp->ptr = p->ptr;

  if (p + p->size == bp) {              /* Join to lower nbr */
    p->size += bp->size;
    p->ptr = bp->ptr;
  } else
    p->ptr = bp;

  freep = p;
}

#define min(a, b)	((a)<(b)?(a):(b))

void *my_realloc(void *ap, uint64_t nbytes)
{
  Header *oldp;
  Header *morecore(uint64_t);
  uint64_t nunits;
  void *new;

  oldp = (Header *)ap - 1;

  nunits = (nbytes + sizeof(Header) -1) / sizeof(Header) + 1;
  // Already the same "size".
  if (oldp->size == nunits) return ap;

  new = my_malloc(nbytes);
  memcpy(new, ap, min(sizeof(Header)*oldp->size, nbytes));
  my_free(ap);
  return new;
}

void *calloc(size_t nmemb, size_t size)
{
  void *ptr = my_malloc(nmemb * size);
  memset(ptr, 0, nmemb*size);
  return ptr;
}