vector has segfault null dereference

Discussion in 'C++' started by andrey.vul@gmail.com, Oct 2, 2007.

  1. Guest

    code:

    #include <iostream>
    #include <vector>
    #include <stdexcept>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <cstring>

    using namespace std;

    #ifdef _MSC_VER
    #define inline __inline
    #endif

    typedef unsigned __int8 u8;
    typedef signed __int8 s8;
    typedef unsigned __int16 u16;

    #define nullptr(T) (T *)0

    #define check_calloc(ptr, ptrname, type, n, if_fail, if_fail_msg) \
    if (ptr == nullptr(type)) {\
    cerr << "calloc could not allocate " << ptrname << " [n=" << n <<
    "], " << if_fail_msg; \
    if_fail; \
    }

    template <typename T>
    class array {
    public:
    size_t length;
    array(size_t _length) {
    data = new T[_length];
    length = _length;
    }
    T& operator[](unsigned int n) {
    if ((size_t)n >= length) {
    cerr << "Array index out of range (n=" << n << ", length=" <<
    length << "\"\n";
    throw std::eek:ut_of_range("Array index out of range");
    }
    return data[n];
    }
    T& elem(unsigned int n) {
    if ((size_t)n >= length) {
    cerr << "Array index out of range (n=" << n << ", length=" <<
    length << "\"\n";
    throw std::eek:ut_of_range("Array index out of range");
    }
    return data[n];
    }
    ~array() { delete[] data; }
    private:
    T* data;
    };

    class solver {
    public:
    solver() {
    cells = (u16 *)calloc(81, 2);
    zeroBit = (char *)calloc(11, 1);
    }
    //garbage collection
    ~solver() {
    free(cells);
    cells = (u16 *)0;
    free(zeroBit);
    zeroBit = (char *)0;
    }
    static u8 *solve(u8 *board) {
    solver *s = encode(board);
    solver *s_copy = s;
    u8 *sol = nullptr(u8);
    solution = false;
    s = s->search();
    if (solution) {
    sol = s->decode();
    delete s;
    } else
    delete s_copy;
    return sol;
    }
    protected:
    //data
    u16 *cells;
    //0th bit
    char *zeroBit;
    //is the puzzle solved
    static bool solution;
    //copy current solver
    solver *duplicate(void) {
    solver *dest = new solver();
    u8 i;
    for (i = 0; i < 81; i++) {
    dest->cells = cells;
    dest->zeroBit = zeroBit;
    }
    return dest;
    }
    //check zeroBit
    inline bool checkBit(u8 i, char bit) {
    u8 _byte = (u8)floor((i + 1) / 8.0);
    return ((zeroBit[_byte] & (1 << (i % 8))) == bit) ? true : false;
    }
    //find most constrained position
    u8 constrained(void) {
    u8 max = 0x7f;
    u8 maxp = 0x7f, i;
    u8 j, v;

    for (i = 0; i < 81; ++i) {
    if (checkBit(i, 0)) {
    v = 0;
    for (j = 0; j < 9; ++j)
    if (((1 << j) & cells) != 0)
    ++v;
    if (v >= max || max >= 0x7f) {
    max = v;
    maxp = i;
    }
    }
    }
    return maxp;
    }
    //get all available options for value val
    array<u8> *options(u16 val) {
    vector<u8> cc(0);;
    array<u8> *arr;
    u8 i;
    //find and add avialbale numbers
    for (i = 0; i < 9; ++i)
    if (((1 << i) & val) == 0)
    cc.push_back(i + 1);
    arr = new array<u8>(cc.size());
    for (i = 0; i < arr->length; i++)
    arr->elem(i) = cc;
    return arr;
    ^ segfault null dereference at this line when vc++
    does cleanup of vector before returning ^
    }
    //set value val in position pos, NOT-masking the other positions in
    the group
    void set(u8 pos, u8 val) {
    //column
    u8 x = pos % 9;
    //row
    u8 y = (u8)floor((pos * 1.0) / 9);
    //zone column, row
    u8 zx = (u8)floor((x * 1.0) / 3) * 3;
    u8 zy = (u8)floor((y * 1.0) / 3) * 3;
    //value bit
    u16 add = 1 << ((u16)val - 1);
    u8 k;
    //NOT-mask the other positions in the group
    for (k = 0; k < 9; ++k) {
    //mask column
    cells[x + k * 9] |= add;
    //mask row
    cells[k + y * 9] |= add;
    //mask zone
    cells[zx + (k % 3) + 9 * (zy + (u8)floor((k * 1.0) / 3))] |= add;
    }
    //unmask pos
    cells[pos] = 0x1ff - add;
    }
    //sanity check
    inline bool okay(void) {
    u8 i;
    for (i = 0; i < 81; ++i)
    if (((cells & 0x1ff) == 0x1ff) && checkBit(i, 0))
    return false;
    return true;
    }
    //check if solved
    inline bool solved(void) {
    u8 i;
    for (i = 0; i < 81; ++i) {
    if (checkBit(i, 0))
    return false;
    }
    return true;
    }
    //search for solutions, return pointer to solution or null pointer
    solver *search(void) {
    u8 p;
    array<u8> *l;
    u8 i;
    solver *ns;
    solver *ns_backup; //avoid memory leaks by backing up pointer
    while (okay()) {
    if (solved()) {
    solution = true;
    return this;
    }
    //start solving from most constrained position
    p = constrained();
    //no solution
    if (p < 0)
    return nullptr(solver);
    //get all the available options for cell p
    l = options(cells[p]);
    //no solution
    if (l->length < 1)
    return nullptr(solver);
    //try each option in cell p by recursing ourselves
    //(i.e., (...(ns = this) ... = this))
    for (i = 0; i < l->length; ++i) {
    //recurse
    ns = duplicate();
    ns->set(p, l->elem(i));
    ns_backup = ns; //avoid memory leaks
    ns = ns->search();
    //solution found, recurse back up
    if (ns != nullptr(solver))
    return ns;
    else //solution not found, deallocate ns using backup
    delete ns_backup;
    }
    //try first option
    set(p, l->elem(0));
    delete l;
    }
    //failed sanity check
    return nullptr(solver);
    }
    //decode bitmask solution to numerical solution
    u8 *decode(void) {
    u8 *arr = (u8 *)calloc(81, sizeof(u8));
    if (arr == nullptr(u8))
    return arr;
    u8 i;
    u8 j;
    for (i = 0; i < 81; ++i)
    for (j = 0; j < 9; ++j)
    if (((cells | (u16)(1 << j)) == 0x1ff) &&
    checkBit(i, 1)) {
    arr = j + 1;
    break;
    }
    return arr;
    }
    static solver *encode(u8 *arr) {
    solver *a = new solver();
    u8 i;
    for (i = 0; i < 81; ++i) {
    /* MAKE SURE that the number is between 1 and 9,
    inclusive so that the
    * solver does NOT mask 0 because that would break
    function isOK() and
    * hence prevent the solver from reaching a solution.
    */
    if (arr >= 1 && arr <= 9)
    a->set(i, arr);
    }
    return a;
    }
    };
    bool solver::solution;

    //pase sIng to array
    u8 *parse (const char *str) {
    u8 i;
    u8 *arr = (u8 *)calloc(81, 1);
    if (arr == nullptr(u8))
    return nullptr(u8);
    for (i = 0; i < 81; i++) {
    if (str > 0x30 && str <= 0x39) //'1'-'9'
    arr = str - 0x30;
    else
    arr = 1 << 7;
    }
    return arr;
    }
    //create sIng from array
    char *arr_str(const u8 *arr) {
    char *str = (char *)calloc(82, 1);
    u16 i;
    if (str == nullptr(char))
    return nullptr(char);
    for (i = 0; i < 81; i++)
    if (arr < 10)
    str = arr + 0x30; //1-9
    else
    str[i] = 0x3f; //?
    str[81] = '\0';
    return str;
    }

    int main(int argc, char *argv[]) {
    u8 *arr;
    u8 *sol;
    FILE *f;
    char *sIn = nullptr(char);
    switch (argc) {
    case 2:
    if (argv[1][0] < 0x31 || argv[1][0] > 0x39)
    goto from_file;
    arr = parse(argv[1]);
    check_calloc(arr, "arr", u8, 81, return 1, "exiting...
    \n");
    break;
    case 1:
    sIn = (char *)calloc(82, 1);
    check_calloc(sIn, "sIn", char, 82, return 1, "exiting...
    \n");
    cin >> sIn;
    arr = parse(sIn);
    check_calloc(arr, "arr", u8, 81, return 1, "exiting...
    \n");
    break;
    default:
    fprintf(stderr, "usage:\n\tsudoku input\n\tsudoku < input
    \n");
    return 1;
    } //switch(argc)
    goto solve;
    from_file:
    f = fopen(argv[1], "r");
    sIn = (char *)calloc(82, 1);
    check_calloc(sIn, "sIn", char, 82, return 1, "exiting...\n");
    fgets(sIn, 81, f);
    arr = parse(sIn);
    check_calloc(arr, "arr", u8, 81, return 1, "exiting...\n");
    solve:
    sol = solver::solve(arr);
    if (sol == nullptr(u8)) {
    cout << "No solution found for puzzle "
    << (argc == 2 ? argv[1] : (sIn != nullptr(char)) ?
    sIn : '\0') << endl;
    return 0;
    } else {
    cout << "Solution for puzzle " << (argc == 2 ? argv[1] : (sIn !
    = nullptr(char)) ? sIn : '\0')
    << " is " << arr_str(sol) << endl;
    return 0;
    }
    }[/i]
    , Oct 2, 2007
    #1
    1. Advertising

  2. * :
    > code:
    >
    > #include <iostream>
    > #include <vector>
    > #include <stdexcept>
    > #include <cstdio>
    > #include <cstdlib>
    > #include <cmath>
    > #include <cstring>
    >
    > using namespace std;
    >
    > #ifdef _MSC_VER
    > #define inline __inline
    > #endif
    >
    > typedef unsigned __int8 u8;
    > typedef signed __int8 s8;
    > typedef unsigned __int16 u16;
    >
    > #define nullptr(T) (T *)0
    >
    > #define check_calloc(ptr, ptrname, type, n, if_fail, if_fail_msg) \
    > if (ptr == nullptr(type)) {\
    > cerr << "calloc could not allocate " << ptrname << " [n=" << n <<
    > "], " << if_fail_msg; \
    > if_fail; \
    > }
    >
    > template <typename T>
    > class array {
    > public:
    > size_t length;
    > array(size_t _length) {
    > data = new T[_length];
    > length = _length;
    > }
    > T& operator[](unsigned int n) {
    > if ((size_t)n >= length) {
    > cerr << "Array index out of range (n=" << n << ", length=" <<
    > length << "\"\n";
    > throw std::eek:ut_of_range("Array index out of range");
    > }
    > return data[n];
    > }
    > T& elem(unsigned int n) {
    > if ((size_t)n >= length) {
    > cerr << "Array index out of range (n=" << n << ", length=" <<
    > length << "\"\n";
    > throw std::eek:ut_of_range("Array index out of range");
    > }
    > return data[n];
    > }
    > ~array() { delete[] data; }
    > private:
    > T* data;

    };

    The lack of a copy constructor and copy assignment operator will cause
    bad things to happen. The lack of a swap operation will cause
    inefficiency. Implement swap and copy constructor, and implement copy
    assignment in terms of copy construction and swap, OR restrict the class
    to dynamic allocation only.

    This is known as the "rule of three".

    Btw., why don't you just use std::vector?


    Cheers, & hth.,

    - Alf


    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Oct 2, 2007
    #2
    1. Advertising

  3. Guest

    On Oct 1, 8:01 pm, "Alf P. Steinbach" <> wrote:
    > * :
    >
    >
    >
    > > code:

    >
    > > #include <iostream>
    > > #include <vector>
    > > #include <stdexcept>
    > > #include <cstdio>
    > > #include <cstdlib>
    > > #include <cmath>
    > > #include <cstring>

    >
    > > using namespace std;

    >
    > > #ifdef _MSC_VER
    > > #define inline __inline
    > > #endif

    >
    > > typedef unsigned __int8 u8;
    > > typedef signed __int8 s8;
    > > typedef unsigned __int16 u16;

    >
    > > #define nullptr(T) (T *)0

    >
    > > #define check_calloc(ptr, ptrname, type, n, if_fail, if_fail_msg) \
    > > if (ptr == nullptr(type)) {\
    > > cerr << "calloc could not allocate " << ptrname << " [n=" << n <<
    > > "], " << if_fail_msg; \
    > > if_fail; \
    > > }

    >
    > > template <typename T>
    > > class array {
    > > public:
    > > size_t length;
    > > array(size_t _length) {
    > > data = new T[_length];
    > > length = _length;
    > > }
    > > T& operator[](unsigned int n) {
    > > if ((size_t)n >= length) {
    > > cerr << "Array index out of range (n=" << n << ", length=" <<
    > > length << "\"\n";
    > > throw std::eek:ut_of_range("Array index out of range");
    > > }
    > > return data[n];
    > > }
    > > T& elem(unsigned int n) {
    > > if ((size_t)n >= length) {
    > > cerr << "Array index out of range (n=" << n << ", length=" <<
    > > length << "\"\n";
    > > throw std::eek:ut_of_range("Array index out of range");
    > > }
    > > return data[n];
    > > }
    > > ~array() { delete[] data; }
    > > private:
    > > T* data;

    > };
    >
    > The lack of a copy constructor and copy assignment operator will cause
    > bad things to happen. The lack of a swap operation will cause
    > inefficiency. Implement swap and copy constructor, and implement copy
    > assignment in terms of copy construction and swap, OR restrict the class
    > to dynamic allocation only.
    >
    > This is known as the "rule of three".
    >
    > Btw., why don't you just use std::vector?
    >
    > Cheers, & hth.,
    >
    > - Alf
    >
    > --
    > A: Because it messes up the order in which people normally read text.
    > Q: Why is it such a bad thing?
    > A: Top-posting.
    > Q: What is the most annoying thing on usenet and in e-mail?


    modified code:
    #include <iostream>
    #include <vector>
    #include <stdexcept>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <cstring>

    using namespace std;

    #ifdef _MSC_VER
    #define inline __inline
    #endif

    typedef unsigned __int8 u8;
    typedef unsigned __int16 u16;

    #define nullptr(T) (T *)0

    #define check_calloc(ptr, ptrname, type, n, if_fail, if_fail_msg) \
    if (ptr == nullptr(type)) {\
    cerr << "calloc could not allocate " << ptrname << " [n=" << n
    << "], " << if_fail_msg; \
    if_fail; \
    }

    class solver {
    public:
    solver() {
    cells = (u16 *)calloc(81, 2);
    zeroBit = (char *)calloc(11, 1);
    }
    //garbage collection
    ~solver() {
    free(cells);
    cells = (u16 *)0;
    free(zeroBit);
    zeroBit = (char *)0;
    }
    static u8 *solve(u8 *board) {
    solver *s = encode(board);
    solver *s_copy = s;
    u8 *sol = nullptr(u8);
    solution = false;
    s = s->search();
    if (solution) {
    sol = s->decode();
    delete s;
    } else
    delete s_copy;
    return sol;
    }
    protected:
    //data
    u16 *cells;
    //0th bit
    char *zeroBit;
    //is the puzzle solved
    static bool solution;
    //copy current solver
    solver *duplicate(void) {
    solver *dest = new solver();
    u8 i;
    for (i = 0; i < 81; i++) {
    dest->cells = cells;
    dest->zeroBit = zeroBit;
    }
    return dest;
    }
    //check zeroBit
    inline bool checkBit(u8 i, char bit) {
    u8 _byte = (u8)floor((i + 1) / 8.0);
    return ((zeroBit[_byte] & (1 << (i % 8))) == bit) ? true :
    false;
    }
    //find most constrained position
    u8 constrained(void) {
    u8 max = 0x7f;
    u8 maxp = 0x7f, i;
    u8 j, v;

    for (i = 0; i < 81; ++i) {
    if (checkBit(i, 0)) {
    v = 0;
    for (j = 0; j < 9; ++j)
    if (((1 << j) & cells) != 0)
    ++v;
    if (v >= max || max >= 0x7f) {
    max = v;
    maxp = i;
    }
    }
    }
    return maxp;
    }
    //get all available options for value val
    vector<u8> *options(u16 val) {
    vector<u8> *cc = new vector<u8>();
    ^^^ null pointer here trying to allocate a vector ^^^
    u8 i;
    //find and add avialbale numbers
    for (i = 0; i < 9; ++i)
    if (((1 << i) & val) == 0)
    cc->push_back(i + 1);
    return cc;
    }
    //set value val in position pos, NOT-masking the other positions
    in the group
    void set(u8 pos, u8 val) {
    //column
    u8 x = pos % 9;
    //row
    u8 y = (u8)floor((pos * 1.0) / 9);
    //zone column, row
    u8 zx = (u8)floor((x * 1.0) / 3) * 3;
    u8 zy = (u8)floor((y * 1.0) / 3) * 3;
    //value bit
    u16 add = 1 << ((u16)val - 1);
    u8 k;
    //NOT-mask the other positions in the group
    for (k = 0; k < 9; ++k) {
    //mask column
    cells[x + k * 9] |= add;
    //mask row
    cells[k + y * 9] |= add;
    //mask zone
    cells[zx + (k % 3) + 9 * (zy + (u8)floor((k * 1.0) / 3))] |
    = add;
    }
    //unmask pos
    cells[pos] = 0x1ff - add;
    }
    //sanity check
    inline bool okay(void) {
    u8 i;
    for (i = 0; i < 81; ++i)
    if (((cells & 0x1ff) == 0x1ff) && checkBit(i, 0))
    return false;
    return true;
    }
    //check if solved
    inline bool solved(void) {
    u8 i;
    for (i = 0; i < 81; ++i) {
    if (checkBit(i, 0))
    return false;
    }
    return true;
    }
    //search for solutions, return pointer to solution or null pointer
    solver *search(void) {
    u8 p;
    vector<u8> *l;
    u8 i;
    solver *ns;
    solver *ns_backup; //avoid memory leaks by backing up pointer
    while (okay()) {
    if (solved()) {
    solution = true;
    return this;
    }
    //start solving from most constrained position
    p = constrained();
    //no solution
    if (p < 0)
    return nullptr(solver);
    //get all the available options for cell p
    l = options(cells[p]);
    //no solution
    if (l->size() < 1)
    return nullptr(solver);
    //try each option in cell p by recursing ourselves
    //(i.e., (...(ns = this) ... = this))
    for (i = 0; i < l->size(); ++i) {
    //recurse
    ns = duplicate();
    ns->set(p, (*l));
    ns_backup = ns; //avoid memory leaks
    ns = ns->search();
    //solution found, recurse back up
    if (ns != nullptr(solver))
    return ns;
    else //solution not found, deallocate ns using backup
    delete ns_backup;
    }
    //try first option
    set(p, (*l)[0]);
    delete l;
    }
    //failed sanity check
    return nullptr(solver);
    }
    //decode bitmask solution to numerical solution
    u8 *decode(void) {
    u8 *arr = (u8 *)calloc(81, sizeof(u8));
    if (arr == nullptr(u8))
    return arr;
    u8 i;
    u8 j;
    for (i = 0; i < 81; ++i)
    for (j = 0; j < 9; ++j)
    if (((cells | (u16)(1 << j)) == 0x1ff) &&
    checkBit(i, 1)) {
    arr = j + 1;
    break;
    }
    return arr;
    }
    static solver *encode(u8 *arr) {
    solver *a = new solver();
    u8 i;
    for (i = 0; i < 81; ++i) {
    /* MAKE SURE that the number is between 1 and 9,
    inclusive so that the
    * solver does NOT mask 0 because that would break
    function isOK() and
    * hence prevent the solver from reaching a solution.
    */
    if (arr >= 1 && arr <= 9)
    a->set(i, arr);
    }
    return a;
    }
    };
    bool solver::solution;

    //pase sIng to array
    u8 *parse (const char *str) {
    u8 i;
    u8 *arr = (u8 *)calloc(81, 1);
    if (arr == nullptr(u8))
    return nullptr(u8);
    for (i = 0; i < 81; i++) {
    if (str > 0x30 && str <= 0x39) //'1'-'9'
    arr = str - 0x30;
    else
    arr = 1 << 7;
    }
    return arr;
    }
    //create sIng from array
    char *arr_str(const u8 *arr) {
    char *str = (char *)calloc(82, 1);
    u16 i;
    if (str == nullptr(char))
    return nullptr(char);
    for (i = 0; i < 81; i++)
    if (arr < 10)
    str = arr + 0x30; //1-9
    else
    str[i] = 0x3f; //?
    str[81] = '\0';
    return str;
    }

    int main(int argc, char *argv[]) {
    u8 *arr;
    u8 *sol;
    FILE *f;
    char *sIn = nullptr(char);
    switch (argc) {
    case 2:
    if (argv[1][0] < 0x31 || argv[1][0] > 0x39)
    goto from_file;
    arr = parse(argv[1]);
    check_calloc(arr, "arr", u8, 81, return 1, "exiting...
    \n");
    break;
    case 1:
    sIn = (char *)calloc(82, 1);
    check_calloc(sIn, "sIn", char, 82, return 1, "exiting...
    \n");
    cin >> sIn;
    arr = parse(sIn);
    check_calloc(arr, "arr", u8, 81, return 1, "exiting...
    \n");
    break;
    default:
    fprintf(stderr, "usage:\n\tsudoku input\n\tsudoku < input
    \n");
    return 1;
    } //switch(argc)
    goto solve;
    from_file:
    f = fopen(argv[1], "r");
    sIn = (char *)calloc(82, 1);
    check_calloc(sIn, "sIn", char, 82, return 1, "exiting...\n");
    fgets(sIn, 81, f);
    arr = parse(sIn);
    check_calloc(arr, "arr", u8, 81, return 1, "exiting...\n");
    solve:
    sol = solver::solve(arr);
    if (sol == nullptr(u8)) {
    cout << "No solution found for puzzle "
    << (argc == 2 ? argv[1] : (sIn != nullptr(char)) ?
    sIn : '\0') << endl;
    return 0;
    } else {
    cout << "Solution for puzzle " << (argc == 2 ? argv[1] : (sIn !
    = nullptr(char)) ? sIn : '\0')
    << " is " << arr_str(sol) << endl;
    return 0;
    }
    }

    to make things simpler, I am using std::vector[/i]
    , Oct 2, 2007
    #3
  4. Guest

    On Oct 1, 9:31 pm, wrote:
    > On Oct 1, 8:01 pm, "Alf P. Steinbach" <> wrote:
    >
    >
    >
    >...
    > //get all available options for value val
    > vector<u8> *options(u16 val) {
    > vector<u8> *cc = new vector<u8>();

    According to my debugging, ^this^ line is throwing std::bad_alloc due
    to a null pointer being returned from malloc. What is weird is that I
    am allocating only 1 vector and I have 1 GB of ram so why is malloc
    returning null?
    Call trace:
    [OS-dependent stuff]
    C++ library!malloc()
    C++ library!operator new()
    sudoku![std::vector allocate]
    sudoku!std::vector::insert
    sudoku!std::vector::push_back
    sudoku!solver::eek:ptions
    ....
    sudoku!main
    ....

    > u8 i;
    > //find and add avialbale numbers
    > for (i = 0; i < 9; ++i)
    > if (((1 << i) & val) == 0)
    > cc->push_back(i + 1);
    > return cc;
    > }
    > ...
    , Oct 2, 2007
    #4
  5. * :
    > On Oct 1, 9:31 pm, wrote:
    >> On Oct 1, 8:01 pm, "Alf P. Steinbach" <> wrote:
    >>
    >>
    >>
    >> ...
    >> //get all available options for value val
    >> vector<u8> *options(u16 val) {
    >> vector<u8> *cc = new vector<u8>();

    > According to my debugging, ^this^ line is throwing std::bad_alloc due
    > to a null pointer being returned from malloc. What is weird is that I
    > am allocating only 1 vector and I have 1 GB of ram so why is malloc
    > returning null?
    > Call trace:
    > [OS-dependent stuff]
    > C++ library!malloc()
    > C++ library!operator new()
    > sudoku![std::vector allocate]
    > sudoku!std::vector::insert
    > sudoku!std::vector::push_back
    > sudoku!solver::eek:ptions
    > ...
    > sudoku!main
    > ...
    >
    >> u8 i;
    >> //find and add avialbale numbers
    >> for (i = 0; i < 9; ++i)
    >> if (((1 << i) & val) == 0)
    >> cc->push_back(i + 1);
    >> return cc;
    >> }
    >> ...

    >


    You have an infinite recursion in your search() function.

    But the code has many other problems.

    I suggest you start instead with removing all gotos, all raw arrays, all
    calls to calloc and malloc and so on. One way to do that, which is what
    I would prefer, is to copy your existing code to a backup (to look at),
    than delete all contents of your file and start from scratch with an
    empty main(). Remember to give yourself an electric shock every time
    you even /think/ about reaching for goto or raw array or the like... :)

    Cheers, & hth.,

    - Alf


    PS: Please don't quote signatures.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Oct 2, 2007
    #5
  6. Guest

    On Oct 1, 11:49 pm, "Alf P. Steinbach" <> wrote:
    > * :
    >
    >
    >
    >
    >
    > > On Oct 1, 9:31 pm, wrote:
    > >> On Oct 1, 8:01 pm, "Alf P. Steinbach" <> wrote:

    >
    > >> ...
    > >> //get all available options for value val
    > >> vector<u8> *options(u16 val) {
    > >> vector<u8> *cc = new vector<u8>();

    > > According to my debugging, ^this^ line is throwing std::bad_alloc due
    > > to a null pointer being returned from malloc. What is weird is that I
    > > am allocating only 1 vector and I have 1 GB of ram so why is malloc
    > > returning null?
    > > Call trace:
    > > [OS-dependent stuff]
    > > C++ library!malloc()
    > > C++ library!operator new()
    > > sudoku![std::vector allocate]
    > > sudoku!std::vector::insert
    > > sudoku!std::vector::push_back
    > > sudoku!solver::eek:ptions
    > > ...
    > > sudoku!main
    > > ...

    >
    > >> u8 i;
    > >> //find and add avialbale numbers
    > >> for (i = 0; i < 9; ++i)
    > >> if (((1 << i) & val) == 0)
    > >> cc->push_back(i + 1);
    > >> return cc;
    > >> }
    > >> ...

    >
    > You have an infinite recursion in your search() function.
    >
    > But the code has many other problems.
    >
    > I suggest you start instead with removing all gotos, all raw arrays, all
    > calls to calloc and malloc and so on. One way to do that, which is what
    > I would prefer, is to copy your existing code to a backup (to look at),
    > than delete all contents of your file and start from scratch with an
    > empty main(). Remember to give yourself an electric shock every time
    > you even /think/ about reaching for goto or raw array or the like... :)


    The same thing happened when I tried to optimize my java code. How did
    you catch the infinite recursion and do you know of a free static code
    analyzer that can find infinite recursion?
    Also, the java code used a raw array just fine.
    , Oct 2, 2007
    #6
  7. * :
    > On Oct 1, 11:49 pm, "Alf P. Steinbach" <> wrote:
    >> * :
    >>> On Oct 1, 9:31 pm, wrote:
    >>>> On Oct 1, 8:01 pm, "Alf P. Steinbach" <> wrote:
    >>>> ...
    >>>> //get all available options for value val
    >>>> vector<u8> *options(u16 val) {
    >>>> vector<u8> *cc = new vector<u8>();
    >>> According to my debugging, ^this^ line is throwing std::bad_alloc due
    >>> to a null pointer being returned from malloc. What is weird is that I
    >>> am allocating only 1 vector and I have 1 GB of ram so why is malloc
    >>> returning null?
    >>> Call trace:
    >>> [OS-dependent stuff]
    >>> C++ library!malloc()
    >>> C++ library!operator new()
    >>> sudoku![std::vector allocate]
    >>> sudoku!std::vector::insert
    >>> sudoku!std::vector::push_back
    >>> sudoku!solver::eek:ptions
    >>> ...
    >>> sudoku!main
    >>> ...
    >>>> u8 i;
    >>>> //find and add avialbale numbers
    >>>> for (i = 0; i < 9; ++i)
    >>>> if (((1 << i) & val) == 0)
    >>>> cc->push_back(i + 1);
    >>>> return cc;
    >>>> }
    >>>> ...

    >> You have an infinite recursion in your search() function.
    >>
    >> But the code has many other problems.
    >>
    >> I suggest you start instead with removing all gotos, all raw arrays, all
    >> calls to calloc and malloc and so on. One way to do that, which is what
    >> I would prefer, is to copy your existing code to a backup (to look at),
    >> than delete all contents of your file and start from scratch with an
    >> empty main(). Remember to give yourself an electric shock every time
    >> you even /think/ about reaching for goto or raw array or the like... :)

    >
    > The same thing happened when I tried to optimize my java code.


    Well, C++ may be a powerful language, but translating from Java to C++
    does not automatically fix algorithmic problems.


    > How did
    > you catch the infinite recursion and



    An old dog may not have as keen a sense of smell, nor as acute hearing,
    as a younger dog. But the older dog has some experience that largely
    weights up for that (younger dogs generally refuse to believe that
    unless the older dog keeps them well in line, biting them a little when
    they get too focused on following their own dangerous whims, and this is
    a problem for the older dogs believing in freedom and creativity). On
    the other hand, it's difficult to teach an old dog to stop barking.


    > do you know of a free static code
    > analyzer that can find infinite recursion?


    A good compiler can detect obvious infinite recursion. Less obvious
    infinite recursion is in principle impossible to detect. Read up on the
    halting problem.


    > Also, the java code used a raw array just fine.


    Java has no such thing as a raw array.

    Arrays in Java are dynamically type checked.


    Cheers, & hth.,

    - Alf

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Oct 3, 2007
    #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. Denis Palmeiro

    NULL Pointer Dereference

    Denis Palmeiro, Jul 8, 2003, in forum: C Programming
    Replies:
    10
    Views:
    653
    Shill
    Jul 16, 2003
  2. Replies:
    8
    Views:
    1,895
    Csaba
    Feb 18, 2006
  3. Tony Jackson

    Avoiding dereference of NULL pointer

    Tony Jackson, Dec 15, 2007, in forum: C Programming
    Replies:
    17
    Views:
    765
    Randy Howard
    Dec 29, 2007
  4. Andrey Vul
    Replies:
    8
    Views:
    673
    Richard Bos
    Jul 30, 2010
  5. Armen Tsirunyan
    Replies:
    18
    Views:
    512
    James Kanze
    Oct 5, 2010
Loading...

Share This Page