Skip to content

Instantly share code, notes, and snippets.

@sohamkamani

sohamkamani/localstorage_lru_cache.html

Created July 21, 2020 16:27
Show Gist options
  • Save sohamkamani/3ce4725647ee28b30b1477c03920eb3d to your computer and use it in GitHub Desktop.
Save sohamkamani/3ce4725647ee28b30b1477c03920eb3d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. sohamkamani created this gist Jul 21, 2020.
    198 changes: 198 additions & 0 deletions localstorage_lru_cache.html
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,198 @@
    <!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>