CODEWITHSUNDEEP
c++pointerssegmentation-faultfunction-pointers
salvador p
salvador p

Reputation: 3005

Assignment of address to a pointer-to-pointer gives segmentation fault

I have a binary search tree class, BSTree. It used to have a single member, a root node for the tree. The type of a node is defined by the BSTNode struct. But then i added another member, a pointer to a function that is used to compare two elements. That's when problems started.

Interface:

template <typename T>
struct BSTNode {
public:
    struct BSTNode<T> *left;
    struct BSTNode<T> *right;
    T key;
    BSTNode<T>(T element){ key = element;}
};

template <typename T>
class BSTree {
private:
    BSTNode<T> *root;
    int (*compare)(T el1, T el2); // this is the new member
public:
BSTree<T>(int (*cmp)(T el1, T el2)) {root = NULL; compare = cmp;}
    //...

The function BSTree::add, which adds stuff to the tree, uses a pointer to the pointer to the root node. This function broke after i added the new 'compare' member. The function begins as follows (it has some printf lines i added to find the exact line that crashed):

Function Definition:

template <typename T>
BSTNode<T>* BSTree<T>::add(T element) {
    BSTNode<T> **node;
    printf("&root = %p\n", &root);
    printf("node = %p\n", node); //must be NULL
    printf("compare = %p\n", (int(*)(T, T))compare); //address stored in fn pointer
    node = &root; /////////// THIS PART produces the segmentation fault. ////////
    printf("succeeded");
    //...

Function Call (in main):

BSTree<int> bst(&stdcomp); //stdcomp is the integer compare function
bst.add(6);
//...

Output:

&root = 0x7fff5fbff8c0
node = 0x0
compare = 0x100001325
Segmentation fault

What is especially puzzling to me is that the assignment fails, even though it does not dereference the address that is stored in my pointer-to-pointer 'node', and 'node' is a local variable and is not being dereferenced; I don' know where the illegal memory access occur. I tried to initialize node to several literal values (e.g. NULL or 0x1), and they did not produce the error. It only failed after I added the function pointer to the class, which according to what is printed, is assigned the correct address. Does it have anything to do with misuse of templates?

By the way, the BSTree template is instantiated with typenames int and const char*, each with a different compare function that is correctly assigned (I think). I tested their add function and both produced the fault.

Upvotes: 0

Views: 810

Answers (2)

Chris Dodd
Chris Dodd

Reputation: 126203

Your segmentation fault is proabably happening AFTER the printf("succeeded"); call, as that printf doesn't include a newline, and your output is probably in line-buffered mode. So the string 'succeeded' is going into the stdout buffer but doesn't appear on the screen. Either put stdout into unbuffered mode, or stick a \n in the string. Or better yet, stick fflush(stdout); after each printf so the buffer gets flushed regardless of the stdout buffering mode.

Upvotes: 1

jpalecek
jpalecek

Reputation: 47762

printf("compare = %p\n", (int(*)(T, T))compare);

This is undefined behavior - printf's %p expects a pointer to void, but you pass a function pointer. Function pointers are not convertible to void*.

I recommend you to run your program in a debugger, to see it's really the assignment you suspect that's causing the fault. It might be some stack-smashing etc. The assignment itself should only invoke operations referencing the stack.

Upvotes: 0

Related Questions