qsort - Segmentation Fault

Discussion in 'C++' started by KS, Aug 14, 2006.

  1. KS

    KS Guest

    Hello,

    I'm writing some c++ code after a few years with Java and your help is
    appreciated. I am getting a core dump on a call to qsort. Can you take
    a look at the code and see if there are any obvious errors? (The
    function main is at the bottom of the file.)

    Code: http://www.grex.org/~kpp/cmultiknapsack.cpp

    To run this file you will need http://www.grex.org/~kpp/orlib1.txt in
    the same directory.

    KS
    KS, Aug 14, 2006
    #1
    1. Advertising

  2. KS wrote:
    > I'm writing some c++ code after a few years with Java and your help is
    > appreciated. I am getting a core dump on a call to qsort. Can you take
    > a look at the code and see if there are any obvious errors? (The
    > function main is at the bottom of the file.)
    > [...]


    Please follow the recommendations in FAQ 5.8.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Aug 14, 2006
    #2
    1. Advertising

  3. KS

    KS Guest


    > Please follow the recommendations in FAQ 5.8.
    >
    > V


    Thanks. I'm using Borland C++ 5.02 on Windows and gcc on grex. Both
    report the same thing. No special compiler/linker flags are used. The
    message I get is a simple core dump (Segmentation fault). Its not
    possible to post minimal code in this case (all parts from the
    beginning to end are required for compilation and execution). The part
    that causes the segmentation fault is the call to qsort (12th line in
    main()).

    KS
    KS, Aug 14, 2006
    #3
  4. KS schrieb:
    > Hello,
    >
    > I'm writing some c++ code after a few years with Java and your help is
    > appreciated. I am getting a core dump on a call to qsort. Can you take
    > a look at the code and see if there are any obvious errors? (The
    > function main is at the bottom of the file.)
    >
    > Code: http://www.grex.org/~kpp/cmultiknapsack.cpp
    >
    > To run this file you will need http://www.grex.org/~kpp/orlib1.txt in
    > the same directory.


    http://www.parashift.com/c -faq-lite/how-to-post.html#faq-5.8

    Decide if you want to write C++ or C. Mixing the two languages utilize the
    worst of two worlds.

    For C++: Use std containers when possible and std::sort instead of qsort().
    Don't new() everything. It might be necessary in Java, but its bad practice
    in C++.

    --
    Thomas
    Thomas J. Gritzan, Aug 14, 2006
    #4
  5. KS

    Jerry Coffin Guest

    In article <>,
    says...
    >
    > Hello,
    >
    > I'm writing some c++ code after a few years with Java and your help is
    > appreciated. I am getting a core dump on a call to qsort. Can you take
    > a look at the code and see if there are any obvious errors? (The
    > function main is at the bottom of the file.)


    I haven't tried to find the specific problem you're citing in the code.
    Just at first glance, it has enough problems that I'd advise nearly a
    complete rewrite. I'll cite only a few of the most obvious problems, and
    leave it to you to clean it up enough that it's worth looking at in more
    detail.

    > /* Globals */
    > int POPULATION = 10;
    > int NUMBER_OBJECTS = 100;
    > int NUMBER_CONSTRAINTS = 5;


    Commenting that these are globals is silly -- anybody who knows enough
    to read the rest at all already knows these are globals.

    In C and C++, all-caps names are normally reserved for macros -- these
    names are misleading. Most of these probably shouldn't exist in the
    first place -- in a typical case, the number of objects, constraints,
    etc. should be detected from the input data. I'd use things like:

    const int population = 10;
    const int number_objects = 100;
    const int number_constraints = 5;

    > int generateRandomNumber(int min, int max)
    > {
    > int r;
    > double randd = ((double)rand() / ((double)(RAND_MAX)+(double)(1)));
    > r = (int) (randd * (double)(max-min+1)) + min;
    > return r;
    > }


    This manages to be both inefficient and incorrect. Personally, my
    recommendation is:

    int rand_lim(int limit) {
    int divisor = RAND_MAX/(limit+1);
    int retval;

    do {
    retval = rand() / divisor;
    } while (retval > limit);

    return retval;
    }

    int GenerateRandomNumber(int lower, int upper) {
    int range = abs(upper-lower);

    return rand_lim(range) + min(lower, upper);
    }

    This avoids floating point, and produces numbers that are evenly
    distributed within the specified range (assuming rand() produces an even
    distribution in its range).

    > class KNode
    > {
    > private:
    > int * knapsack;
    > int value;
    > int * weights;


    Members of a class are private by default so I'd skip the "private" tag.
    Looking below, knapsack apparently has a fixed size, and is only
    supposed to hold the values 0 and 1. If that's correct, I'd do something
    like this:
    typedef bitset<number_objects> knappy;

    knappy knapsack;

    You might also consider a vector<bool> as an alternative, but offhand
    the bitset looks more suitable to me. It appears that weights does hold
    actual integers, so I'd define it as:

    vector<int> weights;

    > public:
    > KNode()
    > {
    > printf("\nShould Not Call Default Constructor!");
    > }


    If you don't want this to be called, declare it private, and don't
    define it. This prevent code that attempts to use it from building at
    all instead of building and then giving an error message at runtime.

    > KNode(int * knap)
    > {
    > //printf("\nThe right constructor");
    > knapsack = new int [NUMBER_OBJECTS];
    > for(int i=0; i<NUMBER_OBJECTS; i++)
    > {
    > if(knap == 1)
    > {
    > knapsack = 1;
    > }
    > else if(knap == 0)
    > {
    > knapsack = 0;
    > }
    > else
    > {
    > printf("Invalid Knapsack passed to constructor!");
    > printf("i = %d, value = %d", i, knap);
    > exit(1);
    > }
    > }


    Using the definition of knapsack from above (i.e. as a bitset), this
    code becomes something like:

    KNode(knappy knap) : knapsack(knap) {
    calculateWeights();
    calculateValue();
    crossoverType = randomCrossover();
    }

    Your copy ctor isn't entirely clear. Do you really need to recalculate
    the weights and value in it? It appears that it can simply copy those in
    the existing one. If that's so, you can simply skip defining it at all,
    as the one the compiler will produce will work fine (once you've defined
    knapsack and weights properly). Likewise with operator=; in fact, the
    one you have right now almost certainly does NOT do what you want -- it
    does a shallow copy, so you end up with two objects pointing to the same
    knapsack and weights rather than having two independent copies of those.
    Right now, KNodes also leak memory -- you don't have a ctor for KNode,
    so the memory it allocates in its ctor is never freed. Fortunately, when
    you redefine its pointer members as container types, you no longer have
    to worry about that.

    > KNode * mutate(KNode * node, double prob)
    > {
    > printf("Inside mutator\n");
    > int * knapsack = node->getKnapsack();
    > int * kk = new int[NUMBER_OBJECTS];
    > for(int i=0; i<NUMBER_OBJECTS; i++)
    > {
    > double rand = generateDoubleRandomNumber();
    > if(rand < prob)
    > {
    > // invert
    > if(knapsack == 1)
    > {
    > kk=0;
    > }
    > else if(knapsack == 0)
    > {
    > kk=1;
    > }
    > else
    > {
    > printf("%d\n\n", knapsack);
    > printf("Invalid Knapsack");
    > exit(1);
    > }
    > }
    > }
    >
    > KNode * nd = new KNode(kk);
    > return nd;
    >}


    Using the prior definitions, this becomes something like:

    KNode mutate(Knode const &node, double prob) {
    knappy kk(node.knapsack);

    for (int i=0; i<node.knapsack.size(); i++) {
    double random = ;
    if (generateDoubleRandomNumber() < prob)
    kk.flip(i);
    }
    return KNode(kk);
    }

    I'd also consider re-defining this in general though -- 'mutate' sounds
    like a verb -- i.e. that when you do something like "mutate(x)' it
    should change the value of 'x'. Given what it really does, create_mutant
    or something like that would probably be a better name.

    I'll stop here with the specifics, and instead add a few general
    comments: your code shows your Java background quite clearly -- in fact,
    even if a C++ compiler will accept what you write, what you have is
    still really more Java than C++.

    My advice would be to treat the 'new' keyword as strictly forbidden, at
    least for a while, until you're most accustomed to how C++ works. Right
    now, you're using dynamic allocation when it's unnecessary, and leaking
    memory all over everywhere. These problems should mostly evaporate if
    you start to use containers from the standard library. Along with those,
    you should look into using some of the standard algorithms -- for
    example, you have a number of loops that could be replaced with
    algorithsm such as std::accumulate.

    Getting back to your original question, the problem is almost certainly
    related to your (mis-)management of memory. My immediate advice would be
    to ignore the existence of qsort, and use std::sort instead. With
    careful use, qsort undoubtedly CAN do what you need -- but std::sort
    will almost certainly do it more easily, and as a minor bonus, will
    probably run quite a bit faster as well.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Aug 14, 2006
    #5
  6. KS

    Jerry Coffin Guest

    In article <>,
    says...

    [ a couple of errors in editing...]

    > Right now, KNodes also leak memory -- you don't have a ctor for KNode,


    That should be 'dtor' rather than ctor.

    [ ... ]

    > KNode mutate(Knode const &node, double prob) {
    > knappy kk(node.knapsack);
    >
    > for (int i=0; i<node.knapsack.size(); i++) {
    > double random = ;


    And this line shouldn't be there at all. There's also no real need to
    use node.knapsack.size here -- kk.size works fine:

    KNode mutate(Knode const &node, double prob) {
    knappy kk(node.knapsack);

    for (int i=0; i<kk.size(); i++)
    if (generateDoubleRandomNumber() < prob)
    kk.flip(i);
    return KNode(kk);
    }

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Aug 14, 2006
    #6
  7. KS

    KS Guest


    > Getting back to your original question, the problem is almost certainly
    > related to your (mis-)management of memory. My immediate advice would be
    > to ignore the existence of qsort, and use std::sort instead. With
    > careful use, qsort undoubtedly CAN do what you need -- but std::sort
    > will almost certainly do it more easily, and as a minor bonus, will
    > probably run quite a bit faster as well.
    >
    > --
    > Later,
    > Jerry.


    Thanks for the detailed critique of the code. I have now switched to
    STL (vector and std::sort()) and the original problem has been solved.
    (Now it is complaining about bad parsing, which I can handle).
    KS, Aug 15, 2006
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alex Hunsley
    Replies:
    17
    Views:
    863
  2. Pud
    Replies:
    0
    Views:
    574
  3. Replies:
    0
    Views:
    526
  4. Ivan Vecerina
    Replies:
    0
    Views:
    482
    Ivan Vecerina
    Jun 29, 2003
  5. Vasileios Zografos

    Re: segmentation fault exception handling

    Vasileios Zografos, Jun 30, 2003, in forum: C++
    Replies:
    5
    Views:
    15,594
    Pete Becker
    Jul 1, 2003
Loading...

Share This Page