PoC LRU cache

example.js

var cache = new LRU({
  maxLimit: 1000
})

console.log(Date.now())
var entries = []

for (var i=0; i< 10000; i++) {
  entries.push({key: 'test'+i, val: 'test'+i})
}

console.log('Loading cache')
loadCache(0, entries)
console.log(Date.now())

var res = cache.match(/^test/i)
console.log(res)
console.log(Date.now())

function loadCache (init, entries) {
  if (init >= entries.length) {
    var res = cache.match(/^test/i)
    console.log(res)

    console.log('Done cache loading')
    return;
  }

  var max = init + Math.min(entries.length - init, 50)

  for (i = init; i < max; i++) {
    cache.add(entries[i].key, entries[i].val)
  }

  setTimeout(function(){
    loadCache(max, entries)
  }, 50)
}

LRU.js

(function (exports) {
  
  var keys = Object.keys || function(o) {
    var result = [];
    for(var name in o) {
        if (o.hasOwnProperty(name))
          result.push(name);
    }
    return result;
  };

  exports.LRU = function (options) {
    if (!(this instanceof LRU)) {
      return new LRU(options);
    }

    var cache = {};
    options.maxLimit = options.maxLimit || 100;

    this.cleanCache = function () {
      var entryKeys = keys(cache),
          candidate = cache[entryKeys[0]],
          toRemove = entryKeys.length - options.maxLimit;

      while (toRemove > 0) {
        var candidate = this.tail;
        this.tail = candidate.newer;
        this.tail.older = undefined;
        delete(cache[candidate.key]);
        toRemove--;
      }
    }

    this.add = function (key, val) {
      var entry = cache[key] ? cache[key] : {key: key};

      cache[key] = entry;
      entry.val = val;

      this.updateEntry(entry);
      this.cleanCache();
    }

    this.match = function (regex) {
      var result = [];

      for (var key in cache) {
        if (regex.test(key)) {
          result.push(cache[key].val);
          this.updateEntry(cache[key]);
        }
      }

      return result;
    }

    this.updateEntry = function (entry) {
      // if it is the first, nothing to do
      if (entry === this.head) return;
      // Take the entry from his position and make it the first
      var newer = entry.newer,
          older = entry.older;

      if (newer) newer.older = older;
      if (older) older.newer = newer;

      // Make the entry the first in the list
      entry.older = this.head;
      if (this.head) this.head.newer = entry;
      this.head = entry;

      // if empty cache, set the tail
      if (!this.tail) this.tail = entry;
    }

    /* //Debugging purpose
    this.dumpCache = function () {
      var it = this.head;
      while (it) {
        console.log(it.val);
        it = it.older;
      }
    }*/
  }

})(window)