1
\$\begingroup\$

As I'm learning to program in C, I'm making my way through K&R.

The goal of the exercise is to add a option to the program so that the sorting does not depend on upper or lower-case letters.

What are your opinions on my use of function pointers in this exercise? Do you see any obvious beginner traps in the code?

#include "main.h"
char *pointersToLines[MAX_NO_OF_LINES];
int (*compareFunctionPointers[3])(void *, void *);
int main(int argc, char *argv[]) {

    // Store pointers to the diffrent types of
    // compare functions in a array of
    // function pointers.
    compareFunctionPointers[COMPARE_DEFAULT] = &strcmp;
    compareFunctionPointers[COMPARE_FOLDED] = &strcmpFold;
    compareFunctionPointers[COMPARE_NUMERICLY] = &numcmp;

    int numberOfLines;
    int sortDecreasing  = 0; // 1 if the input is to be sorted in a decreasing order
    int compareFunction = COMPARE_DEFAULT; // Index for the compare-function
    // Parse the command line arguments
    if (argc > 1) {
        for (int i = 1; *(argv + i); i++) {
            char *c = *(argv + i);
            if(strcmp(c, "-n") == 0) 
                compareFunction = COMPARE_NUMERICLY;
            if(strcmp(c, "-r") == 0) 
                sortDecreseingly = 1;
            if(strcmp(c, "-f"))
                compareFunction = COMPARE_FOLDED;


        }
    }

    if ((numberOfLines = readLines(pointersToLines, MAX_NO_OF_LINES)) >= 0) {
        qsort1((void **)pointersToLines, 0, numberOfLines - 1,
           (int (*)(void *, void *))compareFunctionPointers[compareFunction],
            sortDecreasing);

        writeLines(pointersToLines, numberOfLines);
        return 0;
    }
}

Sorting Function

void qsort1(void *v[], int left, int right, int (*comp)(void *, void *),
           int increesingOrDecresing) {
    int last, compare;
    //Base case 
    if (left >= right) {
    return;
    }

    swap(v, left, (right + left) / 2);
    last = left;
    for (int i = left + 1; i <= right; i++) {
        compare = (increesingOrDecresing) ? -(*comp)(v[i], v[left])
                                    : (*comp)(v[i], v[left]);
    if (compare < 0)
        swap(v, ++last, i);
    }
    swap(v, last, left);
    qsort1(v, left, last - 1, comp, increesingOrDecresing);
    qsort1(v, last + 1, right, comp, increesingOrDecresing);
}

Compare functions

int strcmpFold(char *s1, char *s2) {
    while (toupper(*s1) == toupper(*s2)) {
        s1++;
        s2++;
    }
    if (toupper(*s1) < toupper(*s2))
        return -1;
    else if (toupper(*s1) > toupper(*s2))
        return 1;
    else
        return 0;
}

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;
}
\$\endgroup\$
3
  • \$\begingroup\$ I left them out since i did not really find them that important. Just simple compare functions similar to strcmp \$\endgroup\$
    – svs
    Jul 19, 2018 at 18:07
  • 1
    \$\begingroup\$ Maybe you don't find them importat but other people need them to be able to understand your code so please add them. \$\endgroup\$
    – t3chb0t
    Jul 19, 2018 at 19:12
  • 1
    \$\begingroup\$ Point taken! Added them. \$\endgroup\$
    – svs
    Jul 19, 2018 at 19:52

2 Answers 2

1
\$\begingroup\$

Unless you really want the exercise of writing your own sort function, I'd argue that it's better to use the Standard Library qsort().

The way to make it sort in either ascending or descending order is to add extra comparison functions. They can all follow the same pattern (they are adapters), like this:

// ascending order

int compare_strings(const void *v1, const void *v2)
{
    const char *s1 = *(const char**)v1;
    const char *s2 = *(const char**)v2;
    return strcmp(s1, s2);
}
int compare_strings_ci(const void *v1, const void *v2)
{
    const unsigned char *s1 = *(const unsigned char**)v1;
    const unsigned char *s2 = *(const unsigned char**)v2;
    while (toupper(*s1) == toupper(*s2) && *s1) {
        s1++;
        s2++;
    }

    return toupper(*s1) - toupper(*s2);
}

int compare_numeric(const void *v1, const void *v2)
{
    double v1 = atof(*(const char**)v1);
    double v2 = atof(*(const char**)v2);

    return (v1 > v2) - (v2 < v1);
}

// descending order

int compare_strings_desc(const void *v1, const void *v2)
{
    return compare_strings(v2, v1);
}


int compare_strings_ci_desc(const void *v1, const void *v2)
{
    return strcmpFold(v2, v1);
}

int compare_numeric_desc(const void *v1, const void *v2)
{
    return numcmp(v2, v1);
}

I changed your names slightly, because names beginning with str are reserved for future standard functions. I also fixed the bug in your case-insensitive string compare, which would happily run off the ends of two equivalent strings.

You could then select between the two arrays of functions:

typedef int (*Comparer)(const void *v1, const void *v2);

const Comparer compare_asc[] = {
    compare_strings,
    compare_strings_ci,
    compare_numeric
};
const Comparer compare_desc[] = {
    compare_strings_desc,
    compare_strings_ci_desc,
    compare_numeric_desc
};

You can new select and use the correct function from the above arrays:

Comparer comp = (is_reverse ? compare_desc : compare_asc)[compare_type];
qsort(lines, line_count, sizeof *lines, comp);
\$\endgroup\$
2
  • \$\begingroup\$ Thank you! Your suggestions are looking great. Just one thing regarding the function which compares the two doubles. Is it not possible that it will return the wrong value when casting from double to int? Lets assume we have two numbers like 0.2 and 0.3, then the casting from double to int will make the return value 0 when it should be -1 or am I missing something? \$\endgroup\$
    – svs
    Jul 20, 2018 at 11:10
  • \$\begingroup\$ Ah yes, that's a good point, and a bug in my code. I've now fixed it (I can't remember where I first saw that subtraction-of-comparisons idiom, but it's a succinct way to get a positive, zero or negative outcome). \$\endgroup\$ Jul 20, 2018 at 11:37
1
\$\begingroup\$

I'd use a typedef for a pointer to your compare functions:

typedef int (*cmpfnc)(void *,void *);

This simplifies things and eliminates the ugly cast used in main's call to qsort1

I'd remove the & from &strcmp et. al. It is less idiomatic than strcmp. Both say "I want the address of ...". This allows the address of a function and a function pointer of the same type to be used interchangeably syntactically.

That is, you can say:

typedef int (*cmpfnc)(void *,void *);

cmpfnc myptr;

myptr = (cmpfnc) strcmp;

strcmp(x,y);
myptr(x,y);

And, they're all interchangeable. Also, note that (*myptr)(x,y) is simplified.

If you compile with [more] warning (e.g. -Wall), setting compareFunctionPointers needs a cast for strcmp. Using strcmp directly here is a slight blemish (because its signature uses const char * instead of void *, but it works in practice with the cast.

You could wrap strcmp with a wrapper function: int mystrcmp(void *left,void *right) { return strcmp(left,right); } as an alternative to using the cast. This would allow the compiler to do more type checking. But, using strcmp directly would probably run faster.

For most of your functions, you're breaking type safety of the arguments, so you have to be careful when doing that to be sure that things match up when the program runs.

Side note: You use sortDecreasing in main, but rename it in qsort1. Note that the the name in main is much more descriptive of its meaning. Also, you could replace the value with 1 or -1 and simplify qsort1 with a multiply (see my cleaned up code below).


Here is your code annotated with what I think could be cleaned up a bit [Note that it's based on the code in your original post, so I had to guess about some missing functions]:

#include <string.h>

#define MAX_NO_OF_LINES     100

// NOTE/BUG: this should be a typedef
int (*compareFunctionPointers[3]) (void *, void *);

void
swap(void **v,int left,int right)
{
    void *tmp;

    tmp = v[left];
    v[left] = v[right];
    v[right] = tmp;
}

int
numcmp(void *left,void *right)
{
    return *(int *) right - *(int *) left;
}

// NOTE/BUG: this should use a typedef
void
qsort1(void *v[], int left, int right, int (*comp) (void *, void *), int increesingOrDecresing)
{
    int last,
     compare;

    // Base case
    if (left >= right) {
        return;
    }

    swap(v, left, (right + left) / 2);
    last = left;
    for (int i = left + 1; i <= right; i++) {
        compare = (increesingOrDecresing) ? -(*comp) (v[i], v[left])
            : (*comp) (v[i], v[left]);
        if (compare < 0)
            swap(v, ++last, i);
    }
    swap(v, last, left);
    qsort1(v, left, last - 1, comp, increesingOrDecresing);
    qsort1(v, last + 1, right, comp, increesingOrDecresing);
}

enum {
    COMPARE_DEFAULT,
    COMPARE_FOLDED,
    COMPARE_NUMERICLY
};

char *pointersToLines[MAX_NO_OF_LINES];

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

    // Store pointers to the diffrent types of
    // compare functions in a array of
    // function pointers.
    // NOTE/BUG: these require a cast
    // NOTE/BUG: leave off the "&" as it is more idiomatic
    compareFunctionPointers[COMPARE_DEFAULT] = &strcmp;
#if 0
    compareFunctionPointers[COMPARE_FOLDED] = &strcmpFold;
#else
    compareFunctionPointers[COMPARE_FOLDED] = &strcasecmp;
#endif
    compareFunctionPointers[COMPARE_NUMERICLY] = &numcmp;

    int numberOfLines;
    int sortDecreasing = 0;             // 1 if the input is to be sorted in a decreasing order
    int compareFunction = COMPARE_DEFAULT;  // Index for the compare-function

    // Parse the command line arguments
    if (argc > 1) {
        for (int i = 1; *(argv + i); i++) {
            char *c = *(argv + i);

            if (strcmp(c, "-n") == 0)
                compareFunction = COMPARE_NUMERICLY;
            if (strcmp(c, "-r") == 0)
                sortDecreasing = 1;
            if (strcmp(c, "-f"))
                compareFunction = COMPARE_FOLDED;

        }
    }

#if 0
    if ((numberOfLines = readLines(pointersToLines, MAX_NO_OF_LINES)) >= 0) {
#endif

    // NOTE/BUG: too much casting, particularly on compareFunctionPointers
        qsort1((void **) pointersToLines, 0, numberOfLines - 1, (int (*)(void *, void *)) compareFunctionPointers[compareFunction], sortDecreasing);

#if 0
        writeLines(pointersToLines, numberOfLines);
    }
#endif

    return 0;
}

Here is a more cleaned up version incorporating the ideas I've expressed above:

#include <string.h>

#define MAX_NO_OF_LINES     100

typedef int (*cmpfnc)(void *,void *);

cmpfnc compareFunctionPointers[3];

void
swap(void **v,int left,int right)
{
    void *tmp;

    tmp = v[left];
    v[left] = v[right];
    v[right] = tmp;
}

int
numcmp(void *left,void *right)
{
    return *(int *) right - *(int *) left;
}

void
qsort1(void *v[], int left, int right, cmpfnc comp, int sortdir)
{
    int last,
     compare;

    // Base case
    if (left >= right) {
        return;
    }

    swap(v, left, (right + left) / 2);
    last = left;
    for (int i = left + 1; i <= right; i++) {
        compare = sortdir * comp(v[i], v[left]);
        if (compare < 0)
            swap(v, ++last, i);
    }
    swap(v, last, left);
    qsort1(v, left, last - 1, comp, sortdir);
    qsort1(v, last + 1, right, comp, sortdir);
}

enum {
    COMPARE_DEFAULT,
    COMPARE_FOLDED,
    COMPARE_NUMERICLY
};

char *pointersToLines[MAX_NO_OF_LINES];

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

    // Store pointers to the diffrent types of
    // compare functions in a array of
    // function pointers.
    compareFunctionPointers[COMPARE_DEFAULT] = (cmpfnc) strcmp;
    compareFunctionPointers[COMPARE_FOLDED] = (cmpfnc) strcasecmp;
    compareFunctionPointers[COMPARE_NUMERICLY] = numcmp;

    int numberOfLines;
    int sortDecreasing = 1;             // 1=increasing, -1=decreasing
    int compareFunction = COMPARE_DEFAULT;  // Index for the compare-function

    // Parse the command line arguments
    if (argc > 1) {
        for (int i = 1; *(argv + i); i++) {
            char *c = *(argv + i);

            if (strcmp(c, "-n") == 0)
                compareFunction = COMPARE_NUMERICLY;
            if (strcmp(c, "-r") == 0)
                sortDecreasing = -1;
            if (strcmp(c, "-f"))
                compareFunction = COMPARE_FOLDED;

        }
    }

#if 0
    if ((numberOfLines = readLines(pointersToLines, MAX_NO_OF_LINES)) >= 0) {
#endif

    // NOTE/BUG: too much casting, particularly on compareFunctionPointers
        qsort1((void **) pointersToLines, 0, numberOfLines - 1,
        compareFunctionPointers[compareFunction], sortDecreasing);

#if 0
        writeLines(pointersToLines, numberOfLines);
    }
#endif

    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.