Problem mit qsort() - steh auf'm Schlauch =)



  • Hi!

    ich steh momentan komplett auf'm Schlauch. Ich versuche, ein Array von Pointern auf Pointern zu sortieren, bekomme dabei aber immer ein Segfault, weil auf illegalem Speicher zugreif.

    Ich vermute, dass irgendwas mit der Art, wie ich qsort() verwende, nicht stimmt. Ich hab ein kleines Testprogramm geschrieben, indem ich all das aus meinem Code entfernt hab, das nicht fuer's Sortieren relevant ist und indem ich meine eigene Datenstruktur mit ints ersetzt hab.
    Dieses einfache Testprogramm segfaultet zwar nicht, sortiert aber die Daten auch nicht so, wie es sollte:

    #include <stdio.h>
    #include <stdlib.h>
    
    int cmp(const void* a, const void* b)
    {
    	int* el1 = *((int**) a);
    	int* el2 = *((int**) b);
    
    	return el1 - el2;
    }
    
    int main()
    {
    	const int N = 5;
    	int i = 0;
    	int** a = malloc(sizeof(int*) * N);
    	for (i = 0; i < N; ++i)
    	{
    		a[i] = malloc(sizeof(int));
    		*a[i] = 10 - i;
    	}
    
    	for (i = 0; i < N; ++i) printf("%i\n", *a[i]);
    	printf("\n");
    
    	qsort(a, N, sizeof(int*), cmp);
    
    	for (i = 0; i < N; ++i) printf("%i\n", *(a[i]));
    }
    

    was mach ich falsch? πŸ˜•



  • Blue-Tiger schrieb:

    int* el1 = ((intπŸ˜‰ a);
    int* el2 = ((intπŸ˜‰ b);

    nicht eher

    int e11 = *((int*)a);
    int e12 = *((int*)b);
    

    ?



  • SG1 schrieb:

    Blue-Tiger schrieb:

    int* el1 = ((intπŸ˜‰ a);
    int* el2 = ((intπŸ˜‰ b);

    nicht eher

    int e11 = *((int*)a);
    int e12 = *((int*)b);
    

    ?

    Nope, qsort uebergibt der Vergleichsfunktion ja pointer auf die Array-Elemente. Da die Array-Elemente vom Typ int* sind, sind die Pointer, die der Vergleichsfunktion uebergeben werden, vom Typ int**. Aber dein Post hat mich auf den Fehler in meinem Testprogramm aufmerksam gemacht... die Vergleichsfunktion fuer qsort() muesste logisch so gehen:

    int cmp(const void* a, const void* b)
    {
    	int* el1 = *((int**) a);
    	int* el2 = *((int**) b);
    
    	return *el1 - *el2;
    }
    

    Ich hatte das Dereferenzieren beim Subtrahieren vergessen πŸ™‚

    Hmmm... jetzt versteh ich umso weniger, was an meinem urspruenglichen Programm falsch ist... πŸ˜•

    Vielleicht sieht ja jemand den Fehler, ich post einfach mal den Original-Quelltest:

    typedef struct record
    {
    	char c;  // the byte this record represents
    	int cnt; // frecquency
    
    //	[...]
    }Record;
    
    /*
     * compares two records based on their frequency-counts
     */
    int compareRecords(const void* a, const void* b)
    {
    	Record* el1 = *((Record**) a);
    	Record* el2 = *((Record**) b);
    	return el1->cnt - el2->cnt;
    }
    
    /*
     * reads the file to encode it
     */
    void encodeFile(const char* filename)
    {
    	const int BUFFERSIZE = 1024;
    	const int NRECORDS = 256;
    	FILE* file = fopen(filename, "rb");
    	long nCharsRead = 0;
    	char* buf = malloc(BUFFERSIZE);
    	Record** recs = malloc(sizeof(Record*) * NRECORDS);
    	Record* tmp = 0;
    	int i, j;
    
    	for (i = 0; i < NRECORDS; ++i)
    	{
    		recs[i] = malloc(sizeof(Record));
    		memset(recs[i], 0, sizeof(Record));
    	}
    
    	// read file in chunks of 1 kb and count 
    	// how often each byte-value occurs
    	while (!feof(file))
    	{
    		nCharsRead = fread(buf, sizeof(char), BUFFERSIZE, file);
    		printf("read %u bytes\n", nCharsRead);
    		for (i = 0; i < nCharsRead; ++i)
    		{
    			recs[buf[i]]->c = buf[i];
    			++(recs[buf[i]]->cnt);
    		}
    	}
    
    	qsort(recs, NRECORDS, sizeof(Record*), compareRecords);
    
    //	[...]
    

    Das Programm verabschiedet sich in compareRecords(), der GNU Debugger meint dazu noch:

    Starting program: D:\works\study\ad\week7/a4.exe test.txt
    
    Program received signal SIGSEGV, Segmentation fault.
    0x004012ac in compareRecords (a=0x3d8a20, b=0x3d63d8)
        at D:/works/study/ad/week7/a4.c:34
    34              return el1->cnt - el2->cnt;
    (gdb) print *el1
    $1 = {c = 42 '*', h = 42 '*', cnt = 707406378, left = 0x1801d2,
      right = 0x12a002a}
    (gdb) print *el2
    Cannot access memory at address 0x72
    


  • Blue-Tiger schrieb:

    Dieses einfache Testprogramm segfaultet zwar nicht, sortiert aber die Daten auch nicht so, wie es sollte:

    int cmp (void* a, void* b) 
    { 
        return *(int*)a - *(int*)b; 
    } 
    
    int main() 
    { 
        int N = 10; 
        int i = 0; 
        int* a = malloc(sizeof(int*) * N); 
        for (i = 0; i < N; ++i) 
        {
            a[i] = rand(); 
            printf("%i\n", a[i]);
        } 
        printf("\n"); 
    
        qsort (a, N, sizeof(int*), cmp); 
    
        for (i = 0; i < N; ++i) 
            printf("%i\n", a[i]); 
    }
    


  • Blue-Tiger schrieb:

    Da die Array-Elemente vom Typ int* sind,

    Ah, das hatte ich ueberlesen, sorry.



  • Problem geloest, ich hab in einer anderen (fehlerhaftimplementierten) Funktion nochmal compareRecords() aufgerufen, da lag der Fehler πŸ™‚


Log in to reply