--- /dev/null
+/**\r
+ * A doubly linked list-based Least Recently Used (LRU) cache. Will keep most\r
+ * recently used items while discarding least recently used items when its limit\r
+ * is reached.\r
+ *\r
+ * Licensed under MIT. Copyright (c) 2010 Rasmus Andersson <http://hunch.se/>\r
+ * See README.md for details.\r
+ *\r
+ * Illustration of the design:\r
+ *\r
+ * entry entry entry entry\r
+ * ______ ______ ______ ______\r
+ * | head |.newer => | |.newer => | |.newer => | tail |\r
+ * | A | | B | | C | | D |\r
+ * |______| <= older.|______| <= older.|______| <= older.|______|\r
+ *\r
+ * removed <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- added\r
+ */\r
+function LRUCache (limit) {\r
+ // Current size of the cache. (Read-only).\r
+ this.size = 0;\r
+ // Maximum number of items this cache can hold.\r
+ this.limit = limit;\r
+ this._keymap = {};\r
+}\r
+\r
+/**\r
+ * Put <value> into the cache associated with <key>. Returns the entry which was\r
+ * removed to make room for the new entry. Otherwise undefined is returned\r
+ * (i.e. if there was enough room already).\r
+ */\r
+LRUCache.prototype.put = function(key, value) {\r
+ var entry = {key:key, value:value};\r
+ // Note: No protection agains replacing, and thus orphan entries. By design.\r
+ this._keymap[key] = entry;\r
+ if (this.tail) {\r
+ // link previous tail to the new tail (entry)\r
+ this.tail.newer = entry;\r
+ entry.older = this.tail;\r
+ } else {\r
+ // we're first in -- yay\r
+ this.head = entry;\r
+ }\r
+ // add new entry to the end of the linked list -- it's now the freshest entry.\r
+ this.tail = entry;\r
+ if (this.size === this.limit) {\r
+ // we hit the limit -- remove the head\r
+ return this.shift();\r
+ } else {\r
+ // increase the size counter\r
+ this.size++;\r
+ }\r
+}\r
+\r
+/**\r
+ * Purge the least recently used (oldest) entry from the cache. Returns the\r
+ * removed entry or undefined if the cache was empty.\r
+ *\r
+ * If you need to perform any form of finalization of purged items, this is a\r
+ * good place to do it. Simply override/replace this function:\r
+ *\r
+ * var c = new LRUCache(123);\r
+ * c.shift = function() {\r
+ * var entry = LRUCache.prototype.shift.call(this);\r
+ * doSomethingWith(entry);\r
+ * return entry;\r
+ * }\r
+ */\r
+LRUCache.prototype.shift = function() {\r
+ // todo: handle special case when limit == 1\r
+ var entry = this.head;\r
+ if (entry) {\r
+ if (this.head.newer) {\r
+ this.head = this.head.newer;\r
+ this.head.older = undefined;\r
+ } else {\r
+ this.head = undefined;\r
+ }\r
+ // Remove last strong reference to <entry> and remove links from the purged\r
+ // entry being returned:\r
+ entry.newer = entry.older = undefined;\r
+ // delete is slow, but we need to do this to avoid uncontrollable growth:\r
+ delete this._keymap[entry.key];\r
+ }\r
+ return entry;\r
+}\r
+\r
+/**\r
+ * Get and register recent use of <key>. Returns the value associated with <key>\r
+ * or undefined if not in cache.\r
+ */\r
+LRUCache.prototype.get = function(key, returnEntry) {\r
+ // First, find our cache entry\r
+ var entry = this._keymap[key];\r
+ if (entry === undefined) return; // Not cached. Sorry.\r
+ // As <key> was found in the cache, register it as being requested recently\r
+ if (entry === this.tail) {\r
+ // Already the most recenlty used entry, so no need to update the list\r
+ return entry.value;\r
+ }\r
+ // HEAD--------------TAIL\r
+ // <.older .newer>\r
+ // <--- add direction --\r
+ // A B C <D> E\r
+ if (entry.newer) {\r
+ if (entry === this.head)\r
+ this.head = entry.newer;\r
+ entry.newer.older = entry.older; // C <-- E.\r
+ }\r
+ if (entry.older)\r
+ entry.older.newer = entry.newer; // C. --> E\r
+ entry.newer = undefined; // D --x\r
+ entry.older = this.tail; // D. --> E\r
+ if (this.tail)\r
+ this.tail.newer = entry; // E. <-- D\r
+ this.tail = entry;\r
+ return returnEntry ? entry : entry.value;\r
+}\r
+\r
+// ----------------------------------------------------------------------------\r
+// Following code is optional and can be removed without breaking the core\r
+// functionality.\r
+\r
+/**\r
+ * Check if <key> is in the cache without registering recent use. Feasible if\r
+ * you do not want to chage the state of the cache, but only "peek" at it.\r
+ * Returns the entry associated with <key> if found, or undefined if not found.\r
+ */\r
+LRUCache.prototype.find = function(key) {\r
+ return this._keymap[key];\r
+}\r
+\r
+/**\r
+ * Update the value of entry with <key>. Returns the old value, or undefined if\r
+ * entry was not in the cache.\r
+ */\r
+LRUCache.prototype.set = function(key, value) {\r
+ var oldvalue, entry = this.get(key, true);\r
+ if (entry) {\r
+ oldvalue = entry.value;\r
+ entry.value = value;\r
+ } else {\r
+ oldvalue = this.put(key, value);\r
+ if (oldvalue) oldvalue = oldvalue.value;\r
+ }\r
+ return oldvalue;\r
+}\r
+\r
+/**\r
+ * Remove entry <key> from cache and return its value. Returns undefined if not\r
+ * found.\r
+ */\r
+LRUCache.prototype.remove = function(key) {\r
+ var entry = this._keymap[key];\r
+ if (!entry) return;\r
+ delete this._keymap[entry.key]; // need to do delete unfortunately\r
+ if (entry.newer && entry.older) {\r
+ // relink the older entry with the newer entry\r
+ entry.older.newer = entry.newer;\r
+ entry.newer.older = entry.older;\r
+ } else if (entry.newer) {\r
+ // remove the link to us\r
+ entry.newer.older = undefined;\r
+ // link the newer entry to head\r
+ this.head = entry.newer;\r
+ } else if (entry.older) {\r
+ // remove the link to us\r
+ entry.older.newer = undefined;\r
+ // link the newer entry to head\r
+ this.tail = entry.older;\r
+ } else {// if(entry.older === undefined && entry.newer === undefined) {\r
+ this.head = this.tail = undefined;\r
+ }\r
+\r
+ this.size--;\r
+ return entry.value;\r
+}\r
+\r
+/** Removes all entries */\r
+LRUCache.prototype.removeAll = function() {\r
+ // This should be safe, as we never expose strong refrences to the outside\r
+ this.head = this.tail = undefined;\r
+ this.size = 0;\r
+ this._keymap = {};\r
+}\r
+\r
+/**\r
+ * Return an array containing all keys of entries stored in the cache object, in\r
+ * arbitrary order.\r
+ */\r
+if (typeof Object.keys === 'function') {\r
+ LRUCache.prototype.keys = function() { return Object.keys(this._keymap); }\r
+} else {\r
+ LRUCache.prototype.keys = function() {\r
+ var keys = [];\r
+ for (var k in this._keymap) keys.push(k);\r
+ return keys;\r
+ }\r
+}\r
+\r
+/**\r
+ * Call `fun` for each entry. Starting with the newest entry if `desc` is a true\r
+ * value, otherwise starts with the oldest (head) enrty and moves towards the\r
+ * tail.\r
+ *\r
+ * `fun` is called with 3 arguments in the context `context`:\r
+ * `fun.call(context, Object key, Object value, LRUCache self)`\r
+ */\r
+LRUCache.prototype.forEach = function(fun, context, desc) {\r
+ if (context === true) { desc = true; context = undefined; }\r
+ else if (typeof context !== 'object') context = this;\r
+ if (desc) {\r
+ var entry = this.tail;\r
+ while (entry) {\r
+ fun.call(context, entry.key, entry.value, this);\r
+ entry = entry.older;\r
+ }\r
+ } else {\r
+ var entry = this.head;\r
+ while (entry) {\r
+ fun.call(context, entry.key, entry.value, this);\r
+ entry = entry.newer;\r
+ }\r
+ }\r
+}\r
+\r
+/** Returns a JSON (array) representation */\r
+LRUCache.prototype.toJSON = function() {\r
+ var s = [], entry = this.head;\r
+ while (entry) {\r
+ s.push({key:entry.key.toJSON(), value:entry.value.toJSON()});\r
+ entry = entry.newer;\r
+ }\r
+ return s;\r
+}\r
+\r
+/** Returns a String representation */\r
+LRUCache.prototype.toString = function() {\r
+ var s = '', entry = this.head;\r
+ while (entry) {\r
+ s += String(entry.key)+':'+entry.value;\r
+ if (entry = entry.newer)\r
+ s += ' < ';\r
+ }\r
+ return s;\r
+}\r
+\r
+// Export ourselves\r
+if (typeof this === 'object') this.LRUCache = LRUCache;\r
projects / openlib.git / blobdiff