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

#define NSAVED 67108864

#ifdef __x86_64__
#define STATE_INUSE 0x7b2067045ef8d8fc
#define STATE_SAVED 0x43585dd9567256fd
#define STATE_FREED 0x8e433e847e0aeec9
#define STATE_REALLOCED 0x37a916dbd277e9b
#endif

extern void *__libc_malloc(size_t);
extern void *__libc_free(void *);
extern void *__libc_realloc(void *, size_t);

struct header {
    size_t usz;
    uint64_t state;
};

static struct header *saved[NSAVED];
static size_t savehead, savetail;

void *malloc(size_t sz)
{
    struct header *hdr;

    hdr = __libc_malloc(sizeof(struct header) + sz);
    hdr->usz = sz;
    hdr->state = STATE_INUSE;
    return((void *)(hdr + 1));
}

void free(void *chunk)
{
    struct header *hdr;

    if(chunk == NULL)
    return;
    hdr = ((struct header *)chunk) - 1;
    if(hdr->state != STATE_INUSE)
    abort();
    if(hdr->usz < 128) {
    saved[savehead] = hdr;
    hdr->state = STATE_SAVED;
    savehead = (savehead + 1) % NSAVED;
    if(savehead == savetail) {
        if(saved[savetail]->state != STATE_SAVED)
        abort();
        saved[savetail]->state = STATE_FREED;
        __libc_free(saved[savetail]);
        savetail = (savetail + 1) % NSAVED;
    }
    } else {
    hdr->state = STATE_FREED;
    __libc_free(hdr);
    }
}

void *calloc(size_t n, size_t es)
{
    size_t sz;
    void *ret;

    sz = n * es;
    ret = malloc(sz);
    memset(ret, 0, sz);
    return(ret);
}

void *realloc(void *chunk, size_t nsz)
{
    struct header *hdr;

    if(chunk == NULL)
    return(malloc(nsz));
    hdr = ((struct header *)chunk) - 1;
    if(hdr->state != STATE_INUSE)
    abort();
    hdr->state = STATE_REALLOCED;
    hdr = __libc_realloc(hdr, sizeof(struct header) + nsz);
    hdr->usz = nsz;
    hdr->state = STATE_INUSE;
    return((void *)(hdr + 1));
}