/*
 * Copyright 2006 The Android Open Source Project
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "SkChunkAlloc.h"

// Don't malloc any chunks smaller than this
#define MIN_CHUNKALLOC_BLOCK_SIZE   1024

// Return the new min blocksize given the current value
static size_t increase_next_size(size_t size) {
    return size + (size >> 1);
}

///////////////////////////////////////////////////////////////////////////////

struct SkChunkAlloc::Block {
    Block*  fNext;
    size_t  fFreeSize;
    char*   fFreePtr;
    // data[] follows

    size_t blockSize() { 
        char* start = this->startOfData();
        size_t bytes = fFreePtr - start;
        return fFreeSize + bytes;
    }

    void reset() {
        fNext = NULL;
        fFreeSize = this->blockSize();
        fFreePtr = this->startOfData();
    }

    char* startOfData() {
        return reinterpret_cast<char*>(this + 1);
    }

    static void FreeChain(Block* block) {
        while (block) {
            Block* next = block->fNext;
            sk_free(block);
            block = next;
        }
    };

    bool contains(const void* addr) const {
        const char* ptr = reinterpret_cast<const char*>(addr);
        return ptr >= (const char*)(this + 1) && ptr < fFreePtr;
    }
};

///////////////////////////////////////////////////////////////////////////////

SkChunkAlloc::SkChunkAlloc(size_t minSize) {
    if (minSize < MIN_CHUNKALLOC_BLOCK_SIZE) {
        minSize = MIN_CHUNKALLOC_BLOCK_SIZE;
    }

    fBlock = NULL;
    fMinSize = minSize;
    fChunkSize = fMinSize;
    fTotalCapacity = 0;
    fTotalUsed = 0;
    SkDEBUGCODE(fTotalLost = 0;)
    SkDEBUGCODE(fBlockCount = 0;)
}

SkChunkAlloc::~SkChunkAlloc() {
    this->reset();
}

void SkChunkAlloc::reset() {
    Block::FreeChain(fBlock);
    fBlock = NULL;
    fChunkSize = fMinSize;  // reset to our initial minSize
    fTotalCapacity = 0;
    fTotalUsed = 0;
    SkDEBUGCODE(fTotalLost = 0;)
    SkDEBUGCODE(fBlockCount = 0;)
}

void SkChunkAlloc::rewind() {
    SkDEBUGCODE(this->validate();)

    Block* largest = fBlock;

    if (largest) {
        Block* next;
        for (Block* cur = largest->fNext; cur; cur = next) {
            next = cur->fNext;
            if (cur->blockSize() > largest->blockSize()) {
                sk_free(largest);
                largest = cur;
            } else {
                sk_free(cur);
            }
        }

        largest->reset();
        fTotalCapacity = largest->blockSize();
        SkDEBUGCODE(fBlockCount = 1;)
    } else {
        fTotalCapacity = 0;
        SkDEBUGCODE(fBlockCount = 0;)
    }

    fBlock = largest;
    fChunkSize = fMinSize;  // reset to our initial minSize
    fTotalUsed = 0;
    SkDEBUGCODE(fTotalLost = 0;)
    SkDEBUGCODE(this->validate();)
}

SkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) {
    size_t size = bytes;
    if (size < fChunkSize) {
        size = fChunkSize;
    }

    Block* block = (Block*)sk_malloc_flags(sizeof(Block) + size,
                        ftype == kThrow_AllocFailType ? SK_MALLOC_THROW : 0);

    if (block) {
        block->fFreeSize = size;
        block->fFreePtr = block->startOfData();

        fTotalCapacity += size;
        SkDEBUGCODE(fBlockCount += 1;)

        fChunkSize = increase_next_size(fChunkSize);
    }
    return block;
}

SkChunkAlloc::Block* SkChunkAlloc::addBlockIfNecessary(size_t bytes, AllocFailType ftype) {
    SkASSERT(SkIsAlign4(bytes));

    if (!fBlock || bytes > fBlock->fFreeSize) {
        Block* block = this->newBlock(bytes, ftype);
        if (!block) {
            return NULL;
        }
#ifdef SK_DEBUG
        if (fBlock) {
            fTotalLost += fBlock->fFreeSize;
        }
#endif
        block->fNext = fBlock;
        fBlock = block;
    }

    SkASSERT(fBlock && bytes <= fBlock->fFreeSize);
    return fBlock;
}

void* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) {
    SkDEBUGCODE(this->validate();)

    bytes = SkAlign4(bytes);

    Block* block = this->addBlockIfNecessary(bytes, ftype);
    if (!block) {
        return NULL;
    }

    char* ptr = block->fFreePtr;

    fTotalUsed += bytes;
    block->fFreeSize -= bytes;
    block->fFreePtr = ptr + bytes;
    SkDEBUGCODE(this->validate();)
    return ptr;
}

size_t SkChunkAlloc::unalloc(void* ptr) {
    SkDEBUGCODE(this->validate();)

    size_t bytes = 0;
    Block* block = fBlock;
    if (block) {
        char* cPtr = reinterpret_cast<char*>(ptr);
        char* start = block->startOfData();
        if (start <= cPtr && cPtr < block->fFreePtr) {
            bytes = block->fFreePtr - cPtr;
            fTotalUsed -= bytes;
            block->fFreeSize += bytes;
            block->fFreePtr = cPtr;
        }
    }
    SkDEBUGCODE(this->validate();)
    return bytes;
}

bool SkChunkAlloc::contains(const void* addr) const {
    const Block* block = fBlock;
    while (block) {
        if (block->contains(addr)) {
            return true;
        }
        block = block->fNext;
    }
    return false;
}

#ifdef SK_DEBUG
void SkChunkAlloc::validate() {
    int numBlocks = 0;
    size_t totCapacity = 0;
    size_t totUsed = 0;
    size_t totLost = 0;
    size_t totAvailable = 0;

    for (Block* temp = fBlock; temp; temp = temp->fNext) {
        ++numBlocks;
        totCapacity += temp->blockSize();
        totUsed += temp->fFreePtr - temp->startOfData();
        if (temp == fBlock) {
            totAvailable += temp->fFreeSize;
        } else {
            totLost += temp->fFreeSize;
        }
    }

    SkASSERT(fBlockCount == numBlocks);
    SkASSERT(fTotalCapacity == totCapacity);
    SkASSERT(fTotalUsed == totUsed);
    SkASSERT(fTotalLost == totLost);
    SkASSERT(totCapacity == totUsed + totLost + totAvailable);
}
#endif