Discussion :

[Arzar]

Oula. Ce n'est peut être pas un exo sur les pointeurs mais un peu quand même, hein

Code :

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

char* temp_db = (char*)malloc(sizeof(database));

database est un char*; Vu que la taille d'un pointeur est généralement de 4 octets tu fais en réalité un malloc(4);

bon en révisant un peu l'allocation dynamique, j'ai vu qu'en c++, on devait plutot utilisé new et delete...
bref, mon problème est donc résolue:

Code :

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

1
2
 
char* temp_db = new char;

Attention le "new char" n'alloue qu'un seul char sur le tas.
Mais tu as besoin d'allouer un tableau de char, un tableau assez grand pour contenir toute la base de donnée.

Code :

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

1
2
3
4
5
 
char* temp_db = new char[taille_database]; // et pas sizeof(database)
//...
// après utilisation
delete[] temp_db;

La fonction strncat écrit les charactères voulus, plus '\0' (selon la doc)...

D'ailleurs est-ce que tu as vérifié que ta base de donnée à l'origine contient bien ces '\0' ? Si oui strncat est parfait, si non il vaut mieux faire des memcpy (qui n'ajoute pas de '\0')

Code :

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

database = strdup(temp_db);

Attention ! La doc de strdup explique que cette fonction renvoie une nouvelle chaine allouée avec malloc. Tu ne vas donc pas modifier l'ancienne database (ce qui était le but, non ?)

[ncheboi]

Bonjour,

Je ne suis pas sûr (je n'utilise jamais de char*), mais qu'est-ce que ça donne si tu fais:

Code :

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

delete [] temp_db;

J'avais essayé mais ça résoud pas mon problème....

[Invité]

mais au niveau du main, l'appel à pRadixSort(char* database) la laisse inchangée...

Code :

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

database = strdup(temp_db);

Cette ligne modifie l'adresse pointée par database, donc si tu veux modifier database il faut la passer par référence non constante.
D'autre part ces deux ligne devraient poser un problème :

Code :

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

1
2
3
4
 
char* temp_db = new char;
//....
strncat(temp_db, *pKey, 48);

temp_db pointe vers un caractère(char), qu'on peut à la rigueur considérer comme un tableau de taille 1. D'après la doc de cppreference, strncat nécessite un buffer destination suffisamment grand, c'est à dire donc la taille fait soit la taille du buffer source, soit 48+1 caractères. Donc tu a le choix soit tu passe par un allocation dynamique de tableau, soit par une creation statique :

Code :

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

1
2
3
4
5
6
7
8
 
char* tmp_db(new char[ LaTailleDynamiqueQueTuVeux ] );
//....
delete [] tmp_db;
 
// ou bien
char tmp_db[49] = { '\0' };// je crois qu'on peut initialiser statiquement l'intégralité d'un tableau ainsi
//note : pas de delete dans ce cas

[ncheboi]

oups j'étais retourné sur la page 1 et j'avais pas vu la réponse d'Arzar. Désolé d'avoir reposté les mêmes erreurs. Je prends en compte vos remarques et je reviens vers vous.
Merci beaucoup en tout cas...

[ncheboi]

Code :

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

database = strdup(temp_db);

Cette ligne modifie l'adresse pointée par database, donc si tu veux modifier database il faut la passer par référence non constante.

Par référence non constante? J'imagine que tu veux dire:

Code :

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

void pRadixSort(char &database);

en signature de fonction? Si c'est le cas, je ne peux pas modifier la signature de ma fonction donc il faut que je m'y prenne autrement.

Code :

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

1
2
3
4
5
6
7
8
 
char* tmp_db(new char[ LaTailleDynamiqueQueTuVeux ] );
//....
delete [] tmp_db;
 
// ou bien
char tmp_db[49] = { '\0' };// je crois qu'on peut initialiser statiquement l'intégralité d'un tableau ainsi
//note : pas de delete dans ce cas

J'ai modifié en prenant la première option. Je ne peux toujours pas faire de delete.
En plus j'ai tenté:

Code :

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

1
2
3
4
5
6
7
8
 
database = (char*)memmove(database,temp_db,sizeof(temp_db));
//et
memmove(database,temp_db,sizeof(temp_db));
//et
database = (char*)memcpy(database,temp_db,sizeof(temp_db));
//et
memcpy(database,temp_db,sizeof(temp_db));

et aucun d'eux marche. maintenant le programme plante carrément...memcpy et memmove demande à ce que le dernier paramètre soit le nombre de bytes à copie et que la copie est binaire... je sais pas trop si ça peut être la source du problème...

[Arzar]

Je m'autocite :

char* temp_db = (char*)malloc(sizeof(database));

database est un char*; Vu que la taille d'un pointeur est généralement de 4 octets tu fais en réalité un malloc(4);

sizeof(temp_db) == sizeof(database) == sizeof(char*) == 4

[ncheboi]

Ok, désolé pour la gourde .

Code :

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

1
2
 
database = (char*)memmove(database,temp_db,sizeof(temp_db)*strlen(temp_db));

... pour être sur j'ai bien vérifié que sizeof(temp_db)*strlen(temp_db) contiennent le nombre d'octet que je veux...
ça replante...

[ncheboi]

j'ai aussi essaye

Code :

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

1
2
 
strncpy(database,temp_db,strlen(temp_db) + 1);

mais en vain. j'ai l'impression que je peux pas modifier database. pourtant elle n'est pas constante...

[Arzar]

Peux-tu remontrer l'intégralité de la fonction pRadix_sort2 ? (mais sans le détail de pCounting_sort2)
J'ai eu peu perdu le fil des modifs faites

[ncheboi]

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
 
void pRadix_sort2(char *database)
{
	vector <char*> keys;
	int db_length = strlen(database);
	//after his for loop, the keys vector will contain pointers to the beginning of each key
	for(int i = 0 ; i < db_length ; i+=48)
	{
		keys.push_back(database + i);
	}
 
	//we sort the keys array starting from the end of the keys
	for(int i = KEY_LENGTH - 1; i >=0 ; i--)
		pCounting_sort2(keys,i);
 
	char* temp_db = new char[strlen(database)];
	*temp_db = '\0';//sinon temp_db contient des trucs bizarres avant...
	//iterate on the keys vector and append the 48 chars following the pointer to temp_db
	for(std::vector<char*>::iterator pKey = keys.begin(); pKey != keys.end(); ++pKey)
	{
		strncat(temp_db, *pKey, 48);
	}
 
	/*c'est ici que je dois faire en sorte que ce vers quoi pointe database soit modifé.
*/
        //database = strdup(temp_db); -> database pointe vers l'espace alloué par strdup... Du coup c'est pas ce qu'il faut.
	//strncat(database,temp_db,48);
	//strncpy(database,temp_db,1); rien que copier un char ça marche pas...
        //strncpy(database,temp_db,strlen(temp_db)); non plus du coup...
	print_database(database);
	//delete [] temp_db; <-- tjs pas résolu ce problème non plus
}

[Invité]

En fait, pourquoi passe tu par une variable temporaire ? Tu ne peux pas faire strncat directement sur database ?

[ncheboi]

En fait, pourquoi passe tu par une variable temporaire ? Tu ne peux pas faire strncat directemnt sur database ?

Non parce que le strncat concatène dans temp_db des charactères qui sont dans database. En gros le vector keys contient des pointeurs à différents endroits de database... J'ai trié en utilisant ces pointueurs pour utiliser moins de place.
Bref, du coup, si je modifie database en même temps...

Mais je comprends vraiment pas pourquoi ça marche pas... C'est bizarre...

[Invité]

A chaque fois que tu fais strlen, tu oublie de rajouter 1 pour le marqueur de fin. Donc le dernier strncat de ta boucle écrit un '\0' hors de la zone de mémoire alloués. En fait 'je pense' que tu peux remplacer ta boucle par celle-ci, qui doit consommer moins de mémoire, surtout si strlen est grand :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
 
	char temp_db[48] = { '\0' };
 
	//iterate on the keys vector and append the 48 chars following the pointer to temp_db
	for(std::vector<char*>::iterator pKey = keys.begin(); pKey != keys.end(); ++pKey)
	{
		strncat(temp_db, *pKey, 48);
                strncat(database, temp);
	}
 
	print_database(database);

En fait en regardant cette solution je viens de voir que la dernière boucle est totalement inutile : les valeurs pointées par les entrées de keys et par database sont les même. Donc si tu modifie l'un, tu modifie l'autre, pas besoin de copie

[ncheboi]

A chaque fois que tu fais strlen, tu oublie de rajouter 1 pour le marqueur de fin. Donc le dernier strncat de ta boucle écrit un '\0' hors de la zone de mémoire alloués. En fait 'je pense' que tu peux remplacer ta boucle par celle-ci, qui doit consommer moins de mémoire, surtout si strlen est grand :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
 
	char temp_db[48] = { '\0' };
 
	//iterate on the keys vector and append the 48 chars following the pointer to temp_db
	for(std::vector<char*>::iterator pKey = keys.begin(); pKey != keys.end(); ++pKey)
	{
		strncat(temp_db, *pKey, 48);
                strncat(database, temp);
	}
 
	print_database(database);

En fait en regardant cette solution je viens de voir que la dernière boucle est totalement inutile : les valeurs pointées par les entrées de keys et par database sont les même. Donc si tu modifie l'un, tu modifie l'autre, pas besoin de copie

euh j'ai peur de ne pas t'avoir suivi là.
dans la boucle si j'utilise strncat(database), ben je modifie database sans avoir fini de tout copier... bref, c'est ce que j'expliqué au dessus.

sinon, la boucle est utile parce que
database point au déput d'un char* de taille 480 par exemple (10 entrées).
et vector <char*>keys pointe vers le début de chaque entrée dans avec les pointeurs trié comme il faut...

Du coup, le problème est le suivant:
itérer keys, et prendre les 48 chars pointés par chaque pointeur et les mettre (les chars) les un à la suite de l'autre dans database.

[Invité]

Ah pardon je n'avais compris que tu triais les entrées entre elles. Mea Culpa, je pensais que tu triais les 48 valeurs correspondant à chaque entrée, mais que l'ordre global ne changeait pas. Sinon rajouter 1 au résultat de strlen ne résoud pas ton problème ?

[Arzar]

C'est presque bon, j'ai l'impression

Code :

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

int db_length = strlen(database);

Tu as dis dans un post plus haut que la taille renvoyée est correcte, or comme strlen s'arrête au premier '\0" j'en conclue donc que database ne contient qu'un seul '\0' à la toute fin. Chaque entrée de la base de donnée est donc une séquence d'octet et pas une chaine terminée par un '\0'.

Et du coup je ne comprends pas du tout pourquoi tu utilises les fonctions de la lib C en str*** (strcpy, strdup, strncat...), fonctions qui ne travaillent que sur des chaines terminées par '\0'. Dans ton cas il faut juste copier des séquences d'octets depuis un buffer (la database) vers un buffer temporaire dans le bon ordre, puis une fois fait tout reclaquer dans le buffer original. memcpy devrait suffire amplement, par exemple :

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
 
const int KEY_LENGTH = 16;
const int DATA_LENGTH = 32;
const int ENTRY_LENGTH = KEY_LENGTH + DATA_LENGTH;
 
void pRadix_sort2(char *database)
{
   std::vector<char*> keys;
   int db_length = strlen(database);
   //after his for loop, the keys vector will contain pointers to the beginning of each key
   for(int i = 0 ; i < db_length ; i += ENTRY_LENGTH)
  {
      keys.push_back(database + i);
   }
 
   //we sort the keys array starting from the end of the keys
   for(int i = KEY_LENGTH - 1; i >=0 ; i--)
   {
      pCounting_sort2(keys,i);
   }
 
   char* temp_db = new char[db_length]; // allocate buffer big enough to hold temporary database
   memset(temp_db, 0, db_length); // clear buffer
   for(unsigned int i = 0; i < keys.size(); i++)
   {
      // copy each entry of the database into the temporary buffer
      // at the right position
      memcpy(temp_db + (i * ENTRY_LENGTH), keys[i], ENTRY_LENGTH);
   }
 
   // then copy back to database	
   memcpy(database, temp_db, db_length);
 
   print_database(database);
   delete [] temp_db; // release temporary buffer
}

[ncheboi]

J'ai pris en compte tes modifs mais j'ai toujours une exception levée:
Violation d'accès lors de l'écriture à l'emplacement...

dès que j'essaye d'accéder à database...

En plus, en débogant, je vois que temp_db est plus grand que database. Il a alloué strlen + 16....
J'y comprends plus grand chose...

[ncheboi]

Dites-moi, j'ai bien le droit de modifier un char* passé à une fonction???
Parce que j'ai cherché sur internet pour des gens ayant la même erreur que moi et on dit que c'est une erreur de gestion de mémoire, qu'il faut allouer de la mémoire pour le char*.
J'ai:

Code :

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

1
2
3
4
5
6
 
int main()
{
   char* db = "doeklpfjfgykflejwww.yahoo.frwww.yahoo.frwww.yahoaaaalpfjfgykflejwww.yahoo.frwww.yahoo.frwww.yaho"
   pRadixSort2(db);
}

et dans mon pRadixSort, je modifie db... enfin j'essaye... j'ai bien le droit(enfin sinon j'ai pas de solution à mon problème mais bon c'est juste pour être sur...

[ncheboi]

Pour confirmer mes suspicions je viens de trouver quelque chose sur un autre blog.

Il dit que le fait d'avoir fait char* db = "..." dans le main fait que db est un const char qui ne peut donc pas être modifié par la fonction pRadixSort....

hmmm....

[ncheboi]

Bon ben problème résolue alors...
Ca venait de la manière dont j'utilisais ma fonction, pas de la fonction elle même... Désolé de vous avoir fait galérer...

Pour conclure voici le code final:

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
 
void pRadix_sort(char *database)
{
	vector <char*> keys;
	int db_length = strlen(database);
	//after his for loop, the keys vector will contain pointers to the beginning of each key
	for(int i = 0 ; i < db_length ; i+=48)
	{
		keys.push_back(database + i);
	}
 
	//we sort the keys array starting from the end of the keys
	for(int i = KEY_LENGTH - 1; i >=0 ; i--)
		pCounting_sort2(keys,i);
 
	char* temp_db = new char[db_length];
	//iterate on the keys vector and append the 48 chars following the pointer to temp_db
	for(unsigned int i = 0; i < keys.size(); i++)
	{
		memcpy(temp_db + i*ENTRY_LENGTH,keys.at(i),ENTRY_LENGTH);
	}
	//copy temp_db into database	
	memcpy(database,temp_db,db_length);
 
	delete [] temp_db;
}

et voici comment je m'en sert:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int main()
{
	char db[] = "doeklpfjfgykflejwww.yahoo.frwww.yahoo.frwww.yahoaaaalpfjfgykflejwww.yahoo.frwww.yahoo.frwww.yahoabcdlpfjfgykflejwww.yahoo.frwww.yahoo.frwww.yaho";
	cout << "before sort: " <<endl;
	print_database(db);
	pRadix_sort2(db);
	cout << "after sort: " <<endl;
	print_database(db);
 
 
	return 0;
}

Mon problème venait donc du fait que quand on passe un char* défini comme ça:

Code :

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

1
2
 
char* s = "testest" ;

a une fonction, ben il est constant et ne peux être modifié...