Memory Allocator

Interesting problem: build a memory allocator class. Given the small n (1000), approach was the following:

1/ Keep track of the memory as an array of integers
2/ Keep track of the total size allocated for mID (HashTable)
3/ Keep track of which mIDs have been freed up (HashTable)
4/ To allocate, scan the memory array looking for a consecutive free block. Allocate it if found. There is some math needed here to ensure the proper allocation, simple math with the indexes. There is some perf optimization that can be done with a "jump" table, but again n=1000, there is no need
5/ To free, just operate with the HashTables in #2 and #3 above

Code is down below, cheers, ACC.

Design Memory Allocator - LeetCode

2502. Design Memory Allocator

Medium

You are given an integer n representing the size of a 0-indexed memory array. All memory units are initially free.

You have a memory allocator with the following functionalities:

1. Allocate a block of size consecutive free memory units and assign it the id mID.
2. Free all memory units with the given id mID.

Note that:

• Multiple blocks can be allocated to the same mID.
• You should free all the memory units with mID, even if they were allocated in different blocks.

Implement the Allocator class:

• Allocator(int n) Initializes an Allocator object with a memory array of size n.
• int allocate(int size, int mID) Find the leftmost block of size consecutive free memory units and allocate it with the id mID. Return the block's first index. If such a block does not exist, return -1.
• int free(int mID) Free all memory units with the id mID. Return the number of memory units you have freed.

 

Example 1:

Input
["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
Output
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

Explanation
Allocator loc = new Allocator(10); // Initialize a memory array of size 10. All memory units are initially free.
loc.allocate(1, 1); // The leftmost block's first index is 0. The memory array becomes [1,_,_,_,_,_,_,_,_,_]. We return 0.
loc.allocate(1, 2); // The leftmost block's first index is 1. The memory array becomes [1,2,_,_,_,_,_,_,_,_]. We return 1.
loc.allocate(1, 3); // The leftmost block's first index is 2. The memory array becomes [1,2,3,_,_,_,_,_,_,_]. We return 2.
loc.free(2); // Free all memory units with mID 2. The memory array becomes [1,_, 3,_,_,_,_,_,_,_]. We return 1 since there is only 1 unit with mID 2.
loc.allocate(3, 4); // The leftmost block's first index is 3. The memory array becomes [1,_,3,4,4,4,_,_,_,_]. We return 3.
loc.allocate(1, 1); // The leftmost block's first index is 1. The memory array becomes [1,1,3,4,4,4,_,_,_,_]. We return 1.
loc.allocate(1, 1); // The leftmost block's first index is 6. The memory array becomes [1,1,3,4,4,4,1,_,_,_]. We return 6.
loc.free(1); // Free all memory units with mID 1. The memory array becomes [_,_,3,4,4,4,_,_,_,_]. We return 3 since there are 3 units with mID 1.
loc.allocate(10, 2); // We can not find any free block with 10 consecutive free memory units, so we return -1.
loc.free(7); // Free all memory units with mID 7. The memory array remains the same since there is no memory unit with mID 7. We return 0.

 

Constraints:

• 1 <= n, size, mID <= 1000
• At most 1000 calls will be made to allocate and free.

public class Allocator
{
    private int[] memory = null;
    private Hashtable mIDtoSize = null;
    private Hashtable freedmID = null;
    public Allocator(int n)
    {
        memory = new int[n];
        mIDtoSize = new Hashtable();
        freedmID = new Hashtable();
    }

    public int Allocate(int size, int mID)
    {
        int freeIndex = 0;
        int retVal = -1;
        bool found = false;
        for (int i = 0; i < memory.Length; i++)
        {
            if (freeIndex == size)
            {
                retVal = i - freeIndex;
                for (int j = 0; j < size; j++)
                {
                    memory[i - freeIndex + j] = mID;
                }
                found = true;
                break;
            }
            if (memory[i] == 0 || freedmID.ContainsKey(memory[i])) freeIndex++;
            else freeIndex = 0;
        }
        if (!found && freeIndex == size)
        {
            retVal = memory.Length - size;
            for (int j = 0; j < size; j++)
            {
                memory[memory.Length - size + j] = mID;
            }
            found = true;
        }

        if (found)
        {
            if (freedmID.ContainsKey(mID)) freedmID.Remove(mID);
            if (!mIDtoSize.ContainsKey(mID)) mIDtoSize.Add(mID, 0);
            mIDtoSize[mID] = (int)mIDtoSize[mID] + size;
        }

        return retVal;
    }

    public int Free(int mID)
    {
        int retVal = 0;
        if (mIDtoSize.ContainsKey(mID))
        {
            retVal = (int)mIDtoSize[mID];
            mIDtoSize.Remove(mID);
        }
        if (!freedmID.ContainsKey(mID)) freedmID.Add(mID, true);
        return retVal;
    }
}