cachemap.js

// Find at which index an element should be inserted
// into a sorted array, using binary search
function insertionIndexUsingBinarySearch(sortedArray, value, from, to) {
  if (sortedArray.length === 0) {
    return 0;
  }

  if (typeof(from) === 'undefined') {
    from = 0;
  }

  if (typeof(to) === 'undefined') {
    to = sortedArray.length - 1;
  }

  const mid = Math.floor((from + to) / 2);
  if (isNaN(mid)) {
    throw "Mid is nan"
  }

  // There is no exact matching index but we zeroed in on the
  // index where we should insert
  if (from > to) {
    return from;
  }

  if (value < sortedArray[mid]) { // left
    return insertionIndexUsingBinarySearch(sortedArray, value, from, mid - 1);
  } else if (value > sortedArray[mid]) { // right
    return insertionIndexUsingBinarySearch(sortedArray, value, mid + 1, to);
  } else {
    return mid;
  }
}

function insertSortedInplace(into_array, value) {
  const insert_at = insertionIndexUsingBinarySearch(into_array, value)
  into_array.splice(insert_at, 0, value);
  return insert_at;
}

function didRead(readOffsets, readSizes, at, n) {
  const i = insertSortedInplace(readOffsets, at);
  readSizes.splice(i, 0, n);

  // Collapse neighbouring elements until no elements remain
  let len_before = 0;
  let len_after = 0;
  while(true) {
    len_before = readOffsets.length;
    collapse(readOffsets, readSizes, i-1, i);
    collapse(readOffsets, readSizes, i, i+1);
    len_after = readOffsets.length;
    if (len_before === len_after) return;
  }
}

function collapse(readOffsets, readSizes, ia, ib) {
  if (ia < 0) return;
  if (ib >= readOffsets.length) return;

  const [cur_off, cur_bytes] = [readOffsets[ib], readSizes[ib]]
  const [prev_off, prev_bytes] = [readOffsets[ia], readSizes[ia]]
  if (prev_off + prev_bytes >= (cur_off - 1)) {
    const union_start = prev_off
    const union_end = Math.max(prev_off + prev_bytes, cur_off + cur_bytes)
    const union_length = union_end - union_start;
    readSizes[ia] = union_length;
    readOffsets.splice(ib, 1);
    readSizes.splice(ib, 1);
  }
}

// Provides an interface to a bitmap with contiguous reads
// that get connected if they join, so the data structure is self-compacting
class CacheMap {
  constructor() {
    this.offsets = [];
    this.reads = [];
  }

  didReadOne(at) {
    this.didRead(at, 1);
  }

  didRead(at, n) {
    didRead(this.offsets, this.reads, at, n);
  }

  map(fn) {
    return this.offsets.map((regionOffset, i) => {
      const regionLength = this.reads[i];
      fn({regionOffset, regionLength});
    });
  }

  forEach(fn) {
    return this.offsets.forEach((regionOffset, i) => {
      const regionLength = this.reads[i];
      fn({regionOffset, regionLength});
    })
  }
}

class CacheBar {
  constructor(barCanvasElement, numFrames, cachedColor) {
    this.barCanvas = barCanvasElement;
    this.cacheMap = new CacheMap();
    this.numFrames = numFrames;
    this.color = cachedColor;
  }

  didLoad(at) {
    this.cacheMap.didReadOne(at);
    const {width, height} = this.barCanvas;
    const inCanvasPixels = (frameN) => frameN / this.numFrames * width;
    const ctx = this.barCanvas.getContext('2d');

    ctx.clearRect(0, 0, width, height);
    ctx.fillStyle = this.color;
    this.cacheMap.forEach((region) => {
      const {regionOffset, regionLength} = region;
      ctx.fillRect(inCanvasPixels(regionOffset), 0, inCanvasPixels(regionLength), height);
    });
  }
}

export { CacheMap, CacheBar };