Created
July 21, 2020 16:27
-
-
Save sohamkamani/3ce4725647ee28b30b1477c03920eb3d to your computer and use it in GitHub Desktop.
An example of how to implement LRU cache with eviction using the HTML5 localStorage API
This file contains hidden or 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
| <!DOCTYPE html> | |
| <html lang="en"> | |
| <head> | |
| <meta charset="UTF-8" /> | |
| <meta name="viewport" content="width=device-width, initial-scale=1.0" /> | |
| <title>LocalStorage With LRU Eviction</title> | |
| </head> | |
| <body> | |
| <button id="btn-set">Set</button><br /> | |
| Key: <input id="input-set-key" /><br /> | |
| Value: <input id="input-set-val" /> <br /><br /> | |
| <button id="btn-get">Get</button><br /> | |
| Key: <input id="input-get-key" /><br /> | |
| <div>Value: <span id="value"></span></div> | |
| <div> | |
| <p>Keys (Ordered in ascending recency of use)</p> | |
| <p id="current-keys"></p> | |
| </div> | |
| <script> | |
| const headKeyName = "_nodelist_head" | |
| class NodeList { | |
| constructor() { | |
| this.head = null | |
| this.tail = null | |
| this.count = 0 | |
| } | |
| add(key) { | |
| const node = { key } | |
| return this.addNode(node) | |
| } | |
| setHead(node) { | |
| this.head = node | |
| if (!node) { | |
| localStorage.removeItem(headKeyName) | |
| } | |
| localStorage.setItem(headKeyName, node.key) | |
| } | |
| addNode(node) { | |
| this.count += 1 | |
| if (!this.head && !this.tail) { | |
| this.setHead(node) | |
| this.tail = node | |
| return node | |
| } | |
| this.tail.next = node | |
| node.prev = this.tail | |
| node.next = null | |
| this.tail = node | |
| return node | |
| } | |
| remove(node) { | |
| if (!node) { | |
| return | |
| } | |
| this.count -= 1 | |
| if (this.tail === node) { | |
| this.tail = node.prev | |
| } | |
| if (this.head === node) { | |
| this.setHead(node.next) | |
| } | |
| if (node.prev) { | |
| node.prev.next = node.next | |
| } | |
| if (node.next) { | |
| node.next.prev = node.prev | |
| } | |
| } | |
| pop() { | |
| if (!this.head) { | |
| return null | |
| } | |
| const node = this.head | |
| this.remove(this.head) | |
| return node | |
| } | |
| moveToTail(node) { | |
| this.remove(node) | |
| return this.addNode(node) | |
| } | |
| load() { | |
| const headKey = localStorage.getItem(headKeyName) | |
| if (!headKey) { | |
| return | |
| } | |
| const headNode = JSON.parse(localStorage.getItem(headKey)) | |
| let currentNode = headNode | |
| let currentKey = headKey | |
| while (currentNode) { | |
| this.add(currentKey) | |
| if (!currentNode.next) { | |
| return | |
| } | |
| currentKey = currentNode.next | |
| currentNode = JSON.parse( | |
| localStorage.getItem(currentKey) | |
| ) | |
| } | |
| } | |
| toString() { | |
| const values = [] | |
| let current = this.head | |
| while (current) { | |
| values.push(current.key) | |
| current = current.next | |
| } | |
| return values.join(",") | |
| } | |
| } | |
| function serializeNode(node, value) { | |
| return JSON.stringify({ | |
| value: value, | |
| next: node.next && node.next.key, | |
| prev: node.prev && node.prev.key, | |
| }) | |
| } | |
| function getNodeValue(nodeStr) { | |
| const node = JSON.parse(nodeStr) | |
| return node.value | |
| } | |
| class LocalStorageLRU { | |
| constructor(maxKeys) { | |
| this.maxKeys = maxKeys | |
| this.keys = {} | |
| this.nodes = new NodeList() | |
| this.nodes.load() | |
| } | |
| set(key, value) { | |
| const existingNode = this.keys[key] | |
| if (existingNode) { | |
| this.nodes.remove(existingNode) | |
| } | |
| if (this.nodes.count >= this.maxKeys) { | |
| this.removeLeastUsedNode() | |
| } | |
| const node = this.nodes.add(key) | |
| this.keys[key] = node | |
| localStorage.setItem(key, serializeNode(node, value)) | |
| } | |
| get(key) { | |
| if (!this.keys[key]) { | |
| return | |
| } | |
| const value = getNodeValue(localStorage.getItem(key)) | |
| const node = this.nodes.moveToTail(this.keys[key]) | |
| localStorage.setItem(key, serializeNode(node, value)) | |
| return value | |
| } | |
| removeLeastUsedNode() { | |
| const node = this.nodes.pop() | |
| delete this.keys[node.key] | |
| localStorage.removeItem(node.key) | |
| } | |
| } | |
| const btnSet = document.getElementById("btn-set") | |
| const btnGet = document.getElementById("btn-get") | |
| const inputSetKey = document.getElementById("input-set-key") | |
| const inputSetVal = document.getElementById("input-set-val") | |
| const inputGetKey = document.getElementById("input-get-key") | |
| const valueDisplay = document.getElementById("value") | |
| const currentKeyDisplay = document.getElementById("current-keys") | |
| const lruStorage = new LocalStorageLRU(5) | |
| btnSet.addEventListener("click", () => { | |
| lruStorage.set(inputSetKey.value, inputSetVal.value) | |
| currentKeyDisplay.innerHTML = lruStorage.nodes.toString() | |
| }) | |
| btnGet.addEventListener("click", () => { | |
| const value = lruStorage.get(inputGetKey.value) | |
| valueDisplay.innerHTML = value | |
| currentKeyDisplay.innerHTML = lruStorage.nodes.toString() | |
| }) | |
| </script> | |
| </body> | |
| </html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment