malloc灾难性地失败了

Question

我正在尝试在C中实现Queue.来自Java和其他托管语言,我真的在努力进行内存管理.这是enqueue()功能:

int enqueue(Queue q, int value) {

    Node newNode = malloc(sizeof(Node));
    /*newNode->value = value;

    if (q->size == 0)
        q->head = newNode;
    else
        q->head->next = &newNode;

    q->size++;*/
}

我收到此错误:

malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.

FWIW,这是代码的其余部分(这是对的吗？):

typedef struct NodeStruct *Node;
struct NodeStruct {
    Node* prev;
    Node* next;
    int value;
};

typedef struct QueueStruct *Queue;
struct QueueStruct {
    Node* head;
    Node* tail;
    int size;
    int capacity;
};

Queue newQueue(int size) {
    Queue q = malloc(sizeof(Queue));

    q->capacity = size;
    q->size = 0;
    q->head = NULL;
    q->tail = NULL;

    return q;
}

void printQueue(Queue q) {
    printf("Queue of size %d, capacity %d", q->size, q->capacity);
}    

int main() {
    Queue myQ = newQueue(10);

    // this seems to work
    printQueue(myQ);
    // epic fail
    enqueue(myQ, 5);

    return 0;
}

为什么会这样？

Answer 1

以下行可能会让你感到悲痛:

Node newNode = malloc(sizeof(Node));

Node是指针类型,所以你只分配足够的空间来保存指针,而不是整个指针NodeStruct.我想你想要做的是:

Node newNode = malloc(sizeof(*newNode));

要么

Node newNode = malloc(sizeof(NodeStruct));

存在同样的问题Queue,你只需要分配空间来保存指针,而不是QueueStruct.我刚刚注意到的其他东西,就是在你的NodeStruct和QueueStruct你正在使用的类型Node*,实际上NodeStruct **,这可能不是你想要的,因为Node它已经是一个指针.

Answer 2

在C中隐藏指针通常被认为是不好的风格typedef.这是因为无论如何你需要知道某些东西是指向正确使用它的指针.(例如,即使FILE使用标准库中的opaque类型并将其作为a传递FILE *).

这似乎让你误入歧途 - 例如,你next和prev成员实际上是指针指针,这不是你想要的.我建议:

typedef struct NodeStruct Node;
typedef struct QueueStruct Queue;

struct NodeStruct {
    Node *prev;
    Node *next;
    int value;
};

struct QueueStruct {
    Node *head;
    Node *tail;
    int size;
    int capacity;
};

Queue *newQueue(int size) {
    Queue *q = malloc(sizeof(Queue));

    q->capacity = size;
    q->size = 0;
    q->head = NULL;
    q->tail = NULL;

    return q;
}

int enqueue(Queue *q, int value) {

    Node *newNode = malloc(sizeof(Node));

    newNode->value = value;
    newNode->next = NULL;

    if (q->size == 0)
    {
        newNode->prev = NULL;
        q->tail = q->head = newNode;
    }
    else
    {
        newNode->prev = q->tail;
        q->tail->next = newNode;
        q->tail = newNode;
    }

    q->size++;
    return 0;
}

void printQueue(Queue *q) {
    printf("Queue of size %d, capacity %d\n", q->size, q->capacity);
}

int main() {
    Queue *myQ = newQueue(10);

    printQueue(myQ);
    enqueue(myQ, 5);

    return 0;
}

Answer 3

你已经破坏了你的堆

如果你在Linux上使用电栅栏或valgrind来找出你出错的地方

编辑:你的意思

Queue q = malloc(sizeof(QueueStruct));

和节点相同

Node n = malloc(sizeof(NodeStruct));

我同意其他人 - 调用指向NodeStruct节点的指针非常误导.最好将其称为NodePtr或PNode并调用结构节点.