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
14static size_t increase_next_size(size_t size) {
15    return size + (size >> 1);
16}
17
18///////////////////////////////////////////////////////////////////////////////
19
20struct 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
58SkChunkAlloc::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
72SkChunkAlloc::~SkChunkAlloc() {
73    this->reset();
74}
75
76void 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
86void 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
118SkChunkAlloc::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
139SkChunkAlloc::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
160void* 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
179size_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
198bool 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
210void 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