Created
December 22, 2016 19:28
-
-
Save ericso/b4ce730d4aa80b37d0297b7c2e559914 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Least Recently Used cache | |
// Implement a data structure to store keys for a LRU cache | |
/* | |
doubly linked list to hold order of keys | |
front of list is the most recently used key | |
back of list is the least recently used key | |
dictionary holds references to each node in the linked list | |
keys are the keys being held | |
values are pointers to the nodes | |
node structure | |
var cacheNode = { | |
data: 'key', | |
previous: null, | |
next: null, | |
}; | |
The LRU Cache implements two methods: | |
get(key) - | |
if the key is not in the cache, return null | |
if the key is in the cache, return the value for that key and | |
move the node representing that key's position to the front of the list | |
set(key, value) - | |
if the key is already in the cache, replace the value for that key and | |
move that node to the front of the list | |
if the key is not in the cache and the cache is not full, add that key to | |
the front of the list | |
if the key is not in the cache and the cache is full, delete the least | |
recently used key and add the new key to the front of the list | |
*/ | |
function Cache(max) { | |
this.cacheStore = {}; | |
this.cachePointers = {}; | |
this.firstNode = null; | |
this.lastNode = null; | |
this.maxNodes = max; | |
} | |
Cache.prototype.newNode = function(data, previous, next) { | |
return { | |
data: data, | |
previous: prev, | |
next: next, | |
}; | |
} | |
Cache.prototype.get = function(key) { | |
if (key in this.cachePointers) { | |
/* Move the corresponding node to the front of the list */ | |
var currentNode = this.cachePointers[key]; | |
// Splice out the node | |
currentNode.previous.next = currentNode.next; | |
// Move the node to the front | |
this.firstNode.previous = currentNode; | |
this.firstNode = currentNode; | |
return this.cacheStore[key]; | |
} else { | |
return -1; | |
} | |
}; | |
Cache.prototype.set = function(key, value) { | |
if (Object.keys(this.cachePointers).length === this.maxNodes) { | |
// Delete the least recently used key | |
this.lastNode = this.lastNode.previous; | |
// Potential memory leak? Do we need to delete the old node? | |
} | |
/* Store the new value */ | |
if (key in this.cachePointers) { | |
/* Move the corresponding node to the front of the list */ | |
var currentNode = this.cachePointers[key]; | |
// Splice out the node | |
currentNode.previous.next = currentNode.next; | |
// Move the node to the front | |
this.firstNode.previous = currentNode; | |
this.firstNode = currentNode; | |
this.cacheStore[key] = value; | |
} else { | |
// Create a new node | |
var newNode = this.newNode(key, null, this.firstNode); | |
// If firstNode is null, that means the cache is empty | |
if (this.firstNode === null) { | |
// Set the lastNode to point to the new node | |
this.lastNode = newNode; | |
} else { | |
// Set the old first node's prev pointer to the new node | |
this.firstNode.previous = newNode; | |
} | |
// Set the new node's next pointer to the previous first node | |
newNode.next = this.firstNode; | |
// Set the first node pointer to the new node | |
this.firstNode = newNode; | |
// Store the key,value pair in the cache and the pointer to the node | |
this.cacheStore[key] = value; | |
this.cachePointers[key] = newNode; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment