Erreur d'implémentation de pile bizarre

Question

Juste pour le plaisir, j'ai implémenté ma propre pile, mais sans utiliser une liste chaînée, mais elle était toujours dynamique, parce que chaque fois que vous appuyez dessus, une taille plus grande ou plus petite, et puis le remplit avec ce qui était déjà là (et un de moins ou un de plus). Je comprends que c'est très lent et une façon stupide de le faire, mais je voulais juste voir si ça fonctionne.

Le code est un peu long, donc je pastied il here:

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

typedef struct { 
    int size; 
    int *stack_array; 
}stack; 

void newStack(stack *a) { 
    a->size = 0; 
    a->stack_array = malloc(sizeof(int) * 1); 
} 

void push(stack *a, int x) { 
    int *new_array = malloc(sizeof(int) * a->size); 
    int i; 
    for(i=0; i < a->size; i++) { 
     new_array[i] = a->stack_array[i]; 
    } 

    new_array[i] = x; 

    a->stack_array = new_array; 

    a->size += 1; 
} 

int pop(stack *a) { 
    if(a->size <= 0) { 
     printf("CALL POP() WITH FILLED STACK"); 
     exit(1); 
    } 
    int *new_array = malloc(sizeof(int) * (a->size)-1); 
    int i; 
    for(i=0; i < a->size-1; i++) { 
     new_array[i] = a->stack_array[i]; 
    } 

    int popped = a->stack_array[i]; 

    a->stack_array = new_array; 
    a->size -= 1; 
    return popped; 
} 

void printStack(stack *a) { 
    int i; 
    printf("{"); 
    for(i=0; i<a->size-1; i++) { 
     printf("%d, ", (a->stack_array)[i]); 
    } 
    printf("%d}\n", (a->stack_array)[i]); 
} 

int main (void) { 
    stack a; 
    newStack(&a); 

    push(&a, 6); 
    push(&a, 12); 
    push(&a, 13); 

    printStack(&a); 

    printf("Popped: %d\n", pop(&a)); 

    printStack(&a); 
    return 0; 
} 

Et, comme vous pouvez le voir, cela fonctionne très bien.

Maintenant, quand j'ajouter une boucle à lui, pour ajouter un peu plus à la pile (pastied here):

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

typedef struct { 
    int size; 
    int *stack_array; 
}stack; 

void newStack(stack *a) { 
    a->size = 0; 
    a->stack_array = malloc(sizeof(int) * 1); 
} 

void push(stack *a, int x) { 
    int *new_array = malloc(sizeof(int) * a->size); 
    int i; 
    for(i=0; i < a->size; i++) { 
     new_array[i] = a->stack_array[i]; 
    } 

    new_array[i] = x; 

    a->stack_array = new_array; 

    a->size += 1; 
} 

int pop(stack *a) { 
    if(a->size <= 0) { 
     printf("CALL POP() WITH FILLED STACK"); 
     exit(1); 
    } 
    int *new_array = malloc(sizeof(int) * (a->size)-1); 
    int i; 
    for(i=0; i < a->size-1; i++) { 
     new_array[i] = a->stack_array[i]; 
    } 

    int popped = a->stack_array[i]; 

    a->stack_array = new_array; 
    a->size -= 1; 
    return popped; 
} 

void printStack(stack *a) { 
    int i; 
    printf("{"); 
    for(i=0; i<a->size-1; i++) { 
     printf("%d, ", (a->stack_array)[i]); 
    } 
    printf("%d}\n", (a->stack_array)[i]); 
} 

int main (void) { 
    stack a; 
    newStack(&a); 

    int i = 0; 
    for(i = 0; i<12; i++) { 
     push(&a, i); 
    } 

    printStack(&a); 

    return 0; 
} 

Il fonctionne bien sur CodePad (qui me embrouille un peu plus), mais, ma machine, il me donne cette erreur (que je ne l'ai jamais vu auparavant, et est donnée lors de l'exécution):

a.out: 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. 
Aborted 

il peut ou ne peut pas faire une différence que la machine exécutant c'est une machine Linux VirtualBox. Aussi, je n'ai évidemment pas très bien écrit l'implémentation, vu qu'elle ne libère pas de pointeurs, ni d'espace, ou ne vérifie pas beaucoup d'erreurs.

Answer 1

En newStack, vous dites ceci:

void newStack(stack *a) { 
    a->size = 0; 
    a->stack_array = malloc(sizeof(int) * 1); 
} 

Alors a->size est l'indice du dernier élément, et non le nombre d'éléments. Puis, en push, vous faites ceci:

int *new_array = malloc(sizeof(int) * a->size); 
int i; 
for(i=0; i < a->size; i++) { 
    new_array[i] = a->stack_array[i]; 
} 
new_array[i] = x; 

La première fois, vous malloc zéro octets pour new_array, courir à travers zéro temps de boucle for, puis attribuez-lui x-new_array[0]. Et vous avez maintenant un tas corrompu à partir d'un débordement de tampon. Vous devriez dire ceci:

int *new_array = malloc(sizeof(int) * (a->size + 1)); 

Vous devriez aussi être votre mémoire et libérez peut-être vous devriez en apprendre davantage sur realloc et memcpy.

Answer 2

Lorsque vous placez quelque chose sur la pile, vous en allouez un trop peu. push() devrait peut-être ressembler à:

void push(stack *a, int x) { 
    int *new_array = malloc(sizeof(int) * (a->size + 1)); // <=== changed 
    int i; 
    for(i=0; i < a->size; i++) { 
     new_array[i] = a->stack_array[i]; 
    } 

    new_array[i] = x; 

    a->stack_array = new_array; 

    a->size += 1; 
} 

Et pop(), même si vous soustrayez un lors de l'exécution de la nouvelle allocation que vous n'êtes pas correctement l'arithmétique exécution en raison de la priorité des opérateurs. Ce n'est pas vraiment un problème (en termes de corruption de tas) parce que votre allocation est trop grande d'un peu; vous allouez juste quelques octets que vous n'utiliserez jamais réellement. Sans oublier que votre exemple de programme ne l'appelle jamais. Essayez:

int pop(stack *a) { 
    if(a->size <= 0) { 
     printf("CALL POP() WITH FILLED STACK"); 
     exit(1); 
    } 
    int *new_array = malloc(sizeof(int) * ((a->size)-1)); // <=== changed 
    int i; 
    for(i=0; i < a->size-1; i++) { 
     new_array[i] = a->stack_array[i]; 
    } 

    int popped = a->stack_array[i]; 

    a->stack_array = new_array; 
    a->size -= 1; 
    return popped; 
} 

Vous mentionnez dans un commentaire que vous n'êtes pas encore libérant la mémoire, de sorte que votre prochaine étape consiste à libérer correctement les blocs de mémoire vous n'utilisez plus donc il n'y a pas de fuites ...