c - C 中段错误的不稳定行为

Question

以下是我在 C 中用于实现 B-Tree 的代码。该代码有时工作起来很奇怪，因为它有时会给出“Segmentation Fault”，如果我再次运行它并提供相同的输入值，它就可以正常工作。

也有这样的情况，我输入了 1 个值(例如 500)，现在这应该是根值，但是代码还打印了两个空的 (nil) 子值。

而且所有这些行为都是不稳定的，并不是每次都会发生。它几乎不会发生第二次。我敢肯定，这与内存有关。有人可以建议我治疗。

提前致谢!!

#include <stdio.h>
#include <stdlib.h>

#define ORDER 4

struct node{
    int n;
    int keys[ORDER-1];
    struct node *children[ORDER];
};

struct toReturn{
    int result;
    struct node* nodeReturn;
};

struct node* splitNodeAndAdd(struct node* , int );
struct  node* insertInTree(struct node* , int );
struct toReturn* insertRecursive(struct node *, int );
struct node* splitNodeAndAddNode(struct node* , struct node* );


struct node* addElement(struct node *, int);
void printTree(struct node*, int);
void addAndSort(int *, int, int);
int checkLeaf(struct node* node);




int main(){

    int inputElement = 0;
    printf("Enter the element you want to add. Press 0 to quit\n");
    scanf("%d",&inputElement);


    struct node * root;
    root = (struct node*) malloc(sizeof(struct node));

    while(inputElement != 0){
        root = addElement(root,inputElement);
        printTree(root,0);
        scanf("%d",&inputElement);
    }

    return 0;
}

struct node* addElement(struct node * rootNode, int inputElement){

    if(rootNode->n == 0){
        rootNode->keys[0] = inputElement;
        rootNode->n += 1;
        return rootNode;
    }
    else{
        rootNode = insertInTree(rootNode,inputElement);
        return rootNode;
    }
}


struct  node* insertInTree(struct node* node, int inputElement){

    if(checkLeaf(node) == 0){           //It is leaf node.
        if(node->n == ORDER - 1){
            struct node * temp = node;
            struct node *newRoot = (struct node*) malloc(sizeof(struct node));
            node = newRoot;
            newRoot->children[0] = temp;
            newRoot = splitNodeAndAdd(newRoot,inputElement);
            return newRoot;
        } else{
            addAndSort(node->keys,node->n,inputElement);
            node->n += 1;
        }
    } else{
        //recursive add . DO IT.
        struct toReturn * returnedValue = insertRecursive(node,inputElement);
        node = returnedValue->nodeReturn;
    }
    return node;
}


//Change split node and add before running. Won't work otherwise.
struct toReturn* insertRecursive(struct node *node, int inputElement){

    if(checkLeaf(node) == 0){
        if(node->n == ORDER - 1){
            struct node * temp = node;
            struct node *newRoot = (struct node*) malloc(sizeof(struct node));
            node = newRoot;
            newRoot->children[0] = temp;
            newRoot = splitNodeAndAdd(newRoot,inputElement);
            struct toReturn *value = (struct toReturn*) malloc(sizeof(struct toReturn));
            value->result = 0;
            value->nodeReturn = newRoot;
            return value; // Also send parameter to show its done.


        } else{
            addAndSort(node->keys,node->n,inputElement);
            node->n += 1;
            struct toReturn *value = (struct toReturn*) malloc(sizeof(struct toReturn));
            value->result = 1;
            value->nodeReturn = node;
            return value; // Also send parameter to show its done.
        }
    }
    else{
        int i = node->n;
        i -= 1;

        while( i >= 0 && inputElement < node->keys[i]){
            i -= 1;
        }
        i += 1;
        //Go to child node of this using 'i'
        struct toReturn* returnedValue = insertRecursive(node->children[i],inputElement);

        if(returnedValue->result == 0){
            //Now we have a node in returnedValue to be added to current node.

            //Check if current root is also going to be full.
            if(node->n == ORDER - 1){
                struct node* currentNode = node;
                struct node* nodeToAdd = returnedValue->nodeReturn;
                struct node* newRoot = (struct node*) malloc(sizeof(struct node));
                newRoot->children[0] = currentNode;
                newRoot = splitNodeAndAddNode(newRoot,nodeToAdd);


                struct toReturn* temp = (struct toReturn*) malloc(sizeof(struct toReturn));
                temp->result = 0;
                temp->nodeReturn = newRoot;// whatever is returned from splitNodeAndAddNode.
                return temp;
            } else{

                int k = i;
                for(k = node->n; k>i; k--){
                    node->keys[k] = node->keys[k-1];
                }
                for(k = node->n + 1; k > i; k--){
                    node->children[k] = node->children[k-1];
                }

                node->keys[i] = returnedValue->nodeReturn->keys[0];
                node->n += 1;
                node->children[i] = returnedValue->nodeReturn->children[0];
                node->children[i+1] = returnedValue->nodeReturn->children[1];
                returnedValue->result = 1;
                returnedValue->nodeReturn = node;
            }
        }else{
            node->children[i] = returnedValue->nodeReturn;
            returnedValue->nodeReturn = node;
        }
        return returnedValue;
    }
}

struct node* splitNodeAndAddNode(struct node* node, struct node* toAdd){

    struct node* leftChild = node->children[0];
    struct node* allChildren[ORDER+1];

    int i = 0;
    for(i = 0; i<ORDER; i++){
        allChildren[i] = leftChild->children[i];
    }

    int childrenCount = 0;

    int j = 0;
    struct node* rightChild = (struct node*) malloc(sizeof(struct node));
    int array[ORDER];

    for(i=0; i<ORDER - 1; i++){
        array[i] = leftChild->keys[i];
    }
    addAndSort(array,ORDER-1,toAdd->keys[0]);
    int addedPosition = 0;
    for(i=0; i<ORDER; i++){
        if(array[i] == toAdd->keys[0]){
            addedPosition = i;
        }
    }

    for(j=ORDER-1; j>= addedPosition; j--){
        allChildren[j+1] = allChildren[j];
    }
    allChildren[addedPosition] = toAdd->children[0];
    allChildren[addedPosition+1] = toAdd->children[1];


    int median = ORDER / 2;
    node->keys[0] = array[median];
    node->n += 1;

    //add left and right child of node.
    for(i = 0; i<median; i++){
        leftChild->keys[i] = array[i];
        leftChild->children[i] = allChildren[childrenCount];
        childrenCount++;
    }
    leftChild->children[i] = allChildren[childrenCount];
    childrenCount++;
    leftChild->n = median;

    for(i = median; i<ORDER-1; i++){
        leftChild->keys[i] = 0;
    }

    int k = 0;

    for(i = median+1; i<ORDER; i++){
        rightChild->keys[k] = array[i];
        rightChild->n += 1;
        rightChild->children[k] = allChildren[childrenCount];
        childrenCount++;
        k++;
    }

    rightChild->children[k] = allChildren[childrenCount];
    childrenCount++;

    node->children[0] = leftChild;
    node->children[1] = rightChild;
    return node;
}


struct node* splitNodeAndAdd(struct node* rootNode, int inputElement){

    struct node* leftChild = rootNode->children[0];
    struct node* rightChild = (struct node*) malloc(sizeof(struct node));

    int i = 0;
    int j = 0;

    int array[ORDER];
    for(i =0; i<ORDER-1;i++){
        array[i] = leftChild->keys[i];
    }
    addAndSort(array,ORDER-1,inputElement);

    int medianIndex = 0;
    for(i = 0; i<ORDER; i++){
        if(inputElement == array[i]){
            medianIndex = i;
            break;
        }
    }
    int median = ORDER / 2;

    for(j=0; j<median; j++){
        leftChild->keys[j] = array[j];
    }

    for(j=median; j<ORDER-1;j++){
        leftChild->keys[j] = 0;
    }

    leftChild->n = median;
    rootNode->keys[0] = array[median];
    rootNode->n += 1;

    int k = 0;
    for(j= median+1; j<ORDER; j++){
        rightChild->keys[k] = array[j];
        rightChild->n += 1;
        k++;
    }
    rootNode->children[0] = leftChild;
    rootNode->children[1] = rightChild;

    //Have to add all children if this is not leaf node.
    //Have to change rootNode[0] to long term picture.

    return rootNode;

}




void printTree(struct node *a, int level){

    printf("%d : ",level);
    for(int i=0; i<a->n; i++){
        printf("%d ",a->keys[i]);
    }
    printf("\n");
    if(checkLeaf(a) == 1){
        for(int i=0; i <= a->n ; i++){
            printTree(a->children[i],level+1);
        }
    }else {
        return;
    }

}


int checkLeaf(struct node* node){
    int i = 0;
    if(node->children[i] != NULL){
        return 1;
    }
    return 0;
}


void addAndSort(int *array, int elementCount, int inputElement){
    int i = 0;

    for(i = elementCount-1; i >=0 && array[i] > inputElement; i--){       //else find the best
        array[i+1] = array[i];
    }
    array[i+1] = inputElement;
}

Answer 1

正如我在评论中所说，需要审查的代码太多，特别是当您没有给我们足够的提示从哪里开始看问题。

Can you elaborate a bit on allocated memory for the root node in main, you didn't initialize it, I am not sure if I follow. I think I reserved memory, then why is it causing such erratic behaviour. I presume it takes garbage value sometimes, am I right ?

我简要地查看了代码，发现了相同的模式。你刚才分配内存，但在读取内容之前不初始化内存分配的内存。这会产生未定义的行为以及你是什么观察，有时工作，有时不工作，这是一个经典的标志未定义的行为。由于未定义行为的性质，它非常很难，有时几乎不可能预测会发生什么。在多数情况下您需要做的就是找到未定义行为的来源。

在你的情况下，我做的第一件事就是查看你的 malloc 调用，看看在哪里你初始化内存。你没有做到这一点，所以我停止寻找更多错误，因为这很可能是您所有问题的根源。

当你用malloc分配内存时，你只能从操作系统，不能保证内存在任何初始化方式，这意味着内存具有随机值。你在 main

中做

root = (struct node*) malloc(sizeof(struct node));
while(inputElement != 0) {
    root = addElement(root,inputElement);
    ...
}

然后 addElement 执行:

struct node* addElement(struct node * rootNode, int inputElement){

    if(rootNode->n == 0){
        rootNode->keys[0] = inputElement;
        ...
    } else {
        rootNode = insertInTree(rootNode,inputElement);
        ...
    }
}

如您所见，您已经为 root 节点分配了内存，但是 root->n 不是初始化后，它的值是随机的，可能是 0，但也可能是 24 或-12389。所以你的代码已经在做一些不可预测的事情，因为只是查看代码，您无法知道 rootNode->keys[0] = inputElement;被执行，或者 rootNode = insertInTree(rootNode,inputElement);。那就是未定义行为的性质。在 rootNode->n 为 0 的幸运情况下，功能可能会正常工作。

你必须做

root = malloc(sizeof *root);

if(root == NULL)
{
    fprintf(stderr, "No memory left\n");
    return 1;
}

// initializing the memory
root->n = 0;
memset(root->keys, 0, sizeof root->keys / sizeof root->keys[0]);
for(size_t i = 0; i < sizeof root->children / sizeof root->children[0]; ++i)
    root->children[i] = NULL;

while(inputElement != 0) {
    root = addElement(root,inputElement);
    ...
}

1. Don't cast malloc
2. 勾选always，我的意思是alwaysmalloc/realloc
的返回值
3. 以防你错过了，检查always，我的意思是always malloc/realloc
4. 避免使用sizeof(struct node)，改用sizeof *root，使代码更健壮。
5. 不要忘记free()内存。
6. 如果你错过了，别忘了free()内存

我还建议您创建一个函数，返回一个新的分配+初始化节点，否则您将一次又一次地重复相同的代码。这适用于您所有的 malloc 调用。

当然，在您的情况下，可以通过使用 calloc 来避免初始化而不是 malloc。 calloc 的工作方式类似于 malloc 但它还会设置分配的内存为 0。这是一个很棒的功能，因为如果您的内存必须用 0 和 NULL 指针¹ 初始化，这样可以节省很多时间和你可以做

root = calloc(1, sizeof *root);

if(root == NULL)
{
    fprintf(stderr, "No memory left\n");
    return 1;
}

// initializing the memory with 0 is not needed
// anymore as calloc takes care of that

while(inputElement != 0) {
    root = addElement(root,inputElement);
    ...
}

在整个代码中进行此更改，这将消除许多未定义行为的来源。这并不意味着你所有的问题都是虽然解决了。

---

脚注

¹传说说存在 NULL 的架构未解释为 0，因此使用 calloc 初始化 NULL 指针可能会失败。但我敢说任何人都可以找到人们使用的任何商业上成功的架构这些天在这种情况下富有成效。