1 /* 2 * Copyright 2006 The Android Open Source Project 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "SkChunkAlloc.h" 9 10 // Don't malloc any chunks smaller than this 11 #define MIN_CHUNKALLOC_BLOCK_SIZE 1024 12 13 // Return the new min blocksize given the current value 14 static size_t increase_next_size(size_t size) { 15 return size + (size >> 1); 16 } 17 18 /////////////////////////////////////////////////////////////////////////////// 19 20 struct SkChunkAlloc::Block { 21 Block* fNext; 22 size_t fFreeSize; 23 char* fFreePtr; 24 // data[] follows 25 26 size_t blockSize() { 27 char* start = this->startOfData(); 28 size_t bytes = fFreePtr - start; 29 return fFreeSize + bytes; 30 } 31 32 void reset() { 33 fNext = NULL; 34 fFreeSize = this->blockSize(); 35 fFreePtr = this->startOfData(); 36 } 37 38 char* startOfData() { 39 return reinterpret_cast<char*>(this + 1); 40 } 41 42 static void FreeChain(Block* block) { 43 while (block) { 44 Block* next = block->fNext; 45 sk_free(block); 46 block = next; 47 } 48 }; 49 50 bool contains(const void* addr) const { 51 const char* ptr = reinterpret_cast<const char*>(addr); 52 return ptr >= (const char*)(this + 1) && ptr < fFreePtr; 53 } 54 }; 55 56 /////////////////////////////////////////////////////////////////////////////// 57 58 SkChunkAlloc::SkChunkAlloc(size_t minSize) { 59 if (minSize < MIN_CHUNKALLOC_BLOCK_SIZE) { 60 minSize = MIN_CHUNKALLOC_BLOCK_SIZE; 61 } 62 63 fBlock = NULL; 64 fMinSize = minSize; 65 fChunkSize = fMinSize; 66 fTotalCapacity = 0; 67 fTotalUsed = 0; 68 SkDEBUGCODE(fTotalLost = 0;) 69 SkDEBUGCODE(fBlockCount = 0;) 70 } 71 72 SkChunkAlloc::~SkChunkAlloc() { 73 this->reset(); 74 } 75 76 void SkChunkAlloc::reset() { 77 Block::FreeChain(fBlock); 78 fBlock = NULL; 79 fChunkSize = fMinSize; // reset to our initial minSize 80 fTotalCapacity = 0; 81 fTotalUsed = 0; 82 SkDEBUGCODE(fTotalLost = 0;) 83 SkDEBUGCODE(fBlockCount = 0;) 84 } 85 86 void SkChunkAlloc::rewind() { 87 SkDEBUGCODE(this->validate();) 88 89 Block* largest = fBlock; 90 91 if (largest) { 92 Block* next; 93 for (Block* cur = largest->fNext; cur; cur = next) { 94 next = cur->fNext; 95 if (cur->blockSize() > largest->blockSize()) { 96 sk_free(largest); 97 largest = cur; 98 } else { 99 sk_free(cur); 100 } 101 } 102 103 largest->reset(); 104 fTotalCapacity = largest->blockSize(); 105 SkDEBUGCODE(fBlockCount = 1;) 106 } else { 107 fTotalCapacity = 0; 108 SkDEBUGCODE(fBlockCount = 0;) 109 } 110 111 fBlock = largest; 112 fChunkSize = fMinSize; // reset to our initial minSize 113 fTotalUsed = 0; 114 SkDEBUGCODE(fTotalLost = 0;) 115 SkDEBUGCODE(this->validate();) 116 } 117 118 SkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) { 119 size_t size = bytes; 120 if (size < fChunkSize) { 121 size = fChunkSize; 122 } 123 124 Block* block = (Block*)sk_malloc_flags(sizeof(Block) + size, 125 ftype == kThrow_AllocFailType ? SK_MALLOC_THROW : 0); 126 127 if (block) { 128 block->fFreeSize = size; 129 block->fFreePtr = block->startOfData(); 130 131 fTotalCapacity += size; 132 SkDEBUGCODE(fBlockCount += 1;) 133 134 fChunkSize = increase_next_size(fChunkSize); 135 } 136 return block; 137 } 138 139 SkChunkAlloc::Block* SkChunkAlloc::addBlockIfNecessary(size_t bytes, AllocFailType ftype) { 140 SkASSERT(SkIsAlign4(bytes)); 141 142 if (!fBlock || bytes > fBlock->fFreeSize) { 143 Block* block = this->newBlock(bytes, ftype); 144 if (!block) { 145 return NULL; 146 } 147 #ifdef SK_DEBUG 148 if (fBlock) { 149 fTotalLost += fBlock->fFreeSize; 150 } 151 #endif 152 block->fNext = fBlock; 153 fBlock = block; 154 } 155 156 SkASSERT(fBlock && bytes <= fBlock->fFreeSize); 157 return fBlock; 158 } 159 160 void* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) { 161 SkDEBUGCODE(this->validate();) 162 163 bytes = SkAlign4(bytes); 164 165 Block* block = this->addBlockIfNecessary(bytes, ftype); 166 if (!block) { 167 return NULL; 168 } 169 170 char* ptr = block->fFreePtr; 171 172 fTotalUsed += bytes; 173 block->fFreeSize -= bytes; 174 block->fFreePtr = ptr + bytes; 175 SkDEBUGCODE(this->validate();) 176 return ptr; 177 } 178 179 size_t SkChunkAlloc::unalloc(void* ptr) { 180 SkDEBUGCODE(this->validate();) 181 182 size_t bytes = 0; 183 Block* block = fBlock; 184 if (block) { 185 char* cPtr = reinterpret_cast<char*>(ptr); 186 char* start = block->startOfData(); 187 if (start <= cPtr && cPtr < block->fFreePtr) { 188 bytes = block->fFreePtr - cPtr; 189 fTotalUsed -= bytes; 190 block->fFreeSize += bytes; 191 block->fFreePtr = cPtr; 192 } 193 } 194 SkDEBUGCODE(this->validate();) 195 return bytes; 196 } 197 198 bool SkChunkAlloc::contains(const void* addr) const { 199 const Block* block = fBlock; 200 while (block) { 201 if (block->contains(addr)) { 202 return true; 203 } 204 block = block->fNext; 205 } 206 return false; 207 } 208 209 #ifdef SK_DEBUG 210 void SkChunkAlloc::validate() { 211 int numBlocks = 0; 212 size_t totCapacity = 0; 213 size_t totUsed = 0; 214 size_t totLost = 0; 215 size_t totAvailable = 0; 216 217 for (Block* temp = fBlock; temp; temp = temp->fNext) { 218 ++numBlocks; 219 totCapacity += temp->blockSize(); 220 totUsed += temp->fFreePtr - temp->startOfData(); 221 if (temp == fBlock) { 222 totAvailable += temp->fFreeSize; 223 } else { 224 totLost += temp->fFreeSize; 225 } 226 } 227 228 SkASSERT(fBlockCount == numBlocks); 229 SkASSERT(fTotalCapacity == totCapacity); 230 SkASSERT(fTotalUsed == totUsed); 231 SkASSERT(fTotalLost == totLost); 232 SkASSERT(totCapacity == totUsed + totLost + totAvailable); 233 } 234 #endif 235 236
