/*
 * Copyright (c) 2007 Teemu Voipio

Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to do
so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

******************************************************************************/


#undef __MALLOC_DEBUG__ // define this for tons of flood


/////////////////////////////////////////////////////////
/// COMPABILITY WRAPPERS, KLUDGES AND WHATEVER FOLLOW ///
/// ================================================= ///
#ifdef __KERNEL__ // YMMV, this works for VOIX

#include <library.h>
void * morecore(unsigned long);
#define printf printk

#else // otherwise just assume a normal POSIX environment

void exit(int status);
int puts(const char *s);
void panic(const char *s) { puts(s); exit(1); }

void * sbrk(unsigned);
void * morecore(unsigned long s) { return sbrk(s); }

int printf(const char *format, ...);

void *memset(void *s, int c, unsigned n);
void *memmove(void *d, const void *s, unsigned n);

#endif
/// END OF COMPABILITY WRAPPERS, KLUDGES and WHATEVER ///
/////////////////////////////////////////////////////////



// Size of block that malloc itself will alloc from OS.
//
//   large values -> less cpu overhead, more memory wastage
//
#define MALLOC_CORE_BLOCK 64*1024


// This info block is kept between any two blocks. It is the base of
// the whole strategy here, and allows moving in both directions.
//
// The two sizes are signed, as we use positive values for free blocks
// and negative values for in-use blocks. Zero means start/end of heap.
//
// The sizeof this struct must be a power of 2, for alignment to work.
//
struct malloc_info {
    signed sPrev; // size of the block before infoblock
    signed sNext; // size of the block after infoblock
};

#define MALLOC_ALIGN_BITS (sizeof(struct malloc_info)-1)
#define MALLOC_SIZE_ALIGN(_size) \
    (((_size)+MALLOC_ALIGN_BITS) & (~MALLOC_ALIGN_BITS))


static const int malloc_min_size = MALLOC_SIZE_ALIGN(1);

static struct malloc_info * malloc_heap_start = 0;
static int malloc_morecore_counter = 0;


static inline struct malloc_info * mi_next(struct malloc_info * mi) {
    return (struct malloc_info *)
        ( ((char*)mi)
        + (mi->sNext > 0 ? mi->sNext : -mi->sNext)
        + sizeof(struct malloc_info)
        );
}

static inline struct malloc_info * mi_prev(struct malloc_info * mi) {
    return (struct malloc_info *)
        ( ((char*)mi)
        - (mi->sPrev > 0 ? mi->sPrev : -mi->sPrev)
        - sizeof(struct malloc_info)
        );
}

void free(void * p) {
    
    if(!p) return; // ok to free NULL pointers :)
   
#ifdef __MALLOC_DEBUG__
    printf("[Free: ");
#endif
    
    // find info block just before the free'd block, and the block after
    struct malloc_info * ib = ((struct malloc_info*)p)-1;
    struct malloc_info * eb = mi_next(ib);

    if(ib->sNext > 0) panic("free: block doesn't look like it's allocated");
    if(ib->sNext != eb->sPrev) panic("free: heap corruption detected");

    // mark the block free
    eb->sPrev = ib->sNext = -ib->sNext;
    
    // coalesce forwards
    while(eb->sNext > 0) {
        ib->sNext = ib->sNext + eb->sNext + sizeof(struct malloc_info);
        eb = mi_next(ib);
        eb->sPrev = ib->sNext;
#ifdef __MALLOC_DEBUG__
        printf(">");
#endif
    }

    // coalesce backwards
    while(ib->sPrev > 0) {
        eb->sPrev = eb->sPrev + ib->sPrev + sizeof(struct malloc_info);
        ib = mi_prev(eb);
        ib->sNext = eb->sPrev;
#ifdef __MALLOC_DEBUG__
        printf("<");
#endif
    }
#ifdef __MALLOC_DEBUG__
    printf(" ]\n");
#endif

}


void * malloc(unsigned sz) {

    if(!sz) return 0; // NULL pointer for anyone requeting zero bytes
#ifdef __MALLOC_DEBUG__
    printf("[Malloc( %d ):", sz);
#endif
    signed size = MALLOC_SIZE_ALIGN(sz);

    // Check that we actually do have a heap
    if(!malloc_heap_start) {
        //
        // Do init
        //
#ifdef __MALLOC_DEBUG__
        printf("[init]");
#endif
        ++malloc_morecore_counter;

        malloc_heap_start = morecore(MALLOC_CORE_BLOCK);
        malloc_heap_start->sPrev = 0;
        malloc_heap_start->sNext = MALLOC_CORE_BLOCK - 2*sizeof(struct malloc_info);

        struct malloc_info * eb = mi_next(malloc_heap_start);

        eb->sPrev = malloc_heap_start->sNext;
        eb->sNext = 0;
    }

    struct malloc_info * ib = malloc_heap_start;

    // Loop until we have large enough block
    while(ib->sNext < size) {

        // have we reached end of heap?
        if(!ib->sNext) {
            ++malloc_morecore_counter;

#ifdef __MALLOC_DEBUG__
            printf("[growing heap to %d bytes]\n",
                    malloc_morecore_counter * MALLOC_CORE_BLOCK);
#endif
            struct malloc_info * nb = morecore(MALLOC_CORE_BLOCK);

            // adjust backwards to where the info block is already
            if(nb-1 != ib) {
                printf("[NB: %d, IB: %d]\n", nb, ib);
                panic("malloc: can't deal with non-continuous heap (yet?)");
            }

            // set initially to negative values
            ib->sNext = sizeof(struct malloc_info) - MALLOC_CORE_BLOCK;
            nb = mi_next(ib);
            nb->sPrev = ib->sNext;
            nb->sNext = 0;

            // then free the new block to get coalescing if possible
            free(ib+1);
            
            // finally, we know the new block can't be coalesced forward
            // so get the pointer from the end in case we coalesced back
            ib = mi_prev(nb);
        } else {
            ib = mi_next(ib);
        }
    }

    // Check if block is large enough that we can split it
    if((ib->sNext - size - (signed)sizeof(struct malloc_info)) > malloc_min_size) {

#ifdef __MALLOC_DEBUG__
        printf("[split( %d,%d )]", size, ib->sNext);
#endif
        
        // Get pointer to the ending info block
        struct malloc_info * eb = mi_next(ib);

        // Mark new size
        ib->sNext = size;

        // Get pointer to the info block in the middle of the split
        struct malloc_info * mb = mi_next(ib);
        
        // Fix the values in middle and ender block
        mb->sPrev = ib->sNext;
        eb->sPrev = mb->sNext = eb->sPrev - size - sizeof(struct malloc_info);
    }

    // Finally mark the block as allocated and return
    struct malloc_info * eb = mi_next(ib);
    eb->sPrev = ib->sNext = -ib->sNext;
#ifdef __MALLOC_DEBUG__
    printf("]\n");
#endif

    return (void*) (ib+1); // +1 skips the info block just fine

}

void *calloc(unsigned nmemb, unsigned size) {
    void * block = malloc(nmemb * size);
    memset(block, 0, nmemb * size);
    return block;
}

void * realloc(void * p, unsigned sz) {

    if(!sz) { free(p); return 0; }
    if(!p) return malloc(sz);

    signed size = sz;
    struct malloc_info * ib = ((struct malloc_info *)p)-1;

    // this looks weird but allocated blocks size is negative so..
    if(size + ib->sNext > 0) {

        void * newblock = malloc(size);
        memmove(newblock, p, -ib->sNext);

        free(p);
        p = newblock;
    }

    return p;
}


// vim: syntax=c sw=4 expandtab