Malloc терпит неудачу катастрофически - PullRequest
Новая
       5

Malloc терпит неудачу катастрофически

0 голосов
/ 22 сентября 2010

Я пытаюсь реализовать очередь в C. Исходя из 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;
}

Почему это происходит?

Ответы [ 3 ]

10 голосов
/ 22 сентября 2010

Следующая строка, вероятно, доставит вам горе: 

Node newNode = malloc(sizeof(Node));

Node - это тип указателя, поэтому вы выделяете достаточно места только для хранения указателя, а не всего NodeStruct.Я думаю, что вы хотите сделать, это: 

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

или 

Node newNode = malloc(sizeof(NodeStruct));

Та же проблема существует для Queue, вам выделено только место для хранения указателя, а неQueueStruct.Что-то еще, что я только что заметил, это то, что в ваших NodeStruct и QueueStruct вы используете тип Node*, который на самом деле NodeStruct **, что, вероятно, не то, что вы хотите, так как Node ужеуказатель.

8 голосов
/ 22 сентября 2010

В C часто считается плохим стилем, чтобы скрыть указатель внутри typedef. Это потому, что вам нужно , чтобы знать, что что-то является указателем, чтобы правильно его использовать, в любом случае. (Например, даже непрозрачный тип FILE в стандартной библиотеке используется и передается как 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;
}
5 голосов
/ 22 сентября 2010

вы уничтожили свою кучу

если вы используете Linux, используйте электрический забор или valgrind, чтобы узнать, где вы ошиблись

edit: вы имеете в виду 

Queue q = malloc(sizeof(QueueStruct));

и то же самое для узла 

Node n = malloc(sizeof(NodeStruct));

, и я согласен с другими - его очень вводит в заблуждение, вызывая указатель на NodeStruct Node.Лучше назвать его NodePtr или PNode и вызвать struct Node.

...