docs/lru.js.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>JSDoc: Source: lru.js</title>
<script src="scripts/prettify/prettify.js"> </script>
<script src="scripts/prettify/lang-css.js"> </script>
<!--[if lt IE 9]>
<script src="//html5shiv.googlecode.com/svn/trunk/html5.js"></script>
<![endif]-->
<link type="text/css" rel="stylesheet" href="styles/prettify-tomorrow.css">
<link type="text/css" rel="stylesheet" href="styles/jsdoc-default.css">
</head>
<body>
<div id="main">
<h1 class="page-title">Source: lru.js</h1>
<section>
<article>
<pre class="prettyprint source linenums"><code>
/**
* A doubly linked list-based Least Recently Used (LRU) cache. Will keep most
* recently used items while discarding least recently used items when its limit
* is reached.
*
* Licensed under MIT. Copyright (c) 2010 Rasmus Andersson <http://hunch.se/>
* See README.md for details.
*
* Illustration of the design:
*
* entry entry entry entry
* ______ ______ ______ ______
* | head |.newer => | |.newer => | |.newer => | tail |
* | A | | B | | C | | D |
* |______| <= older.|______| <= older.|______| <= older.|______|
*
* removed <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- added
*/
function LRUCache (limit) {
// Current size of the cache. (Read-only).
this.size = 0;
// Maximum number of items this cache can hold.
this.limit = limit;
this._keymap = {};
}
/**
* Put <value> into the cache associated with <key>. Returns the entry which was
* removed to make room for the new entry. Otherwise undefined is returned
* (i.e. if there was enough room already).
*/
LRUCache.prototype.put = function(key, value) {
var entry = {key:key, value:value};
// Note: No protection agains replacing, and thus orphan entries. By design.
this._keymap[key] = entry;
if (this.tail) {
// link previous tail to the new tail (entry)
this.tail.newer = entry;
entry.older = this.tail;
} else {
// we're first in -- yay
this.head = entry;
}
// add new entry to the end of the linked list -- it's now the freshest entry.
this.tail = entry;
if (this.size === this.limit) {
// we hit the limit -- remove the head
return this.shift();
} else {
// increase the size counter
this.size++;
}
return null;
};
/**
* Purge the least recently used (oldest) entry from the cache. Returns the
* removed entry or undefined if the cache was empty.
*
* If you need to perform any form of finalization of purged items, this is a
* good place to do it. Simply override/replace this function:
*
* var c = new LRUCache(123);
* c.shift = function() {
* var entry = LRUCache.prototype.shift.call(this);
* doSomethingWith(entry);
* return entry;
* }
*/
LRUCache.prototype.shift = function() {
// todo: handle special case when limit == 1
var entry = this.head;
if (entry) {
if (this.head.newer) {
this.head = this.head.newer;
this.head.older = undefined;
} else {
this.head = undefined;
}
// Remove last strong reference to <entry> and remove links from the purged
// entry being returned:
entry.newer = entry.older = undefined;
// delete is slow, but we need to do this to avoid uncontrollable growth:
delete this._keymap[entry.key];
}
return entry;
};
/**
* Get and register recent use of <key>. Returns the value associated with <key>
* or undefined if not in cache.
*/
LRUCache.prototype.get = function(key, returnEntry) {
// First, find our cache entry
var entry = this._keymap[key];
if (entry === undefined) return null; // Not cached. Sorry.
// As <key> was found in the cache, register it as being requested recently
if (entry === this.tail) {
// Already the most recenlty used entry, so no need to update the list
return returnEntry ? entry : entry.value;
}
// HEAD--------------TAIL
// <.older .newer>
// <--- add direction --
// A B C <D> E
if (entry.newer) {
if (entry === this.head)
this.head = entry.newer;
entry.newer.older = entry.older; // C <-- E.
}
if (entry.older)
entry.older.newer = entry.newer; // C. --> E
entry.newer = undefined; // D --x
entry.older = this.tail; // D. --> E
if (this.tail)
this.tail.newer = entry; // E. <-- D
this.tail = entry;
return returnEntry ? entry : entry.value;
};
// ----------------------------------------------------------------------------
// Following code is optional and can be removed without breaking the core
// functionality.
/**
* Check if <key> is in the cache without registering recent use. Feasible if
* you do not want to chage the state of the cache, but only "peek" at it.
* Returns the entry associated with <key> if found, or undefined if not found.
*/
LRUCache.prototype.find = function(key) {
return this._keymap[key];
};
/**
* Update the value of entry with <key>. Returns the old value, or undefined if
* entry was not in the cache.
*/
LRUCache.prototype.set = function(key, value) {
var oldvalue, entry = this.get(key, true);
if (entry) {
oldvalue = entry.value;
entry.value = value;
} else {
oldvalue = this.put(key, value);
if (oldvalue) oldvalue = oldvalue.value;
}
return oldvalue;
};
/**
* Remove entry <key> from cache and return its value. Returns undefined if not
* found.
*/
LRUCache.prototype.remove = function(key) {
var entry = this._keymap[key];
if (!entry) return null;
delete this._keymap[entry.key]; // need to do delete unfortunately
if (entry.newer && entry.older) {
// relink the older entry with the newer entry
entry.older.newer = entry.newer;
entry.newer.older = entry.older;
} else if (entry.newer) {
// remove the link to us
entry.newer.older = undefined;
// link the newer entry to head
this.head = entry.newer;
} else if (entry.older) {
// remove the link to us
entry.older.newer = undefined;
// link the newer entry to head
this.tail = entry.older;
} else { // if(entry.older === undefined && entry.newer === undefined) {
this.head = this.tail = undefined;
}
this.size--;
return entry.value;
};
/** Removes all entries */
LRUCache.prototype.removeAll = function() {
// This should be safe, as we never expose strong refrences to the outside
this.head = this.tail = undefined;
this.size = 0;
this._keymap = {};
};
/**
* Return an array containing all keys of entries stored in the cache object, in
* arbitrary order.
*/
if (typeof Object.keys === 'function') {
LRUCache.prototype.keys = function() { return Object.keys(this._keymap); };
} else {
LRUCache.prototype.keys = function() {
var keys = [];
for (var k in this._keymap) keys.push(k);
return keys;
};
}
/**
* Call `fun` for each entry. Starting with the newest entry if `desc` is a true
* value, otherwise starts with the oldest (head) enrty and moves towards the
* tail.
*
* `fun` is called with 3 arguments in the context `context`:
* `fun.call(context, Object key, Object value, LRUCache self)`
*/
LRUCache.prototype.forEach = function(fun, context, desc) {
var entry;
if (context === true) { desc = true; context = undefined; }
else if (typeof context !== 'object') context = this;
if (desc) {
entry = this.tail;
while (entry) {
fun.call(context, entry.key, entry.value, this);
entry = entry.older;
}
} else {
entry = this.head;
while (entry) {
fun.call(context, entry.key, entry.value, this);
entry = entry.newer;
}
}
};
/** Returns a JSON (array) representation */
LRUCache.prototype.toJSON = function() {
var s = [], entry = this.head;
while (entry) {
s.push({key:entry.key.toJSON(), value:entry.value.toJSON()});
entry = entry.newer;
}
return s;
};
/** Returns a String representation */
LRUCache.prototype.toString = function() {
var s = '', entry = this.head;
while (entry) {
s += String(entry.key)+':'+entry.value;
entry = entry.newer;
if (entry)
s += ' < ';
}
return s;
};
module.exports = LRUCache;
</code></pre>
</article>
</section>
</div>
<nav>
<h2><a href="index.html">Home</a></h2><h3>Classes</h3><ul><li><a href="Api.html">Api</a></li><li><a href="Doc.html">Doc</a></li><li><a href="Experiments.html">Experiments</a></li><li><a href="Fragments_Color.html">Fragments:Color</a></li><li><a href="Fragments_CompositeSlice.html">Fragments:CompositeSlice</a></li><li><a href="Fragments_Date.html">Fragments:Date</a></li><li><a href="Fragments_DocumentLink.html">Fragments:DocumentLink</a></li><li><a href="Fragments_Embed.html">Fragments:Embed</a></li><li><a href="Fragments_FileLink.html">Fragments:FileLink</a></li><li><a href="Fragments_GeoPoint.html">Fragments:GeoPoint</a></li><li><a href="Fragments_Group.html">Fragments:Group</a></li><li><a href="Fragments_ImageEl.html">Fragments:ImageEl</a></li><li><a href="Fragments_ImageLink.html">Fragments:ImageLink</a></li><li><a href="Fragments_ImageView.html">Fragments:ImageView</a></li><li><a href="Fragments_Num.html">Fragments:Num</a></li><li><a href="Fragments_Select.html">Fragments:Select</a></li><li><a href="Fragments_Separator.html">Fragments:Separator</a></li><li><a href="Fragments_SimpleSlice.html">Fragments:SimpleSlice</a></li><li><a href="Fragments_SliceZone.html">Fragments:SliceZone</a></li><li><a href="Fragments_StructuredText.html">Fragments:StructuredText</a></li><li><a href="Fragments_Text.html">Fragments:Text</a></li><li><a href="Fragments_Timestamp.html">Fragments:Timestamp</a></li><li><a href="Fragments_WebLink.html">Fragments:WebLink</a></li><li><a href="Ref.html">Ref</a></li><li><a href="Response.html">Response</a></li><li><a href="SearchForm.html">SearchForm</a></li><li><a href="WithFragments.html">WithFragments</a></li></ul><h3>Namespaces</h3><ul><li><a href="Predicates.html">Predicates</a></li></ul><h3>Global</h3><ul><li><a href="global.html#ApiCache">ApiCache</a></li><li><a href="global.html#data">data</a></li><li><a href="global.html#fragments">fragments</a></li><li><a href="global.html#insertSpans">insertSpans</a></li><li><a href="global.html#LRUCache">LRUCache</a></li><li><a href="global.html#parseDoc">parseDoc</a></li></ul>
</nav>
<br class="clear">
<footer>
Documentation generated by <a href="https://github.com/jsdoc3/jsdoc">JSDoc 3.4.3</a> on Mon Oct 02 2017 12:18:09 GMT+0200 (CEST)
</footer>
<script> prettyPrint(); </script>
<script src="scripts/linenumber.js"> </script>
</body>
</html>