![Cover image for Build a function memoizer [Part-4]](https://media2.dev.to/dynamic/image/width=1000,height=420,fit=cover,gravity=auto,format=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fi%2F9ec506x5qnfvtbug2ja6.jpg)
In the final part of the series we'll be adding expiry to cached values.
Breakdown:
- Just like the cacheSize we'll accept an expiresAt param with value in ms.
- If it's present then each node should store a timestamp of when it was created
- after finding a node we have to check if it expired
- clean expired nodes
Update cache options
let options = {
cacheSize: DEFAULT_CACHE_SIZE,
expiresAt: null,
...params,
};
Update Node structure
function Node(key, value, expires) {
this.key = key;
this.value = value;
this.next = null;
this.prev = null;
this.timestamp = expires ? Date.now() : null;
}
Add a function to check expiry
Node.prototype.hasExpired = function (diff) {
if (diff && this.timestamp) {
return Date.now() - this.timestamp >= diff;
}
};
Pass expires flag when creating a new node
// inside add function
const node = new Node(key, value, options.expiresAt);
Update find function to ignore an expired node
// check for cached node
function find(key) {
if (key in hash) {
const node = hash[key];
if (!node.hasExpired(options.expiresAt)) {
refresh(node);
return node;
}
// TODO: remove expired node
}
return null;
}
Time for some tests,
(async function () {
// expires after one second
const testCache = Cache({ cacheSize: 3, expiresAt: 1000 });
testCache.add("1-2", 3);
testCache.add("2-3", 5);
testCache.add("5-5", 10);
testCache.add("4-2", 6);
console.log(testCache.find("2-3")); // returns Node
// wait for 2 seconds
await new Promise((r) => setTimeout(r, 2000));
console.log(testCache.find("2-3")); // returns null
})();
Find returned null for "2-3" because it expired after one second.
To remove expired nodes we have to modify the remove function to remove any node passed to it rather than just the tail node.
function remove(node) {
if (node) {
delete hash[node.key];
// if the node is in the middle
if (node.prev) {
node.prev.next = node.next;
}
if (node.next) {
node.next.prev = node.prev;
}
// if it's the tail node
if (node === tail) {
tail = node.prev;
}
// if it's the head node
if (node === head) {
head = node.next;
}
size--;
}
}
Also update the existing call in the add function to remove(tail)
Update the find function to remove expired nodes
function find(key) {
if (key in hash) {
const node = hash[key];
if (node.hasExpired(options.expiresAt)) {
remove(node);
} else {
refresh(node);
return node;
}
}
return null;
}
Update the test above, add a print at the end
console.log(testCache.print());
// output: "[4-2: 6] -> [5-5: 10]"
Referring an expired node removed it from the linked list. The cache is working, let's test the memoizer
(async function () {
let count = 0;
function add(a, b, c = 0) {
count++;
return a + b + c;
}
const memoAdd = memoizer(add, { cacheSize: 3, expiresAt: 1000 });
memoAdd(5, 3);
memoAdd(3, 3);
memoAdd(1, 2);
memoAdd(2, 4);
console.log(count); // 4
await new Promise((r) => setTimeout(r, 2000));
memoAdd(1, 2);
console.log(count); // 5, cache expired
memoAdd(1, 2);
console.log(count); // 5, pulled from cache
memoAdd(2, 4);
console.log(count); // 6, expired value
})();
Works as expected, we are done with a good enough implementation of a memoizer function with support for cacheSize and expiry.
The memoizer code and jest tests can reviewed here
That's all folks :)
Photo by Steve Johnson on Unsplash
Top comments (0)