Memory Manager

memory-manager.js

// Description:
// 
// One of the services provided by an operating system is memory management. 
// The OS typically provides an API for allocating and releasing memory in a 
// process's address space. A process should only read and write memory at
// addresses which have been allocated by the operating system. In this kata you
// will implement a simulation of a simple memory manager.
// 
// JavaScript has no low level memory API, so for our simulation we will simply
// use an array as the process address space. The memory manager constructor
// will accept an array and will allocate blocks of indices from that array
// rather than memory pages.
// 
// Memory Manager Contract
// 
// allocate
// 
// allocate accepts an integer and returns an integer pointer which should be
// the index of the beginning of a sequential block of indices of length size
// in the array passed to the constructor. If there is no such sequential
//  block available this method should throw an exception.
// 
// release
// 
// release accepts an integer which must be a pointer previously returned from
// allocate and releases the block beginning at that pointer. If the released
// block is adjacent to another free block, the two blocks should be merged to
// form a larger free block. Releasing an unallocated block should cause an
// exception.
// 
// write
// 
// To support testing this simulation our memory manager needs to enforce
// read/write restrictions. Only indices within allocated blocks may be written
// to. The write method accepts an index integer and a value. If the index is
// within an allocated block, the value should be stored to the backing
// array; otherwise, this method should throw an exception.
// 
// read
// 
// This method is the counterpart to write. Only indices within allocated
// blocks may be read. The read method accepts an index integer. If the index
// is within an allocated block, the method should return the value from the
// backing array at that index; otherwise, this method should throw an
// exception.


// -----------------------------------------------------------------------------
// SOLUTION
// -----------------------------------------------------------------------------

/**
 * @constructor Creates a new memory manager for the provided array.
 * @param {memory} An array to use as the backing memory.
 */
function MemoryManager(memory){
  this.memory = memory;
  this.values = [ ...memory ];
  this.allocations = [];
}

/**
 * Allocates a block of memory of requested size.
 * @param {number} size - The size of the block to allocate.
 * @returns {number} A pointer which is the index of the first location in the allocated block.
 * @throws If it is not possible to allocate a block of the requested size.
 */
MemoryManager.prototype.allocate = function(size){
  const available = this.getFreeSlots().find(slot => slot.size >= size);
    
   if (!available) {
     throw new Error('Not enough memory !');
   }

  for (var i = available.at; i < available.at + size; i++) {
    this.values[i] = 1;
  }
  
  this.allocations.push({ at: available.at, size: size });
  
  return available.at;
};

/**
 * Releases a previously allocated block of memory.
 * @param {number} pointer - The pointer to the block to release.
 * @throws If the pointer does not point to an allocated block.
 */
MemoryManager.prototype.release = function(pointer){
  const slot = this.allocations.find(slot => slot.at === pointer);
  
  if (!slot) {
    throw new Error('invalid pointer');
  }
  
  for (var i = slot.at; i < slot.at + slot.size; i++) {
    this.values[i] = undefined;
  }
  
  this.allocations = this.allocations.filter(slot => slot.at !== pointer);
};

/**
 * Reads the value at the location identified by pointer
 * @param {number} pointer - The location to read.
 * @returns {number} The value at that location.
 * @throws If pointer is in unallocated memory.
 */
MemoryManager.prototype.read = function(pointer){
  const slot = this.allocations
    .find(slot => slot.at <= pointer && pointer < slot.at + slot.size);
  
  if (!slot) {
    throw new Error('invalid pointer'); 
  }
  
  return this.memory[pointer];
}

/**
 * Writes a value to the location identified by pointer
 * @param {number} pointer - The location to write to.
 * @param {number} value - The value to write.
 * @throws If pointer is in unallocated memory.
 */
MemoryManager.prototype.write = function(pointer, value){
  const slot = this.allocations
    .find(slot => slot.at <= pointer && pointer < slot.at + slot.size);
  
  if (!slot) {
    throw new Error('invalid pointer'); 
  }
  
  this.memory[pointer] = value;
}

MemoryManager.prototype.maxAvailable = function() {
  return this.getFreeSlots()
    .map(slot => slot.size)
    .reduce((p,c) => c > p ? c : p, 0);
}

MemoryManager.prototype.getFreeSlots = function() {
  var res = [];
  var counter = 0;
  var at = null;
  
  this.values.forEach((v, i) => {
    const isFree = typeof(v) === 'undefined';
    const endsFreeBlock = !isFree || i === this.values.length - 1;
    
    if (isFree) {
      if (counter === 0) { at = i; }
      counter++;
    } 
    if (endsFreeBlock && counter > 0) {
      res.push({ size: counter, at: at });
      at = null;
      counter = 0;
    }
  });
  
  return res;
}