-
Notifications
You must be signed in to change notification settings - Fork 478
/
block_cache.h
200 lines (167 loc) · 6.37 KB
/
block_cache.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
// Copyright (c) 2009, Niels Martin Hansen
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
// * Neither the name of the Aegisub Group nor the names of its contributors
// may be used to endorse or promote products derived from this software
// without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
//
// Aegisub Project http://www.aegisub.org/
/// @file block_cache.h
/// @ingroup utility
/// @brief Template class for creating caches for blocks of data
#pragma once
#include <algorithm>
#include <list>
#include <vector>
/// @class DataBlockCache
/// @brief Cache for blocks of data in a stream or similar
/// @tparam BlockT Type of blocks to store
/// @tparam MacroblockExponent Controls the number of blocks per macroblock, for tuning memory usage
/// @tparam BlockFactoryT Type of block factory, see BasicDataBlockFactory class for detail on these
template <typename BlockT, int MacroblockExponent, typename BlockFactoryT>
class DataBlockCache {
/// Type of an array of blocks
typedef std::vector<typename BlockFactoryT::BlockType> BlockArray;
struct MacroBlock {
/// This macroblock's position in the age list
/// Is valid iff blocks.size() > 0
typename std::list<MacroBlock*>::iterator position;
/// The blocks contained in the macroblock
BlockArray blocks;
};
/// Type of an array of macro blocks
typedef std::vector<MacroBlock> MacroBlockArray;
/// The data in the cache
MacroBlockArray data;
/// Type of a list of macro blocks
typedef std::list<MacroBlock*> AgeList;
/// The data sorted by how long it's been since they were used
AgeList age;
/// Number of blocks per macroblock
size_t macroblock_size;
/// Bitmask to extract the inside-macroblock index for a block by bitwise and
size_t macroblock_index_mask;
/// Current size of the cache in bytes
size_t size = 0;
/// Factory object for blocks
BlockFactoryT factory;
/// @brief Dispose of all blocks in a macroblock and mark it empty
/// @param mb_index Index of macroblock to clear
void KillMacroBlock(MacroBlock &mb)
{
if (mb.blocks.empty())
return;
auto& ba = mb.blocks;
size -= (ba.size() - std::count(ba.begin(), ba.end(), nullptr)) * factory.GetBlockSize();
ba.clear();
age.erase(mb.position);
}
public:
/// @brief Constructor
/// @param block_count Total number of blocks the cache will manage
/// @param factory Factory object to use for producing blocks
///
/// Note that the block_count is the maximum block index the cache will ever see,
/// it is an error to request a block number greater than block_count.
///
/// The factory object passed must respond well to copying.
DataBlockCache(size_t block_count, BlockFactoryT factory = BlockFactoryT())
: factory(std::move(factory))
{
SetBlockCount(block_count);
}
DataBlockCache(DataBlockCache&&) = default;
DataBlockCache& operator=(DataBlockCache&&) = default;
/// @brief Change the number of blocks in cache
/// @param block_count New number of blocks to hold
///
/// This will completely de-allocate the cache and re-allocate it with the new block count.
void SetBlockCount(size_t block_count)
{
if (data.size() > 0)
Age(0);
macroblock_size = 1UL << MacroblockExponent;
macroblock_index_mask = macroblock_size - 1;
data.resize((block_count + macroblock_size - 1) >> MacroblockExponent);
size = 0;
}
/// @brief Clean up the cache
/// @param max_size Target maximum size of the cache in bytes
///
/// Passing a max_size of 0 (zero) causes the cache to be completely flushed
/// in a fast manner.
///
/// The max_size is not a hard limit, the cache size might somewhat exceed the max
/// after the aging operation, though it shouldn't be by much.
void Age(size_t max_size)
{
// Quick way out: get rid of everything
if (max_size == 0)
{
size_t block_count = data.size();
data.clear();
data.resize(block_count);
age.clear();
size = 0;
return;
}
// Remove old entries until we're under the max size
for (auto it = age.rbegin(); size > max_size && it != age.rend(); )
KillMacroBlock(**it++);
}
/// @brief Obtain a data block from the cache
/// @param i Index of the block to retrieve
/// @param[out] created On return, tells whether the returned block was created during the operation
/// @return A pointer to the block in cache
///
/// It is legal to pass 0 (null) for created, in this case nothing is returned in it.
BlockT& Get(size_t i, bool *created = nullptr)
{
size_t mbi = i >> MacroblockExponent;
assert(mbi < data.size());
auto &mb = data[mbi];
// Move this macroblock to the front of the age list
if (mb.blocks.empty())
{
mb.blocks.resize(macroblock_size);
age.push_front(&mb);
}
else if (mb.position != begin(age))
age.splice(begin(age), age, mb.position);
mb.position = age.begin();
size_t block_index = i & macroblock_index_mask;
assert(block_index < mb.blocks.size());
BlockT *b = mb.blocks[block_index].get();
if (!b)
{
mb.blocks[block_index] = factory.ProduceBlock(i);
b = mb.blocks[block_index].get();
assert(b != nullptr);
size += factory.GetBlockSize();
if (created) *created = true;
}
else
if (created) *created = false;
return *b;
}
};