lru - npm Package Compare versions

Comparing version 0.2.0 to 0.2.2

index.js

@@ -15,10 +15,15 @@ var events = require('events');
     var element = this.cache[key];
+
     if(element) {
         delete this.cache[key];
+
         --this.length;
+
         if(element.prev) this.cache[element.prev].next = element.next;
         if(element.next) this.cache[element.next].prev = element.prev;
+
         if(this.head == key) {
             this.head = element.prev;
         }
+
         if(this.tail == key) {
@@ -32,11 +37,24 @@ this.tail = element.next;
 LRU.prototype.set = function (key, value) {
-    element = this.remove(key);
-    element = element || { value:value };
+    if( this.cache.hasOwnProperty(key) ) {
+        element = this.cache[key]
+        element.value = value
 
-    element.value = value
+        // If it's already the head, there's nothing more to do:
+        if( key === this.head ) {
+            return value;
+        }
+    } else {
+        element = { value:value };
+
+        this.cache[key] = element;
+
+        // Eviction is only possible if the key didn't already exist:
+        if (++this.length > this.max) {
+            this.evict();
+        }
+    }
+
     element.next = null;
     element.prev = this.head;
 
-    this.cache[key] = element;
-
     if (this.head) {
@@ -51,6 +69,2 @@ this.cache[this.head].next = key;
 
-    if (++this.length > this.max) {
-        this.evict();
-    }
-
     return value
@@ -63,3 +77,21 @@ };
 
-    this.set(key, element.value);
+    if( this.length > 1 ) {
+        // Tail only changes if this was the tail:
+        if( key === this.tail ) this.tail = element.next
+
+        if( this.head !== key ) {
+            // Set prev -> next:
+            if( element.prev ) this.cache[element.prev].next = element.next
+
+            // Set prevhead->next:
+            if( this.head ) this.cache[this.head].next = key
+        }
+
+        // Set next -> prev:
+        if( element.next ) this.cache[element.next].prev = element.prev
+
+        // Set new head:
+        this.head = key
+    }
+
     return element.value;
@@ -66,0 +98,0 @@ };

package.json

 {
   "name": "lru",
   "description": "A simple O(1) LRU cache",
-  "version": "0.2.0",
+  "version": "0.2.2",
   "author": "Chris O'Hara <[e-mail]>",
@@ -6,0 +6,0 @@ "main": "index",

README.md

@@ -0,1 +1,3 @@
+# lru
+
 **A simple LRU cache supporting O(1) set, get and eviction of old keys**
@@ -9,3 +11,3 @@
 
-### Usage
+### Example
 
@@ -15,8 +17,44 @@ ```javascript
 
-var cache = new LRU(10);
+var cache = new LRU(2),
+    evicted
 
+cache.on('evict',function(data) { evicted = data });
+
 cache.set('foo', 'bar');
 cache.get('foo'); //=> bar
+
+cache.set('foo2', 'bar2');
+cache.get('foo2'); //=> bar2
+
+cache.set('foo3', 'bar3');
+cache.get('foo3'); //=> bar3,  evicted = { key: 'foo', value: 'bar' }
 ```
 
+### API
+
+#### `require('lru').LRU( length )`
+Create a new LRU cache that stores `length` elements before evicting the least recently used.
+
+**Returns**: the newly created LRU cache
+
+
+#### Methods
+
+##### `.set( key, value )`
+Set the value of the key and mark the key as most recently used.
+
+**Returns**: `value`
+
+##### `.set( key, value )`
+Set the value of the key and mark the key as most recently used.
+
+##### `.get( key )`
+Query the value of the key and mark the key as most recently used.
+
+**Returns**: value of key if found; `undefined` otherwise.
+
+##### `.on( event, callback )`
+Respond to events. Currently only the `evict` event is implemented. When a key is evicted, the callback is executed with an associative array containing the evicted key: `{key: key, value: value}`.
+
+
 ### Credits
@@ -27,1 +65,4 @@
 
+### License
+
+MIT

test/lru-test.js

 var assert = require('assert');
 var vows = require('vows');
-var LRU = require('../index');
+var LRU = require('../').LRU;
 
@@ -19,3 +19,3 @@ function keys(obj) {
   "setting keys doesn't grow past max size": function() {
-    var lru = new LRU.LRU(3);
+    var lru = new LRU(3);
     assert.equal(0, lru.length);
@@ -35,4 +35,16 @@ lru.set('foo1', 'bar1');
 suite.addBatch({
+  "setting keys returns the value": function() {
+    var lru = new LRU(2);
+    assert.equal('bar1', lru.set('foo1', 'bar1'));
+    assert.equal('bar2', lru.set('foo2', 'bar2'));
+    assert.equal('bar3', lru.set('foo3', 'bar3'));
+    assert.equal('bar2', lru.get('foo2'));
+    assert.equal(undefined, lru.get('foo1'));
+    assert.equal('bar1', lru.set('foo1','bar1'));
+  }
+});
+
+suite.addBatch({
   "lru invariant is maintained for set()": function() {
-    var lru = new LRU.LRU(2);
+    var lru = new LRU(2);
 
@@ -49,4 +61,14 @@ lru.set('foo1', 'bar1');
 suite.addBatch({
+  "ovrewriting a key updates the value": function() {
+    var lru = new LRU(2);
+    lru.set('foo1', 'bar1');
+    assert.equal('bar1', lru.get('foo1'))
+    lru.set('foo1', 'bar2');
+    assert.equal('bar2', lru.get('foo1'))
+  }
+})
+
+suite.addBatch({
   "lru invariant is maintained for get()": function() {
-    var lru = new LRU.LRU(2);
+    var lru = new LRU(2);
 
@@ -65,4 +87,31 @@ lru.set('foo1', 'bar1');
 suite.addBatch({
+  "lru invariant is maintained for get()": function() {
+    var lru = new LRU(2);
+
+    lru.set('foo1', 'bar1');
+    lru.set('foo2', 'bar2');
+
+    lru.get('foo2'); //now foo2 should be deleted instead of foo1
+
+    lru.set('foo3', 'bar3');
+
+    assert.deepEqual(['foo2','foo3'], keys(lru.cache));
+  },
+  "lru invariant is maintained in the corner case size == 1": function() {
+    var lru = new LRU(1);
+
+    lru.set('foo1', 'bar1');
+    lru.set('foo2', 'bar2');
+
+    lru.get('foo2'); //now foo2 should be deleted instead of foo1
+
+    lru.set('foo3', 'bar3');
+
+    assert.deepEqual(['foo3'], keys(lru.cache));
+  }
+});
+
+suite.addBatch({
   "get() returns item value": function() {
-    var lru = new LRU.LRU(2)
+    var lru = new LRU(2)
 
@@ -76,3 +125,3 @@ assert.equal( lru.set('foo','bar'), 'bar')
     "set() and remove() on empty LRU is idempotent": function() {
-      var lru = new LRU.LRU();
+      var lru = new LRU();
       var json1 = JSON.stringify(lru);
@@ -89,3 +138,3 @@
     "2 set()s and 2 remove()s on empty LRU is idempotent": function() {
-      var lru = new LRU.LRU();
+      var lru = new LRU();
       var json1 = JSON.stringify(lru);
@@ -103,3 +152,3 @@
     "2 set()s and 2 remove()s (in opposite order) on empty LRU is idempotent": function() {
-      var lru = new LRU.LRU();
+      var lru = new LRU();
       var json1 = JSON.stringify(lru);
@@ -117,3 +166,3 @@
     "after setting one key, get() is idempotent" : function() {
-      var lru = new LRU.LRU(2);
+      var lru = new LRU(2);
       lru.set('a', 'a');
@@ -129,3 +178,3 @@ var json1 = JSON.stringify(lru);
     "after setting two keys, get() on last-set key is idempotent" : function() {
-      var lru = new LRU.LRU(2);
+      var lru = new LRU(2);
       lru.set('a', 'a');
@@ -146,3 +195,3 @@ lru.set('b', 'b');
     "'evict' event is fired when evicting old keys": function() {
-      var lru = new LRU.LRU(2);
+      var lru = new LRU(2);
       var events = [];
@@ -163,2 +212,1 @@ lru.on('evict', function(element) { events.push(element); });
 suite.export(module);
-

No alert changes

Improved metrics

Total package byte prevSize

10560

increased by47.71%

Number of package files

7

increased by16.67%

Lines of code

245

increased by40%

Number of lines in readme file

66

increased by164%

No dependency changes