Pomoć u razumevanju pokazavača na funkcije

Započeo Adis A., 15.05.2012, 10:19

prethodna tema - sledeća tema

Adis A.

15.05.2012, 10:19 Poslednja Izmena: 15.05.2012, 10:35 od Adis A.
Naišao sam na jedan problem prilikom razumevanja pokazivača na funkcije u sledećem primeru.
(Primer je iz knjige "The C Programming Language" - Brian W. Kerninghan, Dennis M. Ritchie)

"... We will illustrate this by modifying the sorting procedure written earlier in this chapter so that if the optional argument  -n is given, it will sort the input lines numerically instead of lexicographically."
"...Lexicographic comparasion of two lines is done by strcmp, as before; we will also need a routine numcmp that compares two lines of the basis of numeric value and returns the same kind of condition as strcmp does. These function are declared ahead of main and a pointer to the appropriate one is passed to qsort."


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


#define MAXLINES 5000 // max #lines to be stored

char *lineptr[MAXLINES]; // pointers to text line

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
int getline(char line[], int maxline);

void qsort(void *lineptr[], int left, int right, int (*comp) (void *, void *));
int numcmp(char *, char *);

int main(int argc, char *argv[]) {

int nlines; // number of input lines read
int numeric = 0; // 1 if numeric sort

if (argc > 1 && strcmp(argv[1], "-n") == 0)
numeric = 1;
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
qsort((void **) lineptr, 0, nlines - 1, (int (*)(void*,void*)) (numeric ? numcmp : strcmp));
writelines(lineptr, nlines);
//return 0;
}
else {
printf("error: input too big to sort\n");
//return 1;
}

return EXIT_SUCCESS;
}

#define MAXLEN 1000 // max length of any input line
int getline(char *, int);
char *alloc(int);

// readlines: read input lines
int readlines(char *lineptr[], int maxlines)
{
int len, nlines;
char *p, line[MAXLEN];

nlines = 0;
while ((len = getline(line, MAXLEN)) > 0) {
if (nlines >= maxlines || (p = alloc(len)) == NULL)
return -1;
else {
line[len-1] = '\0'; // delete newline
strcpy(p, line);
lineptr[nlines++] = p;
}
}


return nlines;
}

// writelines: write output lines
void writelines(char *lineptr[], int nlines)
{
int i;

for (i = 0; i < nlines; i++)
printf("%s\n", lineptr[i]);
}

// qsort: sort v[left]...v[right] into increasing order
void qsort(char *v[], int left, int right, int (*comp)(void *, void *))
{
int i, last;
void swap(char *v[], int i, int j);

if (left >= right) // do nothing if array contains
return; // fewer than two elements

swap(v, left, (left + right)/2);

last = left;

for (i = left + 1; i <= right; i++)
if ((*comp)(v[i], v[left]) < 0)
swap(v, ++last, i);

swap(v, left, last);
qsort_(v, left, last-1, comp);
qsort_(v, last+1, right, comp);

}

// swap: interchange *v[], int i, int j
void swap(void *v[], int i, int j)
{
void *temp;

temp = v[i];
v[i] = v[j];
v[j] = temp;
}


// getline: read a line into s, return length
int getline(char s[], int lim)
{
int c, i;

for (i = 0; i < lim-1 && (c=getchar()) != EOF && c!='\n'; i++)
s[i] = c;
if (c == '\n') {
s[i] = c;
++i;
}
s[i] = '\0';

return i;
}

// numcmp: compare s1 and s2 numerically
int numcmp(char *s1, char *s2)
{
double v1, v2;

v1 = atof(s1);
v2 = atof(s2);

if (v1 < v2)
return -1;
else if (v1 > v2)
return 1;
else
return 0;
}



Ono što mene najviše buni nalazi se u main funkciji, tako da na nju treba obratiti najviše pažnje, tj. na sledeće:

if (argc > 1 && strcmp(argv[1], "-n") == 0)
numeric = 1;
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
qsort((void **) lineptr, 0, nlines - 1, (int (*)(void*,void*)) (numeric ? numcmp : strcmp));
writelines(lineptr, nlines);
//return 0;
}



Prototip funkcije qsort:
void qsort(void *lineptr[], int left, int right, int (*comp) (void *, void *));
"...comp is a pointer to a function that has two void * arguments and returns an int"

Poziv funkcije qsort iz  funkcije main:
qsort((void **) lineptr, 0, nlines - 1, (int (*)(void*,void*)) (numeric ? numcmp : strcmp))

Prva tri argumenta koja funkcija qsort prihvata su mi jasna, međutim kod četvrtog argumenta imam neke neodumice. Kao što vidimo  u zavisnosti od vrednosti promenljive numeric kao rezultat dobićemo funkciju numcmp ili strcmp, što je urađeno koristeći tzv. ternarni operator. Nakon toga se valjda dešava cast-ovanje (konverzija) pokazivača te funkcije na pokazivač koji će pokazivati na funkciju koja ima dva void * argumenta i kao rezultat vratiti int. Ako je ovo tačno, nije mi jasno na koji način se to radi. Ako ovo nije tačno, ako neko zna šta se ovde dešava bio bih mu zahvalan da mi to objasni.

Bilo kakva pomoć u razjašnjenju poziva funkcije qsort je dobro došla.


Marko Аcović

Pokazivaci na funkcije koriste isti mehanizam kao i pokazivaci na podatke. Sadrze adresu necega sto je smesteno u memoriji.
Kao i pokazivaci na podatke, pokazivaci na funkcije moraju da imaju istu formu (potpis) kao i ono na sta pokazuju.
Tako, na primer, u tvom primeru, pre poziva f-je qsort, mozes da napises sledece:

int numeric = 1;
int (*fp)(void*, void*);  // pokazivac na funkciju (ima isti potpis kao i sama funkcija na koju pokazuje)
fp = numeric ? &numcmp : &strcmp;  // dodeljujes adresu funkcije pokazivacu zavisno od vrednosti promenljive numeric

Dalje u kodu umesto da koristis funkciju, koristis pokazivac na funkciju

char word1[20];
char word2[20];
int result;

result = (*fp)(word1, word2); // *fp znaci vrati sadrzaj pokazivaca a to je funkcija na koju pokazuje

Nadam se da sam bio od pomoci :)

Adis A.

16.05.2012, 10:19 #2 Poslednja Izmena: 16.05.2012, 10:21 od Adis A.
Malopre sam našao u dokumentu "Errata for The C Programming Language, Second Edition", da su K&R zakomplikovali ovaj izraz, kao što su to i sami objasnili na sledeći način:

"The qsort discussion needs recasting in several ways. First, qsort is a standard routine in ANSI/ISO C, so the rendition here should be given a different name, especially because the arguments to standard qsort are a bit different: the standard accepts a base pointer and a count, while this example uses a base pointer and two offsets.
Also, the comparison-routine argument is not treated well. The call shown on p 119, with an argument

(int (*)(void*,void*))(numeric? numcmp : strcmp)

is not only complicated, but only barely passes muster. Both numcmp and strcmp take char * arguments, but this expression casts pointers to these functions to a function pointer that takes void * arguments. The standard does say that void * and char * have the same representation, so the example will almost certainly work in practice, and is at least defensible under the standard. There are too many lessons in these pages."

I tek nakon tvog objašnjenja, Marko, sve mi je postalo kristalno jasno!
Hvala.  :bravo: