Skip to content
Create a gist now

Instantly share code, notes, and snippets.

Adaptive replacement cache, implemented in JavaScript, extending Montage Collections, using CommonJS packaging suitable for NodeJS for servers and Montage or Mr for browsers.
"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
);
};
// 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());
};
{
"name": "arc",
"version": "0.0.0",
"dependencies": {
"collections": "0.1.5 - 0.2"
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.