www/resources/lru/lru.js

   1 /**\r
   2  * A doubly linked list-based Least Recently Used (LRU) cache. Will keep most\r
   3  * recently used items while discarding least recently used items when its limit\r
   4  * is reached.\r
   5  *\r
   6  * Licensed under MIT. Copyright (c) 2010 Rasmus Andersson <http://hunch.se/>\r
   7  * See README.md for details.\r
   8  *\r
   9  * Illustration of the design:\r
  10  *\r
  11  *       entry             entry             entry             entry\r
  12  *       ______            ______            ______            ______\r
  13  *      | head |.newer => |      |.newer => |      |.newer => | tail |\r
  14  *      |  A   |          |  B   |          |  C   |          |  D   |\r
  15  *      |______| <= older.|______| <= older.|______| <= older.|______|\r
  16  *\r
  17  *  removed  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  added\r
  18  */\r
  19 function LRUCache (limit) {\r
  20   // Current size of the cache. (Read-only).\r
  21   this.size = 0;\r
  22   // Maximum number of items this cache can hold.\r
  23   this.limit = limit;\r
  24   this._keymap = {};\r
  25 }\r
  26 \r
  27 /**\r
  28  * Put <value> into the cache associated with <key>. Returns the entry which was\r
  29  * removed to make room for the new entry. Otherwise undefined is returned\r
  30  * (i.e. if there was enough room already).\r
  31  */\r
  32 LRUCache.prototype.put = function(key, value) {\r
  33   var entry = {key:key, value:value};\r
  34   // Note: No protection agains replacing, and thus orphan entries. By design.\r
  35   this._keymap[key] = entry;\r
  36   if (this.tail) {\r
  37     // link previous tail to the new tail (entry)\r
  38     this.tail.newer = entry;\r
  39     entry.older = this.tail;\r
  40   } else {\r
  41     // we're first in -- yay\r
  42     this.head = entry;\r
  43   }\r
  44   // add new entry to the end of the linked list -- it's now the freshest entry.\r
  45   this.tail = entry;\r
  46   if (this.size === this.limit) {\r
  47     // we hit the limit -- remove the head\r
  48     return this.shift();\r
  49   } else {\r
  50     // increase the size counter\r
  51     this.size++;\r
  52   }\r
  53 }\r
  54 \r
  55 /**\r
  56  * Purge the least recently used (oldest) entry from the cache. Returns the\r
  57  * removed entry or undefined if the cache was empty.\r
  58  *\r
  59  * If you need to perform any form of finalization of purged items, this is a\r
  60  * good place to do it. Simply override/replace this function:\r
  61  *\r
  62  *   var c = new LRUCache(123);\r
  63  *   c.shift = function() {\r
  64  *     var entry = LRUCache.prototype.shift.call(this);\r
  65  *     doSomethingWith(entry);\r
  66  *     return entry;\r
  67  *   }\r
  68  */\r
  69 LRUCache.prototype.shift = function() {\r
  70   // todo: handle special case when limit == 1\r
  71   var entry = this.head;\r
  72   if (entry) {\r
  73     if (this.head.newer) {\r
  74       this.head = this.head.newer;\r
  75       this.head.older = undefined;\r
  76     } else {\r
  77       this.head = undefined;\r
  78     }\r
  79     // Remove last strong reference to <entry> and remove links from the purged\r
  80     // entry being returned:\r
  81     entry.newer = entry.older = undefined;\r
  82     // delete is slow, but we need to do this to avoid uncontrollable growth:\r
  83     delete this._keymap[entry.key];\r
  84   }\r
  85   return entry;\r
  86 }\r
  87 \r
  88 /**\r
  89  * Get and register recent use of <key>. Returns the value associated with <key>\r
  90  * or undefined if not in cache.\r
  91  */\r
  92 LRUCache.prototype.get = function(key, returnEntry) {\r
  93   // First, find our cache entry\r
  94   var entry = this._keymap[key];\r
  95   if (entry === undefined) return; // Not cached. Sorry.\r
  96   // As <key> was found in the cache, register it as being requested recently\r
  97   if (entry === this.tail) {\r
  98     // Already the most recenlty used entry, so no need to update the list\r
  99     return entry.value;\r
 100   }\r
 101   // HEAD--------------TAIL\r
 102   //   <.older   .newer>\r
 103   //  <--- add direction --\r
 104   //   A  B  C  <D>  E\r
 105   if (entry.newer) {\r
 106     if (entry === this.head)\r
 107       this.head = entry.newer;\r
 108     entry.newer.older = entry.older; // C <-- E.\r
 109   }\r
 110   if (entry.older)\r
 111     entry.older.newer = entry.newer; // C. --> E\r
 112   entry.newer = undefined; // D --x\r
 113   entry.older = this.tail; // D. --> E\r
 114   if (this.tail)\r
 115     this.tail.newer = entry; // E. <-- D\r
 116   this.tail = entry;\r
 117   return returnEntry ? entry : entry.value;\r
 118 }\r
 119 \r
 120 // ----------------------------------------------------------------------------\r
 121 // Following code is optional and can be removed without breaking the core\r
 122 // functionality.\r
 123 \r
 124 /**\r
 125  * Check if <key> is in the cache without registering recent use. Feasible if\r
 126  * you do not want to chage the state of the cache, but only "peek" at it.\r
 127  * Returns the entry associated with <key> if found, or undefined if not found.\r
 128  */\r
 129 LRUCache.prototype.find = function(key) {\r
 130   return this._keymap[key];\r
 131 }\r
 132 \r
 133 /**\r
 134  * Update the value of entry with <key>. Returns the old value, or undefined if\r
 135  * entry was not in the cache.\r
 136  */\r
 137 LRUCache.prototype.set = function(key, value) {\r
 138   var oldvalue, entry = this.get(key, true);\r
 139   if (entry) {\r
 140     oldvalue = entry.value;\r
 141     entry.value = value;\r
 142   } else {\r
 143     oldvalue = this.put(key, value);\r
 144     if (oldvalue) oldvalue = oldvalue.value;\r
 145   }\r
 146   return oldvalue;\r
 147 }\r
 148 \r
 149 /**\r
 150  * Remove entry <key> from cache and return its value. Returns undefined if not\r
 151  * found.\r
 152  */\r
 153 LRUCache.prototype.remove = function(key) {\r
 154   var entry = this._keymap[key];\r
 155   if (!entry) return;\r
 156   delete this._keymap[entry.key]; // need to do delete unfortunately\r
 157   if (entry.newer && entry.older) {\r
 158     // relink the older entry with the newer entry\r
 159     entry.older.newer = entry.newer;\r
 160     entry.newer.older = entry.older;\r
 161   } else if (entry.newer) {\r
 162     // remove the link to us\r
 163     entry.newer.older = undefined;\r
 164     // link the newer entry to head\r
 165     this.head = entry.newer;\r
 166   } else if (entry.older) {\r
 167     // remove the link to us\r
 168     entry.older.newer = undefined;\r
 169     // link the newer entry to head\r
 170     this.tail = entry.older;\r
 171   } else {// if(entry.older === undefined && entry.newer === undefined) {\r
 172     this.head = this.tail = undefined;\r
 173   }\r
 174 \r
 175   this.size--;\r
 176   return entry.value;\r
 177 }\r
 178 \r
 179 /** Removes all entries */\r
 180 LRUCache.prototype.removeAll = function() {\r
 181   // This should be safe, as we never expose strong refrences to the outside\r
 182   this.head = this.tail = undefined;\r
 183   this.size = 0;\r
 184   this._keymap = {};\r
 185 }\r
 186 \r
 187 /**\r
 188  * Return an array containing all keys of entries stored in the cache object, in\r
 189  * arbitrary order.\r
 190  */\r
 191 if (typeof Object.keys === 'function') {\r
 192   LRUCache.prototype.keys = function() { return Object.keys(this._keymap); }\r
 193 } else {\r
 194   LRUCache.prototype.keys = function() {\r
 195     var keys = [];\r
 196     for (var k in this._keymap) keys.push(k);\r
 197     return keys;\r
 198   }\r
 199 }\r
 200 \r
 201 /**\r
 202  * Call `fun` for each entry. Starting with the newest entry if `desc` is a true\r
 203  * value, otherwise starts with the oldest (head) enrty and moves towards the\r
 204  * tail.\r
 205  *\r
 206  * `fun` is called with 3 arguments in the context `context`:\r
 207  *   `fun.call(context, Object key, Object value, LRUCache self)`\r
 208  */\r
 209 LRUCache.prototype.forEach = function(fun, context, desc) {\r
 210   if (context === true) { desc = true; context = undefined; }\r
 211   else if (typeof context !== 'object') context = this;\r
 212   if (desc) {\r
 213     var entry = this.tail;\r
 214     while (entry) {\r
 215       fun.call(context, entry.key, entry.value, this);\r
 216       entry = entry.older;\r
 217     }\r
 218   } else {\r
 219     var entry = this.head;\r
 220     while (entry) {\r
 221       fun.call(context, entry.key, entry.value, this);\r
 222       entry = entry.newer;\r
 223     }\r
 224   }\r
 225 }\r
 226 \r
 227 /** Returns a JSON (array) representation */\r
 228 LRUCache.prototype.toJSON = function() {\r
 229   var s = [], entry = this.head;\r
 230   while (entry) {\r
 231     s.push({key:entry.key.toJSON(), value:entry.value.toJSON()});\r
 232     entry = entry.newer;\r
 233   }\r
 234   return s;\r
 235 }\r
 236 \r
 237 /** Returns a String representation */\r
 238 LRUCache.prototype.toString = function() {\r
 239   var s = '', entry = this.head;\r
 240   while (entry) {\r
 241     s += String(entry.key)+':'+entry.value;\r
 242     if (entry = entry.newer)\r
 243       s += ' < ';\r
 244   }\r
 245   return s;\r
 246 }\r
 247 \r
 248 // Export ourselves\r
 249 if (typeof this === 'object') this.LRUCache = LRUCache;\r