c - 二叉树结构实现的问题

Question

我正在尝试使用 C 语言中的二叉树来实现内存管理模拟(伙伴)。系统工作原理概述如下:

http://en.wikipedia.org/wiki/Buddy_memory_allocation

第一次输入值时，代码工作正常，并给出所需的输出。第二次输入值时会出现此问题。我正在使用递归函数来遍历树，并且收到错误，结构存在，但结构的成员不存在。

 Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 1 (LWP 1)]
 0x00010b2c in allocate (node=0x401ba18a, reqSize=1000) at temp.c:95
 95         if(node->flag == 1){
 (gdb) print node
 $1 = (struct block *) 0x401ba18a
 (gdb) print node->flag
 Cannot access memory at address 0x401ba192

相关代码发布在下面，任何帮助将不胜感激!

 static int allocate(struct block* node, int reqSize) {
 //BASE CASES!
 printf("We've called allocate\n");
 //check if the request is too small
 if(reqSize < minSize){
     printf("The request is too small!\n");
     return -1;
 }
 //check if the request is too large
 if(reqSize > memory){
     printf("The request is too large!\n");
     return -1;
 }
 //check if the current block is already allocated
 if(node->flag == 1){
     printf("This block has been allocated!\n");
    return -1;
  }
   //var to hold returned value
   int returnVal = 0;
   //If the size of the request is less than or equal to half the node
  if(reqSize<(node->size)/2){
    printf("The size of the request is less than or equal too half the node\n");
    //check if there is a left node, if not, make one and call allocate
    if(node->left == NULL){
        printf("There's no left node so we are making one and calling allocate with     it\n");

        struct block buddy1 = { .init =1.};
        buddy1 = findSpace();
        buddy1.init = 1;
        buddy1.size = ((node->size)/2);
        printf("with the size %d\n",(node->size)/2);
        buddy1.flag = 0;
        buddy1.parent = node;
        buddy1.left = NULL;
        buddy1.right = NULL;

        struct block buddy2 = { .init =1.};
        buddy2 = findSpace();
        buddy2.init = 1;
        buddy2.size = ((node->size)/2);
        printf("with the size %d\n",(node->size)/2);
        buddy2.flag = 0;
        buddy2.parent = node;
        buddy1.left = NULL;
        buddy1.right = NULL;

        node->left = &buddy1;
        node->right = &buddy2;
        returnVal = allocate(node->left,reqSize);
        return returnVal;
    }
    //otherwise call allocate on the left node
    printf("There is a left node so we are calling allocate on it\n");
    returnVal = allocate(node->left,reqSize);

    if(returnVal == -1){
        printf("couldn't allocate a left node for some reason, so we are checking if a right node exists\n");
        if(node->right ==NULL){
            printf("it doesn't. We're making one and calling allocate on it!\n");
            struct block buddy = { .init =1.};
            buddy = findSpace();
            buddy.init = 1;
            buddy.size = ((node->size)/2);
            printf("with the size %d\n",(node->size)/2);
            buddy.flag = 0;
            buddy.parent = node;
            //node->left = NULL;
            node->right = &buddy;
            returnVal = allocate(&buddy,reqSize);
            }
            printf("it did, so we are calling allocate on it\n");
            returnVal = allocate(node->right,reqSize);
            //return returnVal;

    }
    return returnVal;
}

if(node->flag == 1){
    return -1;
}

printf("This is the node we need!\n");
node->flag = 1;
printPostOrder(&blockArr[position]);
return 1;
}

Answer 1

您的好友节点是局部变量，在堆栈上分配，并在分配函数返回时销毁。您没有显示 block 结构或 findSpace 函数的定义，因此很难提供更多帮助。

为什么要部分初始化每个伙伴(.init 被分配一个浮点 1)，然后立即用 的返回值覆盖整个结构找到空间？

第三个伙伴(当从左侧分配失败时为右侧)没有像其他两个伙伴一样将其左右指针初始化为NULL。这里有很多重复的代码，最好将它们放在自己的函数中。

通常，树结构是隐式的，您只需从位于每个空闲 block 前面的结构创建一个空闲列表。合并 block 时，您可以通过将您的地址与您的大小进行异或来确定您好友的地址。您所需要的只是每个 block 一个位来告诉您伙伴是否空闲(并且具有 header 结构)，如果是这样，您可以检查 header 以确保其大小相同。唯一需要的额外存储是每个最小可分配 block 1 位的位 vector ，它允许您快速确定 header 是否存在，而无需扫描空闲列表。哦，空闲列表应该是双向链接的，以允许您从中间删除元素(而不必从头开始扫描列表)。如果您愿意向分配的 block 添加 header ，则可用大小将不再是 2 的幂，但您可以避免需要外部位 vector 。