Checkpoint 2 Submision:
cd into your cs44/labs/ subdirectory and copy over this
directory and its contents:
cp -r /home/newhall/public/cs44/lab05/checkpt2 .
cd into the checkpt2 directory, open the README file and follow the
The directions assume that your Lab repo is in
If it is in a different subdirectory, then adjust the cp command
examples in the README accordingly.
(you are going to copy your btree.[cpp,h] files into this directory,
run make, run the test script redirecting its output to a file,
cp the file to your repo, and add, commit and push the output file).
I will demo these steps in lab on Monday, but you can do them
before then, and must run and add, commit, and push the ouput
file to your repo anytime before 4:30 on Monday.
I will pull everyone's repo at that time to get your checkpoint 2
Here is a samle of what your chkpt2_out file might look like:
Final Part of Lab 5
The last functionality to implement is:
- File scans. These are the support for range queries (and exact match
queries) on the index. The state of a scan is kept in the BTreeIndex
data members. You need to implement methods to start and end a scan and
to get the next rid in an initialized scan.
- Splitting internal nodes. This may be the most difficult part of
the lab. I suggest that you start by drawing different examples and cases
and stepping through them on paper, and then planning out your algorithm
before jummping in and coding. Remember that all split nodes must be
at least 50% full. Test with DEBUG defined so you can trigger a lot
of splitting, and use a printTree method to help you see the effects of
You sould also do some testing without DEBUG defined to see that
it works on larger capacity nodes. File scan functionality is useful for
large index testing; you can do some scans over the resulting index to see
if ranges of K* entries are in correct order after splits.
- Further testing and test code development to stress test your solution:
inserts, scans, correctness and error handling. Make sure you test some
large size indexes. File scans are useful for large index testing.
As you work on C++ labs, remember all these resources:
- Mapping a type onto a Raw Page
Some examples of mapping types onto arrays of bytes (the difference between creating
an object of a type and mapping a type onto a chunk of bytes (a Page in this lab)).
- Week 5 Monday lab: C++ strings and mapping
structures onto raw memory.
- Week 2 Monday lab: C++ exceptions, reference parameters, const
- Week 1 Monday lab: C++ programming, C++ debugging
tools (valgrind and gdb), C-style strings, other resources for CS lab work
- There is lots of documentation also available off
my help pages
Under "Language Help" the C and C++ headings have a lot of information and
resources for C++ and C programming (and look under both for resources, most of
the common parts of the language are listed under my C resources), including
command line arguments in C (and C++).
- If you are interested in writing your own bash scripts for testing,
you can use the run_all.sh script as an example (it uses command line
arguments defined by my main program, so you should adjust to yours).
Also, here are some bash programming links that might be helpful:
shell programming links