Malloc : Process returned -1073741819

Merci pour ta réponse.
Je ne savais pas qu'il y avait un débord d'allocation en mode debug, c'est un indice.
L'explosion intervient 'dans' le malloc : celui-ci est directement suivi d'un printf qui ne s'affiche pas.

Salut,

Pep : ne t’étonnes pas avec un truc de bac + 10 en algorithmique d’obtenir si peu de feedback sur ton problème.

Effectivement, ton bug est toute bête : tu as écrit :

t_next = t->children[a[d_index]] = …

au lieu de

t_next = t->children[d_index] = …

(105ième ligne).

Mamie : je t’invite à consulter les pages 60 et 61 du Kernighan & Ritchie, avant de dire trop d’âneries. La polémique du « for against while » date des années 60 (ça nous rajeunit pas^^). Il te sera par ailleurs profitable d’approfondir tes connaissances en techniques de compilation et d’optimisation de code.

k.

Merci pour ta proposition que je saisis au vol.

J'ai isolé en 160 lignes les éléments de structures et de fonctionnalités minimaux qui reproduisent le bug et ajouté des traces explicites.

Un progrès : le malloc retourne à présent un pointeur NULL, alors qu'auparavant il plantait le programme sans davantage de prises.

Le plantage intervient ici au troisième appel de la fonction get_permut dans le main, à mi-chemin de la descente récursive via .

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

#define DEBUG 1

typedef struct permut
{
unsigned n;
unsigned *a;

} permut;

/// stockage des éléments du groupe symétrique d'ordre n selon l'ordre lexicographique
typedef struct permut_group_tree_node
{
unsigned n; /// ordre du groupe hérité du parent
permut *p; /// non NULL ssi feuille
struct permut_group_tree_node **children; /// la descendance

} permut_group_tree_node;

typedef permut_group_tree_node *permut_group_tree;

/** affiche un vecteur d'entier positifs **/
void print_vector(char *s, unsigned *v, unsigned n)
{
if (n == 0) printf("%s : {}", s);
else
{
unsigned i = 0;
printf("%s : { ", s);
while (i++ < n) printf("%u ", v[i - 1]);
printf("}");
}
}

static permut_group_tree *permut_groups = NULL; /// stockage statique des groupes de permutation
static unsigned max_order = 15;

/** initialise l'espace de stockage statique pour les groupes de permutations **/
void init_permut_groups()
{
if (DEBUG) printf("\n---* init_permut_groups[%u]\n\n", max_order);
permut_groups = (permut_group_tree *) malloc(max_order * sizeof(permut_group_tree));
unsigned n = max_order;
while (n-- > 0) permut_groups[n] = NULL;
}

/** private : recursive method to search/init storage structure **/
permut *find_or_create_permut(unsigned *a, permut_group_tree t, unsigned d)
{
if (DEBUG)
{
printf("\nFIND OR CREATE (current tree node address : %u)\n", t);
printf(" group order: %u", t->n);
printf(" depth: %u", d);
printf(" distance to end: %u\n", t->n - d);
printf(" local permut address (!= NULL iff leaf node) : %u\n", t->p);
printf(" local children array address : %u\n", t->children);
}

unsigned n = t->n;
unsigned dist2end = t->n - d;

if (dist2end > 0 && t->children == NULL)
{
if (DEBUG) printf("---* t->children NULL => malloc(%u * %u);\n", dist2end, sizeof(permut_group_tree));

t->children = (permut_group_tree *) malloc(dist2end * sizeof(permut_group_tree));
if (DEBUG)
{
if (t->children != NULL) printf("---* %u children tab allocated\n", dist2end);
else
{
printf("---* %u children tab NOT allocated !!!!!!!!!!!!!!!!!!\n", dist2end);
printf(">>>> ON PROGRESSE : CATCH DE l'ERR !!!!!!!!!!!!!!!!!\n");
exit(-1);
}
}

unsigned i = dist2end;
while (i-- > 0) {
if (DEBUG) printf("t->children[%u] = NULL;", i);
t->children[i] = NULL;
if (DEBUG) printf(" done\n");
}
}

/// condition de terminaison
if (dist2end == 0) return t->p;

/// vue naïve : permut_group_tree t_next = t->children[a[d]]; -> plus compliqué :
/// l'index relatif (d_index) de l'élément a[d] dans le tableau de successeurs (children)
/// correspond à la position relative de a[d] par rapport à a[d], a[d + 1] ... a[n - 1]
/// si a[d] est le minorant de cet ensemble, d_index vaut zéro
/// en pratique (pas optimisé cf. récursion), on initialise d_index à 0 et on l'augmente de l'unité pour chaque a[j > d] tq a[j] < a[d]

unsigned d_index = 0;
unsigned i = n;
unsigned a_d = a[d];
while (--i > d) if (a[i] < a_d) d_index++;

if (DEBUG) printf("---* d = %u, a[d] = %u, d_index = %u => t_next = t->children[%u]\n", d, a[d], d_index, d_index);
permut_group_tree t_next = t->children[d_index];

if (t_next == NULL)
{
if (DEBUG) printf("---* t_next is NULL : init it \n");
t_next = t->children[a[d_index]] = (permut_group_tree) malloc(sizeof(permut_group_tree_node));
t_next->n = t->n;
t_next->children = NULL;
t_next->p = NULL;
}

return find_or_create_permut(a, t_next, d + 1);
}

/** renvoie la permutation du groupe symétrique d'ordre n donnée par sa clé a **/
permut *get_permut(unsigned *a, unsigned n)
{
if (DEBUG)
{
print_vector("\n\n >>>> get_permut <<<<", a, n);
printf("\n");
}
if (a == NULL || n > max_order) return NULL;

if (permut_groups == NULL) init_permut_groups();

permut_group_tree group_n_tree = permut_groups[n - 1];
if (group_n_tree == NULL)
{
group_n_tree = permut_groups[n - 1] = (permut_group_tree) malloc(sizeof(permut_group_tree_node));
group_n_tree->n = n;
group_n_tree->children = NULL;
group_n_tree->p = NULL;
}

return find_or_create_permut(a, group_n_tree, 0);
}

int main()
{
printf("\n> GROUPE SYMETRIQUE ET PERMUTATIONS\n\n");

printf("\n > Reconnaitre une permutation puis l'instancier (et la stocker)\n\n");

unsigned id[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
get_permut(id, 10);

unsigned a[10] = {0, 2, 1, 5, 3, 4, 9, 8, 7, 6};
get_permut(a, 10);

unsigned b[10] = {0, 6, 4, 7, 9, 8, 2, 1, 5, 3};
get_permut(b, 10);

system("pause");

return 0;
}

Bien lu ta proposition..

Je comprends la motivation de tes remarques 1) et 3) en regard de ta dernière phrase parenthésée.
Elles ne sont malheureusement pas pertinentes : il s'agit d'une structure et d'une fonctionnalité de caching d'instances d'objets mathématiques. J'ai dégrafé les 160 lignes de code du reste, ce morceau apparaît donc hors contexte.

Pour la 2), c'est une question de forme et d'habitude : une boucle for est une construction élaborée sur la base d'un while, et j'encourage mes étudiants à se passer du for pour développer leur sens algorithmique.

Sur le fond, je cherche toujours où se joue l'effet de bord assassin : je penche pour une bêtise évidente, .. mais seulement une fois le nez dessus^^

Merci pour ton temps.