lru.js 1.9 KB

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