Added user malloc/free/realloc functions to the range tree.

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

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

Checkpoint in lock tree implementation

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

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

Added doxygen file and the generated doxygen documentation for range trees

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

Make benchmark-test a little quieter by default, and make -v make it a little louder again.  Addresses #13.

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

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

This makes big difference for space (46% smaller) and a small time difference (5% faster), as measured by benchmark-test.

Before:
{{{
$ ./benchmark-test
nodesize=1048576
keysize=8
valsize=8
Serial and random insertions of 1048576 per batch
serial  8.753964s   119783/s    random  5.640094s   185915/s    cumulative 14.394118s   145695/s
serial  9.381472s   111771/s    random  7.325284s   143145/s    cumulative 31.100944s   134861/s
serial  9.859233s   106355/s    random  6.734307s   155707/s    cumulative 47.694553s   131911/s
serial 11.069200s    94729/s    random  6.885863s   152280/s    cumulative 65.649695s   127778/s
Shutdown  4.636875s
Total time 70.286611s for 8388608 insertions =   119349/s
$ ls -l sinsert.brt
-rwxrwxr-x 1 bradley bradley 730344924 Jan 22 11:47 sinsert.brt
}}}

After:
{{{
$ ./benchmark-test
nodesize=1048576
keysize=8
valsize=8
Serial and random insertions of 1048576 per batch
serial  8.521855s   123046/s    random  5.730942s   182967/s    cumulative 14.252861s   147139/s
serial  9.106047s   115152/s    random  7.001765s   149759/s    cumulative 30.360740s   138149/s
serial  9.543696s   109871/s    random  6.651000s   157657/s    cumulative 46.555503s   135139/s
serial 10.627035s    98671/s    random  6.555884s   159944/s    cumulative 63.738491s   131610/s
Shutdown  2.818513s
Total time 66.557042s for 8388608 insertions =   126036/s
$ ls -l sinsert.brt
-rwxrwxr-x 1 bradley bradley 396894480 Jan 22 11:45 sinsert.brt
}}}



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

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

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

Addresses #293

Checkpoint in header and implementation of lock tree.

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

from ydb-internal.h



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

Added comment about static buffers being fine if they are of sufficient size
i.e. for limited queries.

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

Addresses #290

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

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