Commit Graph

4 Commits

Author SHA1 Message Date
Michael Gottesman
0612d886e9 Add a "hasEmptyIntersection" method to ImmutablePointerSet.
We do this by doing a traversal of our sorted lists in a similar manner as one
would when one is merging two such sets, i.e. one has two iterators and always
advances the iterator that has a value that is less than the other. If we ever
hit a situation where the two iterators equal, we must have a non-empty
intersection.

A unittest that exercises very basic functionality is provided as well.
2016-03-08 14:05:10 -08:00
Michael Gottesman
90dcaa7de3 Rename ImmutablePointerSet::concat => ImmutablePointerSet::merge. 2016-02-16 02:13:56 -08:00
Michael Gottesman
6434e5b032 Some small fixes suggested by Jordan to ImmutablePointerSet.
The larger changes are coming in a subsequent commit.
2016-02-16 02:13:55 -08:00
Michael Gottesman
0936d3d4b8 [arc] Add a new data structure called ImmutablePointerSet.
This is an immutable data structure with the following properties:

1. All of the sets are sorted and can be iterated over.
2. It takes in a bump ptr allocator and uses that allocator for all
allocations.
3. All concatenation operations involve only one bump ptr allocation.
4. Since we are only storing pointers, the data structure does not need any
destructors to be invoked to be cleaned up. The bumpptrallocator memory just
needs to be freed.

I am going to use this to improve the compile time performance of ARC.
2016-02-14 15:26:59 -08:00