Build a function memoizer [Part-4]

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