Write a BCPL library that provides a proper fully functional implementation
of newvec, freevec, and init. Make sure it works with your assigment 4
program.

Remember that you need to test things throughly. Do runs with strings of all 
sorts of lengths, with lots of additions and deletions. Change your linked
list printer show that it shows the addresses of everything (each link and
each string), so you can demonstrate that feevec is working properly,
recycling memory and combining neighbouring free chunks.

Start simply and build up to the final result. First just make freevec keep
a linked list of free chunks, no combining, just recycling. Then move on to
multiple free lists for different sizes. Then move on the the final version.

You must test everything fully. It is required that your new functions work 
properly with the linked list program, but that may not provide a very
convenient way of doing a full test. Feel free to use the "Testing a heap
allocation system" code from class 13.

And something I forgot to mention in class: We know that the best way to get
a heap of the biggest possible size is to call init like this: 
    init(!0x101, !0x100 - !0x101);
which is a bit confusing to a new programmer. Why not just get rid of the
parameters, so the programmer can just type init();, and make your version
of init always use the values !0x101 and !0x100 - !0x101, no need for
parameters at all. Even better, give your heap.b library program a pre_start
function so that everything is automatic, the programmer doesn't have to
know or do anything about init.

Because of the potential problems caused by the unpredictable ordering of
pre_starts and other initialisations, I recommend that you don't use pre_start
here. Instead, give your version of init a distinct name. Your init should
as well as doing its current job of making the memory starting at !0x101 into
a proper ready-to-use heap, also do the two assignments newvec := my_newvec
and freevec := my_freevec. The user will have to add an explicit call my_init()
at the beginning of their start, but then you'll know that everything is done
in the right order.

Example run, but not good enough.

$ run hw4
Enter the strings and deletions:
> hello
> this
> program
> works
> ALL
(link@434)(string@42C)works 
(link@424)(string@41C)program 
(link@414)(string@40C)this
(link@404)(string@3FC)hello
> properly
> DELETE program
> dog
> ALL
(link@41C)(string@424)dog 
(link@444)(string@43C)properly
(link@434)(string@42C)works 
(link@414)(string@40C)this
(link@404)(string@3FC)hello
> cat
> DELETE dog
> ALL
(link@454)(string@44C)cat 
(link@444)(string@43C)properly
(link@434)(string@42C)works 
(link@414)(string@40C)this
(link@404)(string@3FC)hello
> END
$

Some sensible stages to go through:

version 1:
   Write your own init, make it take the space it is given, and divide it into
something like 8 equally sized pieces. Make each into a chunk, setting its
used/free entry to indicate free, both copies of the size correctly, and the
prev and next pointers to stitch them all together in a linked list. Make
sure the first chunk's prev is nil, and the last chunk's next is nil. Create
a global variable, something like first_free and make it point to the first chunk.
   Write a function that is given a pointer to a chunk, and assuming that chunk
is in the freelist, removes it from the list. No loops or anything. This is a
doubly-linked list, no searching is needed.
   Write a very basic newvec(N) function. It should search the free list to
find the first chunk whose size is >= the needed size. Remember that the needed
size is not just N. Every chunk needs at least N+3 words, and that must be a 
minimum of 5, and for the future it will need to be rounded UP to a multiple
of 8. If no such chunk is found, error. When you do find a suitable chunk, use
the remove function that you just wrote to remove it from the free-list, and
return the pointer to that chunk. Remember that you will really return pointer+2.
Your users will expect to be able to say something like { p = newvec(2);
p ! 0 := xxxx; p ! 1 := yyyy; ... }. If the value of p is actually the pointer
to the beginning of the chunk, those two assignments will be overwriting
the free/sued code and the size.
   Don't bother with freevec yet.
   Test it carefully, but be aware that you will only be able to use newvec
8 times before you get the out-of-memory error. Your tests, right from the
beginning, should include printing every pointer that newvec gives you. If
init also prints the chunk pointers that it creates, you will be able to
verify that newvec is giving you the right chunks.
   Right from the beginning, I suggest using something like this for your
testing: http://rabbit.eng.miami.edu/class/een421/n272a.txt. Forget about
the linked lists from assignment 4, time is getting short.

version 2:
   Write another function that does the opposite of remove. It is given a 
pointer to a chunk as its parameter, and it adds that chunk to the beginning
of the free list. The chunk will need to be given correct values for next and
prev, and whatever used to be at the fron of the free list (if there was
anything) will need to have its prev pointer changed.
   Modify newvec to make it less wasteful. If its search finds a chunk of exactly
the right size, then just do as before, everything is good. If the chunk is
bigger than needed, remove it from the list as before, then split it in two.
The first half will consist of words 0 to needed-1, the second half will consist
of words needed to true-size. Make the second half into a new chunk by setting
its free/used, andboth copies of size. Then use the add-to-freelist function
that you just wrote to add it to the free list. The first half will need to have
both copies of its size set, and its free/used set to used. return it+2 as the
result to the caller.
   Test it carefully. This time, because newvec splits large chunks, you should
be able to do newvec a lot of times before running out of memory.

version 3:
   Now that newvec can split a large chunk, there is no need for init to divide
the original space up into 8 chunks. Change it (it will become a lot simpler) so
that it just creates one giant chunk, with free, size, and size, and with prev
and next both nil. Make first_free point to it.
   Test it. You won't need very thorough tests. After such a small change it will
either work or it won't, you'll see which very quickly.

version 4:
   Write a freevec function. Don't make it do very much. Just set the chunk to
free and add it to the free list. Remember that you will have to subtract 2 from
freevec's parameter to get the true address of the chunk.
   Test it carefully. If freevec also prints all the pointers it receives, you
will again be able to verify that the correct things are happening. Make sure
that after a freevec, the next newvec does receive the same chunk if it is big
enough.

version 5:
   Create multiple free lists, one for each of the possible sizes 8, 16, 24, 32,
40, ... up to some reasonable maximum maybe 1018 (8 less than 1024, 2**10) and
one extra for any chunks bigger than that maximum. Doing this is an easy modification
of init. Assuming you do use 1018 as I said, init should check that the size it
is given is significantly bigger that 1024. Let's say the call was init(space, size):
we'll use the first 1024 words of space as our vector of free lists, and the
remainder as our one initial chunk. A free_list is now set equal to the parameter
space. Fill the first 1024 words with nils to indicate that the free lists are all
still empty.
   Ch := space + 1024 is now the pointer to your first giant free chunk. Set its
free/used, sizes, next and prev appropriately and make free_list ! 1023 point to
it.
   Newvec will need a modification. From the size requested, it should work out
which free list a chunk of that size should be in. It should start at that position
but carry on going up through the free lists until it finds one that is not empty.
   Modify your functions for adding to and removing from the free list. It will be
a small modification. remove can look at the chunk's size and perform a simple
calculation to discover which free list it is on. I'd expect size = 8 to go to
freelist ! 0, size = 16 to go to freelist ! 1, etc (just dividing by 8), but don't
forget that the maximum is 1024. The add function can also do the same, it will
only be given proper chunks with their sizes correctly set.
   Test it carefully. This time the printfrees function in the test code is important.
After every operation make sure that the free lists contain exactly the chunks
they should contain.

version 6:
   The final step. Make freevec merge neighbouring free chunks. Every time freevec
is used, it should look at the chunk immediately before it (with a lower address)
and the chunk immediately after it (with a higher address). No searching is wanted.
We are not talking about the chunk's positions in the free lists, we are talking
about their actual addresses in memory. Having access to a chunk's sizes lets you
very simply calculate the addresses of the two neighbouting chunks.
   If either or both of the neighbouring chunks are free, they need to be merged
into a single chunk. Do it in steps. First look at the following chunk. If it is
free, remove it from its linked list, adjust the current chunk's sizes so that
it swallows up the following chunk. Then look at the preceding chunk. If it is
also free, remove it from its own free list, then modify its sizes so that it
swallows up the current one. Whatever the result is should then be added to the
free list appropriate to its size.
   Test it carefully. If it really works, you're done.