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 }