www.aleph1.co.uk Git - yaffs-website/blob - node_modules/aws4/lru.js

   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 }