La liste triplement triée donne une erreur de bus lors d'un accès inversé

Question

J'ai une implémentation de liste générique à double liaison, et je travaillais sur l'insertion. Après l'insertion, j'essaie de revenir en arrière dans la liste en commençant par le pied, et j'obtiens une erreur de bus. Pour tester le code et essayer d'isoler l'erreur, j'ai saupoudré les instructions d'impression (pas la meilleure procédure de débogage mais utile pour me dire d'un coup d'œil ce que fait mon code). Pour essayer de voir où le problème se pose, après chaque insertion, je demande la valeur de l'avant-dernier élément de la liste. J'insère toujours des éléments dans l'ordre 5, 2, 10, 80, 4, 1, 7, 8, et après l'insertion de 4 dans la liste, il s'étouffe constamment. Le code complet du programme suit.

dlist_t * 
insert_in_order (dlist_t *list, void *value, size_t size, 
    int (*cmp_fptr)(const void *, const void *)) 
{ 
dlnode_t * prev = NULL; 
dlnode_t * current = list->head; 
dlnode_t * newnode = safe_malloc(sizeof(dlnode_t)); 

newnode->data = value; 
newnode->next = NULL; 
newnode->prev = NULL; 

printf("Beginning list loop for %d.\n", *(int *) newnode->data); 
while (current != NULL && cmp_fptr(newnode->data, current->data) != -1) 
{ 
    prev = current; 
    current = current->next; 
} 
printf("Insertion point found.\n"); 

newnode->next = current; 
newnode->prev = prev; 

if (prev == NULL) 
{ 
    printf("Setting for new head\n"); 
    list->head = newnode; 
} 
else 
{ 
    printf("Setting previous next to new node\n"); 
    prev->next = newnode; 
} 

if (current == NULL) 
{ 
    printf("setting for new foot."); 
    list->foot = newnode; 
} 
else 
{ 
    printf("Setting for new current previous\n"); 
    current->prev = newnode; 
} 

list->list_len++; 
list->size = sizeof(list); 
printf("Insertion compete for %d\n\n", *(int *) newnode->data); 
printf("Data for surrounding:\n"); 
if(newnode->next !=NULL) 
{ 
    printf("Next is %d \n", *(int *) newnode->next->data); 
} 
if(newnode->prev != NULL) 
{ 
    printf("Prev is %d \n\n", *(int *) newnode->prev->data); 
} 

if(list->foot->prev != NULL) 
{ 
    printf("Gonna print secondlast!\n"); 
    printf("secondlast is%d \n\n", *(int *)list->foot->prev->data); 
} 

return list; 
} 

Les définitions de liste sont élémentaires, juste

struct dlnode 
{ 
    void *data;  /* A pointer to a generic satellite data payload */ 
    dlnode_t *next; /* A pointer to the next item in the list */ 
    dlnode_t *prev; /* A pointer to the previous item in the list */ 
}; 

typedef struct 
{ 
    dlnode_t *head; /* A pointer to the head node of the list */ 
    dlnode_t *foot; /* A pointer to the foot node of the list */ 
    int list_len; /* Total number of items in the list */ 
    int size;  /* Size of the list in bytes */ 
} dlist_t; 

Vous pouvez modifier la définition de la fonction mais vous voulez, et safe_malloc est juste une méthode de raccourci pour malloc que vous pouvez remplacer si vous testez le code vous-même. cmp_fptr est un pointeur de fonction vers une méthode simple 'est plus grande que b'.

EDIT: MISE A JOUR La ligne

printf("secondlast is%d \n\n", *(int *)list->foot->prev->data); 

est ce qui cause le programme d'arrêter, je l'ai utilisé un débogueur. Lors de l'insertion d'éléments dans la liste, il s'arrête sur cette ligne après plusieurs insertions. Ce qui suit est mon code de harnais de test que j'utilise en ce moment.

int * 
alloc_data (int val) 
{ 
    int *rv = safe_malloc (sizeof (int)); 
    *rv = val; 
    return (rv); 
} 

int 
main (void) 
{ 
    dlist_t *list = NULL; 
    int *num = NULL, *rv = NULL; 
    dlnode_t *tnode = NULL; 

    list = make_empty_list(); 

    list = insert_in_order (list, alloc_data (5), sizeof(int), cmp_int); 
    list = insert_in_order (list, alloc_data (2), sizeof(int), cmp_int); 
    list = insert_in_order (list, alloc_data (10), sizeof(int), cmp_int); 
    list = insert_in_order (list, alloc_data (80), sizeof(int), cmp_int); 
    list = insert_in_order (list, alloc_data (4), sizeof(int), cmp_int); 
    list = insert_in_order (list, alloc_data (1), sizeof(int), cmp_int); 
    list = insert_in_order (list, alloc_data (7), sizeof(int), cmp_int); 
    list = insert_in_order (list, alloc_data (8), sizeof(int), cmp_int); 
    return(EXIT_SUCCESS); 
} 

Il y a un peu plus mais c'est tout ce que je suis en train de tester.

Merci pour la pointe de la liste-> taille, je ne suis pas sûr de ce que je pensais à l'origine. Edit2: merci pour le message d'erreur safe_malloc, je pensais que c'était la cause du problème mais j'ai toujours la même erreur. Le débogueur me donne un sigsegv (défaut de segmentation) après que 4 est inséré et il arrive à la ligne où pour la santé mentale je demande des données list-> foot-> prev-> (voir ci-dessus). Édition finale: problème résolu en allouant correctement un espace suffisant pour les données de noeud. Merci à ceux qui ont aidé. Il y a d'autres problèmes dans mon code, mais cela convient mieux à une autre question, et à un extrait de code différent.

Answer 1

Quelques choses:

Comme il a été déjà dit, le list->size = sizeof(list); ne probablement pas ce que vous pensez

Le size_t size passé comme argument est probablement votre principal problème et semble dangereux (ce qui est cette variable valeur lorsque vous appelez la fonction?)

Faire dlnode_t * newnode = safe_malloc(size); avec une mauvaise taille peut expliquer votre problème

dlnode_t * newnode = safe_malloc(size);

devrait probablement être remplacé par

dlnode_t * newnode = safe_malloc(sizeof(dlnode_t));

dernier, dans votre liste, vous utilisez directement void *value et non une copie de celui-ci. Donc, si vous n'appelez pas toujours cette fonction dans le même bloc, vous aurez des problèmes

Avec la même signature de fonction, je pense que le paramètre size devrait représenter la taille du paramètre value pour faire un malloc/memset de et l'enregistrer dans votre liste