unittest_radix_tree.cpp

Go to the documentation of this file.

/* SPDX-License-Identifier: MPL-2.0 */
 
#include "../tests/testutil.hpp"
 
#include <radix_tree.hpp>
#include <stdint.hpp>
 
#include <set>
#include <string>
#include <string.h>
#include <unity.h>
#include <vector>
 
void setUp ()
{
}
void tearDown ()
{
}
 
bool tree_add (zmq::radix_tree_t &tree_, const std::string &key_)
{
    return tree_.add (reinterpret_cast<const unsigned char *> (key_.data ()),
                      key_.size ());
}
 
bool tree_rm (zmq::radix_tree_t &tree_, const std::string &key_)
{
    return tree_.rm (reinterpret_cast<const unsigned char *> (key_.data ()),
                     key_.size ());
}
 
bool tree_check (zmq::radix_tree_t &tree_, const std::string &key_)
{
    return tree_.check (reinterpret_cast<const unsigned char *> (key_.data ()),
                        key_.size ());
}
 
void test_empty ()
{
    zmq::radix_tree_t tree;
 
    TEST_ASSERT_TRUE (tree.size () == 0);
}
 
void test_add_single_entry ()
{
    zmq::radix_tree_t tree;
 
    TEST_ASSERT_TRUE (tree_add (tree, "foo"));
}
 
void test_add_same_entry_twice ()
{
    zmq::radix_tree_t tree;
 
    TEST_ASSERT_TRUE (tree_add (tree, "test"));
    TEST_ASSERT_FALSE (tree_add (tree, "test"));
}
 
void test_rm_when_empty ()
{
    zmq::radix_tree_t tree;
 
    TEST_ASSERT_FALSE (tree_rm (tree, "test"));
}
 
void test_rm_single_entry ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "temporary");
    TEST_ASSERT_TRUE (tree_rm (tree, "temporary"));
}
 
void test_rm_unique_entry_twice ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "test");
    TEST_ASSERT_TRUE (tree_rm (tree, "test"));
    TEST_ASSERT_FALSE (tree_rm (tree, "test"));
}
 
void test_rm_duplicate_entry ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "test");
    tree_add (tree, "test");
    TEST_ASSERT_FALSE (tree_rm (tree, "test"));
    TEST_ASSERT_TRUE (tree_rm (tree, "test"));
}
 
void test_rm_common_prefix ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "checkpoint");
    tree_add (tree, "checklist");
    TEST_ASSERT_FALSE (tree_rm (tree, "check"));
}
 
void test_rm_common_prefix_entry ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "checkpoint");
    tree_add (tree, "checklist");
    tree_add (tree, "check");
    TEST_ASSERT_TRUE (tree_rm (tree, "check"));
}
 
void test_rm_null_entry ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "");
    TEST_ASSERT_TRUE (tree_rm (tree, ""));
}
 
void test_check_empty ()
{
    zmq::radix_tree_t tree;
 
    TEST_ASSERT_FALSE (tree_check (tree, "foo"));
}
 
void test_check_added_entry ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "entry");
    TEST_ASSERT_TRUE (tree_check (tree, "entry"));
}
 
void test_check_common_prefix ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "introduce");
    tree_add (tree, "introspect");
    TEST_ASSERT_FALSE (tree_check (tree, "intro"));
}
 
void test_check_prefix ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "toasted");
    TEST_ASSERT_FALSE (tree_check (tree, "toast"));
    TEST_ASSERT_FALSE (tree_check (tree, "toaste"));
    TEST_ASSERT_FALSE (tree_check (tree, "toaster"));
}
 
void test_check_nonexistent_entry ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "red");
    TEST_ASSERT_FALSE (tree_check (tree, "blue"));
}
 
void test_check_query_longer_than_entry ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "foo");
    TEST_ASSERT_TRUE (tree_check (tree, "foobar"));
}
 
void test_check_null_entry_added ()
{
    zmq::radix_tree_t tree;
 
    tree_add (tree, "");
    TEST_ASSERT_TRUE (tree_check (tree, "all queries return true"));
}
 
void test_size ()
{
    zmq::radix_tree_t tree;
 
    // Adapted from the example on wikipedia.
    std::vector<std::string> keys;
    keys.push_back ("tester");
    keys.push_back ("water");
    keys.push_back ("slow");
    keys.push_back ("slower");
    keys.push_back ("test");
    keys.push_back ("team");
    keys.push_back ("toast");
 
    for (size_t i = 0; i < keys.size (); ++i)
        TEST_ASSERT_TRUE (tree_add (tree, keys[i]));
    TEST_ASSERT_TRUE (tree.size () == keys.size ());
    for (size_t i = 0; i < keys.size (); ++i)
        TEST_ASSERT_FALSE (tree_add (tree, keys[i]));
    TEST_ASSERT_TRUE (tree.size () == 2 * keys.size ());
    for (size_t i = 0; i < keys.size (); ++i)
        TEST_ASSERT_FALSE (tree_rm (tree, keys[i]));
    TEST_ASSERT_TRUE (tree.size () == keys.size ());
    for (size_t i = 0; i < keys.size (); ++i)
        TEST_ASSERT_TRUE (tree_rm (tree, keys[i]));
    TEST_ASSERT_TRUE (tree.size () == 0);
}
 
void return_key (unsigned char *data_, size_t size_, void *arg_)
{
    std::vector<std::string> *vec =
      reinterpret_cast<std::vector<std::string> *> (arg_);
    std::string key;
    for (size_t i = 0; i < size_; ++i)
        key.push_back (static_cast<char> (data_[i]));
    vec->push_back (key);
}
 
void test_apply ()
{
    zmq::radix_tree_t tree;
 
    std::set<std::string> keys;
    keys.insert ("tester");
    keys.insert ("water");
    keys.insert ("slow");
    keys.insert ("slower");
    keys.insert ("test");
    keys.insert ("team");
    keys.insert ("toast");
 
    const std::set<std::string>::iterator end = keys.end ();
    for (std::set<std::string>::iterator it = keys.begin (); it != end; ++it)
        tree_add (tree, *it);
 
    std::vector<std::string> *vec = new std::vector<std::string> ();
    tree.apply (return_key, static_cast<void *> (vec));
    for (size_t i = 0; i < vec->size (); ++i)
        TEST_ASSERT_TRUE (keys.count ((*vec)[i]) > 0);
    delete vec;
}
 
int main (void)
{
    setup_test_environment ();
 
    UNITY_BEGIN ();
 
    RUN_TEST (test_empty);
    RUN_TEST (test_add_single_entry);
    RUN_TEST (test_add_same_entry_twice);
 
    RUN_TEST (test_rm_when_empty);
    RUN_TEST (test_rm_single_entry);
    RUN_TEST (test_rm_unique_entry_twice);
    RUN_TEST (test_rm_duplicate_entry);
    RUN_TEST (test_rm_common_prefix);
    RUN_TEST (test_rm_common_prefix_entry);
    RUN_TEST (test_rm_null_entry);
 
    RUN_TEST (test_check_empty);
    RUN_TEST (test_check_added_entry);
    RUN_TEST (test_check_common_prefix);
    RUN_TEST (test_check_prefix);
    RUN_TEST (test_check_nonexistent_entry);
    RUN_TEST (test_check_query_longer_than_entry);
    RUN_TEST (test_check_null_entry_added);
 
    RUN_TEST (test_size);
 
    RUN_TEST (test_apply);
 
    return UNITY_END ();
}