#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
 
static char *start;
static const int head = sizeof(uintptr_t);
 
static void dump() {
    char *p, *last = (char *)sbrk(0), *next;
    for (p = start; p && p < last; p = next) {
        uintptr_t sz = *(uintptr_t *)p;
        next = p + head + (sz & ~1);
        printf("* %p, %p - %p: %s %d\n",
            p, p + head, next - 1, sz & 1 ? "used" : "free", sz & ~1);
    }
    printf("==%p\n", last);
}
 
void *mymalloc(uintptr_t size) {
    char *p, *last = (char *)sbrk(0), *next;
    if (!start) start = last;
    size = (size + head - 1) & ~(head - 1);
    for (p = start; p < last; p = next) {
        uintptr_t sz = *(uintptr_t *)p;
        next = p + head + (sz & ~1);
        if (!(sz & 1) && sz >= size) {
            if (sz > size)
                *(uintptr_t *)(p + head + size) = sz - size - head;
            break;
        }
    }
    if (p >= last) p = (char *)sbrk(head + size);
    *(uintptr_t *)p = size | 1;
    printf("mymalloc(%d) -> %p\n", size, p + head);
    dump();
    return p + head;
}
 
void myfree(void *ptr) {
    char *p, *last = (char *)sbrk(0), *next;
    uintptr_t *h;
    printf("myfree(%p)\n", ptr);
    if (!ptr || !start) return;
    h = (uintptr_t *)(((char *)ptr) - head);
    for (p = start; p < last; p = next) {
        uintptr_t sz = *(uintptr_t *)p;
        if (!(sz & 1) && p + head + sz == (char *)h) {
            sz += head + (*h & ~1);
            h = (uintptr_t *)p;
        }
        sz &= ~1;
        next = p + head + sz;
        if (p == (char *)h) {
            if (next < last) {
                int nextsz = *(uintptr_t *)next;
                if (!(nextsz & 1)) sz += head + nextsz;
            }
            if (p + head + sz >= last) brk(p); else *h = sz;
            dump();
            return;
        }
    }
}
 
int main(void) {
    void *p[4];
    dump();
    p[0] = mymalloc(8);
    p[1] = mymalloc(16);
    p[2] = mymalloc(8);
    myfree(p[1]);
    p[1] = mymalloc(8);
    p[3] = mymalloc(8);
    myfree(p[3]);
    myfree(p[1]);
    myfree(p[2]);
    myfree(p[0]);
    return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRpbnQuaD4KI2luY2x1ZGUgPHVuaXN0ZC5oPgoKc3RhdGljIGNoYXIgKnN0YXJ0OwpzdGF0aWMgY29uc3QgaW50IGhlYWQgPSBzaXplb2YodWludHB0cl90KTsKCnN0YXRpYyB2b2lkIGR1bXAoKSB7CiAgICBjaGFyICpwLCAqbGFzdCA9IChjaGFyICopc2JyaygwKSwgKm5leHQ7CiAgICBmb3IgKHAgPSBzdGFydDsgcCAmJiBwIDwgbGFzdDsgcCA9IG5leHQpIHsKICAgICAgICB1aW50cHRyX3Qgc3ogPSAqKHVpbnRwdHJfdCAqKXA7CiAgICAgICAgbmV4dCA9IHAgKyBoZWFkICsgKHN6ICYgfjEpOwogICAgICAgIHByaW50ZigiKiAlcCwgJXAgLSAlcDogJXMgJWRcbiIsCiAgICAgICAgICAgIHAsIHAgKyBoZWFkLCBuZXh0IC0gMSwgc3ogJiAxID8gInVzZWQiIDogImZyZWUiLCBzeiAmIH4xKTsKICAgIH0KICAgIHByaW50ZigiPT0lcFxuIiwgbGFzdCk7Cn0KCnZvaWQgKm15bWFsbG9jKHVpbnRwdHJfdCBzaXplKSB7CiAgICBjaGFyICpwLCAqbGFzdCA9IChjaGFyICopc2JyaygwKSwgKm5leHQ7CiAgICBpZiAoIXN0YXJ0KSBzdGFydCA9IGxhc3Q7CiAgICBzaXplID0gKHNpemUgKyBoZWFkIC0gMSkgJiB+KGhlYWQgLSAxKTsKICAgIGZvciAocCA9IHN0YXJ0OyBwIDwgbGFzdDsgcCA9IG5leHQpIHsKICAgICAgICB1aW50cHRyX3Qgc3ogPSAqKHVpbnRwdHJfdCAqKXA7CiAgICAgICAgbmV4dCA9IHAgKyBoZWFkICsgKHN6ICYgfjEpOwogICAgICAgIGlmICghKHN6ICYgMSkgJiYgc3ogPj0gc2l6ZSkgewogICAgICAgICAgICBpZiAoc3ogPiBzaXplKQogICAgICAgICAgICAgICAgKih1aW50cHRyX3QgKikocCArIGhlYWQgKyBzaXplKSA9IHN6IC0gc2l6ZSAtIGhlYWQ7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgIH0KICAgIGlmIChwID49IGxhc3QpIHAgPSAoY2hhciAqKXNicmsoaGVhZCArIHNpemUpOwogICAgKih1aW50cHRyX3QgKilwID0gc2l6ZSB8IDE7CiAgICBwcmludGYoIm15bWFsbG9jKCVkKSAtPiAlcFxuIiwgc2l6ZSwgcCArIGhlYWQpOwogICAgZHVtcCgpOwogICAgcmV0dXJuIHAgKyBoZWFkOwp9Cgp2b2lkIG15ZnJlZSh2b2lkICpwdHIpIHsKICAgIGNoYXIgKnAsICpsYXN0ID0gKGNoYXIgKilzYnJrKDApLCAqbmV4dDsKICAgIHVpbnRwdHJfdCAqaDsKICAgIHByaW50ZigibXlmcmVlKCVwKVxuIiwgcHRyKTsKICAgIGlmICghcHRyIHx8ICFzdGFydCkgcmV0dXJuOwogICAgaCA9ICh1aW50cHRyX3QgKikoKChjaGFyICopcHRyKSAtIGhlYWQpOwogICAgZm9yIChwID0gc3RhcnQ7IHAgPCBsYXN0OyBwID0gbmV4dCkgewogICAgICAgIHVpbnRwdHJfdCBzeiA9ICoodWludHB0cl90ICopcDsKICAgICAgICBpZiAoIShzeiAmIDEpICYmIHAgKyBoZWFkICsgc3ogPT0gKGNoYXIgKiloKSB7CiAgICAgICAgICAgIHN6ICs9IGhlYWQgKyAoKmggJiB+MSk7CiAgICAgICAgICAgIGggPSAodWludHB0cl90ICopcDsKICAgICAgICB9CiAgICAgICAgc3ogJj0gfjE7CiAgICAgICAgbmV4dCA9IHAgKyBoZWFkICsgc3o7CiAgICAgICAgaWYgKHAgPT0gKGNoYXIgKiloKSB7CiAgICAgICAgICAgIGlmIChuZXh0IDwgbGFzdCkgewogICAgICAgICAgICAgICAgaW50IG5leHRzeiA9ICoodWludHB0cl90ICopbmV4dDsKICAgICAgICAgICAgICAgIGlmICghKG5leHRzeiAmIDEpKSBzeiArPSBoZWFkICsgbmV4dHN6OwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmIChwICsgaGVhZCArIHN6ID49IGxhc3QpIGJyayhwKTsgZWxzZSAqaCA9IHN6OwogICAgICAgICAgICBkdW1wKCk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKHZvaWQpIHsKICAgIHZvaWQgKnBbNF07CiAgICBkdW1wKCk7CiAgICBwWzBdID0gbXltYWxsb2MoOCk7CiAgICBwWzFdID0gbXltYWxsb2MoMTYpOwogICAgcFsyXSA9IG15bWFsbG9jKDgpOwogICAgbXlmcmVlKHBbMV0pOwogICAgcFsxXSA9IG15bWFsbG9jKDgpOwogICAgcFszXSA9IG15bWFsbG9jKDgpOwogICAgbXlmcmVlKHBbM10pOwogICAgbXlmcmVlKHBbMV0pOwogICAgbXlmcmVlKHBbMl0pOwogICAgbXlmcmVlKHBbMF0pOwogICAgcmV0dXJuIDA7Cn0K