Why does this seg fault?

[Neb1000]

I have two functions that could be the cause of this but I don't know which one or how to fix it. Any help will be appreciated.
Edit: I know now that the clear function is wrong but even when I run it without using the clear function it still seg faults. Shouldn't it only have a memory leak but no seg fault without a clear function.

function:

template<typename generic>
void BST<generic>::insert(generic x)
{
	if(m_size == 0)
	{
		m_root = new BTN<generic>;
		*(m_root -> data) = x;
		m_root -> p = NULL;
		m_root -> r = NULL; 
		m_root -> l = NULL;
		m_size++;
	}
}

or other function:

template<typename generic>
void BST<generic>::clear()
{
	if(m_size > 0)
	{
		BTN<generic>* temp = m_root;
		m_root = NULL;
		delete temp;
		m_size = 0;
	}
}

BTN struct if you need it.

template<typename generic>
struct BTN
{
    BTN* p;
    BTN* l;
    BTN* r;
    generic* data;
};

BST class file:

template<typename generic>
class BST
{
  public:
    BST();
    ~BST();
    void insert(generic x);
    void remove(generic x);
    bool search(generic x) const;
    void clear();
    bool empty() const;
    unsigned int size () const;

  private:
	unsigned int m_size;
	BTN<generic>* m_root;
};

I have only tried testing by putting one item on the tree while empty. And that is when it breaks.

[jsmith]

m_root->data is not initialized when you attempt to dereference it in insert().

[Neb1000]

Example of a fix?

[filipe]

Initialize it before you try to dereference it.

[Neb1000]

So are you saying to do this?

m_root -> data = NULL;
*(m_root -> data) = x;

[filipe]

If it's null what do you expect to find when you dereference it? That's a guaranteed crash. The data pointer has to point to a valid address if you're going to access the contents of that address.

[Neb1000]

ok so

m_root -> data = x;
*(m_root -> data) = x;

Edit: This doesn't work. Could you please just show me what to put to make that work. It's my first doing it that way.

[filipe]

m_root->data = &x;

x is not a pointer. data is. You want to store the address of x in data (it seems). The & operator, in its prefix form, returns the address of its operand.

[Neb1000]

Ok it works now thanks for all the help.

[coder777]

Neb1000 wrote:

Ok it works now thanks for all the help.

Sorry, but no it doesn't.
You're assigning a pointer to a local variable that gets invalid as soon as the function 'insert' ends. You should pass a pointer to 'generic' to insert and make sure that you don't pass pointers to local variables.

[Neb1000]

Yes I just figured this out so I should pass insert a (generic* x)?

[Neb1000]

Ok I needed to do

m_root -> data = new generic;
*(m_root -> data) = x;

[coder777]

Neb1000 wrote:

Ok I needed to do

Yes, but that has two flaws:

1. You're using a pointer (dynamic object) while you really don't want to
2. This requires that 'generic' has an empty constructor (which is not always good)

You can write the following instead:

template<typename generic>
struct BTN
{
    BTN(const generic &g) : data(g) { } // Note: avoids the empty constructor of generic
    BTN* p;
    BTN* l;
    BTN* r;
    generic data; // Note: not a pointer
};

Your insert function:

template<typename generic>
void BST<generic>::insert(const generic &x) // Note: Better as const reference (no copy involved)
{
	if(m_size == 0) // Alternative: if(NULL == m_root) -> m_size can be omitted
	{
		m_root = new BTN<generic>(x); // Note: x as paramter
		// *(m_root -> data) = x;
		m_root -> p = NULL;
		m_root -> r = NULL; 
		m_root -> l = NULL;
		m_size++;
	}
}

This way the only requirement to 'generic' is the opterator == for remove() and search() (EDIT1: and operator= of course) (EDIT2: Then clear() would not leak any more)