COL 106 Assignment 3


  • Please make sure the when a node with two children is deleted, it is replaced always by its in-order successor.
  • When freeing a block, first merge with any contiguous block before it. If non exist, attempt to merge with any contiguous block after it. (Merge a block by deleting old node and adding a new one.)
  • The error in the examples has been corrected.
  • There is no space between "-" and "l" in the optional argument "-l". (And that is letter ell not number one.)
  • You should not VISIT any node more than once in any ALLOC. Note that the print is only for the traversal for searching for the closest match. Traversal for re-insertion is not to be printed.
  • In case multiple nodes of the best-fit size are found, pick the node encountered first.
  • You should print the free-list at the end in the increasing order of the addresses.


    In this assignment you will use binary search tree to create a memory allocation system that supports "allocate" and "free" primitives. Write a MemAlloc that implements the following interface:
    interface MemAllocator {
       int allocate(int size);
       void free(int address, int size);
       int allocatedSize();
    The class implementing MemAllocator maintains the set of maximal blocks of free memory. Initially a single block 1 to ∞ is free. A block from address a to b is maximal if addresses a-1 and b+1 are both allocated, i.e., not free.

    allocate returns the address starting at which size free bytes are free. In order to reduce fragmentation, the implementation must ensure that the smallest maximal block larger than the requested size is always found. If no such block exists, 0 is returned (0 is not a valid address). If the size of the block is less than twice the requested size, the entire block is allocated. Otherwise, only the first size addresses are allocated; the block is split and the remaining block remains free.

    allocatedSize returns the allocated size of the last most recently block (which may be larger than the requested size).

    free is permissive, meaning a non-allocated block may be "freed". The address specified in "free" need not be one returned in a previous allocate either. After the method is complete, all addresses from the given address to address+size-1 must be free. If a block contiguous with the freed block is already free, the two are merged before the method returns.

    You must implement a binary search tree class called BST to speed up allocate and free. You will maintain one tree on the address key and another on the size key. allocate employs size-BST to find the closest matching block and free employs address-BST to find if any contiguous blocks are free. BST will require methods to find by keyword, delete a Position, insert a Position, as well as find the predecessar and successor Positions

    Note that in your BST, all values less than or equal to a given node's must lie in its left subtree.


    Implement public class Assignment3, with a static main that takes on the command line, the name of a file containing a sequence of "alloc" and "free" calls. It reads the contents of the file, performing the requested actions. It produces the list of free blocks remaining at the end. The program should also take an optional argument "-l". When provided, it writes a log of operations to System.out (before producing the final list of free blocks).


    The input file has one command per line, one of
    FREE <address> <size>
    ALLOC <size>
    FREE and ALLOC are keywords and the values in angled brackets are integers.

    On output, the free list is written on a single line as a sequence:

    FINAL <address1> <size1> <address2> <size2> ...
    If the log option is enabled, at the end of the allocate method, the following line is printed:
    ALLOC <address>
    Also, for each size-BST node visited to find the closest matching node by allocate, the following line is printed:
    VISIT  <address> <size>


    ALLOC 100
    ALLOC 1000
    ALLOC 10000
    FREE  1101 100 
    FREE  1201 1000
    FREE 1 100
    ALLOC 50
    VISIT 1 ∞
    ALLOC 1
    VISIT 101 ∞
    ALLOC 101
    VISIT 1101 ∞
    ALLOC 1101
    VISIT 11101 ∞
    VISIT 1101 1100
    VISIT 1 100
    ALLOC 1
    FINAL 51 50 1101 1100 11101 ∞
    More To be added

    Submission instructions

    Submission will be at moodle.

    Please ensure that you follow the following set of instructions meticulously while submitting the assignment on Moodle. Also, please note that in case of deviation from this procedure will render your submission faulty, and your assignment might not be evaluated at all by the script. Please follow these steps:

    1. On eclipse, by default, all your source files (.java files) are saved into a directory called "src" inside your project. You have to compress this directory (to zip format) and rename the zip file in this format:
      Example: If your entry number is 2012CSZ8019, the zip file should be named It should expand to a directory called src, which contains all your .java files. Please make sure that you follow exactly this naming format.
    2. Next, convert the zip file to base64 format. On any linux system, you can do this easily by issuing the following command on the terminal :
         base64 >
      This will create a file with the same name with a b64 extension appended at the end.
    3. Upload this b64 file on moodle and submit it (in the "Submission" section). After Submission, there is an option of "Evaluate" in the "Edit" section. Click on "Evaluate". On the right side of the window, you will get information about the submission status. On clicking the "Evaluate" link, you should see a script running and producing an output of your codes' performance against the standard set of test cases that we supply internally for the assessment. A dialog box will show you the messages on how your codes performed against the benchmarks that we provided.
            Important notes