The memory manager is implemented as a standalone class that tracks its buffer as well as the current amount of memory in use by the buffer. Memory is allocated in blocks of a certain number of bytes. If multiple blocks are needed to allocate the required amount of memory due to fragmentation, each block tracks a pointer to the next block in its chain. That is, memory blocks support a linked list structure to ensure that the entire buffer is available for use, even when it is fragmented. Memory blocks are indexed by a unique ID that is generated at the time a block is created. This allows for easy and fast retrieval of any block from the buffer, regardless of its position in a chain. Memory block IDs are also indexed by their starting index in the buffer so that checking if a section of the buffer is already allocated will be efficient.
The memory manager allocates memory on a first found basis. That is, when the memory manager is looking for available memory for a block, it will always choose the first available slot for the block. If more blocks are required, the manager repeats this process until all the required memory has been allocated. When a new block is created, it is added to the index, and its ID is added to the index of block IDs by starting position.
When a block is freed by the memory manager, it is removed from the block index and its ID is removed from the index of block IDs by their starting position. If there is another block in the chain, the process is repeated for that block. This continues until the full chain has been freed.
When data is written to the buffer, the memory manager asks the given block to calculate how much of its available space was used to write the data to that block. If the block does not have enough space to store all the data, then it will store as much as it can and the memory manager will move to the next block in the chain to save more of the data. This process repeats until all the data has been stored in the buffer.
When data is read from the buffer, the memory manager asks the given block where its data is stored in the buffer. It then reads the appropriate section of the buffer to retrieve that block's data. If there are additional blocks in the chain, the manager repeats this process for each subsequent block and concatenates all the data read from the buffer together before returning the full value that was read.
Each memory block tracks its starting position in the buffer, as well as its full allocated size, the total size of all the blocks in its chain, and how much of its available memory is in use. The allocated size is tracked to ensure that if a full block is not used, the memory manager does not return too much data from the buffer than it should for a given block. For example, if a block has a size of 10 bytes, but only 7 have been used to store data in the block, then reading the block should only return 7 bytes of data from the buffer.
Each block also tracks whether or not it is the root block in its chain so that the memory manager can easily detect if it is attempting to begin reading from a block that is not the start of the chain.
Each memory block also stores the unique ID of the next block in its chain.
The first found approach to allocating memory in the buffer makes allocating memory simple, but can lead to inefficient block allocation and fragmentation. This is because the manager will always choose to break up a memory block into smaller blocks if the first empty space it finds in the buffer is not big enough to store the full block.
Maintaining multiple indexes in the manager makes finding memory blocks and detecting empty space in the buffer easier, but increases the overhead of the manager. A manager that did not maintain multiple indexes would require less memory itself, but would make finding existing memory blocks and checking for the open space in the buffer more computationally expensive.
The buffer managed by the memory manager is not actually a contiguous block of memory, it only simulates one using a list.
The memory manager is only capable of storing strings in the buffer.
Memory blocks are not reusable. Each block or chain of blocks can only be assigned a value one time. In order to reuse the space assigned to each block in the buffer, the block must be freed and then new blocks must be reallocated.
The largest improvement that I believe can be made is to expand the capability of the memory manager to allocate more than just strings to the buffer. This would greatly increase the utility of the memory manager. Doing so using a bytearray for the buffer would also make it so the memory manager was truly managing a single contiguous block of memory.
In the future, I would improve the algorithm used to select empty space on the buffer for a memory block. Rather than always selecting the first open space in the buffer, regardless of its size or whether is it big enough for the full block, I would implement an algorithm that looks for the largest available space in the buffer first. This would often reduce the total number of memory blocks required to allocate sections of the buffer, and would reduce the occurrence of discontiguous blocks.
I would also address the lack of reusability by memory blocks. If memory blocks could be reused, provided the data stored when the block is reused does not exceed its allocated size, then users of the memory manager would not have to purposefully free blocks they no longer needed in order to reallocate memory to store a new value.
I would like to improve the free method on the memory manager to also scrub the data whose blocks are being freed from the buffer. That is, when a block is freed, I would update the section of the buffer that belongs to that block with empty values. This would make it so that data is cleared from the buffer when it is no longer needed and cannot be mistakenly misread or maliciously accessed.