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

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

Add accessor function for allow_overlaps in range trees.

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

toku_malloc/calloc/realloc/memdup now use size_t instead of
nonportable int types.

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

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

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