Re: vector has segfault null dereference
On Oct 1, 8:01 pm, "Alf P. Steinbach" <al...@start.no> wrote:
* andrey....@gmail.com:
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::out_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::out_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[i] = cells[i];
dest->zeroBit[i] = zeroBit[i];
}
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[i]) != 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[i] & 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)[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)[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[i] | (u16)(1 << j)) == 0x1ff) &&
checkBit(i, 1)) {
arr[i] = 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[i] >= 1 && arr[i] <= 9)
a->set(i, arr[i]);
}
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[i] > 0x30 && str[i] <= 0x39) //'1'-'9'
arr[i] = str[i] - 0x30;
else
arr[i] = 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[i] < 10)
str[i] = arr[i] + 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