Spaces:
Sleeping
Sleeping
File size: 6,176 Bytes
fcf3b03 | 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 201 202 203 204 205 206 207 208 209 210 211 212 213 | // @flow
import {OverscaledTileID} from './tile_id';
import type Tile from './tile';
/**
* A [least-recently-used cache](http://en.wikipedia.org/wiki/Cache_algorithms)
* with hash lookup made possible by keeping a list of keys in parallel to
* an array of dictionary of values
*
* @private
*/
class TileCache {
max: number;
data: {[key: string]: Array<{ value: Tile, timeout: ?TimeoutID}>};
order: Array<string>;
onRemove: (element: Tile) => void;
/**
* @param {number} max number of permitted values
* @param {Function} onRemove callback called with items when they expire
*/
constructor(max: number, onRemove: (element: Tile) => void) {
this.max = max;
this.onRemove = onRemove;
this.reset();
}
/**
* Clear the cache
*
* @returns {TileCache} this cache
* @private
*/
reset() {
for (const key in this.data) {
for (const removedData of this.data[key]) {
if (removedData.timeout) clearTimeout(removedData.timeout);
this.onRemove(removedData.value);
}
}
this.data = {};
this.order = [];
return this;
}
/**
* Add a key, value combination to the cache, trimming its size if this pushes
* it over max length.
*
* @param {OverscaledTileID} tileID lookup key for the item
* @param {*} data any value
*
* @returns {TileCache} this cache
* @private
*/
add(tileID: OverscaledTileID, data: Tile, expiryTimeout: number | void) {
const key = tileID.wrapped().key;
if (this.data[key] === undefined) {
this.data[key] = [];
}
const dataWrapper = {
value: data,
timeout: undefined
};
if (expiryTimeout !== undefined) {
dataWrapper.timeout = setTimeout(() => {
this.remove(tileID, dataWrapper);
}, expiryTimeout);
}
this.data[key].push(dataWrapper);
this.order.push(key);
if (this.order.length > this.max) {
const removedData = this._getAndRemoveByKey(this.order[0]);
if (removedData) this.onRemove(removedData);
}
return this;
}
/**
* Determine whether the value attached to `key` is present
*
* @param {OverscaledTileID} tileID the key to be looked-up
* @returns {boolean} whether the cache has this value
* @private
*/
has(tileID: OverscaledTileID): boolean {
return tileID.wrapped().key in this.data;
}
/**
* Get the value attached to a specific key and remove data from cache.
* If the key is not found, returns `null`
*
* @param {OverscaledTileID} tileID the key to look up
* @returns {*} the data, or null if it isn't found
* @private
*/
getAndRemove(tileID: OverscaledTileID): ?Tile {
if (!this.has(tileID)) { return null; }
return this._getAndRemoveByKey(tileID.wrapped().key);
}
/*
* Get and remove the value with the specified key.
*/
_getAndRemoveByKey(key: string): ?Tile {
const data = this.data[key].shift();
if (data.timeout) clearTimeout(data.timeout);
if (this.data[key].length === 0) {
delete this.data[key];
}
this.order.splice(this.order.indexOf(key), 1);
return data.value;
}
/*
* Get the value with the specified (wrapped tile) key.
*/
getByKey(key: string): ?Tile {
const data = this.data[key];
return data ? data[0].value : null;
}
/**
* Get the value attached to a specific key without removing data
* from the cache. If the key is not found, returns `null`
*
* @param {OverscaledTileID} tileID the key to look up
* @returns {*} the data, or null if it isn't found
* @private
*/
get(tileID: OverscaledTileID): ?Tile {
if (!this.has(tileID)) { return null; }
const data = this.data[tileID.wrapped().key][0];
return data.value;
}
/**
* Remove a key/value combination from the cache.
*
* @param {OverscaledTileID} tileID the key for the pair to delete
* @param {Tile} value If a value is provided, remove that exact version of the value.
* @returns {TileCache} this cache
* @private
*/
remove(tileID: OverscaledTileID, value: ?{ value: Tile, timeout: ?TimeoutID}) {
if (!this.has(tileID)) { return this; }
const key = tileID.wrapped().key;
const dataIndex = value === undefined ? 0 : this.data[key].indexOf(value);
const data = this.data[key][dataIndex];
this.data[key].splice(dataIndex, 1);
if (data.timeout) clearTimeout(data.timeout);
if (this.data[key].length === 0) {
delete this.data[key];
}
this.onRemove(data.value);
this.order.splice(this.order.indexOf(key), 1);
return this;
}
/**
* Change the max size of the cache.
*
* @param {number} max the max size of the cache
* @returns {TileCache} this cache
* @private
*/
setMaxSize(max: number): TileCache {
this.max = max;
while (this.order.length > this.max) {
const removedData = this._getAndRemoveByKey(this.order[0]);
if (removedData) this.onRemove(removedData);
}
return this;
}
/**
* Remove entries that do not pass a filter function. Used for removing
* stale tiles from the cache.
*
* @param {function} filterFn Determines whether the tile is filtered. If the supplied function returns false, the tile will be filtered out.
*/
filter(filterFn: (tile: Tile) => boolean) {
const removed = [];
for (const key in this.data) {
for (const entry of this.data[key]) {
if (!filterFn(entry.value)) {
removed.push(entry);
}
}
}
for (const r of removed) {
this.remove(r.value.tileID, r);
}
}
}
export default TileCache;
|