Refactor LinkedList? #116
Description
lnkd_list.h is full of custom data structures based around LinkedList. It would be nice if we could scrap these in favor of LLVM data structures, but that may not be realistic. If we do scrap it, we should probably ensure we either don't need our custom features or replace our custom features.
The following is mostly notes to myself:
One particular feature of this LinkedList bit me: the maxSize custom allocator. Currently, if you specify a max size, the LinkedList will allocate an array and hand off consecutive elements of the array rather than allocate a new Entry<T>. This is good especially because of locality, making it much cheaper to access the elements of the LinkedList compared to if the nodes were scattered around memory (although I'm curious of how big of an effect this has in our code). However, this causes problems with removing elements from the LinkedList, as the only elements which can be removed is the last element in the array.
This causes problems with Dr. Heffernan's ILP node superiority algorithm, which removes edges from the graph. The predecessor list for a GraphNode is a LinkedList with a maxSize. For now, I'm not removing the edges from the graph, but it would be nice to do so.
In this case, the problem can be solved by using a free list of the removed nodes.