Memory.jack

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/Memory.jack

/**
 * Memory operations library.
 */ 
class Memory {
  static int MEMORY, HEAP_BASE, NEXT_POINTER, SIZE, HEAP_LIMIT, OOM, freeList, i;

  /** Initializes memory parameters. */
  function void init() {
    let MEMORY = 0;
    let SIZE = 0;
    let NEXT_POINTER = 1;
    let HEAP_BASE = 2048;
    let HEAP_LIMIT = 16383;
    let freeList = HEAP_BASE;
    let freeList[SIZE] = HEAP_LIMIT - HEAP_BASE;
    let OOM = 137;
    let i = 0;

    return;
  }

  /** Returns the value of the main memory at the given address. */
  function int peek(int address) {
    return MEMORY[address];
  }

  /** Sets the value of the main memory at this address
   *  to the given value. */
  function void poke(int address, int value) {
    let MEMORY[address] = value;
    
    return;
  }

  /** finds and allocates from the heap a memory block of the 
   *  specified size and returns a reference to its base address. */
  function int alloc(int size) {
    var bool defragged;
    var int currentFreeSegment, block, newFreeSegment, previousFreeSegment;

    let defragged = false;
    let currentFreeSegment = freeList;

    while (~block) {
      if (currentFreeSegment[SIZE] > size) {
        if (currentFreeSegment = freeList) {
          if (currentFreeSegment[NEXT_POINTER]) {
            let freeList = currentFreeSegment[NEXT_POINTER];
          } else {
            let freeList = currentFreeSegment + size + 1;
            let freeList[SIZE] = currentFreeSegment[SIZE] - size - 1;
          }
        } else {
          if (size < (currentFreeSegment[SIZE] - 2)) {
            let newFreeSegment = currentFreeSegment + size + 1;
            let newFreeSegment[SIZE] = currentFreeSegment[SIZE] - size - 1;
            let previousFreeSegment[NEXT_POINTER] = newFreeSegment;
          } else {
            let previousFreeSegment[NEXT_POINTER] = currentFreeSegment[NEXT_POINTER];
          }
        }

        let block = currentFreeSegment + 1;
      } else {
        if (currentFreeSegment[NEXT_POINTER] = null) {
          if (defragged) {
            do Sys.error(OOM);
          } else {
            do Memory.defrag();
            let defragged = true;
            let currentFreeSegment = freeList;
          }
        } else {
          let previousFreeSegment = currentFreeSegment;
          let currentFreeSegment = currentFreeSegment[NEXT_POINTER];
        }
      }
    }

    let block[-1] = size + 1;
    let block[0] = null;

    return block;
  }

  function void defrag() {
    var int currentFreeSegment, nextFreeSegment;

    let currentFreeSegment = freeList;
    let nextFreeSegment = currentFreeSegment[NEXT_POINTER];

    while (~(nextFreeSegment = 0)) {
      if ((currentFreeSegment + currentFreeSegment[SIZE]) = nextFreeSegment) {
        let currentFreeSegment[SIZE] = currentFreeSegment[SIZE] + nextFreeSegment[SIZE];
        let currentFreeSegment[NEXT_POINTER] = nextFreeSegment[NEXT_POINTER];
        let nextFreeSegment[SIZE] = null;
        let nextFreeSegment[NEXT_POINTER] = null;
      }

      let currentFreeSegment = nextFreeSegment;
      let nextFreeSegment = currentFreeSegment[NEXT_POINTER];
    }

    return;
  }

  /** De-allocates the given object and frees its space. */
  function void deAlloc(int block) {
    var int segment, segmentLength, oldFreeList, currentFreeSegment, oldNextSegment;

    let segment = block - 1;
    let segmentLength = segment[0];

    while (i < (segmentLength - 1)) {
      let block[i] = null;
      let i = i + 1;
    }

    if (segment < freeList) {
      let oldFreeList = freeList;
      let freeList = segment;
      let freeList[NEXT_POINTER] = oldFreeList;
      return;
    }

    let currentFreeSegment = freeList;

    while ((currentFreeSegment[NEXT_POINTER] < segment) & currentFreeSegment[NEXT_POINTER]) {
      let currentFreeSegment = currentFreeSegment[NEXT_POINTER];
    }

    if (currentFreeSegment[NEXT_POINTER] > 0) {
      let oldNextSegment = currentFreeSegment[NEXT_POINTER];
      let currentFreeSegment[NEXT_POINTER] = segment;
      let segment[NEXT_POINTER] = oldNextSegment;
    } else {
      let currentFreeSegment[NEXT_POINTER] = segment;
    }
    
    return;
  }
}