twitst4tz

twitter statistics web application
Log | Files | Refs | README | LICENSE

lru.js (1914B)


      1 module.exports = function(size) {
      2   return new LruCache(size)
      3 }
      4 
      5 function LruCache(size) {
      6   this.capacity = size | 0
      7   this.map = Object.create(null)
      8   this.list = new DoublyLinkedList()
      9 }
     10 
     11 LruCache.prototype.get = function(key) {
     12   var node = this.map[key]
     13   if (node == null) return undefined
     14   this.used(node)
     15   return node.val
     16 }
     17 
     18 LruCache.prototype.set = function(key, val) {
     19   var node = this.map[key]
     20   if (node != null) {
     21     node.val = val
     22   } else {
     23     if (!this.capacity) this.prune()
     24     if (!this.capacity) return false
     25     node = new DoublyLinkedNode(key, val)
     26     this.map[key] = node
     27     this.capacity--
     28   }
     29   this.used(node)
     30   return true
     31 }
     32 
     33 LruCache.prototype.used = function(node) {
     34   this.list.moveToFront(node)
     35 }
     36 
     37 LruCache.prototype.prune = function() {
     38   var node = this.list.pop()
     39   if (node != null) {
     40     delete this.map[node.key]
     41     this.capacity++
     42   }
     43 }
     44 
     45 
     46 function DoublyLinkedList() {
     47   this.firstNode = null
     48   this.lastNode = null
     49 }
     50 
     51 DoublyLinkedList.prototype.moveToFront = function(node) {
     52   if (this.firstNode == node) return
     53 
     54   this.remove(node)
     55 
     56   if (this.firstNode == null) {
     57     this.firstNode = node
     58     this.lastNode = node
     59     node.prev = null
     60     node.next = null
     61   } else {
     62     node.prev = null
     63     node.next = this.firstNode
     64     node.next.prev = node
     65     this.firstNode = node
     66   }
     67 }
     68 
     69 DoublyLinkedList.prototype.pop = function() {
     70   var lastNode = this.lastNode
     71   if (lastNode != null) {
     72     this.remove(lastNode)
     73   }
     74   return lastNode
     75 }
     76 
     77 DoublyLinkedList.prototype.remove = function(node) {
     78   if (this.firstNode == node) {
     79     this.firstNode = node.next
     80   } else if (node.prev != null) {
     81     node.prev.next = node.next
     82   }
     83   if (this.lastNode == node) {
     84     this.lastNode = node.prev
     85   } else if (node.next != null) {
     86     node.next.prev = node.prev
     87   }
     88 }
     89 
     90 
     91 function DoublyLinkedNode(key, val) {
     92   this.key = key
     93   this.val = val
     94   this.prev = null
     95   this.next = null
     96 }