public
Created

Adaptive replacement cache, implemented in JavaScript, extending Montage Collections, using CommonJS packaging suitable for NodeJS for servers and Montage or Mr for browsers.

  • Download Gist
arc-map.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
"use strict";
 
var Shim = require("collections/shim");
var ArcSet = require("./arc-set");
var GenericCollection = require("collections/generic-collection");
var GenericMap = require("collections/generic-map");
var PropertyChanges = require("collections/listen/property-changes");
 
module.exports = ArcMap;
 
function ArcMap(values, maxLength, equals, hash, getDefault) {
if (!(this instanceof ArcMap)) {
return new ArcMap(values, maxLength, equals, hash);
}
equals = equals || Object.equals;
hash = hash || Object.hash;
getDefault = getDefault || Function.noop;
this.contentEquals = equals;
this.contentHash = hash;
this.getDefault = getDefault;
this.store = new ArcSet(
undefined,
maxLength,
function keysEqual(a, b) {
return equals(a.key, b.key);
},
function keyHash(item) {
return hash(item.key);
}
);
this.length = 0;
this.addEach(values);
}
 
Object.addEach(ArcMap.prototype, GenericCollection.prototype);
Object.addEach(ArcMap.prototype, GenericMap.prototype);
Object.addEach(ArcMap.prototype, PropertyChanges.prototype);
 
ArcMap.prototype.constructClone = function (values) {
return new this.constructor(
values,
this.maxLength,
this.contentEquals,
this.contentHash,
this.getDefault
);
};
arc-set.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
 
// Adaptive Replacement Cache
// Patented in the USA by IBM in 2006
// Derrived from http://code.activestate.com/recipes/576532/
// And made to extend Montage Collections https://github.com/montagejs/collections
// Copyright 2012 Kris Kowal. MIT License
 
"use strict";
 
var Set = require("collections/set");
var GenericCollection = require("collections/generic-collection");
var GenericSet = require("collections/generic-set");
var PropertyChanges = require("collections/listen/property-changes");
 
module.exports = ArcSet;
 
function ArcSet(values, maxLength, equals, hash, getDefault) {
if (!(this instanceof ArcSet)) {
return new ArcSet(values, maxLength, equals, hash, getDefault);
}
equals = equals || Object.equals;
hash = hash || Object.hash;
getDefault = getDefault || Function.noop;
this.contentEquals = equals;
this.contentHash = hash;
this.getDefault = getDefault;
this.maxLength = maxLength;
this.store = Set(null, equals, hash);
 
// arc strategy data
this.p = 0;
this.t1 = Set(null, equals, hash);
this.t2 = Set(null, equals, hash);
this.b1 = Set(null, equals, hash);
this.b2 = Set(null, equals, hash);
 
this.length = 0;
this.addEach(values);
}
 
Object.addEach(ArcSet.prototype, GenericCollection.prototype);
Object.addEach(ArcSet.prototype, GenericSet.prototype);
Object.addEach(ArcSet.prototype, PropertyChanges.prototype);
 
ArcSet.prototype.get = function (value) {
if (this.store.has(value)) {
this.add(value);
return value;
}
};
 
ArcSet.prototype.add = function (value) {
if (this.t1.has(value)) {
this.t1["delete"](value);
this.t2.add(value);
return;
}
if (this.t2.has(value)) {
this.t2["delete"](value);
this.t2.add(value);
return;
}
this.store.add(value);
if (this.b1.has(value)) {
this.p = Math.min(
this.maxLength,
this.p + Math.max(
this.b2.length / this.b1.length,
1
)
);
this.replace(value);
this.b1["delete"](value);
this.t2.add(value);
return;
}
if (this.b2.has(value)) {
this.p = Math.max(
0,
this.p - Math.max(
this.b1.length / this.b2.length,
1
)
);
this.replace(value);
this.b2["delete"](value);
this.t2.add(value);
return;
}
if (this.t1.length + this.b1.length === this.maxLength) {
if (this.t1.length < this.maxLength) {
this.b1.shift();
this.replace(value);
} else {
this.store["delete"](this.t1.shift())
}
} else {
var total = this.t1.length + this.b1.length + this.t2.length + this.b2.length;
if (total >= this.maxLength) {
if (total === this.maxLength * 2) {
this.b2.shift();
}
this.replace(value);
}
}
this.t1.add(value);
};
 
ArcSet.prototype.replace = function (value) {
var old;
if (this.t1.length && (
(this.b2.has(value) && this.t1.length === this.p) ||
(this.t1.length > this.p)
)) {
old = this.t1.shift();
this.b1.add(old);
} else {
old = this.t2.shift();
this.b2.add(old);
}
this.store["delete"](old);
};
 
ArcSet.prototype.reduce = function (callback, basis /*, thisp*/) {
var thisp = arguments[2];
return this.store.reduce(callback, basis, thisp);
};
 
ArcSet.prototype.reduceRight = function (callback, basis /*, thisp*/) {
var thisp = arguments[2];
return this.store.reduce(callback, basis, thisp);
};
 
ArcSet.prototype.log = function () {
this.report(console.log, console);
};
 
ArcSet.prototype.report = function (write, thisp) {
write.call(thisp, "t1: " + this.t1.toArray());
write.call(thisp, "t2: " + this.t2.toArray());
write.call(thisp, "b1: " + this.b1.toArray());
write.call(thisp, "b2: " + this.b2.toArray());
};
package.json
JSON
1 2 3 4 5 6 7
{
"name": "arc",
"version": "0.0.0",
"dependencies": {
"collections": "0.1.5 - 0.2"
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.