source: trip-planner-front/node_modules/aws4/lru.js@ 76712b2

Last change on this file since 76712b2 was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • Property mode set to 100644
File size: 1.9 KB
Line 
1module.exports = function(size) {
2 return new LruCache(size)
3}
4
5function LruCache(size) {
6 this.capacity = size | 0
7 this.map = Object.create(null)
8 this.list = new DoublyLinkedList()
9}
10
11LruCache.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
18LruCache.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
33LruCache.prototype.used = function(node) {
34 this.list.moveToFront(node)
35}
36
37LruCache.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
46function DoublyLinkedList() {
47 this.firstNode = null
48 this.lastNode = null
49}
50
51DoublyLinkedList.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
69DoublyLinkedList.prototype.pop = function() {
70 var lastNode = this.lastNode
71 if (lastNode != null) {
72 this.remove(lastNode)
73 }
74 return lastNode
75}
76
77DoublyLinkedList.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
91function DoublyLinkedNode(key, val) {
92 this.key = key
93 this.val = val
94 this.prev = null
95 this.next = null
96}
Note: See TracBrowser for help on using the repository browser.