3 * Per-process memory cache for storing items.
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 * http://www.gnu.org/copyleft/gpl.html
23 use Wikimedia\Assert\Assert
;
26 * Handles a simple LRU key/value map with a maximum number of entries
28 * The last-modification timestamp of entries is internally tracked so that callers can
29 * specify the maximum acceptable age of entries in calls to the has() method. As a convenience,
30 * the hasField(), getField(), and setField() methods can be used for entries that are field/value
31 * maps themselves; such fields will have their own internally tracked last-modification timestamp.
33 * @see ProcessCacheLRU
37 class MapCacheLRU
implements IExpiringStore
, Serializable
{
38 /** @var array Map of (key => value) */
40 /** @var array Map of (key => (UNIX timestamp, (field => UNIX timestamp))) */
41 private $timestamps = [];
42 /** @var float Default entry timestamp if not specified */
45 /** @var int Max number of entries */
46 private $maxCacheKeys;
48 /** @var float|null */
49 private $wallClockOverride;
54 /** @var int Array key that holds the entry's main timestamp (flat key use) */
56 /** @var int Array key that holds the entry's field timestamps (nested key use) */
60 * @param int $maxKeys Maximum number of entries allowed (min 1)
61 * @throws Exception When $maxKeys is not an int or not above zero
63 public function __construct( $maxKeys ) {
64 Assert
::parameterType( 'integer', $maxKeys, '$maxKeys' );
65 Assert
::parameter( $maxKeys > 0, '$maxKeys', 'must be above zero' );
67 $this->maxCacheKeys
= $maxKeys;
68 // Use the current time as the default "as of" timestamp of entries
69 $this->epoch
= $this->getCurrentTime();
73 * @param array $values Key/value map in order of increasingly recent access
78 public static function newFromArray( array $values, $maxKeys ) {
79 $mapCache = new self( $maxKeys );
80 $mapCache->cache
= ( count( $values ) > $maxKeys )
81 ?
array_slice( $values, -$maxKeys, null, true )
88 * @return array Key/value map in order of increasingly recent access
91 public function toArray() {
96 * Set a key/value pair.
97 * This will prune the cache if it gets too large based on LRU.
98 * If the item is already set, it will be pushed to the top of the cache.
100 * To reduce evictions due to one-off use of many new keys, $rank can be
101 * set to have keys start at the top of a bottom fraction of the list. A value
102 * of 3/8 means values start at the top of the bottom 3/8s of the list and are
103 * moved to the top of the list when accessed a second time.
106 * @param mixed $value
107 * @param float $rank Bottom fraction of the list where keys start off [default: 1.0]
110 public function set( $key, $value, $rank = self
::RANK_TOP
) {
111 if ( $this->has( $key ) ) {
113 } elseif ( count( $this->cache
) >= $this->maxCacheKeys
) {
114 reset( $this->cache
);
115 $evictKey = key( $this->cache
);
116 unset( $this->cache
[$evictKey] );
117 unset( $this->timestamps
[$evictKey] );
120 if ( $rank < 1.0 && $rank > 0 ) {
121 $offset = intval( $rank * count( $this->cache
) );
122 $this->cache
= array_slice( $this->cache
, 0, $offset, true )
124 +
array_slice( $this->cache
, $offset, null, true );
126 $this->cache
[$key] = $value;
129 $this->timestamps
[$key] = [
130 self
::SIMPLE
=> $this->getCurrentTime(),
136 * Check if a key exists
139 * @param float $maxAge Ignore items older than this many seconds [default: INF]
141 * @since 1.32 Added $maxAge
143 public function has( $key, $maxAge = INF
) {
144 if ( !is_int( $key ) && !is_string( $key ) ) {
145 throw new UnexpectedValueException(
146 __METHOD__
. ': invalid key; must be string or integer.' );
149 if ( !array_key_exists( $key, $this->cache
) ) {
153 return ( $maxAge <= 0 ||
$this->getAge( $key ) <= $maxAge );
157 * Get the value for a key.
158 * This returns null if the key is not set.
159 * If the item is already set, it will be pushed to the top of the cache.
162 * @param float $maxAge Ignore items older than this many seconds [default: INF]
163 * @param mixed|null $default Value to return if no key is found [default: null]
164 * @return mixed Returns $default if the key was not found or is older than $maxAge
165 * @since 1.32 Added $maxAge
166 * @since 1.34 Added $default
168 public function get( $key, $maxAge = INF
, $default = null ) {
169 if ( !$this->has( $key, $maxAge ) ) {
175 return $this->cache
[$key];
179 * @param string|int $key
180 * @param string|int $field
181 * @param mixed $value
182 * @param float $initRank
184 public function setField( $key, $field, $value, $initRank = self
::RANK_TOP
) {
185 if ( $this->has( $key ) ) {
188 $this->set( $key, [], $initRank );
191 if ( !is_int( $field ) && !is_string( $field ) ) {
192 throw new UnexpectedValueException(
193 __METHOD__
. ": invalid field for '$key'; must be string or integer." );
196 if ( !is_array( $this->cache
[$key] ) ) {
197 $type = gettype( $this->cache
[$key] );
199 throw new UnexpectedValueException( "The value of '$key' ($type) is not an array." );
202 $this->cache
[$key][$field] = $value;
203 $this->timestamps
[$key][self
::FIELDS
][$field] = $this->getCurrentTime();
207 * @param string|int $key
208 * @param string|int $field
209 * @param float $maxAge Ignore items older than this many seconds [default: INF]
211 * @since 1.32 Added $maxAge
213 public function hasField( $key, $field, $maxAge = INF
) {
214 $value = $this->get( $key );
216 if ( !is_int( $field ) && !is_string( $field ) ) {
217 throw new UnexpectedValueException(
218 __METHOD__
. ": invalid field for '$key'; must be string or integer." );
221 if ( !is_array( $value ) ||
!array_key_exists( $field, $value ) ) {
225 return ( $maxAge <= 0 ||
$this->getAge( $key, $field ) <= $maxAge );
229 * @param string|int $key
230 * @param string|int $field
231 * @param float $maxAge Ignore items older than this many seconds [default: INF]
232 * @return mixed Returns null if the key was not found or is older than $maxAge
233 * @since 1.32 Added $maxAge
235 public function getField( $key, $field, $maxAge = INF
) {
236 if ( !$this->hasField( $key, $field, $maxAge ) ) {
240 return $this->cache
[$key][$field];
247 public function getAllKeys() {
248 return array_keys( $this->cache
);
252 * Get an item with the given key, producing and setting it if not found.
254 * If the callback returns false, then nothing is stored.
258 * @param callable $callback Callback that will produce the value
259 * @param float $rank Bottom fraction of the list where keys start off [default: 1.0]
260 * @param float $maxAge Ignore items older than this many seconds [default: INF]
261 * @return mixed The cached value if found or the result of $callback otherwise
262 * @since 1.32 Added $maxAge
264 public function getWithSetCallback(
265 $key, callable
$callback, $rank = self
::RANK_TOP
, $maxAge = INF
267 if ( $this->has( $key, $maxAge ) ) {
268 $value = $this->get( $key );
270 $value = call_user_func( $callback );
271 if ( $value !== false ) {
272 $this->set( $key, $value, $rank );
280 * Clear one or several cache entries, or all cache entries
282 * @param string|array|null $keys
285 public function clear( $keys = null ) {
286 if ( func_num_args() == 0 ) {
288 $this->timestamps
= [];
290 foreach ( (array)$keys as $key ) {
291 unset( $this->cache
[$key] );
292 unset( $this->timestamps
[$key] );
298 * Get the maximum number of keys allowed
303 public function getMaxSize() {
304 return $this->maxCacheKeys
;
308 * Resize the maximum number of cache entries, removing older entries as needed
310 * @param int $maxKeys Maximum number of entries allowed (min 1)
312 * @throws Exception When $maxKeys is not an int or not above zero
315 public function setMaxSize( $maxKeys ) {
316 Assert
::parameterType( 'integer', $maxKeys, '$maxKeys' );
317 Assert
::parameter( $maxKeys > 0, '$maxKeys', 'must be above zero' );
319 $this->maxCacheKeys
= $maxKeys;
320 while ( count( $this->cache
) > $this->maxCacheKeys
) {
321 reset( $this->cache
);
322 $evictKey = key( $this->cache
);
323 unset( $this->cache
[$evictKey] );
324 unset( $this->timestamps
[$evictKey] );
329 * Push an entry to the top of the cache
333 private function ping( $key ) {
334 $item = $this->cache
[$key];
335 unset( $this->cache
[$key] );
336 $this->cache
[$key] = $item;
340 * @param string|int $key
341 * @param string|int|null $field [optional]
342 * @return float UNIX timestamp; the age of the given entry or entry field
344 private function getAge( $key, $field = null ) {
345 if ( $field !== null ) {
346 $mtime = $this->timestamps
[$key][self
::FIELDS
][$field] ??
$this->epoch
;
348 $mtime = $this->timestamps
[$key][self
::SIMPLE
] ??
$this->epoch
;
351 return ( $this->getCurrentTime() - $mtime );
354 public function serialize() {
356 'entries' => $this->cache
,
357 'timestamps' => $this->timestamps
361 public function unserialize( $serialized ) {
362 $data = unserialize( $serialized );
363 $this->cache
= $data['entries'] ??
[];
364 $this->timestamps
= $data['timestamps'] ??
[];
365 $this->epoch
= $this->getCurrentTime();
369 * @return float UNIX timestamp
370 * @codeCoverageIgnore
372 protected function getCurrentTime() {
373 return $this->wallClockOverride ?
: microtime( true );
377 * @param float|null &$time Mock UNIX timestamp for testing
378 * @codeCoverageIgnore
380 public function setMockTime( &$time ) {
381 $this->wallClockOverride
=& $time;