11cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 21cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 31cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Copyright 2006 The Android Open Source Project 41cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 51cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Use of this source code is governed by a BSD-style license that can be 61cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * found in the LICENSE file. 71cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 81cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 90910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#include "SkChunkAlloc.h" 110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstruct SkChunkAlloc::Block { 130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Block* fNext; 140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project size_t fFreeSize; 150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* fFreePtr; 160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // data[] follows 170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 185f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed char* startOfData() { 195f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed return reinterpret_cast<char*>(this + 1); 205f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed } 215f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed 220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project void freeChain() { // this can be null 230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Block* block = this; 240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project while (block) { 250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Block* next = block->fNext; 260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project sk_free(block); 270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project block = next; 280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project }; 300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Block* tail() { 320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Block* block = this; 330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (block) { 340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project for (;;) { 350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Block* next = block->fNext; 360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == next) { 370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project break; 380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project block = next; 400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return block; 430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 4440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 4540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger bool contains(const void* addr) const { 4640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const char* ptr = reinterpret_cast<const char*>(addr); 4740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return ptr >= (const char*)(this + 1) && ptr < fFreePtr; 4840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}; 500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkChunkAlloc::SkChunkAlloc(size_t minSize) 520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project : fBlock(NULL), fMinSize(SkAlign4(minSize)), fPool(NULL), fTotalCapacity(0) 530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project{ 540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkChunkAlloc::~SkChunkAlloc() { 570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project this->reset(); 580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkChunkAlloc::reset() { 610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBlock->freeChain(); 620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBlock = NULL; 630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fPool->freeChain(); 640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fPool = NULL; 650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fTotalCapacity = 0; 660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkChunkAlloc::reuse() { 690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (fPool && fBlock) { 700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fPool->tail()->fNext = fBlock; 710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fPool = fBlock; 730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBlock = NULL; 740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fTotalCapacity = 0; 750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) { 780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Block* block = fPool; 790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (block && bytes <= block->fFreeSize) { 810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fPool = block->fNext; 820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return block; 830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 8540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger size_t size = bytes; 8640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (size < fMinSize) 8740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger size = fMinSize; 880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project block = (Block*)sk_malloc_flags(sizeof(Block) + size, 900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project ftype == kThrow_AllocFailType ? SK_MALLOC_THROW : 0); 910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (block) { 930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // block->fNext = fBlock; 940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project block->fFreeSize = size; 955f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed block->fFreePtr = block->startOfData(); 960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fTotalCapacity += size; 980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return block; 1000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) { 1030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project bytes = SkAlign4(bytes); 1040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1050910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Block* block = fBlock; 1060910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1070910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (block == NULL || bytes > block->fFreeSize) { 1080910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project block = this->newBlock(bytes, ftype); 1090910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == block) { 1100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return NULL; 1110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project block->fNext = fBlock; 1130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBlock = block; 1140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(block && bytes <= block->fFreeSize); 1170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project void* ptr = block->fFreePtr; 1180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project block->fFreeSize -= bytes; 1200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project block->fFreePtr += bytes; 1210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return ptr; 1220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1245f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reedsize_t SkChunkAlloc::unalloc(void* ptr) { 1255f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed size_t bytes = 0; 1265f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed Block* block = fBlock; 1275f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed if (block) { 1285f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed char* cPtr = reinterpret_cast<char*>(ptr); 1295f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed char* start = block->startOfData(); 1305f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed if (start <= cPtr && cPtr < block->fFreePtr) { 1315f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed bytes = block->fFreePtr - cPtr; 1325f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed block->fFreeSize += bytes; 1335f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed block->fFreePtr = cPtr; 1345f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed } 1355f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed } 1365f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed return bytes; 1375f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed} 1385f6af4c62d33f128b6617fa4a038f309627a14d0Mike Reed 13940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerbool SkChunkAlloc::contains(const void* addr) const { 14040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const Block* block = fBlock; 14140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger while (block) { 14240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (block->contains(addr)) { 14340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return true; 14440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 14540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger block = block->fNext; 14640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 14740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return false; 14840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 14940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 150