Addresses #290

git-svn-id: file:///svn/tokudb@1782 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1780 c7de825b-a66e-492c-adef-691d508d4ae1

Coded toku_rt_decrease capacity to reclaim memory if size of range tree becomes
too small for local array.

git-svn-id: file:///svn/tokudb@1779 c7de825b-a66e-492c-adef-691d508d4ae1

Linear time range tree implementation complete and passes all tests.

git-svn-id: file:///svn/tokudb@1778 c7de825b-a66e-492c-adef-691d508d4ae1

Fixed minor bugs in tests.

git-svn-id: file:///svn/tokudb@1777 c7de825b-a66e-492c-adef-691d508d4ae1

Checkpoint in implementing linear.c

git-svn-id: file:///svn/tokudb@1776 c7de825b-a66e-492c-adef-691d508d4ae1

test Cases for pred/succ
 * Empty tree
  * Pred return nothing.
  * Succ return nothing.
 * 1 element tree.
  * Pred
  * Before
  * left
  * middle
  * right
  * after.
 * Succ
  * Before
  * left
  * middle
  * right
  * after
 * 2 element tree.
  * Pred, Succ
   * In empty space
    * Nothing to the left/Right (pred/succ) respectively.
    * something to the left/right (pred/succ) respectively.
   * On left endpoint.
    * Nothing to the left/Right (pred/succ) respectively.
    * something to the left/right (pred/succ) respectively.
   * On right endpoint.
    * Nothing to the left/Right (pred/succ) respectively.
    * something to the left/right (pred/succ) respectively.
   * In middle of range.
    * Nothing to the left/Right (pred/succ) respectively.
    * something to the left/right (pred/succ) respectively.


git-svn-id: file:///svn/tokudb@1774 c7de825b-a66e-492c-adef-691d508d4ae1

Bugfix in error cases of range trees.

git-svn-id: file:///svn/tokudb@1773 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1772 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1771 c7de825b-a66e-492c-adef-691d508d4ae1

Fixes bugs in tests where find parameters did not have data == NULL

git-svn-id: file:///svn/tokudb@1770 c7de825b-a66e-492c-adef-691d508d4ae1

 * Query Tests:
  * Tree is empty (return none).
  * Tree contains only elements to the left.
  * Tree contains only elements to the right.
  * Tree contains only elements to the left and to the right.
  * Tree contains overlaps and elements to the left.
  * Tree contains overlaps and elements to the right.
  * Tree contains overlaps and elements to the left and to the right.


git-svn-id: file:///svn/tokudb@1769 c7de825b-a66e-492c-adef-691d508d4ae1

 * Query Tests:
  * Tree is empty (return none).
  * Tree contains only elements to the left.
  * Tree contains only elements to the right.
  * Tree contains only elements to the left and to the right.
  * Tree contains overlaps and elements to the left.
  * Tree contains overlaps and elements to the right.
  * Tree contains overlaps and elements to the left and to the right.


git-svn-id: file:///svn/tokudb@1768 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1767 c7de825b-a66e-492c-adef-691d508d4ae1

Test of     /*
        Limited/Unlimited Queries

        Limit of k does not produce all, but limit of 0 does.         Single point overlaps
    */


git-svn-id: file:///svn/tokudb@1757 c7de825b-a66e-492c-adef-691d508d4ae1

Updated header and makefile for rangetree.h

git-svn-id: file:///svn/tokudb@1746 c7de825b-a66e-492c-adef-691d508d4ae1

Added the following tests:

 * Single point overlaps
  * Tree: {|0-1|}, query of |1-2| returns |0-1|
  * Tree: {|1-2|}, query of |0-1| returns |1-2|
  * Tree: {|1-2|}, insert of of |0-1| success == allow_overlaps
  * Tree: {|0-1|}, insert of of |1-2| success == allow_overlaps
 * Complete overlaps
  * Tree: {|0-3|}, query of |1-2| returns |0-3|
  * Tree: {|1-2|}, query of |0-3| returns |1-2|
  * Tree: {|1-2|}, insert of of |0-3| success == allow_overlaps
  * Tree: {|0-3|}, insert of of |1-2| success == allow_overlaps
 * Exact overlaps
  * Tree: {|0-3|}, query of |0-3| returns |0-3|
  * Tree: {|0-3|}, insert of of |0-3| success == allow_overlaps

Also freed buf and NULLed the pointer to help find memory leaks.

git-svn-id: file:///svn/tokudb@1745 c7de825b-a66e-492c-adef-691d508d4ae1

More range tree tests.

git-svn-id: file:///svn/tokudb@1744 c7de825b-a66e-492c-adef-691d508d4ae1

Additional tests for range trees.

git-svn-id: file:///svn/tokudb@1743 c7de825b-a66e-492c-adef-691d508d4ae1

back to toku_rt_insert.
The error code was for insert, not delete.

git-svn-id: file:///svn/tokudb@1742 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1741 c7de825b-a66e-492c-adef-691d508d4ae1

First set of test cases for range trees.
linear.c is stub implementation so we can compile and write tests before
we actually implement the range tree.

The makefiles were modified just enough to get this to work, and have to
be cleaned up a lot.

git-svn-id: file:///svn/tokudb@1740 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1739 c7de825b-a66e-492c-adef-691d508d4ae1

Added header file with documentation for range trees

git-svn-id: file:///svn/tokudb@1738 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1737 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1736 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1735 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1734 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1733 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1732 c7de825b-a66e-492c-adef-691d508d4ae1

rollback for 5 now runs (but the files are wrong).  Started working on a brtdump that will help debug this stuff.  Right away I see important file differences after recover (the unused memory and unnamed root are wrong). Addresses #27.

git-svn-id: file:///svn/tokudb@1731 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1730 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1729 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1719 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1718 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1717 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1716 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1715 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1714 c7de825b-a66e-492c-adef-691d508d4ae1

git-svn-id: file:///svn/tokudb@1713 c7de825b-a66e-492c-adef-691d508d4ae1