Adding upstream version 2.1.1.upstream/2.1.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1136 insertions, 0 deletions

diff --git a/test/segment_tree/test_main.cpp b/test/segment_tree/test_main.cpp
new file mode 100644
index 0000000..c636a22
--- /dev/null
+++ b/test/segment_tree/test_main.cpp
@@ -0,0 +1,1136 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2010, 2011 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "mdds/segment_tree.hpp"
+
+#include <cstdlib>
+#include <cstdio>
+#include <iostream>
+#include <list>
+#include <memory>
+#include <sstream>
+#include <string>
+#include <vector>
+
+#define ARRAY_SIZE(x) sizeof(x) / sizeof(x[0])
+
+using namespace std;
+using namespace mdds;
+
+template<typename key_type, typename value_type>
+void build_and_dump(segment_tree<key_type, value_type>& db)
+{
+    cout << "build and dump (start) -----------------------------------------" << endl;
+    db.build_tree();
+    db.dump_tree();
+    db.dump_leaf_nodes();
+    cout << "build and dump (end) -------------------------------------------" << endl;
+}
+
+struct test_data
+{
+    string name; // data structure expects the data to have 'name' data member.
+
+    test_data(const string& s) : name(s)
+    {}
+
+    struct ptr_printer
+    {
+        void operator()(const test_data* data) const
+        {
+            cout << data->name << " ";
+        }
+    };
+
+    /**
+     * Use this to sort instances of test_data by name, in ascending order.
+     */
+    struct sort_by_name
+    {
+        bool operator()(const test_data* left, const test_data* right) const
+        {
+            return left->name < right->name;
+        }
+    };
+
+    struct name_printer
+    {
+        void operator()(const test_data* p) const
+        {
+            cout << p->name << " ";
+        }
+    };
+};
+
+template<typename key_type, typename value_type>
+bool check_leaf_nodes(
+    const segment_tree<key_type, value_type>& db, const key_type* keys, value_type* data_chain, size_t key_size)
+{
+    typedef segment_tree<key_type, value_type> st_type;
+    vector<typename st_type::leaf_node_check> checks;
+    checks.reserve(key_size);
+    size_t dcid = 0;
+    for (size_t i = 0; i < key_size; ++i)
+    {
+        typename st_type::leaf_node_check c;
+        c.key = keys[i];
+        value_type p = data_chain[dcid];
+        while (p)
+        {
+            c.data_chain.push_back(p);
+            p = data_chain[++dcid];
+        }
+        checks.push_back(c);
+        ++dcid;
+    }
+
+    return db.verify_leaf_nodes(checks);
+}
+
+template<typename value_type>
+bool check_against_expected(const list<value_type>& test, value_type* expected)
+{
+    size_t i = 0;
+    value_type p = expected[i++];
+    typename list<value_type>::const_iterator itr = test.begin(), itr_end = test.end();
+    while (p)
+    {
+        if (itr == itr_end)
+            // data chain ended prematurely.
+            return false;
+
+        if (*itr != p)
+            // the value is not as expected.
+            return false;
+
+        p = expected[i++];
+        ++itr;
+    }
+    if (itr != itr_end)
+        // data chain is too long.
+        return false;
+
+    return true;
+}
+
+/**
+ * Only check the search result against expected result set.  The caller
+ * needs to run search and pass the result to this function.
+ */
+template<typename key_type, typename value_type>
+bool check_search_result_only(
+    const segment_tree<key_type, value_type>& /*db*/,
+    const typename segment_tree<key_type, value_type>::search_results_type& result, key_type key, value_type* expected)
+{
+    cout << "search key: " << key << " ";
+
+    list<value_type> test;
+    copy(result.begin(), result.end(), back_inserter(test));
+    test.sort(test_data::sort_by_name());
+
+    cout << "search result (sorted): ";
+    for_each(test.begin(), test.end(), test_data::name_printer());
+    cout << endl;
+
+    return check_against_expected(test, expected);
+}
+
+/**
+ * Run the search and check the search result.
+ */
+template<typename key_type, typename value_type>
+bool check_search_result(const segment_tree<key_type, value_type>& db, key_type key, value_type* expected)
+{
+    cout << "search key: " << key << " ";
+
+    typedef typename segment_tree<key_type, value_type>::search_results_type search_result_type;
+    search_result_type data_chain;
+    db.search(key, data_chain);
+    return check_search_result_only(db, data_chain, key, expected);
+}
+
+template<typename key_type, typename value_type>
+bool check_search_result_iterator(const segment_tree<key_type, value_type>& db, key_type key, value_type* expected)
+{
+    cout << "search key: " << key << " ";
+
+    typedef segment_tree<key_type, value_type> db_type;
+    typename db_type::search_results result = db.search(key);
+    list<value_type> test;
+    copy(result.begin(), result.end(), back_inserter(test));
+    test.sort(test_data::sort_by_name());
+
+    cout << "search result (sorted): ";
+    for_each(test.begin(), test.end(), test_data::name_printer());
+    cout << endl;
+
+    return check_against_expected(test, expected);
+}
+
+void st_test_insert_search_removal()
+{
+    stack_printer __stack_printer__("::st_test_insert_segments");
+
+    typedef long key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    db_type db;
+    value_type A("A"), B("B"), C("C"), D("D"), E("E"), F("F"), G("G");
+
+    build_and_dump(db);
+    assert(db_type::node::get_instance_count() == 0);
+
+    db.insert(0, 10, &A);
+    build_and_dump(db);
+    {
+        key_type keys[] = {0, 10};
+        value_type* data_chain[] = {&A, 0, 0};
+        assert(check_leaf_nodes(db, keys, data_chain, ARRAY_SIZE(keys)));
+        assert(db_type::node::get_instance_count() == db.leaf_size());
+        assert(db.verify_node_lists());
+    }
+
+    db.insert(0, 5, &B);
+    build_and_dump(db);
+    {
+        key_type keys[] = {0, 5, 10};
+        value_type* data_chain[] = {&A, &B, 0, &A, 0, 0};
+        assert(check_leaf_nodes(db, keys, data_chain, ARRAY_SIZE(keys)));
+        assert(db_type::node::get_instance_count() == db.leaf_size());
+    }
+
+    db.insert(5, 12, &C);
+    build_and_dump(db);
+    {
+        key_type keys[] = {0, 5, 10, 12};
+        value_type* data_chain[] = {&A, &B, 0, &A, &C, 0, &C, 0, 0};
+        assert(check_leaf_nodes(db, keys, data_chain, ARRAY_SIZE(keys)));
+        assert(db_type::node::get_instance_count() == db.leaf_size());
+        assert(db.verify_node_lists());
+    }
+
+    db.insert(10, 24, &D);
+    build_and_dump(db);
+    {
+        key_type keys[] = {0, 5, 10, 12, 24};
+        value_type* data_chain[] = {&A, &B, 0, &A, &C, 0, &C, &D, 0, &D, 0, 0};
+        assert(check_leaf_nodes(db, keys, data_chain, ARRAY_SIZE(keys)));
+        assert(db_type::node::get_instance_count() == db.leaf_size());
+        assert(db.verify_node_lists());
+    }
+
+    db.insert(4, 24, &E);
+    build_and_dump(db);
+    {
+        key_type keys[] = {0, 4, 5, 10, 12, 24};
+        value_type* data_chain[] = {&B, 0, &B, &E, 0, &A, &C, 0, &C, &D, 0, &D, &E, 0, 0};
+        assert(check_leaf_nodes(db, keys, data_chain, ARRAY_SIZE(keys)));
+        assert(db_type::node::get_instance_count() == db.leaf_size());
+        assert(db.verify_node_lists());
+    }
+
+    db.insert(0, 26, &F);
+    build_and_dump(db);
+    {
+        key_type keys[] = {0, 4, 5, 10, 12, 24, 26};
+        value_type* data_chain[] = {&B, 0, &B, &E, 0, &A, &C, 0, &C, &D, 0, &D, &E, &F, 0, &F, 0, 0};
+        assert(check_leaf_nodes(db, keys, data_chain, ARRAY_SIZE(keys)));
+        assert(db_type::node::get_instance_count() == db.leaf_size());
+        assert(db.verify_node_lists());
+    }
+
+    db.insert(12, 26, &G);
+    build_and_dump(db);
+    {
+        key_type keys[] = {0, 4, 5, 10, 12, 24, 26};
+        value_type* data_chain[] = {&B, 0, &B, &E, 0, &A, &C, 0, &C, &D, 0, &D, &E, &F, &G, 0, &F, &G, 0, 0};
+        assert(check_leaf_nodes(db, keys, data_chain, ARRAY_SIZE(keys)));
+        assert(db_type::node::get_instance_count() == db.leaf_size());
+        assert(db.verify_node_lists());
+    }
+
+    // Search tests.  Test boundary cases.
+
+    for (key_type i = -10; i <= 30; ++i)
+    {
+        db_type::search_results_type data_chain;
+        db.search(i, data_chain);
+        cout << "search key " << i << ": ";
+        for_each(data_chain.begin(), data_chain.end(), test_data::ptr_printer());
+        cout << endl;
+    }
+
+    {
+        key_type key = -1;
+        value_type* expected[] = {0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 0;
+        value_type* expected[] = {&A, &B, &F, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 4;
+        value_type* expected[] = {&A, &B, &E, &F, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 5;
+        value_type* expected[] = {&A, &C, &E, &F, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 10;
+        value_type* expected[] = {&C, &D, &E, &F, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 12;
+        value_type* expected[] = {&D, &E, &F, &G, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 24;
+        value_type* expected[] = {&F, &G, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 30;
+        value_type* expected[] = {0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 9999;
+        value_type* expected[] = {0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    // Remove E, F and G and check search results.
+
+    db.remove(&E);
+    db.remove(&F);
+    db.remove(&G);
+    cout << "removed: E F G" << endl;
+    db.dump_tree();
+    db.dump_leaf_nodes();
+
+    for (key_type i = -10; i <= 30; ++i)
+    {
+        db_type::search_results_type data_chain;
+        db.search(i, data_chain);
+        cout << "search key " << i << ": ";
+        for_each(data_chain.begin(), data_chain.end(), test_data::ptr_printer());
+        cout << endl;
+    }
+
+    {
+        key_type key = -1;
+        value_type* expected[] = {0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 0;
+        value_type* expected[] = {&A, &B, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 4;
+        value_type* expected[] = {&A, &B, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 5;
+        value_type* expected[] = {&A, &C, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 10;
+        value_type* expected[] = {&C, &D, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 12;
+        value_type* expected[] = {&D, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 24;
+        value_type* expected[] = {0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 30;
+        value_type* expected[] = {0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 9999;
+        value_type* expected[] = {0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    // Re-build the tree and check the search results once again, to make sure
+    // we get the same results.
+
+    db.build_tree();
+    db.dump_tree();
+    db.dump_leaf_nodes();
+
+    {
+        key_type key = -1;
+        value_type* expected[] = {0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 0;
+        value_type* expected[] = {&A, &B, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 4;
+        value_type* expected[] = {&A, &B, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 5;
+        value_type* expected[] = {&A, &C, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 10;
+        value_type* expected[] = {&C, &D, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 12;
+        value_type* expected[] = {&D, 0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 24;
+        value_type* expected[] = {0};
+        assert(check_search_result(db, key, expected));
+    }
+
+    {
+        key_type key = 30;
+        value_type* expected[] = {0};
+        assert(check_search_result(db, key, expected));
+    }
+}
+
+void st_test_copy_constructor()
+{
+    stack_printer __stack_printer__("::st_test_copy_constructor");
+
+    typedef long key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    db_type db;
+    value_type A("A"), B("B"), C("C"), D("D"), E("E"), F("F"), G("G");
+    vector<db_type::segment_data> segments;
+    segments.push_back(db_type::segment_data(0, 10, &A));
+    segments.push_back(db_type::segment_data(0, 5, &B));
+    segments.push_back(db_type::segment_data(5, 12, &C));
+    segments.push_back(db_type::segment_data(10, 24, &D));
+    segments.push_back(db_type::segment_data(4, 24, &E));
+    segments.push_back(db_type::segment_data(0, 26, &F));
+    segments.push_back(db_type::segment_data(12, 26, &G));
+    segments.push_back(db_type::segment_data(0, 0, nullptr)); // null-terminated
+
+    db_type::segment_map_type checks;
+    for (size_t i = 0; segments[i].pdata; ++i)
+    {
+        db.insert(segments[i].begin_key, segments[i].end_key, segments[i].pdata);
+        pair<key_type, key_type> range;
+        range.first = segments[i].begin_key;
+        range.second = segments[i].end_key;
+        checks.insert(db_type::segment_map_type::value_type(segments[i].pdata, range));
+    }
+
+    // Copy before the tree is built.
+
+    db.dump_segment_data();
+    assert(db.verify_segment_data(checks));
+
+    db_type db_copied(db);
+    db_copied.dump_segment_data();
+    assert(db_copied.verify_segment_data(checks));
+    assert(db.is_tree_valid() == db_copied.is_tree_valid());
+    assert(db == db_copied);
+
+    // Copy after the tree is built.
+    db.build_tree();
+    db_type db_copied_tree(db);
+    db_copied_tree.dump_segment_data();
+    db_copied_tree.dump_tree();
+    assert(db_copied_tree.verify_segment_data(checks));
+    assert(db.is_tree_valid() == db_copied_tree.is_tree_valid());
+    assert(db == db_copied_tree);
+}
+
+void st_test_equality()
+{
+    stack_printer __stack_printer__("::st_test_equality");
+
+    typedef uint32_t key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    value_type A("A"), B("B"), C("C"), D("D"), E("E"), F("F"), G("G");
+    {
+        db_type db1, db2;
+        db1.insert(0, 10, &A);
+        db2.insert(0, 10, &A);
+        assert(db1 == db2);
+        db2.insert(5, 12, &B);
+        assert(db1 != db2);
+        db1.insert(5, 12, &C);
+        assert(db1 != db2);
+        db1.remove(&C);
+        db2.remove(&B);
+        assert(db1 == db2);
+        db1.insert(4, 20, &D);
+        db2.insert(4, 20, &D);
+        assert(db1 == db2);
+        db1.insert(3, 12, &E);
+        db2.insert(3, 15, &E);
+        assert(db1 != db2);
+    }
+}
+
+void st_test_clear()
+{
+    stack_printer __stack_printer__("::st_test_clear");
+
+    typedef uint8_t key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    value_type A("A"), B("B"), C("C"), D("D"), E("E"), F("F"), G("G");
+
+    vector<db_type::segment_data> segments;
+    segments.push_back(db_type::segment_data(0, 10, &A));
+    segments.push_back(db_type::segment_data(0, 5, &B));
+    segments.push_back(db_type::segment_data(5, 12, &C));
+    segments.push_back(db_type::segment_data(10, 24, &D));
+    segments.push_back(db_type::segment_data(4, 24, &E));
+    segments.push_back(db_type::segment_data(0, 26, &F));
+    segments.push_back(db_type::segment_data(12, 26, &G));
+    segments.push_back(db_type::segment_data(0, 0, nullptr)); // null-terminated
+
+    db_type db;
+    for (size_t i = 0; segments[i].pdata; ++i)
+        db.insert(segments[i].begin_key, segments[i].end_key, segments[i].pdata);
+
+    assert(!db.empty());
+    assert(db.size() == 7);
+    cout << "size of db is " << db.size() << endl;
+
+    db.clear();
+    assert(db.empty());
+    assert(db.size() == 0);
+
+    // Insert the same data set once again, but this time build tree afterwards.
+    for (size_t i = 0; segments[i].pdata; ++i)
+        db.insert(segments[i].begin_key, segments[i].end_key, segments[i].pdata);
+
+    db.build_tree();
+    assert(!db.empty());
+    assert(db.size() == 7);
+
+    db.clear();
+    assert(db.empty());
+    assert(db.size() == 0);
+}
+
+void st_test_duplicate_insertion()
+{
+    stack_printer __stack_printer__("::st_test_duplicate_insertion");
+
+    typedef short key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    value_type A("A"), B("B"), C("C"), D("D"), E("E"), F("F"), G("G");
+
+    db_type db;
+    assert(db.insert(0, 10, &A));
+    assert(!db.insert(0, 10, &A));
+    assert(!db.insert(2, 30, &A));
+    assert(db.insert(0, 10, &B));
+    db.remove(&A);
+    assert(db.insert(2, 30, &A));
+    build_and_dump(db);
+}
+
+/**
+ * When the number of segments is not a multiple of 2, it creates a tree
+ * where the right side becomes "cut off".  Make sure the search works
+ * correctly under those conditions.
+ */
+void st_test_search_on_uneven_tree()
+{
+    stack_printer __stack_printer__("::st_test_search_on_uneven_tree");
+
+    typedef int16_t key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    for (key_type data_count = 10; data_count < 20; ++data_count)
+    {
+        vector<unique_ptr<test_data>> data_store;
+        data_store.reserve(data_count);
+        for (key_type i = 0; i < data_count; ++i)
+        {
+            ostringstream os;
+            os << hex << showbase << i;
+            data_store.emplace_back(new test_data(os.str()));
+        }
+        assert(data_store.size() == static_cast<size_t>(data_count));
+
+        db_type db;
+        for (key_type i = 0; i < data_count; ++i)
+        {
+            test_data* p = data_store[i].get();
+            db.insert(0, i + 1, p);
+        }
+        assert(db.size() == static_cast<size_t>(data_count));
+
+        db.build_tree();
+
+        for (key_type i = -1; i < data_count + 1; ++i)
+        {
+            db_type::search_results_type result;
+            bool success = db.search(i, result);
+            assert(success);
+            cout << "search key: " << i << "  result: ";
+            for_each(result.begin(), result.end(), test_data::name_printer());
+            cout << endl;
+        }
+    }
+}
+
+void st_test_perf_insertion()
+{
+    stack_printer __stack_printer__("::st_test_perf_insertion");
+
+    typedef uint32_t key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    key_type data_count = 1000000;
+
+    // First, create test data instances and store them into a vector.
+    vector<unique_ptr<test_data>> data_store;
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: data array creation");
+        data_store.reserve(data_count);
+        for (key_type i = 0; i < data_count; ++i)
+        {
+            ostringstream os;
+            os << hex << i;
+            data_store.emplace_back(new test_data(os.str()));
+        }
+    }
+    assert(data_store.size() == data_count);
+
+    db_type db;
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: data array insertion into segment tree");
+        for (key_type i = 0; i < data_count; ++i)
+        {
+            test_data* p = data_store[i].get();
+            db.insert(0, i + 1, p);
+        }
+    }
+    assert(db.size() == data_count);
+
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: build tree");
+        db.build_tree();
+    }
+    assert(db.is_tree_valid());
+
+    const test_data* test = nullptr;
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: 200 searches with max results");
+        for (key_type i = 0; i < 200; ++i)
+        {
+            db_type::search_results_type result;
+            db.search(0, result);
+            db_type::search_results_type::const_iterator itr = result.begin(), itr_end = result.end();
+            for (; itr != itr_end; ++itr)
+            {
+                test = *itr;
+                assert(test);
+            }
+        }
+    }
+
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: 200 searches with max results (iterator)");
+        for (key_type i = 0; i < 200; ++i)
+        {
+            db_type::search_results result = db.search(0);
+            db_type::search_results::iterator itr = result.begin(), itr_end = result.end();
+            for (; itr != itr_end; ++itr)
+            {
+                test = *itr;
+                assert(test);
+            }
+        }
+    }
+
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: 200 searches with median results");
+        for (key_type i = 0; i < 200; ++i)
+        {
+            db_type::search_results_type result;
+            db.search(data_count / 2, result);
+            db_type::search_results_type::const_iterator itr = result.begin(), itr_end = result.end();
+            for (; itr != itr_end; ++itr)
+            {
+                test = *itr;
+                assert(test);
+            }
+        }
+    }
+
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: 200 searches with median results (iterator)");
+        for (key_type i = 0; i < 200; ++i)
+        {
+            db_type::search_results result = db.search(data_count / 2);
+            db_type::search_results::iterator itr = result.begin(), itr_end = result.end();
+            for (; itr != itr_end; ++itr)
+            {
+                test = *itr;
+                assert(test);
+            }
+        }
+    }
+
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: 200 searches with empty results");
+        for (key_type i = 0; i < 200; ++i)
+        {
+            db_type::search_results_type result;
+            db.search(data_count, result);
+            db_type::search_results_type::const_iterator itr = result.begin(), itr_end = result.end();
+            for (; itr != itr_end; ++itr)
+            {
+                test = *itr;
+                assert(test);
+            }
+        }
+    }
+
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: 200 searches with empty results (iterator)");
+        for (key_type i = 0; i < 200; ++i)
+        {
+            db_type::search_results result = db.search(data_count);
+            db_type::search_results::iterator itr = result.begin(), itr_end = result.end();
+            for (; itr != itr_end; ++itr)
+            {
+                test = *itr;
+                assert(test);
+            }
+        }
+    }
+
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: 10000 segment removals");
+        for (key_type i = 0; i < 10000; ++i)
+        {
+            test_data* p = data_store[i].get();
+            db.remove(p);
+        }
+    }
+    assert(db.size() == data_count - 10000);
+
+    {
+        stack_printer __stack_printer2__("::st_test_perf_insertion:: clear");
+        db.clear();
+    }
+}
+
+void st_test_aggregated_search_results()
+{
+    stack_printer __stack_printer__("::st_test_aggregated_search_results");
+
+    typedef uint16_t key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    value_type A("A"), B("B"), C("C"), D("D"), E("E"), F("F"), G("G");
+
+    vector<db_type::segment_data> segments;
+    segments.push_back(db_type::segment_data(0, 10, &A));
+    segments.push_back(db_type::segment_data(0, 5, &B));
+    segments.push_back(db_type::segment_data(5, 12, &C));
+    segments.push_back(db_type::segment_data(10, 24, &D));
+    segments.push_back(db_type::segment_data(4, 24, &E));
+    segments.push_back(db_type::segment_data(0, 26, &F));
+    segments.push_back(db_type::segment_data(12, 26, &G));
+    segments.push_back(db_type::segment_data(0, 0, nullptr)); // null-terminated
+
+    db_type db;
+    for (size_t i = 0; segments[i].pdata; ++i)
+        db.insert(segments[i].begin_key, segments[i].end_key, segments[i].pdata);
+
+    db.dump_segment_data();
+    db.build_tree();
+
+    db_type::search_results_type result;
+    {
+        key_type key = 0;
+        db.search(key, result);
+        value_type* expected[] = {&A, &B, &F, 0};
+        assert(check_search_result_only(db, result, key, expected));
+    }
+
+    {
+        key_type key = 10;
+        db.search(key, result);
+        // Note the duplicated F's in the search result.
+        value_type* expected[] = {&A, &B, &C, &D, &E, &F, &F, 0};
+        assert(check_search_result_only(db, result, key, expected));
+    }
+
+    {
+        key_type key = 5;
+        db.search(key, result);
+        value_type* expected[] = {&A, &A, &B, &C, &C, &D, &E, &E, &F, &F, &F, 0};
+        assert(check_search_result_only(db, result, key, expected));
+    }
+
+    {
+        result.clear(); // clear the accumulated result set.
+        key_type key = 5;
+        db.search(key, result);
+        value_type* expected[] = {&A, &C, &E, &F, 0};
+        assert(check_search_result_only(db, result, key, expected));
+    }
+}
+
+void st_test_dense_tree_search()
+{
+    stack_printer __stack_printer__("::st_test_dense_tree_search");
+
+    typedef uint16_t key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    value_type A("A"), B("B"), C("C"), D("D"), E("E"), F("F"), G("G");
+    db_type db;
+    db.insert(0, 1, &A);
+    db.insert(0, 2, &B);
+    db.insert(0, 3, &C);
+    db.insert(0, 4, &D);
+    db.insert(0, 5, &E);
+    db.insert(0, 6, &F);
+    db.insert(0, 7, &G);
+    db.build_tree();
+    db.dump_tree();
+    db.dump_leaf_nodes();
+
+    {
+        db_type::value_type expected[] = {&A, &B, &C, &D, &E, &F, &G, 0};
+        bool success = check_search_result<key_type, value_type*>(db, 0, expected);
+        assert(success);
+    }
+    {
+        db_type::value_type expected[] = {&B, &C, &D, &E, &F, &G, 0};
+        bool success = check_search_result<key_type, value_type*>(db, 1, expected);
+        assert(success);
+    }
+    {
+        db_type::value_type expected[] = {&C, &D, &E, &F, &G, 0};
+        bool success = check_search_result<key_type, value_type*>(db, 2, expected);
+        assert(success);
+    }
+    {
+        db_type::value_type expected[] = {&D, &E, &F, &G, 0};
+        bool success = check_search_result<key_type, value_type*>(db, 3, expected);
+        assert(success);
+    }
+    {
+        db_type::value_type expected[] = {&E, &F, &G, 0};
+        bool success = check_search_result<key_type, value_type*>(db, 4, expected);
+        assert(success);
+    }
+    {
+        db_type::value_type expected[] = {&F, &G, 0};
+        bool success = check_search_result<key_type, value_type*>(db, 5, expected);
+        assert(success);
+    }
+    {
+        db_type::value_type expected[] = {&G, 0};
+        bool success = check_search_result<key_type, value_type*>(db, 6, expected);
+        assert(success);
+    }
+    {
+        db_type::value_type expected[] = {0};
+        bool success = check_search_result<key_type, value_type*>(db, 7, expected);
+        assert(success);
+    }
+}
+
+void st_test_search_on_empty_set()
+{
+    stack_printer __stack_printer__("::st_test_search_on_empty_set");
+
+    typedef uint16_t key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    db_type db;
+    db.build_tree();
+
+    // Search on an empty set should still be considered a success as long as
+    // the tree is built beforehand.
+    db_type::search_results_type result;
+    bool success = db.search(0, result);
+    assert(success);
+    assert(result.empty());
+}
+
+void st_test_search_iterator_basic()
+{
+    stack_printer __stack_printer__("::st_test_search_iterator");
+    typedef uint16_t key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    value_type A("A"), B("B"), C("C"), D("D"), E("E"), F("F"), G("G");
+    db_type db;
+    db.insert(0, 1, &A);
+    db.insert(0, 2, &B);
+    db.insert(0, 3, &C);
+    db.insert(0, 4, &D);
+    db.insert(0, 5, &E);
+    db.insert(0, 6, &F);
+    db.insert(0, 7, &G);
+    db.build_tree();
+    db.dump_tree();
+    db.dump_leaf_nodes();
+
+    db_type::search_results result = db.search(0);
+    db_type::search_results::iterator itr;
+    db_type::search_results::iterator itr_beg = result.begin();
+    db_type::search_results::iterator itr_end = result.end();
+    cout << "Iterate through the search results." << endl;
+    for (itr = itr_beg; itr != itr_end; ++itr)
+        cout << (*itr)->name << " ";
+    cout << endl;
+
+    cout << "Do it again." << endl;
+    for (itr = itr_beg; itr != itr_end; ++itr)
+        cout << (*itr)->name << " ";
+    cout << endl;
+
+    cout << "Iterate backwards" << endl;
+    do
+    {
+        --itr;
+        cout << (*itr)->name << " ";
+    } while (itr != itr_beg);
+    cout << endl;
+
+    cout << "Get the last item from the end position." << endl;
+    itr = itr_end;
+    --itr;
+    cout << (*itr)->name << endl;
+
+    cout << "Use for_each to print names." << endl;
+    for_each(itr_beg, itr_end, test_data::ptr_printer());
+    cout << endl;
+}
+
+void st_test_search_iterator_result_check()
+{
+    stack_printer __stack_printer__("::st_test_search_iterator_result_check");
+
+    typedef uint16_t key_type;
+    typedef test_data value_type;
+    typedef segment_tree<key_type, value_type*> db_type;
+
+    value_type A("A"), B("B"), C("C"), D("D"), E("E"), F("F"), G("G");
+    db_type db;
+    db.insert(0, 1, &A);
+    db.insert(0, 2, &B);
+    db.insert(0, 3, &C);
+    db.insert(0, 4, &D);
+    db.insert(0, 5, &E);
+    db.insert(0, 6, &F);
+    db.insert(0, 7, &G);
+    db.build_tree();
+
+    {
+        value_type* expected[] = {&A, &B, &C, &D, &E, &F, &G, 0};
+        bool success = check_search_result_iterator<key_type, value_type*>(db, 0, expected);
+        assert(success);
+    }
+    {
+        value_type* expected[] = {&B, &C, &D, &E, &F, &G, 0};
+        bool success = check_search_result_iterator<key_type, value_type*>(db, 1, expected);
+        assert(success);
+    }
+    {
+        value_type* expected[] = {&C, &D, &E, &F, &G, 0};
+        bool success = check_search_result_iterator<key_type, value_type*>(db, 2, expected);
+        assert(success);
+    }
+    {
+        value_type* expected[] = {&D, &E, &F, &G, 0};
+        bool success = check_search_result_iterator<key_type, value_type*>(db, 3, expected);
+        assert(success);
+    }
+    {
+        value_type* expected[] = {&E, &F, &G, 0};
+        bool success = check_search_result_iterator<key_type, value_type*>(db, 4, expected);
+        assert(success);
+    }
+    {
+        value_type* expected[] = {&F, &G, 0};
+        bool success = check_search_result_iterator<key_type, value_type*>(db, 5, expected);
+        assert(success);
+    }
+    {
+        value_type* expected[] = {&G, 0};
+        bool success = check_search_result_iterator<key_type, value_type*>(db, 6, expected);
+        assert(success);
+    }
+    {
+        value_type* expected[] = {0};
+        bool success = check_search_result_iterator<key_type, value_type*>(db, 7, expected);
+        assert(success);
+    }
+}
+
+/**
+ * When calling search() on empty tree, even without calling build_tree()
+ * should still return a valid search_result instance with a size of 0.
+ */
+void st_test_empty_result_set()
+{
+    stack_printer __stack_printer__("::st_test_empty_result_set");
+    typedef segment_tree<long, string*> db_type;
+    db_type db;
+    db_type::search_results result = db.search(0);
+    cout << "size of empty result set: " << result.size() << endl;
+    assert(result.size() == 0);
+}
+
+void st_test_non_pointer_data()
+{
+    stack_printer __stack_printer__("::st_test_non_pointer_data");
+
+    typedef uint16_t key_type;
+    typedef size_t value_type;
+    typedef segment_tree<key_type, value_type> db_type;
+
+    db_type db;
+    db.insert(0, 1, 10);
+    db.build_tree();
+
+    db_type::search_results result = db.search(0);
+    assert(result.size() == 1);
+    assert(*result.begin() == 10);
+}
+
+int main(int argc, char** argv)
+{
+    try
+    {
+        cmd_options opt;
+        if (!parse_cmd_options(argc, argv, opt))
+            return EXIT_FAILURE;
+
+        if (opt.test_func)
+        {
+            st_test_insert_search_removal();
+            st_test_copy_constructor();
+            st_test_equality();
+            st_test_clear();
+            st_test_duplicate_insertion();
+            st_test_search_on_uneven_tree();
+            st_test_aggregated_search_results();
+            st_test_dense_tree_search();
+            st_test_search_on_empty_set();
+            st_test_search_iterator_basic();
+            st_test_search_iterator_result_check();
+            st_test_empty_result_set();
+            st_test_non_pointer_data();
+        }
+
+        if (opt.test_perf)
+        {
+            st_test_perf_insertion();
+        }
+
+        // At this point, all of the nodes created during the test run should have
+        // been destroyed.  If not, we are leaking memory.
+        typedef segment_tree<uint32_t, void*> db_type;
+        assert(db_type::node::get_instance_count() == 0);
+    }
+    catch (const std::exception& e)
+    {
+        fprintf(stdout, "Test failed: %s\n", e.what());
+        return EXIT_FAILURE;
+    }
+    fprintf(stdout, "Test finished successfully!\n");
+    return EXIT_SUCCESS;
+}