michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #include "SkChunkAlloc.h"
michael@0: 
michael@0: // Don't malloc any chunks smaller than this
michael@0: #define MIN_CHUNKALLOC_BLOCK_SIZE   1024
michael@0: 
michael@0: // Return the new min blocksize given the current value
michael@0: static size_t increase_next_size(size_t size) {
michael@0:     return size + (size >> 1);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: struct SkChunkAlloc::Block {
michael@0:     Block*  fNext;
michael@0:     size_t  fFreeSize;
michael@0:     char*   fFreePtr;
michael@0:     // data[] follows
michael@0: 
michael@0:     char* startOfData() {
michael@0:         return reinterpret_cast<char*>(this + 1);
michael@0:     }
michael@0: 
michael@0:     static void FreeChain(Block* block) {
michael@0:         while (block) {
michael@0:             Block* next = block->fNext;
michael@0:             sk_free(block);
michael@0:             block = next;
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     bool contains(const void* addr) const {
michael@0:         const char* ptr = reinterpret_cast<const char*>(addr);
michael@0:         return ptr >= (const char*)(this + 1) && ptr < fFreePtr;
michael@0:     }
michael@0: };
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: SkChunkAlloc::SkChunkAlloc(size_t minSize) {
michael@0:     if (minSize < MIN_CHUNKALLOC_BLOCK_SIZE) {
michael@0:         minSize = MIN_CHUNKALLOC_BLOCK_SIZE;
michael@0:     }
michael@0: 
michael@0:     fBlock = NULL;
michael@0:     fMinSize = minSize;
michael@0:     fChunkSize = fMinSize;
michael@0:     fTotalCapacity = 0;
michael@0:     fTotalUsed = 0;
michael@0:     fBlockCount = 0;
michael@0: }
michael@0: 
michael@0: SkChunkAlloc::~SkChunkAlloc() {
michael@0:     this->reset();
michael@0: }
michael@0: 
michael@0: void SkChunkAlloc::reset() {
michael@0:     Block::FreeChain(fBlock);
michael@0:     fBlock = NULL;
michael@0:     fChunkSize = fMinSize;  // reset to our initial minSize
michael@0:     fTotalCapacity = 0;
michael@0:     fTotalUsed = 0;
michael@0:     fBlockCount = 0;
michael@0: }
michael@0: 
michael@0: SkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) {
michael@0:     size_t size = bytes;
michael@0:     if (size < fChunkSize) {
michael@0:         size = fChunkSize;
michael@0:     }
michael@0: 
michael@0:     Block* block = (Block*)sk_malloc_flags(sizeof(Block) + size,
michael@0:                         ftype == kThrow_AllocFailType ? SK_MALLOC_THROW : 0);
michael@0: 
michael@0:     if (block) {
michael@0:         //    block->fNext = fBlock;
michael@0:         block->fFreeSize = size;
michael@0:         block->fFreePtr = block->startOfData();
michael@0: 
michael@0:         fTotalCapacity += size;
michael@0:         fBlockCount += 1;
michael@0: 
michael@0:         fChunkSize = increase_next_size(fChunkSize);
michael@0:     }
michael@0:     return block;
michael@0: }
michael@0: 
michael@0: void* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) {
michael@0:     fTotalUsed += bytes;
michael@0: 
michael@0:     bytes = SkAlign4(bytes);
michael@0: 
michael@0:     Block* block = fBlock;
michael@0: 
michael@0:     if (block == NULL || bytes > block->fFreeSize) {
michael@0:         block = this->newBlock(bytes, ftype);
michael@0:         if (NULL == block) {
michael@0:             return NULL;
michael@0:         }
michael@0:         block->fNext = fBlock;
michael@0:         fBlock = block;
michael@0:     }
michael@0: 
michael@0:     SkASSERT(block && bytes <= block->fFreeSize);
michael@0:     char* ptr = block->fFreePtr;
michael@0: 
michael@0:     block->fFreeSize -= bytes;
michael@0:     block->fFreePtr = ptr + bytes;
michael@0:     return ptr;
michael@0: }
michael@0: 
michael@0: size_t SkChunkAlloc::unalloc(void* ptr) {
michael@0:     size_t bytes = 0;
michael@0:     Block* block = fBlock;
michael@0:     if (block) {
michael@0:         char* cPtr = reinterpret_cast<char*>(ptr);
michael@0:         char* start = block->startOfData();
michael@0:         if (start <= cPtr && cPtr < block->fFreePtr) {
michael@0:             bytes = block->fFreePtr - cPtr;
michael@0:             block->fFreeSize += bytes;
michael@0:             block->fFreePtr = cPtr;
michael@0:         }
michael@0:     }
michael@0:     return bytes;
michael@0: }
michael@0: 
michael@0: bool SkChunkAlloc::contains(const void* addr) const {
michael@0:     const Block* block = fBlock;
michael@0:     while (block) {
michael@0:         if (block->contains(addr)) {
michael@0:             return true;
michael@0:         }
michael@0:         block = block->fNext;
michael@0:     }
michael@0:     return false;
michael@0: }