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    char* startOfData() {
27        return reinterpret_cast<char*>(this + 1);
28    }
29
30    static void FreeChain(Block* block) {
31        while (block) {
32            Block* next = block->fNext;
33            sk_free(block);
34            block = next;
35        }
36    };
37
38    bool contains(const void* addr) const {
39        const char* ptr = reinterpret_cast<const char*>(addr);
40        return ptr >= (const char*)(this + 1) && ptr < fFreePtr;
41    }
42};
43
44///////////////////////////////////////////////////////////////////////////////
45
46SkChunkAlloc::SkChunkAlloc(size_t minSize) {
47    if (minSize < MIN_CHUNKALLOC_BLOCK_SIZE) {
48        minSize = MIN_CHUNKALLOC_BLOCK_SIZE;
49    }
50
51    fBlock = NULL;
52    fMinSize = minSize;
53    fChunkSize = fMinSize;
54    fTotalCapacity = 0;
55    fTotalUsed = 0;
56    fBlockCount = 0;
57}
58
59SkChunkAlloc::~SkChunkAlloc() {
60    this->reset();
61}
62
63void SkChunkAlloc::reset() {
64    Block::FreeChain(fBlock);
65    fBlock = NULL;
66    fChunkSize = fMinSize;  // reset to our initial minSize
67    fTotalCapacity = 0;
68    fTotalUsed = 0;
69    fBlockCount = 0;
70}
71
72SkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) {
73    size_t size = bytes;
74    if (size < fChunkSize) {
75        size = fChunkSize;
76    }
77
78    Block* block = (Block*)sk_malloc_flags(sizeof(Block) + size,
79                        ftype == kThrow_AllocFailType ? SK_MALLOC_THROW : 0);
80
81    if (block) {
82        //    block->fNext = fBlock;
83        block->fFreeSize = size;
84        block->fFreePtr = block->startOfData();
85
86        fTotalCapacity += size;
87        fBlockCount += 1;
88
89        fChunkSize = increase_next_size(fChunkSize);
90    }
91    return block;
92}
93
94void* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) {
95    fTotalUsed += bytes;
96
97    bytes = SkAlign4(bytes);
98
99    Block* block = fBlock;
100
101    if (block == NULL || bytes > block->fFreeSize) {
102        block = this->newBlock(bytes, ftype);
103        if (NULL == block) {
104            return NULL;
105        }
106        block->fNext = fBlock;
107        fBlock = block;
108    }
109
110    SkASSERT(block && bytes <= block->fFreeSize);
111    char* ptr = block->fFreePtr;
112
113    block->fFreeSize -= bytes;
114    block->fFreePtr = ptr + bytes;
115    return ptr;
116}
117
118size_t SkChunkAlloc::unalloc(void* ptr) {
119    size_t bytes = 0;
120    Block* block = fBlock;
121    if (block) {
122        char* cPtr = reinterpret_cast<char*>(ptr);
123        char* start = block->startOfData();
124        if (start <= cPtr && cPtr < block->fFreePtr) {
125            bytes = block->fFreePtr - cPtr;
126            block->fFreeSize += bytes;
127            block->fFreePtr = cPtr;
128        }
129    }
130    return bytes;
131}
132
133bool SkChunkAlloc::contains(const void* addr) const {
134    const Block* block = fBlock;
135    while (block) {
136        if (block->contains(addr)) {
137            return true;
138        }
139        block = block->fNext;
140    }
141    return false;
142}
143