path: root/lib/binary_search_tree/hosttest/binary_search_tree_test.cpp

/*
 * Copyright (c) 2019 LK Trusty Authors. All Rights Reserved.
 *
 * 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 <lib/binary_search_tree.h>
#include <lk/compiler.h>
#include <stdlib.h>

#include "gtest/gtest.h"

class BstTest : public testing::TestWithParam<bool> {
};

struct bst_test_entry {
    struct bst_node node;
};

INSTANTIATE_TEST_SUITE_P(BstTestMirror, BstTest, testing::Bool());

static int bst_test_compare(struct bst_node *a, struct bst_node *b) {
    if (BstTest::GetParam()) {
        return a > b ? 1 : a < b ? -1 : 0;
    } else {
        return a < b ? 1 : a > b ? -1 : 0;
    }
}

static struct bst_node *bst_test_search(struct bst_root *root,
                                        struct bst_node *node) {
    return bst_search(root, node, bst_test_compare);
}

static struct bst_node *bst_node(struct bst_node nodes[], size_t index[],
                                 size_t i, size_t i_size) {
    if (BstTest::GetParam()) {
        i = i_size - 1 - i;
    }
    if (index) {
        i = index[i];
    }
    return &nodes[i];
}

std::ostream& operator<<(std::ostream& os, const struct bst_node* node) {
  return os <<
    "Node (" << (void*)node << "):\n" <<
    "  Parent:" << (void*)node->parent << "\n" <<
    "  Rank: " << node->rank << "\n" <<
    "  Left child: " << (void*)node->child[0] << "\n" <<
    "  Right child: " << (void*)node->child[1] << "\n";
}

std::ostream& operator<<(std::ostream& os, const struct bst_root* root) {
  return os << "Root (" << (void*)root << ")\n";
}

/**
 * bst_subtree_depth - Internal helper function
 * @node:   Root of a subtree.
 *
 * Return: Depth of subtree at @node, or 0 if @node is %NULL.
 */
static size_t bst_subtree_depth(struct bst_node *node) {
    if (!node) {
        return 0;
    } else {
        size_t child_depth[2];
        for (size_t i = 0; i < 2; i++) {
            child_depth[i] = bst_subtree_depth(node->child[i]);
        }
        return 1 + MAX(child_depth[0], child_depth[1]);
    }
}

/**
 * bst_depth - Debug function - return depth of tree
 * @root:   Tree.
 *
 * Return: Depth of @root.
 */
static size_t bst_depth(struct bst_root *root) {
    return bst_subtree_depth(root->root);
}

static bool bst_is_right_child(struct bst_node *node) {
    DEBUG_ASSERT(node);
    DEBUG_ASSERT(!node->parent || node->parent->child[0] == node ||
                 node->parent->child[1] == node);
    return node->parent && node->parent->child[1] == node;
}

static void bst_test_check_node(struct bst_root *root, struct bst_node *node) {
    if (node->parent) {
        ASSERT_NE(root->root, node) << node << root;
        ASSERT_EQ(node->parent->child[bst_is_right_child(node)], node) << node << root;
    } else {
        ASSERT_EQ(root->root, node) << node << root;;
    }
}

static void print_rep(char ch, size_t count) {
    for (size_t i = 0; i < count; i++) {
        printf("%c", ch);
    }
}

static size_t bst_test_node_num(struct bst_node *node,
                                struct bst_node nodes[]) {
    return nodes ? node - nodes : 0;
}

static void bst_test_print_node_at(struct bst_root *root,
                                   struct bst_node nodes[], size_t row,
                                   size_t col, size_t depth) {
    size_t space = (1 << (depth - row)) - 2;
    struct bst_node *node = root->root;
    for (size_t mask = 1 << row >> 1; node && mask; mask >>= 1) {
        node = node->child[!!(col & mask)];
    }
    if (col) {
        printf("    ");
    }
    print_rep(' ', space);
    print_rep(node && node->child[0] ? '_' : ' ', space);
    if (node) {
        printf("%02zur%01zu", bst_test_node_num(node, nodes), node->rank);
    } else {
        printf("    ");
    }
    print_rep(node && node->child[1] ? '_' : ' ', space);
    print_rep(' ', space);
    /*
     *               ______________0004______________
     *       ______0003______                ______0003______
     *   __0002__        __0002__        __0002__        __0002__
     * 0001    0001    0001    0001    0001    0001    0001    0001
     */
}

static void bst_test_print_tree(struct bst_root *root, struct bst_node nodes[]) {
    size_t depth = bst_depth(root);
    printf("Tree depth %zu\n", depth);
    for (size_t row = 0; row < depth; row++) {
        for (size_t col = 0; col < 1 << row; col++) {
            bst_test_print_node_at(root, nodes, row, col, depth);
        }
        printf("\n");
    }
}

static void bst_test_check_tree_valid(struct bst_root *root) {
    struct bst_node *node = 0;
    while (true) {
        node = bst_next(root, node);
        if (!node) {
            break;
        }
        bst_test_check_node(root, node);
    }
    if(::testing::Test::HasFailure()) {
        bst_test_print_tree(root, NULL);
    }
}

static void bst_test_check_array(struct bst_root *root,
                                     struct bst_node nodes[],
                                     size_t index[],
                                     size_t count,
                                     struct bst_node *left,
                                     struct bst_node *right) {
    for (size_t i = 0; i < count; i++) {
        struct bst_node *node = bst_node(nodes, index, i, count);
        EXPECT_EQ(bst_test_search(root, node), node) << "Node: " << (node - nodes) << "\n";
    }

    if (!count) {
        EXPECT_EQ(bst_next(root, left), right);
        EXPECT_EQ(bst_prev(root, right), left);
        return;
    }

    EXPECT_EQ(bst_next(root, left), bst_node(nodes, index, 0, count));
    EXPECT_EQ(bst_prev(root, bst_node(nodes, index, 0, count)), left);
    for (size_t i = 0; i < count - 1; i++) {
        struct bst_node *node = bst_node(nodes, index, i, count);
        struct bst_node *next = bst_node(nodes, index, i + 1, count);
        EXPECT_EQ(bst_next(root, node), next) << "node: " << (node - nodes) << ", next: " << (next - nodes);
        EXPECT_EQ(bst_prev(root, next), node) << "next: " << (next - nodes) << ", node: " << (node - nodes);
    }
    EXPECT_EQ(bst_next(root, bst_node(nodes, index, count - 1, count)), right);
    EXPECT_EQ(bst_prev(root, right), bst_node(nodes, index, count - 1, count));}

#define bst_test_check(root, nodes, items...) do { \
    SCOPED_TRACE("bst_test_check"); \
    size_t index[] = {items}; \
    bst_test_check_array(root, nodes, index, countof(index), NULL, NULL); \
    if (HasFatalFailure()) return; \
} while(0)

static void bst_test_insert_func(struct bst_root *root, struct bst_node *node) {
    ASSERT_EQ(node->rank, 0U);
    bst_insert(root, node, bst_test_compare);
    bst_test_check_tree_valid(root);
    EXPECT_EQ(bst_test_search(root, node), node);
}

#define bst_test_insert(root, node) do { \
    SCOPED_TRACE(testing::Message() << "bst_insert" << node); \
    bst_test_insert_func(root, node); \
    if (HasFatalFailure()) return; \
} while(0)

#define bst_test_insert_check(root, nodes, insert, items...) do { \
    bst_test_insert(root, &nodes[insert]); \
    bst_test_check(root, nodes, items); \
} while(0)

#define bst_test_delete_check(root, nodes, insert, items...) do { \
    bst_test_delete(root, &nodes[insert]); \
    bst_test_check(root, nodes, items); \
} while(0)

static void bst_test_delete_func(struct bst_root *root, struct bst_node *node) {
    bst_delete(root, node);
    bst_test_check_tree_valid(root);
    EXPECT_EQ(bst_test_search(root, node), nullptr);
}

#define bst_test_delete(root, node) do { \
    SCOPED_TRACE(testing::Message() << "bst_delete" << node); \
    bst_test_delete_func(root, node); \
    if (HasFatalFailure()) return; \
} while(0)

/*
 * Test init api
 */
TEST(BstTest, InitRootValue) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    EXPECT_EQ(root.root, nullptr);
}

TEST(BstTest, InitRootFunction) {
    struct bst_root root;
    memset(&root, 0xff, sizeof(root));
    bst_root_initialize(&root);
    EXPECT_EQ(root.root, nullptr);
}

TEST(BstTest, InitNodeValue) {
    struct bst_node node = BST_NODE_INITIAL_VALUE;
    EXPECT_EQ(node.rank, 0U);
}

TEST(BstTest, InitNodeFnction) {
    struct bst_node node;
    memset(&node, 0xff, sizeof(node));
    bst_node_initialize(&node);
    EXPECT_EQ(node.rank, 0U);
}

/*
 * Simple tests to check that api return expected results.
 */
TEST_P(BstTest, InsertAscending) {
    /* Insert nodes in ascending order (or decending for mirrored test) */
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 14] = BST_NODE_INITIAL_VALUE};

    bst_test_check(&root, nodes);
    for (size_t i = 0; i < countof(nodes); i++) {
        bst_test_insert(&root, &nodes[i]);
        if (GetParam()) {
            EXPECT_EQ(bst_prev(&root, &nodes[i]), nullptr);
        } else {
            EXPECT_EQ(bst_next(&root, &nodes[i]), nullptr);
        }
    }
    bst_test_check_array(&root, nodes, NULL, countof(nodes), NULL, NULL);
    EXPECT_GE(bst_depth(&root), 4U); /* Minimum depth for a binary tree */
}

TEST_P(BstTest, InsertBalanced) {
    /*
     *         ______7_____
     *        /            \
     *     __3__           _11_
     *    /     \         /    \
     *   1       5       9      13
     *  / \     / \     / \    /  \
     * 0   2   4   6   8  10  12  14
     */
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 14] = BST_NODE_INITIAL_VALUE};
    size_t index[] = { 7, 3, 11, 1, 5, 9, 13, 0, 2, 4, 6, 8, 10, 12, 14 };
    for (size_t i = 0; i < countof(index); i++) { \
        bst_test_insert(&root, &nodes[index[i]]);
    }
    bst_test_check_array(&root, nodes, NULL, countof(nodes), NULL, NULL);
    EXPECT_EQ(bst_depth(&root), 4U);
}

TEST_P(BstTest, DeleteOnlyEntry) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 0] = BST_NODE_INITIAL_VALUE};
    bst_test_insert_check(&root, nodes, 0, 0);
    /*
     * 0
     */
    bst_test_delete_check(&root, nodes, 0);
}

TEST_P(BstTest, DeleteRootOneChild) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 1] = BST_NODE_INITIAL_VALUE};
    bst_test_insert_check(&root, nodes, 1, 1);
    bst_test_insert_check(&root, nodes, 0, 0, 1);
    /*
     *   1
     *  /
     * 0
     */
    bst_test_delete_check(&root, nodes, 1, 0);
}

TEST_P(BstTest, DeleteRootTwoChildren) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 2] = BST_NODE_INITIAL_VALUE};

    bst_test_insert_check(&root, nodes, 1, 1);
    bst_test_insert_check(&root, nodes, 0, 0, 1);
    bst_test_insert_check(&root, nodes, 2, 0, 1, 2);
    /*
     *   1
     *  / \
     * 0   2
     */
    bst_test_delete_check(&root, nodes, 1, 0, 2);
}

TEST_P(BstTest, DeleteRootManyChildrenOneSide) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 4] = BST_NODE_INITIAL_VALUE};

    bst_test_insert_check(&root, nodes, 3, 3);
    bst_test_insert_check(&root, nodes, 1, 1, 3);
    bst_test_insert_check(&root, nodes, 4, 1, 3, 4);
    bst_test_insert_check(&root, nodes, 0, 0, 1, 3, 4);
    bst_test_insert_check(&root, nodes, 2, 0, 1, 2, 3, 4);
    /*
     *     __3__
     *    /     \
     *   1       4
     *  / \
     * 0   2
     */
    bst_test_delete_check(&root, nodes, 3, 0, 1, 2, 4);
}

TEST_P(BstTest, DeleteRootManyChildrenBothSides) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 6] = BST_NODE_INITIAL_VALUE};

    bst_test_insert_check(&root, nodes, 3, 3);
    bst_test_insert_check(&root, nodes, 1, 1, 3);
    bst_test_insert_check(&root, nodes, 5, 1, 3, 5);
    bst_test_insert_check(&root, nodes, 0, 0, 1, 3, 5);
    bst_test_insert_check(&root, nodes, 2, 0, 1, 2, 3, 5);
    bst_test_insert_check(&root, nodes, 4, 0, 1, 2, 3, 4, 5);
    bst_test_insert_check(&root, nodes, 6, 0, 1, 2, 3, 4, 5, 6);
    /*
     *     __3__
     *    /     \
     *   1       5
     *  / \     / \
     * 0   2   4   6
     */
    bst_test_delete_check(&root, nodes, 3, 0, 1, 2, 4, 5, 6);
}

TEST_P(BstTest, DeleteEdge1) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 4] = BST_NODE_INITIAL_VALUE};

    bst_test_insert_check(&root, nodes, 3, 3);
    bst_test_insert_check(&root, nodes, 1, 1, 3);
    bst_test_insert_check(&root, nodes, 4, 1, 3, 4);
    bst_test_insert_check(&root, nodes, 0, 0, 1, 3, 4);
    bst_test_insert_check(&root, nodes, 2, 0, 1, 2, 3, 4);
    /*
     *     __3__
     *    /     \
     *   1       4
     *  / \
     * 0   2
     */

    bst_test_delete_check(&root, nodes, 4, 0, 1, 2, 3);
}

TEST_P(BstTest, DeleteInternal) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 4] = BST_NODE_INITIAL_VALUE};

    bst_test_insert_check(&root, nodes, 3, 3);
    bst_test_insert_check(&root, nodes, 1, 1, 3);
    bst_test_insert_check(&root, nodes, 4, 1, 3, 4);
    bst_test_insert_check(&root, nodes, 0, 0, 1, 3, 4);
    bst_test_insert_check(&root, nodes, 2, 0, 1, 2, 3, 4);
    /*
     *     __3__
     *    /     \
     *   1       4
     *  / \
     * 0   2
     */
    bst_test_delete_check(&root, nodes, 1, 0, 2, 3, 4);
}

TEST_P(BstTest, ForEveryEntry) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 254] = BST_NODE_INITIAL_VALUE};
    struct bst_test_entry *entry;

    for (size_t i = 0; i < countof(nodes); i++) {
        bst_test_insert(&root, &nodes[i]);
    }

    size_t i = 0;
    bst_for_every_entry(&root, entry, struct bst_test_entry, node) {
        EXPECT_EQ(&entry->node, bst_node(nodes, NULL, i, countof(nodes)));
        i++;
    }
    EXPECT_EQ(i, countof(nodes));
}

TEST_P(BstTest, ForEveryEntryExplicitDelete) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 254] = BST_NODE_INITIAL_VALUE};
    struct bst_test_entry *entry;

    for (size_t i = 0; i < countof(nodes); i++) {
        bst_test_insert(&root, &nodes[i]);
    }

    size_t i = 0;
    bst_for_every_entry(&root, entry, struct bst_test_entry, node) {
        EXPECT_EQ(&entry->node, bst_node(nodes, NULL, i, countof(nodes)));
        i++;
        bst_delete(&root, &entry->node);
    }
    EXPECT_EQ(i, countof(nodes));

    EXPECT_EQ(bst_next(&root, NULL), nullptr);
}

TEST_P(BstTest, ForEveryEntryDelete) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 254] = BST_NODE_INITIAL_VALUE};
    struct bst_test_entry *entry;

    for (size_t i = 0; i < countof(nodes); i++) {
        bst_test_insert(&root, &nodes[i]);
    }

    size_t i = 0;
    bst_for_every_entry_delete(&root, entry, struct bst_test_entry, node) {
        EXPECT_EQ(&entry->node, bst_node(nodes, NULL, i, countof(nodes)));
        i++;
    }
    EXPECT_EQ(i, countof(nodes));

    EXPECT_EQ(bst_next(&root, NULL), nullptr);
}

TEST_P(BstTest, RandomInsert) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 999] = BST_NODE_INITIAL_VALUE};
    for (size_t i = 0; i < countof(nodes);) {
        struct bst_node *node = &nodes[lrand48() % countof(nodes)];
        if (!node->rank) {
            bst_test_insert(&root, node);
            ASSERT_GE(node->rank, 1U);
            EXPECT_EQ(bst_test_search(&root, node), node);
            i++;
        }
    }
}

TEST_P(BstTest, RandomInsertRandomDelete) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 999] = BST_NODE_INITIAL_VALUE};
    for (size_t i = 0; i < countof(nodes);) {
        struct bst_node *node = &nodes[lrand48() % countof(nodes)];
        if (!node->rank) {
            bst_test_insert(&root, node);
            ASSERT_GE(node->rank, 1U);
            EXPECT_EQ(bst_test_search(&root, node), node);
            i++;
        }
    }
    for (size_t i = 0; i < countof(nodes);) {
        struct bst_node *node = &nodes[lrand48() % countof(nodes)];
        if (node->rank) {
            bst_test_delete(&root, node);
            EXPECT_EQ(node->rank, 0U);
            EXPECT_EQ(bst_test_search(&root, node), nullptr) << node;
            i++;
        }
    }
}

TEST_P(BstTest, RandomInsertDelete) {
    struct bst_root root = BST_ROOT_INITIAL_VALUE;
    struct bst_node nodes[] = {[0 ... 499] = BST_NODE_INITIAL_VALUE};
    for (size_t i = 0; i < countof(nodes) * 100; i++) {
        struct bst_node *node = &nodes[lrand48() % countof(nodes)];
        if (node->rank) {
            bst_test_delete(&root, node);
            ASSERT_EQ(node->rank, 0U);
            EXPECT_EQ(bst_test_search(&root, node), nullptr);
        } else {
            bst_test_insert(&root, node);
            EXPECT_GE(node->rank, 1U);
            EXPECT_EQ(bst_test_search(&root, node), node);
        }
    }
}