Simple cache for Node.js

cache.js

'use strict';

var
  EventEmitter = require('events').EventEmitter,
  util = require('util'),
  log = require('./log'),

  DEFAULT_OPTIONS = { capacity: 200, evictionCount: 10 };

function Cache(options) {
  if (!(this instanceof Cache)) { return new Cache(options); }

  EventEmitter.call(this);

  if (typeof options === 'number') { options = { capacity: options }; }
  if (!options) { options = DEFAULT_OPTIONS; }

  this._capacity = options.capacity || 200; // maximum number of items that can be stored
  if (this._capacity <= 0) { throw new Error('cannot create a cache with no capacity'); }

  this._evictionCount = options.evictionCount || Math.ceil(this._capacity * 5 / 100);
  if (this._evictionCount <= 0) {
    this._evictionCount = Math.ceil(this._capacity * 5 / 100); // when cache full, evict 5% of the cached items
    log.warn('Cannot create a cache with negative eviction batch size; using', this._evictionCount,
             '(5%) of the capacity');
  }

  this._size = 0;
  this._head = this._tail = null;    // double-ended queue to maintain a 'least recently used' order
  this._items = Object.create(null); // dict pattern
}
Cache.prototype = Object.create(EventEmitter.prototype);
Cache.prototype.constructor = Cache;

Cache.prototype.get = function(key) {
  var item = this._items[key];
  if (item !== undefined && item !== null) { // cache hit
    log.debug('Retrieving cached value @ key', key);

    if (item !== this._head) {   // update head
      item._prev._next = item._next;

      if (item !== this._tail) {
        item._next._prev = item._prev;
      } else {
        this._tail = item._prev; // move tail
      }

      item._prev = null;
      item._next = this._head;
      this._head._prev = item;
      this._head = item;
    }

    return item._value;
  }
};

Cache.prototype.set = function(key, value) {
  var item = this._items[key];

  if (item !== undefined && item !== null) { // cache hit => evict previous value, set new value and promote as head
    log.debug('Replacing cached value @ key', key);

    try {
      this.emit('eviction', item._key, item._value);
    } catch (err) {
      log.error(err, 'An error has occurred while evicting cached value @ key', item._key);
    }
    item._value = value;

    if (item !== this._head) {   // update head
      item._prev._next = item._next;

      if (item !== this._tail) {
        item._next._prev = item._prev;
      } else {
        this._tail = item._prev; // move tail
      }

      item._prev = null;
      item._next = this._head;
      this._head._prev = item;
      this._head = item;
    }
  } else {
    if (this._size === this._capacity) { // capacity reached => evict least recently used value(s)
      log.debug('Cache full; evicting least recently used value(s)');
      this.evict();
    }

    if (this._size === 0) {
      log.debug('Caching first value @ key', key);
      this._items[key] = this._head = this._tail = {_key: key, _value: value, _prev: null, _next: null};
    } else {
      log.debug('Caching a new value @ key', key);
      this._items[key] = this._head = this._head._prev = {_key: key, _value: value, _prev: null, _next: this._head};
    }

    this._size++;
  }
};

Cache.prototype.evict = function(howMany) {
  var item;

  if (!howMany || howMany <= 0) {
    howMany = this._evictionCount;
  }
  if (howMany > this._size) {
    log.warn('Cannot evict more (' + howMany + ') than the number of cached items; evicting', this._size,
             '(all of them)');
    howMany = this._size;
  }
  log.debug('Evicting', howMany, 'cached item(s)');

  while (howMany-- > 0 && (item = this._tail) !== null) {
    try {
      this.emit('eviction', item._key, item._value); // give a chance to clean up
    } catch (err) {
      log.error(err, 'An error has occurred while evicting cached value @ key', item._key);
    }

    delete this._items[item._key];
    if ((this._tail = item._prev) !== null) {
      this._tail._next = null;
    } else {
      this._head = null;
    }

    item._key = item._value = item._prev = item._next = null;
    this._size--;
  }
};

Cache.prototype.toString = function() {
  var values = [], item;

  for (item = this._head; item !== null; item = item._next) {
    values.push(item._key + ': ' + item._value);
  }

  return '[' + values.join(', ') + ']';
};

module.exports = Cache;