malloc échoue de manière catastrophique

Question

J'essaie d'implémenter une file d'attente dans C. Venant de Java et d'autres langages gérés, je suis vraiment aux prises avec la gestion de la mémoire. Voici la fonction 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++;*/ 
} 

Je reçois cette erreur:

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, voici le reste du code (est-ce même droit?):

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; 
} 

Pourquoi Est-ce que cela arrive?

Answer 1

La ligne suivante est sans doute en vous donnant du chagrin:

Node newNode = malloc(sizeof(Node)); 

Node est un type de pointeur, de sorte que vous êtes seulement allouer suffisamment d'espace pour contenir un pointeur, pas un NodeStruct entier. Je pense que ce que vous voulez faire est:

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

ou

Node newNode = malloc(sizeof(NodeStruct)); 

Le même problème existe pour Queue, vous êtes seulement l'espace alloué pour tenir un pointeur, pas un QueueStruct. Quelque chose d'autre que je viens de remarquer, c'est que dans votre NodeStruct et QueueStruct, vous utilisez le type Node*, qui est en fait NodeStruct **, ce qui n'est probablement pas ce que vous voulez, puisque Node est déjà un pointeur.

Answer 2

vous avez saccagé votre tas

si vous êtes sur la clôture électrique d'utilisation de Linux ou valgrind pour savoir où vous êtes allé mal

modifier: Vous voulez dire

Queue q = malloc(sizeof(QueueStruct)); 

et même pour le noeud

Node n = malloc(sizeof(NodeStruct)); 

et je suis d'accord avec d'autres - ses très trompeuse d'appeler un pointeur vers un nœud NodeStruct. Mieux vaut l'appeler NodePtr ou PNode et appeler le noeud struct.

Answer 3

Il est souvent considéré comme un mauvais style dans C pour masquer un pointeur dans un typedef. C'est parce que besoin pour savoir que quelque chose est un pointeur pour l'utiliser correctement, de toute façon. (Par exemple, même le type opaque FILE dans la bibliothèque standard est utilisé et transmis comme FILE *).

Cela semble vous avoir égaré - par exemple, vos membres next et prev sont en fait des pointeurs vers des pointeurs, ce qui n'est pas vraiment ce que vous voulez. Je suggère:

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; 
}