/*
 * realloc.c
 */

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

#include "malloc.h"

void *realloc(void *ptr, size_t size)
{
    struct free_arena_header *ah, *nah;
    void *newptr;
    size_t newsize, oldsize, xsize;

    if (!ptr)
	return malloc(size);

    if (size == 0) {
	free(ptr);
	return NULL;
    }

    ah = (struct free_arena_header *)
	((struct arena_header *)ptr - 1);

    /* Actual size of the old block */
    oldsize = ah->a.size;

    /* Add the obligatory arena header, and round up */
    newsize = (size + 2 * sizeof(struct arena_header) - 1) & ARENA_SIZE_MASK;

    if (oldsize >= newsize && newsize >= (oldsize >> 2) &&
	oldsize - newsize < 4096) {
	/* This allocation is close enough already. */
	return ptr;
    } else {
	xsize = oldsize;

	nah = ah->a.next;
	if ((char *)nah == (char *)ah + ah->a.size &&
	    nah->a.type == ARENA_TYPE_FREE &&
	    oldsize + nah->a.size >= newsize) {
	    /* Merge in subsequent free block */
	    ah->a.next = nah->a.next;
	    ah->a.next->a.prev = ah;
	    nah->next_free->prev_free = nah->prev_free;
	    nah->prev_free->next_free = nah->next_free;
	    xsize = (ah->a.size += nah->a.size);
	}

	if (xsize >= newsize) {
	    /* We can reallocate in place */
	    if (xsize >= newsize + 2 * sizeof(struct arena_header)) {
		/* Residual free block at end */
		nah = (struct free_arena_header *)((char *)ah + newsize);
		nah->a.type = ARENA_TYPE_FREE;
		nah->a.size = xsize - newsize;
		ah->a.size = newsize;

		/* Insert into block list */
		nah->a.next = ah->a.next;
		ah->a.next = nah;
		nah->a.next->a.prev = nah;
		nah->a.prev = ah;

		/* Insert into free list */
		if (newsize > oldsize) {
		    /* Hack: this free block is in the path of a memory object
		       which has already been grown at least once.  As such, put
		       it at the *end* of the freelist instead of the beginning;
		       trying to save it for future realloc()s of the same block. */
		    nah->prev_free = __malloc_head.prev_free;
		    nah->next_free = &__malloc_head;
		    __malloc_head.prev_free = nah;
		    nah->prev_free->next_free = nah;
		} else {
		    nah->next_free = __malloc_head.next_free;
		    nah->prev_free = &__malloc_head;
		    __malloc_head.next_free = nah;
		    nah->next_free->prev_free = nah;
		}
	    }
	    /* otherwise, use up the whole block */
	    return ptr;
	} else {
	    /* Last resort: need to allocate a new block and copy */
	    oldsize -= sizeof(struct arena_header);
	    newptr = malloc(size);
	    if (newptr) {
		memcpy(newptr, ptr, min(size, oldsize));
		free(ptr);
	    }
	    return newptr;
	}
    }
}