[résolu] [c] Problème malicieux

Sans-Nom · Mai 1, 2005, 1:05

J’ai un algo de listes doublement chainées qui semble foirer, mais je sais pas trop où ni trop pourquoi. J’explique:

J’ai une liste doublement chainée à laquelle je peux adjoindre un comparateur afin de la trier. Jusque là, tout va bien.

Dans mon projet, je dois ouvrir et lire des données depuis un fichier. Chose que je fais sans problèmes, et là c’est le drame : au 88899é élement (ce sont des cellules), seg fault.

Je relis mon code, et m’aperçoit qu’il s’agit d’un pointeur NULL (windows m’a aussi sorti “l’instruction bidule a essayé de lire à l’adresse 0x00000000”).

Là où je suis plus dubitatif, c’est que cette liste chainée, je l’ai testé avec 1000, ou encore 2500, élements et il n’y a pas eu de bug.

Je regarde donc le basar : j’affiche la liste en cours de route, & pan : elle est complétement corrompue.

Mon champ first me permettant de parcourir la liste de A à Z me donne tout les éléments, tandis que le champ last me donne pas tous les éléments. Soit: je relis mon code, et c’était normal.

Une fois cela fait, je recompile (make clean + make histoire de s’assurer), et … pouf : seg fault. Bon ce qui est bien c’est que cette fois, la liste est correctement linkée.

Sauf que…

L’élément qui a fait segfaulté, hé bien la liste est linkée n’importe comment :o

[cpp]
Itération précédente:

list[ first = 003D5EDC, current = 003D5EB8, last = 003D5F18]
first to last :
content: 003D5EDC
content: 003D5EB8
content: 003D5F00
content: 003D5F18
last to first :
content: 003D5F18
content: 003D5F00
content: 003D5EB8
content: 003D5EDC
end.

Plantage:

list[ first = 003D5EDC, current = 003D5F00, last = 003D5F18]
first to last :
content: 003D5EDC
content: 003D5EB8
last to first :
content: 003D5F18
content: 003D5F00
content: 003D5EB8
content: 00578144
content: 00400000
content: 00000003[/cpp]

Bien sûr, lire à l’adresse 00000003 ça doit pas être commmode : mais pire, la liste est corrompue sans que je sache pourquoi.

Je donne le bout de code qui a fait ce basar :
[cpp] /**
* second: feeds the top/bottom links
*/
genlist_double_copy( &copy, &matrix->cols );
genlist_double_reset_to( &copy, previous_iterator[1] );

debug = 1;

/* printf( “----------- row %u col %u ------------- :\n”, row, col ); /
/ printf( “LISTE COLONNES:\n” ); /
/ if ( row == 4194307 && col == 4194304 ) /
/ printf( “–| debug %d\n”, LINE ); */
iterator = genlist_double_search( &copy, item, &isequal );

/* if ( row == 4194307 && col == 4194304 ) /
/ printf( “–| debug %d\n”, LINE ); /
/ printf( “iterator: %p\n”, iterator ); */
debug = 0;
[/cpp]

A noter:

copy est copie superficielle de matrix->cols (une autre liste d. chainée), et seul les éléments first, last sont conservés, le reste est mis à NULL. En fait, cela permet de parcourir la liste sans modifier le curseur initial.
previous_iterator[1] est dans la liste …
ajouter dans une copie ajoute dans la liste copiée.

Et en fait, c’est la fonction genlist_double_search() qui segfault, et la voici :

[cpp]GenListDoubleItem* genlist_double_search( GenListDouble* list, void* ptr, int isequal )
{
GenListDoubleItem needle = NULL;
GenListDoubleItem* last = NULL;
int cmp = 0;

if ( list->comparator == NULL )
	{
		fprintf(stderr, "[error] list is not using a comparator, you can't use add_sorted()!" );
		return NULL;
	}

if ( isequal != NULL )
	*isequal = 0;

if ( list->first == NULL )
	return NULL;

if ( debug )
	{
		printf( "list[ first = %p, current = %p, last = %p]\n", list->first, list->current, list->last );
		{
			GenListDoubleItem *iterator;
			printf( "first to last :\n" );
			for ( iterator = list->first; iterator != NULL; iterator = iterator->next )
				printf( "content: %p\n", iterator );
			printf( "last to first :\n" );
			for ( iterator = list->last; iterator != NULL; iterator = iterator->previous )
				printf( "content: %p\n", iterator );
		}
		printf( "end.\n");
	}
/**
 * Where is ptr in the list ?
 *  1. before the first item, or it's the same
 */
if ( ( cmp = list->comparator(ptr, list->first->ptr) ) < 0 )
	return NULL;
else if ( cmp == 0 )
	{
		if ( isequal != NULL )
			*isequal = !0;
		return list->first;
	}
/**
 * it's after, and we don't test for the last
 */
else if ( list->first->next == NULL )
	return list->first;

/**
 *  2. after the last ?
 */
if ( ( cmp = list->comparator(ptr, list->last->ptr) ) > 0 )
	return list->last;
else if ( cmp == 0 )
	{
		if ( isequal != NULL )
			*isequal = !0;
		return list->last;
	}

/**
 *  3. before current, the same? ? do some test before testing current
 *    we also store our local needle &amp; last, that will avoid to recomp.
 *    the same thing twice (or more)
 */

/* if ( debug ) /
/ printf( “–| who is needle?\n” ); /
if ( list->current && list->first != list->current && list->last != list->current )
{
if ( ( cmp = list->comparator(ptr, list->current->ptr) ) == 0 )
{
if ( isequal != NULL )
isequal = !0;
return list->current;
}
else if ( cmp < 0 )
{
/ if ( debug ) /
/ printf( “–| needle: list->first->next\n” /
/ “–| last = list->current\n”); /
needle = list->first->next;
last = list->current;
}
else
{
/ if ( debug ) /
/ printf( “–| needle: list->current->next\n” /
/ “–| last = list->last\n”); /
needle = list->current->next;
last = list->last;
}
}
else
{
/ if ( debug ) /
/ printf( “–| needle: list->first->next\n” /
/ “–| last = list->last\n”); /
needle = list->first->next;
last = list->last;
}
/ if ( debug ) /
/ printf( “–| searching… %s:%d needle %p last %p\n”, FILE, LINE, needle, last ); /
/
* needle is not NULL here, list->current may be NULL, but not list->first->next
* and needle == list->current only if list->current != NULL
*
* we advance until needle != last, and until cmp > 0 (meaning ptr > needle->ptr)
*/
while ( needle != last && ( cmp = list->comparator(ptr, needle->ptr) ) > 0 )
needle = needle->next;

/* if ( needle == NULL ) /
/ { /
/ fprintf(stderr, /
/ “{warning] the double list is broken. needle should not be NULL at %s,%d\n” /
/ “[notice] it means that needle was not in the list, but why?\n”, FILE, LINE); /
/ return NULL; /
/ } */

if ( cmp == 0 )
	{
		if ( isequal != NULL )
			*isequal = !0;
		return needle;
	}

/**
 * if needle == last, it means it's before last (we already tested last)
 * else if cmp < 0, it means that ptr is just before needle->ptr
 *   eg: needle->previous must be returned.
 */
return needle->previous;

}[/cpp]

Le bug est tout con c’est needle qui vaut NULL. SAUF QUE : ce n’est pas possible, je suis dans ma liste :o

Je continue donc, je me dis, et si j’affichais à chaque fois la variable iterator qui traîne dans le premier bout de code. j’affiche donc et là … la liste n’est plus corrompue.

Je supprime pour voir si c’est bon, et zou la liste est de nouveau corrompue :o

Je vois pas du tout comment elle a pu se corrompre :x et surtout, j’ai que gdb, pas de valgrind, ni de strace pour voir ce qu’il a fait :o

Quelqu’un a-t’il un conseil? Linux pour compiler & voir mon cas?

Ca m’énerve :o

(et j’ai 5 projets : Système/C, POO (Java (<= caca)), Algo/C, BDD (SQL) et puis un projet tutoré …)

guitoo · Mai 1, 2005, 12:31

fait voir comment tu genere ta liste.

Sans-Nom · Mai 1, 2005, 1:38

La liste est généré par à coup avec ma méthode add_sorted:

[cpp]void* genlist_double_add_sorted( GenListDouble* list, void* ptr, char update )
{
GenListDoubleItem* previous;
GenListDoubleItem* item;
int isequal = 0;

genlist_warn(ptr);
if ( list->comparator == NULL )
	{
		fprintf(stderr, "error: list is not using a comparator, you can't use add_sorted()!" );
		return NULL;
	}

if ( list->copy )
	{
		void* p = genlist_double_add_sorted( list->copy, ptr, update );
		list->first = list->copy->first;
		list->last = list->copy->last;
		return p;
	}

if ( list->first == NULL )
	{
		item = (GenListDoubleItem*)massalloc(sizeof(GenListDoubleItem));
		
		if ( item == NULL )
			return NULL;

		item->ptr = ptr;
		item->next = NULL;
		item->previous = NULL;
		
		list->last = item;
		list->first = item;
		return ptr;
	}
	
previous = genlist_double_search( list, ptr, &amp;isequal );

if ( isequal )
	{
		void* pptr = previous->ptr;
		if ( update )
			previous->ptr = ptr;
		return pptr;
	}

item = (GenListDoubleItem*)massalloc(sizeof(GenListDoubleItem));

if ( item == NULL )
	return ptr;

item->ptr = ptr;
item->previous = previous;
if ( previous != NULL )
	{
		item->next = previous->next;
		if ( previous->next == NULL )
			list->last = item;
		else
			previous->next->previous = item;
		previous->next = item;
	}
else
	{
		item->next = list->first;
		list->first->previous = item;
		list->first = item;
	}

return ptr;

}[/cpp]

En fait, j’ai un maillage sphérique, et je conserve à chaque fois la liste des rangées/colonnes (c’est pour le jeu de la vie).

Mais ce qui m’emmerde, c’est surtout que sur 2500 éléments pas de problèmes, et là avec largement moins d’éléments ça plante, et surtout si je rajoute une ligne de code utilisant iterator, ça ne plante plus :o c’est ce que j’appelle Malicieux.

Sans-Nom · Mai 1, 2005, 4:47

Résolu : j’ai une table de hashage, et à chaque fois que j’ouvrais mon fichier, je définissais le destructeur de cellule à gol_cell_free, puis je détruisais le contenu de la table.

Sauf qu’après ce n’était pas remis à zéro (en gros, y avait encore un destructeur). Et en particulier, dans ma table de hashage, si on ajoute et qu’il y avait déjà quelque chose, alors ce quelque chose est détruit s’il y a le destructeur.

Vais quand même voir si c’est vraiment ça, car dans ma table de hashage je ne met que des cellules, et jamais un maillon de la liste.

[edit] bien malicieux :

[cpp]char genhash_table_insert2( GenHashTable* t, void* key, void* value, void** old_value)
{
unsigned int hash = t->key_hashgen(key, t->size) % t->size;
struct __gol_hash_table_list* current;

if ( t->table[hash] == NULL )
	{
		if ( ( t->table[hash] = genhash_create_list(t, key, value, NULL ) ) == NULL )
			return 0;
		t->count++;
		return !0;
	}

/**
 * check if the key is in...
 */
current = t->table[hash];
while ( current != NULL &amp;&amp; !t->key_comparator(current->key, key) )
	current = current->next;

/**
 * The key is not in list, add it.
 */
if ( current == NULL )
	{
		current = genhash_create_list(t, key, value, t->table[hash] );
		if ( current == NULL )
			return 0;
		t->table[hash] = current;
		t->count++;
		return !0;
	}

*old_value = current->value;
current->value = value;
return !0;
}

char genhash_table_insert( GenHashTable* t, void* key, void* value)
{
void* old_value;
char ret = genhash_table_insert2(t, key, value, &old_value);

if ( t->value_destroy_handler )
	t->value_destroy_handler(old_value);
return ret;

}[/cpp]

Sauf que : old_value ne vaut soit pas NULL, soit il n’est pas mis à NULL. J’ai corrigé, et ça marche. OUF.

Sur ce…