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 | }
|