c/c++ question: comparing/sorting sctructs

[Cardoso]

Hi,
I'm in the process of translating my engine to c/c++.
I need to sort an array of structs so that I can do a binary search to find an element on it.
The array is nothing more than a big opening book loaded into RAM wich needs to be sorted for binary searches to work. Also during book generation my program is processing games and adding positions to the opening book, after adding each position it needs to do an Insertion Sort to sort the array of structs.
The old compiler/programming language (PowerBasic) allowed many things like structs comparisons, pointers, mixing language statements with assembler, threads, etc.
But it will be stuck with 32bit for a very long time since the company don't have plans to produce a 64bit compiler.
So what's the current state of the art in comparing structs in c/c++?
I understand I could use memcmp, but padding bytes could be uninitialized and contain trash values so that two struct variables could be the same memberwise but different bytewise.
What about pointers? My EGTB generater wich I'm also translating to c needs to compare struct variables wich have a pointer in one of it's member.
I think in 16bit programing this could be an issue since two different pointers could point to the same adress because of the segment:offset architecture.
What about now? Is it also an issue with 32bit and 64bit pointers?

Going back to the padding bytes in struct variables issue I suppose I can force padding to 1 byte in the compiler switches. Does that means we are getting rid of padding bytes altogether?. Does that hurt too much performance?
I'ts just for opening book lookups, so...
Also the opening book is a file that is loaded into RAM, is it better to let the struct variables have padding bytes or force padding to 1 byte (if that really means no padding whatsoever)?

What about operator overloading? I know it exists but I don't know much about it. Can I overload the == > < != operators so that a comparison on struct variables is exactly the same as a comparison on strings? If so please give me an example. Please remember I'm poorly educated in c/c++


Thanks in advance,
Alvaro

[mcostalba]

Please post the struct you need to compare and tell what are the fields (if not all) on which make the comparison.

[Dann Corbit]

Don't use memcmp(). It's not portable to assume you can pack on one byte alignment. Just compare field by field.

If you are using C++ you can overload comparison operators very easily.

You might consider using a hash table which has lookups O(1). Then you do not even need to sort.

Of course, with an opening book, the time for lookup will probably not be important anyway.

Sloppy uses an AVL tree.

I would advocate using something like FastDB which will handle all the addressing stuff for you (and since it is a memory resident database there is no speed penalty for disk based lookups).
http://www.garret.ru/~knizhnik/fastdb.html

[Cardoso]

Here's the PowerBasic structure I want to handle in c.
Remeber it's a checkers engine.
The structure in question is ClassicBook_type

Code: Select all

TYPE board_type
    W AS LONG 'WPieces
    B AS LONG 'BPieces
    Q  AS LONG 'Queens
END TYPE

TYPE ClassicBook_type
    brd AS board_type
    Score AS INTEGER
    SearchDepth AS BYTE
    flags AS BYTE
END TYPE

Thanks,
Alvaro

[Dann Corbit]

Here's the PowerBasic structure I want to handle in c.
Remeber it's a checkers engine.
The structure in question is ClassicBook_type

Code: Select all

TYPE board_type
    W AS LONG 'WPieces
    B AS LONG 'BPieces
    Q  AS LONG 'Queens
END TYPE

TYPE ClassicBook_type
    brd AS board_type
    Score AS INTEGER
    SearchDepth AS BYTE
    flags AS BYTE
END TYPE

Thanks,
Alvaro

Maybe something like this:

Code: Select all

typedef struct board_type {
    long            W;          // WPieces
    long            B;          // BPieces
    long            Q;          // Queens
}   board_type;

typedef struct ClassicBook_type {
    board_type      brd;
    int             Score;
    unsigned char   SearchDepth;
    unsigned char   flags;
}   ClassicBook_type;

// Compare the boards of book elements
int compare_book_boards(const void *l, const void *r)
{
    const ClassicBook_type *left = (ClassicBook_type *) l;
    const ClassicBook_type *right = (ClassicBook_type *) r;
    return left->brd.W > right->brd.W ? 1 :
    left->brd.W < right->brd.W ? -1 &#58;
    left->brd.B > right->brd.B ? 1 &#58;
    left->brd.B < right->brd.B ? -1 &#58;
    left->brd.Q > right->brd.Q ? 1 &#58;
    left->brd.Q < right->brd.Q ? -1 &#58;
    0;
&#125;

// Compare the entire book elements
int compare_book_types&#40;const void *l, const void *r&#41;
&#123;
    const ClassicBook_type *left = &#40;ClassicBook_type *) l;
    const ClassicBook_type *right = &#40;ClassicBook_type *) r;
    return left->brd.W > right->brd.W ? 1 &#58;
    left->brd.W < right->brd.W ? -1 &#58;
    left->brd.B > right->brd.B ? 1 &#58;
    left->brd.B < right->brd.B ? -1 &#58;
    left->brd.Q > right->brd.Q ? 1 &#58;
    left->brd.Q < right->brd.Q ? -1 &#58;
    left->Score > right->Score ? 1 &#58;
    left->Score < right->Score ? -1 &#58;
    left->SearchDepth > right->SearchDepth ? 1 &#58;
    left->SearchDepth < right->SearchDepth ? -1 &#58;
    left->flags > right->flags ? 1 &#58;
    left->flags < right->flags ? -1 &#58;
    0;
&#125;

[mcostalba]

Ok. First the structs in c/c++ are traslated as:

struct Board_type {
long w;
long b;
long q;
};

struct ClassicBook_type {
Board_type brd;
int score;
unsigned char searchDepth;
unsigned char flags;
};

Ok now I consider you want compare variables of type ClassicBook_type on the Board_type (I'm guessing because you didn't told me on which fields you compare the structs).

So given to variables of type Board_type

Board_type b1, b2;

we can say b1 is greater of b2 as example if b1.w > b2.w. On the contrary b1 will be smaller then b2 if b1.w < b2.w

In case b1.w is equal to b2.w (in c/c++ you write b1.w == b2.w) then we go to check b1.b and b1.q

So our comparison function could be something like:

bool greater(const Board_type& b1, const Board_type& b2) {

if (b1.w != b2.w) return (b1.w > b2.w);
if (b1.b != b2.b) return (b1.b > b2.b);
return (b1.q > b2.q);
}

Until now the code is valid both in C and C++.

Now to overload operator > you simply need to change the name of the function 'greater' in ...guess what... operator>

So instead of greater() you can write (only in C++):

bool operator>(const Board_type& b1, const Board_type& b2) {

if (b1.w != b2.w) return (b1.w > b2.w);
if (b1.b != b2.b) return (b1.b > b2.b);
return (b1.q > b2.q);
}

And that's all !

Now you can write something like

Board_type b1, b2;

if (b1 > b2) std::cout << "operator> has been called ! " << std::endl;

Note that you cannot write expressions like

(b1 < b2)
(b1 == b2)

because you have defined only operator>(), so to be able to do other comparisons you can define also:

bool operator==(const Board_type& b1, const Board_type& b2) {

return (b1.w == b2.w) && (b1.b == b2.b) && (b1.q == b2.q);
}

bool operator!=(const Board_type& b1, const Board_type& b2) {

return !(b1 == b2);
}

bool operator<(const Board_type& b1, const Board_type& b2) {

return !(b1 > b2) && (b1 != b2);
}

And so on as you like, note that for sorting with std::sort only operator<() is required and you can sort any struct, as example to sort an array of Board_type you can write:


#include <algorithm> // where std::sort() lives

Board_type boards[100];

std::sort(boards, boards + 100);

And that's all.


Marco

[Harald]

Here's the PowerBasic structure I want to handle in c.
Remeber it's a checkers engine.
The structure in question is ClassicBook_type

Code: Select all

TYPE board_type
    W AS LONG 'WPieces
    B AS LONG 'BPieces
    Q  AS LONG 'Queens
END TYPE

TYPE ClassicBook_type
    brd AS board_type
    Score AS INTEGER
    SearchDepth AS BYTE
    flags AS BYTE
END TYPE

Thanks,
Alvaro

In the same spirit as the C example here ist some code in C++.
I changed the style a little bit to look more like C++.

Code: Select all

// In some header file

struct Board
{
    long            wPieces;
    long            bPieces;
    long            queens;
    bool operator<&#40;const Board &b&#41; const;
&#125;;

struct ClassicBook
&#123;
    Board           board;
    int             score;
    unsigned char   searchDepth;
    unsigned char   flags;
    bool operator<&#40;const ClassicBook &cb&#41; const;
&#125;;


// In some cpp file
#include ...

bool Board&#58;&#58;operator<&#40;const Board &b&#41; const
&#123;
    if &#40;wPieces < b.wPieces&#41;  return true;
    if &#40;wPieces > b.wPieces&#41;  return false;
    if &#40;bPieces < b.bPieces&#41;  return true;
    if &#40;bPieces > b.bPieces&#41;  return false;
    if &#40;queens  < b.queens&#41;   return true;
                              return false;
&#125;

bool ClassicBook&#58;&#58;operator<&#40;const ClassicBook &cb&#41; const
&#123;   // compare most important member first to get a nice linear list
    // or compare first what is most often not equal for performance
    if &#40;board < cb.board&#41;  return true;
    if &#40;cb.board < board&#41;  return false;   // no need for Board&#58;&#58;operator>()
    if &#40;score < cb.score&#41;  return true;    // do you really compare score?
    if &#40;score > cb.score&#41;  return false;
    if &#40;searchDepth < cb.searchDepth&#41;  return true;
    if &#40;searchDepth > cb.searchDepth&#41;  return false;
    if &#40;flags < cb.flags&#41;  return true;
                           return false;
&#125;

I did not compile or test it.

Harald

[Aleks Peshkov]

Do not use generic long data type in C, it will make your book non-portable between Windows and Linux, use uint32_t or uint64_t.

SQLite is a good alternative for DB approach.

[sje]

Do you have regular access to a Unix-like system?

If so, you should consider the use of the Unix "sort" utility.

1) Have your program output one structure per text line to a scratch file; use a text format that corresponds with the desired collation ordering. This would likely be the position hash code output in hexadecimal using lower case letters.

2) Run sort on this file.

3) Read in the sorted file; you need a text-to-structure decoder.

4) All done!

[trojanfoe]

As far as comparison is concerned in C/C++, this has always worked and will generate a call to the compiler's internal 'memcmp' library function:

Code: Select all

struct typex a, b;

initialise a and b;

if (a == b)
{
    do something;
}

The only reason to override the equality operator in C++ is if this comparison is meaningless, which would only be case if you store pointers to sibling, parent or child structs (which is fairly common).