On Sat, 8 Oct 2011, Jojy Varghese wrote: > Hi Sage > Wondering about the status of this patch. Oh yeah, I pushed it to a wip-intervaltree branch. We haven't had time to use it for the MDS locking code yet, so it's sitting there waiting for that. It would also be good to integrate your unit tests to the gtest framework (i.e. move it to the src/test/ directory, use gtest to run the tests, and add to the check_PROGRAMS list in the Makefile so it runs with 'make check'). sage > > thanks > Jojy > > On Sat, Sep 24, 2011 at 3:23 PM, Jojy Varghese <jojy.varghese@xxxxxxxxx> wrote: > > Hi > > This patch-set of 2 patches has following changes: > > - Interval tree implementation > > - Unit test cases for the implementation > > > > Interval tree is an optimized data structure for representing and > > querying intervals. Elementary intervals are > > represented as nodes of an avl tree and the corresponding data is > > stored on these nodes based on a concept of span. > > This representation allows log(n) (where n is the number of > > data) storage. The balanced avl tree allows a log(n) query. > > > > The implementation is a template class that is instantiated > > based on parameters : > > - Interval type > > - Data type > > > > This is a basic component which can be used to store byte range locks. > > > > > > -Jojy > > > >
