Last active
January 24, 2019 00:19
-
-
Save ericso/40bca804ea5917ac7cb7f57e52a21565 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// memory manager | |
/** | |
* Simulate a buffer of memory using an Array. | |
* Creating the memory manager would consist of calling the constructor of MemoryManager with a pointer | |
* to the buffer and the size of the buffer. Since we're simulating this, and you can't pass a reference | |
* to an array in Javascript, let's just create the array in the MemoryManager. | |
*/ | |
class MemoryManager { | |
/** | |
* @param {number} bufferSize the size of the buffer | |
*/ | |
constructor(bufferSize) { | |
// In Javascript array's are dynamically sized. Calling `this.buffer.length` would return the length of the array. | |
this.buffer = new Array(bufferSize); | |
// firstChunk is a pointer to the first node of the linked list that keeps track of the chunks of memory. | |
this.firstChunk = new ChunkNode(0, bufferSize, false, null, null); | |
} | |
/** | |
* | |
* @param {number} size the size of a chunk of memory to allocate | |
* @returns {number|null} index of the start of the allocated chunk of memory or `null` if we cannot allocate the memory | |
*/ | |
alloc(size) { | |
// find a chunk | |
let currentChunk = this.firstChunk; | |
do { | |
if (!currentChunk.allocated) { | |
if (currentChunk.size === size) { | |
// All we need to do is to flip the allocated flag | |
currentChunk.allocated = true; | |
return currentChunk.index; | |
} else if (currentChunk.size > size) { | |
// Store the size of the remaining chunk of memory | |
const remainderSize = currentChunk.size - size; | |
currentChunk.size = size; | |
currentChunk.allocated = true; | |
if (currentChunk.nextNode && !currentChunk.nextNode.allocated) { | |
// If the next node exists and it is unallocated, | |
// combine the two chunks by decreasing its index and increasing its size by remainderSize | |
currentChunk.nextNode.index -= remainderSize; | |
currentChunk.nextNode.size += remainderSize; | |
} else { | |
// If there isn't a next node, or if the next node is allocated, then we create an unallocated | |
// node to represent the leftover space. | |
const unallocatedChunk = new ChunkNode( | |
currentChunk.index+size, | |
remainderSize, | |
false, | |
currentChunk, | |
currentChunk.nextNode, | |
); | |
currentChunk.nextNode = unallocatedChunk; | |
} | |
return currentChunk.index; | |
} else { | |
// size requested is too large, do nothing | |
} | |
} else { | |
// current chunk is allocated, so we have to move on to the next node | |
currentChunk = currentChunk.nextNode; | |
} | |
} while(currentChunk); | |
// If we get to here, then we traversed the entire linked list w/o allocating a chunk of memory | |
return null; | |
} | |
/** | |
* | |
* @param {number} index the "pointer" to the chunk of memory to free up | |
* @returns {boolean} `true` if successfully deallocated memory, `false` if unable to find chunk | |
*/ | |
free(index) { | |
let currentChunk = this.firstChunk; | |
do { | |
if (currentChunk.index === index) { | |
if (!currentChunk.allocated) { | |
// For some reason we tried to unallocated non-allocated memory. | |
// TODO: Should we throw an error instead? | |
return false | |
} | |
// Case 1: we can just flip the chunk to unallocated | |
if ( | |
(!currentChunk.prevNode || currentChunk.prevNode.allocated) && | |
(!currentChunk.nextNode || currentChunk.nextNode.allocated) | |
) { | |
currentChunk.allocated = false; | |
return true; | |
} else if ( | |
(currentChunk.prevNode && currentChunk.prevNode.unallocatedChunk) && | |
(currentChunk.nextNode && currentChunk.nextNode.unallocatedChunk) | |
) { | |
// Case 2: both previous and next exist, and they are unallocated | |
currentChunk.prevNode.nextNode = currentChunk.nextNode.nextNode; | |
currentChunk.size += (currentChunk.size + currentChunk.nextNode.size); | |
// We splice out currentChunk and the next node | |
currentChunk = null; | |
currentChunk.nextNode = null; | |
return true; | |
} else if (currentChunk.prevNode && currentChunk.prevNode.unallocatedChunk) { | |
// only previous node is unallocated | |
currentChunk.prevNode.nextNode = currentChunk.nextNode; | |
currentChunk.prevNode.size += currentChunk.size; | |
// Splice out the current node | |
currentChunk = null; | |
return true; | |
} else if (currentChunk.nextNode && currentChunk.nextNode.unallocatedChunk) { | |
// only next node is unallocated | |
currentChunk.nextNode = currentChunk.nextNode.nextNode; | |
currentChunk.size += currentChunk.nextNode.size; | |
// Splice out the next node | |
currentChunk.nextNode = null; | |
return true; | |
} | |
} else { | |
currentChunk = currentChunk.nextNode; | |
} | |
} while(currentChunk); | |
// If we made it here, we didn't find the chunk of memory to deallocate | |
return false; | |
} | |
} | |
/** | |
* Class representing the chunks of memory as nodes of a linked list. | |
*/ | |
class ChunkNode { | |
/** | |
* | |
* @param {number} index the start index of this chunk of memory | |
* @param {number} size size of this chunk of memory | |
* @param {boolean} allocated true if this chunk is allocated, false if not | |
* @param {ChunkNode} prevNode "pointer" to the previous node, which is the previous chunk of memory | |
* @param {ChunkNode} nextNode "pointer" to the next node, which is the next chunk of memory | |
*/ | |
constructor(index, size, allocated, prevNode, nextNode) { | |
this.index = index; | |
this.size = size; | |
this.allocated = allocated; | |
this.prevNode = prevNode; | |
this.nextNode = nextNode; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I fixed issues around infinite loop conditions in an updated gist: https://gist.github.com/ericso/274be53321c3ceddb1956cb4efb894fb