Discussion :

[Modaak]

Bonjour à tous >< ! j'aimerais que quelqu'un m'explique pourquoi j'ai cette erreur dans mon terminal ! (free(): invalid pointer Abandon (core dumped))
pourtant j'estime avoir fait les choses correctement. Merci de votre aide ! je vous donne mon code si-dessous :

Mon main (tests unitaires)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
 
#include "./red-black-tree.h"
 
int main(int argc, char const *argv[])
{
    int data = 0;
    Node racine = create_node(&data, sizeof(data));
    set_color(racine, BLACK);
    printf("data = %p", get_data(racine));
 
    destroy_node(racine);
 
 
    return EXIT_SUCCESS;
}

Mon .h si besoin

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
#ifndef _RED_BLACK_TREE_H_
#define _RED_BLACK_TREE_H_
 
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>
 
typedef struct _Node *Node;
 
// racine de l'arbre
Node root = NULL;
 
typedef enum
{
    RED,
    BLACK
} COLOR;
 
struct _Node
{
    void *data;
    Node left, right, parent;
    COLOR color;
};
 
/*** Getters and Setters ***/
 
COLOR get_color(Node node);
bool set_color(Node node, COLOR color);
 
void *get_data(Node node);
Node get_left(Node node);
Node get_right(Node node);
Node get_parent(Node node);
 
/*** Functions ***/
 
void create_tree(); // je n'ai pas encore fait
Node create_node(const void *data, size_t data_size);
void destroy_node(Node node);
void destroy_tree();  // je n'ai pas encore fait
 
Node binary_search_tree(Node n1, Node n2);
 
void right_rotate(Node node);
void left_rotate(Node node);
 
void fix_up(Node root, Node node);
 
void swapping_colors(Node n1, Node n2);
 
void inorder(Node node);
 
#endif /* _RED_BLACK_TREE_H_ */

et enfin mes fonctions

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
Node create_node(const void *data, size_t data_size)
{
    Node node = NULL;
    node = (Node)malloc(sizeof(Node));
    node->data = malloc(data_size);
    assert(node != NULL);
    assert(node->data != NULL);
 
    if (node && node->data)
    {
        node->right = node->left = node->parent = NULL;
        set_color(node, RED);
        memcpy(node->data, data, data_size);
    }
    return node;
}
 
bool set_color(Node node, COLOR color)
{
    assert(node != NULL);
    if (node)
    {
        node->color = color;
        return true;
    }
    return false;
}
 
void *get_data(Node node)
{
    assert(node != NULL);
    if (node)
    {
        return node->data;
    }
    return NULL;
}

aucune erreurs à la compilation, merci d'avance ! Ah oui j'allais oublié j'ai utilisé l'utilitaire valgrind et il me dit que dans ma fonction create_node() à la ligne 12 dans ce cas il y avait une erreur peut-être parce que je met right, left et parent à NULL et il n'ame pas trop :/

[Sve@r]

Bonjour

pourtant j'estime avoir fait les choses correctement.

Arf, malheureusement dans ce cas là, son propre avis n'a que peu de valeur. Surtout face à un crash mémoire qui, lui, est la preuve concrète que justement ce n'est pas le cas (et c'est une chance car bien souvent le code "semble" fonctionner laissant alors l'erreur bien cachée et invisible prête à ressortir à un autre moment bien souvent bien pire)

Merci de votre aide ! je vous donne mon code ci-dessous

Ce qui est dommage, c'est que dans tout ce code il manque la fonction destroy_node() (probablement celle qui appelle le free()) et qui était donc la plus importante.
Ce que je peux dire de ce que je vois

1. tu fais un malloc pour le node, et sans même vérifier le résultat de cette allocation (donc qui peut échouer) tu vas remplir node->data. Et enfin tu vérifies la réussite de l'allocation de node (tu peux te dire que mieux vaut tard mais en fait pas en C)
2. ton test se fait via assert() donc au cas où c'est pas vérifié tu crashes tout ton code direct. Une gestion d'erreur c'est une gestion d'erreur. Un truc pensé. Si la fonction est en échec, alors elle nettoie proprement les ressources allouées avant l'échec puis elle renvoie une valeur spéciale à l'appelant. Qui lui détectant alors son propre échec fera de même et ainsi de suite jusqu'au main() qui, seul, a le droit de quitter le programme
3. si node->data n'a pas été alloué, alors l'initialisation de right et left passe à la trappe. Pourtant me semble que ces deux éléments n'ont absolument rien à voir avec data...

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node create_node(const void *data, size_t data_size) {
	Node node = malloc(sizeof(Node));
	if (node == NULL) return NULL;
 
	node->data = malloc(data_size);
	if (node->data == NULL) {
		free(node);
		return NULL;
	}
 
	node->right = node->left = node->parent = NULL;
	set_color(node, RED);
	memcpy(node->data, data, data_size);
	return node;
}

Bon, voilà pour les choses qui auraient pu être réellement faites correctement. Ah oui un dernier truc: les globales c'est franchement le truc à éviter. Solution de facilité pour s'éviter de se prendre la tête avec les paramètres à passer aux fonctions mais dans 98% des cas générant plus de soucis au final tout en solutionnant en réalité pas grand chose.

Ah oui j'allais oublié j'ai utilisé l'utilitaire valgrind et il me dit que dans ma fonction create_node() à la ligne 12 dans ce cas il y avait une erreur peut-être parce que je met right, left et parent à NULL et il n'ame pas trop :/

C'est vrai que c'est une écriture assez peu usitée. Pas interdite mais bon, parfois écrire les choses individuellement ne coûte rien et si ça améliore la lisibilité... Mais à mon avis, valgrind râle parce que l'initialisation était faite dans une alternative (donc pouvait ne pas se faire).

[kaitlyn]

Salut,

Node est de type pointeur (conf la ligne typedef struct ... *Node).
Alors quelle quantité de mémoire est supposée allouer la fonction malloc(sizeof(Node)) ??
Et oui !

[Modaak]

Bonjour

Arf, malheureusement dans ce cas là, son propre avis n'a que peu de valeur. Surtout face à un crash mémoire qui, lui, est la preuve concrète que justement ce n'est pas le cas (et c'est une chance car bien souvent le code "semble" fonctionner laissant alors l'erreur bien cachée et invisible prête à ressortir à un autre moment bien souvent bien pire)


Ce qui est dommage, c'est que dans tout ce code il manque la fonction destroy_node() (probablement celle qui appelle le free()) et qui était donc la plus importante.
Ce que je peux dire de ce que je vois

1. tu fais un malloc pour le node, et sans même vérifier le résultat de cette allocation (donc qui peut échouer) tu vas remplir node->data. Et enfin tu vérifies la réussite de l'allocation de node (tu peux te dire que mieux vaut tard mais en fait pas en C)
2. ton test se fait via assert() donc au cas où c'est pas vérifié tu crashes tout ton code direct. Une gestion d'erreur c'est une gestion d'erreur. Un truc pensé. Si la fonction est en échec, alors elle nettoie proprement les ressources allouées avant l'échec puis elle renvoie une valeur spéciale à l'appelant. Qui lui détectant alors son propre échec fera de même et ainsi de suite jusqu'au main() qui, seul, a le droit de quitter le programme
3. si node->data n'a pas été alloué, alors l'initialisation de right et left passe à la trappe. Pourtant me semble que ces deux éléments n'ont absolument rien à voir avec data...

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node create_node(const void *data, size_t data_size) {
	Node node = malloc(sizeof(Node));
	if (node == NULL) return NULL;
 
	node->data = malloc(data_size);
	if (node->data == NULL) {
		free(node);
		return NULL;
	}
 
	node->right = node->left = node->parent = NULL;
	set_color(node, RED);
	memcpy(node->data, data, data_size);
	return node;
}

Bon, voilà pour les choses qui auraient pu être réellement faites correctement. Ah oui un dernier truc: les globales c'est franchement le truc à éviter. Solution de facilité pour s'éviter de se prendre la tête avec les paramètres à passer aux fonctions mais dans 98% des cas générant plus de soucis au final tout en solutionnant en réalité pas grand chose.


C'est vrai que c'est une écriture assez peu usitée. Pas interdite mais bon, parfois écrire les choses individuellement ne coûte rien et si ça améliore la lisibilité... Mais à mon avis, valgrind râle parce que l'initialisation était faite dans une alternative (donc pouvait ne pas se faire).

Merci de ces précieux conseils, j'ai donc recodé ma fonction et pour destroy_node(Node node); que j'ai modifié également, je vous donne ma fonction ci-dessous ! >< :

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
void destroy_node(Node node)
{
    if (node != NULL)
    {
        free(node);
        if (node->data != NULL)
        {
            free(node->data);
        }
    }
}

[dalfab]

Ta fonction destroy_node a un sérieux problème, elle détruit node ligne 6, puis s'en sert ligne 7 et 8! Tu devrais plutôt:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
void destroy_node(Node node)
{
    if (node != NULL)
    {
        if (node->data != NULL)
        {
            free(node->data);
        }
        free(node);
    }
}

[Sve@r]

Node est de type pointeur (conf la ligne typedef struct ... *Node).

@Modaak
Punaise, j'avais même pas vu !!!
Bon, truc supplémentaire: on ne cache jamais une étoile derrière un type. Déjà d'une part parce que ça ne la cache qu'une fois (passe l'adresse de ta variable à une fonction, ta fonction recevra un pointeur et donc l'étoile ré-apparaitra mais en plus on verra une étoile pour un truc qui en réalité en a deux => on sera perdu)
Et donc d'autre part parce que l'étoile est une information super importante. Elle indique l'état pointeur. Mais si cet état est inclus dans le type le lecteur (comme moi) pourra ne pas la voir et ne pas enregistrer l'info. Et pour lui le code sera incompréhensible.
Plus le post de dalfab. Tu libères un truc puis tu t'en ressers juste en dessous. T'as pas senti une certaine incohérence???

[kaitlyn]

@Sve@r, ta citation laisse croire que le principal intéressé a répondu à mon message mais il n'en est rien.

[Sve@r]

@Sve@r...

En fait je voulais montrer que je répondais à Modaak. Mais si c'est pas comme ça qu'on le comprend ok je change le format.