仅当所有测试同时执行时，UnitTest 才会失败

Question

我目前在 VS2013 中运行 Microsoft C++ UnitTest 时遇到一个奇怪的问题。

每次我在 IDE 中执行 Run All 测试时，测试都会失败，但是当我在特定的测试中使用 Run Selected Tests 时，它会成功。

我测试的是我自己的 BinarySearchTree class 的用法。如果失败，将返回异常代码 C0000005（这可能是由于指针的内部链接错误）。

那么这可能是什么原因呢？

额外

最后一段代码的测试失败了，我在其中生成随机 ID 字符串，将它们单独添加到我的 BST 并随机删除它们，直到整个 BST 再次为空。

BinarySearchTree clientList;
Client client;

// test random adding & deletion
std::vector<std::string> idAddList;
for (unsigned int i = 0; i < 100; i++)
    idAddList.push_back(randomID(20));

std::vector<std::string> idRemoveList;
unsigned int id;
while (idAddList.size() > 0)
{
    // pick random id from list and delete it
    id = rand() % idAddList.size();
    client.uniqueID = idAddList.at(id);
    clientList.add(client);
    if (clientList.lastICLResult() == iList::ICLResult::OK)
        idRemoveList.push_back(idAddList.at(id));
    idAddList.erase(idAddList.begin() + id);
}

    while (idRemoveList.size() > 0)
{
    // pick random client from list and delete it
    id = rand() % idRemoveList.size();
    clientList.remove(idRemoveList.at(id));
    if (clientList.lastICLResult() == iList::ICLResult::OK)
        idRemoveList.erase(idRemoveList.begin() + id);
}

Assert::AreEqual<unsigned int>(0, clientList.size());

这里是 randomID() 函数的代码：

std::string randomID(const unsigned int maxLength)
{
    static const char alphanum[] =
        "0123456789"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz"
        "öÖäÄüÜ"
        "!=[]$%&";

    std::string result;
    for (unsigned int i = 0; i < maxLength; i++)
        result += alphanum[rand() % (sizeof(alphanum - 1))];

    return result;
}

与此问题相关的 class-specific 代码是 removeMatch() 函数和相应的 Node class。 BST 将 Client class 作为其 add() 函数的数据 object，并且仅在其 ID 字符串不在 BST。内部还有函数 fetchMinNode() 和 fetchMaxNode()，它们在 BST 中检索指向 left-most 或 right-most 节点的指针。 main/root 节点称为 m_rootNode，如果 BST 为空，则为该节点分配 nullptr。

在 removeMatch() 函数的情况下，我总是去要删除的节点的右边 child node/subtree，并且 - 如果可能的话 - 重新分配内部节点树具体地点。

void iList::removeMatch(Node* toBeDeletedNode)
{
    if (toBeDeletedNode)
    {
        // IN CASE GIVEN NODE IS THE ROOT NODE
        if (!toBeDeletedNode->parent)
        {
            // Case 1: root node is the only node in the BST
            if (!toBeDeletedNode->left && !toBeDeletedNode->right)
                handleRootLeaf(toBeDeletedNode);

            // Case 2: either both child nodes are available or just the right
            //         child node is available
            else if ((toBeDeletedNode->left && toBeDeletedNode->right) || toBeDeletedNode->right)
                handleRootRSubtree(toBeDeletedNode);

            // Case 3: only left child node is present
            else
                handleRootLSubtree(toBeDeletedNode);
        }

        // IN CASE GIVEN NODE IS ANY CHILD NODE
        else
        {
            // Case 1: if given node is a leaf node
            if (!toBeDeletedNode->left && !toBeDeletedNode->right)
                handleChildLeaf(toBeDeletedNode);

            // Case 2: if given node has either both child nodes or just a right child node
            else if ((toBeDeletedNode->left && toBeDeletedNode->right) || toBeDeletedNode->right)
                handleChildRSubtree(toBeDeletedNode);

            // Case 3: if given node has only a left child node
            else
                handleChildLSubtree(toBeDeletedNode);
        }

        m_elementCount--;
    }
}

这里是相应的私有函数：

[私人]handleRootLSubtree()

void handleRootLSubtree(Node* toBeDeletedNode)
{
    // fetch max node in left subtree
    Node* maxNode = fetchMaxNode(toBeDeletedNode->left);

    // in case left child node is the max node
    if (maxNode->parent != toBeDeletedNode)
    {
        if (maxNode->left)
        {
            maxNode->left->parent = maxNode->parent;
            maxNode->parent->right = maxNode->left;
        }
        else
            maxNode->parent->right = nullptr;

        maxNode->left = toBeDeletedNode->left;
        maxNode->parent->parent = maxNode;
    }

    maxNode->parent = nullptr;

    // cut linkage
    toBeDeletedNode->left = nullptr;
    delete toBeDeletedNode;
    m_rootNode = maxNode;
}

[私人]handleRootRSubtree()

void handleRootRSubtree(Node* toBeDeletedNode)
{
    // fetch min node in right subtree
    Node* minNode = fetchMinNode(toBeDeletedNode->right);

    // in case right child node isn't the min node
    if (minNode->parent != toBeDeletedNode)
    {
        if (minNode->right)
        {
            minNode->right->parent = minNode->parent;
            minNode->parent->left = minNode->right;
        }
        else
            minNode->parent->left = nullptr;

        minNode->right = toBeDeletedNode->right;
        toBeDeletedNode->right->parent = minNode;
    }

    minNode->left = toBeDeletedNode->left;
    minNode->parent = nullptr;

    if (toBeDeletedNode->left)
        toBeDeletedNode->left->parent = minNode;

    // cut linkage
    toBeDeletedNode->left = nullptr;
    toBeDeletedNode->right = nullptr;
    delete toBeDeletedNode;
    m_rootNode = minNode;
}

[私人] handleRootLeaf()

void handleRootLeaf(Node* toBeDeletedNode)
{
    delete m_rootNode;
    m_rootNode = nullptr;
}

[私人]handleChildLSubtree()

void handleChildLSubtree(Node* toBeDeletedNode)
{
    // fetch max node in left subtree
    Node* maxNode = fetchMaxNode(toBeDeletedNode->left);

    // in case left child node is the max node
    if (maxNode->parent == toBeDeletedNode)
        maxNode->parent = toBeDeletedNode->parent;
    else
    {
        if (maxNode->left)
        {
            maxNode->left->parent = maxNode->parent;
            maxNode->parent->right = maxNode->left;
        }
        else
            maxNode->parent->right = nullptr;

        maxNode->left = toBeDeletedNode->left;
        toBeDeletedNode->left->parent = maxNode;
        maxNode->parent = toBeDeletedNode->parent;
    }

    if (toBeDeletedNode->parent->left
        && toBeDeletedNode->parent->left == toBeDeletedNode)
        toBeDeletedNode->parent->left = maxNode;
    else
        toBeDeletedNode->parent->right = maxNode;

    // cut linkage
    toBeDeletedNode->left = nullptr;
    toBeDeletedNode->right = nullptr;
    delete toBeDeletedNode;
}

[私人]handleChildRSubtree()

void handleChildRSubtree(Node* toBeDeletedNode)
{
    // fetch min node in right subtree
    Node* minNode = fetchMinNode(toBeDeletedNode->right);

    // in case right child node is the min node
    if (minNode->parent == toBeDeletedNode)
    {
        if (toBeDeletedNode->left)
        {
            minNode->left = toBeDeletedNode->left;
            toBeDeletedNode->left->parent = minNode;
        }
        minNode->parent = toBeDeletedNode->parent;
    }
    else
    {
        if (minNode->right)
        {
            minNode->right->parent = minNode->parent;
            minNode->parent->left = minNode->right;
        }
        else
            minNode->parent->left = nullptr;

        minNode->left = toBeDeletedNode->left;
        if (toBeDeletedNode->left)
            toBeDeletedNode->left->parent = minNode;
        minNode->right = toBeDeletedNode->right;
        toBeDeletedNode->right->parent = minNode;
        minNode->parent = toBeDeletedNode->parent;
    }

    if (toBeDeletedNode->parent->left
        && toBeDeletedNode->parent->left == toBeDeletedNode)
        toBeDeletedNode->parent->left = minNode;
    else
        toBeDeletedNode->parent->right = minNode;

    // cut linkage
    toBeDeletedNode->left = nullptr;
    toBeDeletedNode->right = nullptr;
    delete toBeDeletedNode;
}

[私人]handleChildLeaf()

void handleChildLeaf(Node* toBeDeletedNode)
{
    if (toBeDeletedNode->parent->left
        && toBeDeletedNode->parent->left == toBeDeletedNode)
        toBeDeletedNode->parent->left = nullptr;
    else
        toBeDeletedNode->parent->right = nullptr;
    delete toBeDeletedNode;
}

Node class:

struct Node
{
    Node() : client(nullptr), parent(nullptr), left(nullptr), right(nullptr) {}
    ~Node();
    Client* client;
    Node*   parent;
    Node*   left;
    Node*   right;
};

Answer 1

错误原因在于handleRootLSubtree()函数：

行

maxNode->parent->parent = maxNode;

必须替换为

toBeDeletedNode->left->parent = maxNode;

仅当所有测试同时执行时，UnitTest 才会失败

UnitTest failing only when all tests get executed at once

c++

unit-testing

binary-search-tree

额外

这里是相应的私有函数：