Multi-threaded tree template data structure

[Rakesh Kumar]

Hi All -
To clarify more about the const_cast<T &>(<volatile object
reference>) - I have attempted to write a thread-safe binary-tree
template ( called as SafeTree<T> ). The following code should
compile.
Can somebody help me with letting me know if this would be race-
free. Also please do let me know if there are possible code syntax
with undefined behavior. Thanks for the help.

#include <iostream>
#include <cstdlib>

using std::cerr;

class Mutex
{
public:
//Fill Here: Apply platform specific thread details for a mutex.
//On linux, use pthreads API
bool lock(bool blocking) volatile
{

return true;
}

bool unlock() volatile
{

return false;
}

//pthread_mutex_t mut;
};

/**
* This template snippet is taken from
* Andrei Alexandrescu's article - to avoid race conditions.
* http://www.ddj.com/cpp/184403766 .
* Any errors in the code would be mine.
**/
template<typename T> class LockingPtr
{
public:
// Constructors/destructors
LockingPtr(volatile T& _obj, volatile Mutex & mtx) :
obj(const_cast<T*>(&_obj)), mutex(&mtx)
{
mtx.lock(true);
}
~LockingPtr()
{
mutex->unlock();
}
// Pointer behavior
T& operator*()
{
return *obj;
}
T* operator->()
{
return obj;
}
private:

LockingPtr<T>(const LockingPtr<T> & rhs)
{
obj = rhs.obj;
mutex = rhs.mutex;
}

LockingPtr<T> & operator=(const LockingPtr<T> & rhs)
{
if (this != &obj)
{
obj = rhs.obj;
mutex = rhs.mutex;
}
return *this;
}

T* obj;
volatile Mutex * mutex;

};

template<typename T> class SafeTree
{
public:
SafeTree<T>(const T & _info) :
info(_info), parentnode(0), leftnode(0), rightnode(0), temp(0)
{
}

SafeTree<T>(const T & _info, volatile SafeTree<T> * _parent) :
info(_info), parentnode(_parent), leftnode(0), rightnode(0),
temp(0)
{
}

virtual ~SafeTree<T>()
{
}

T & getInfo() volatile
{
LockingPtr<T> pObj(info, mutex);
return *pObj;
}

void setInfo(const T & _info) volatile
{
LockingPtr<T> pObj(info, mutex);
*pObj = _info;
}

void freeLeft() volatile
{
LockingPtr<int> pObj(temp, mutex);
if (leftnode)
{
delete leftnode;
leftnode = 0;
}

}

void freeRight() volatile
{
LockingPtr<int> pObj(temp, mutex);

if (rightnode)
{
delete rightnode;
rightnode = 0;
}

}

SafeTree<T> * left() volatile
{
return const_cast< SafeTree<T> *>(leftnode);
}

SafeTree<T> * right() volatile
{
return const_cast< SafeTree<T> *>(rightnode);
}

SafeTree<T> * parent() volatile
{
return const_cast< SafeTree<T> *>(parentnode);
}

SafeTree<T> * sibling() volatile
{
LockingPtr<int> pObj(temp, mutex);

if (parentnode == 0)
{
cerr << "Parent node is null. No Sibling hence";
return 0;
}
else
{
if (parentnode->leftnode == this)
{
return parentnode->right();
}
else
{
return parentnode->left();
}
}
}

bool isLeafNode() volatile
{
LockingPtr<int> pObj(temp, mutex);

return (leftnode == 0) && (rightnode == 0);
}

void insertLeft(const T & data) volatile
{
LockingPtr<int> pObj(temp, mutex);

if (leftnode == 0)
{
SafeTree<T> * newnode = new SafeTree<T>(data, this);
leftnode = newnode;
}

}

void insertRight(const T & data) volatile
{
LockingPtr<int> pObj(temp, mutex);

if (rightnode == 0)
{
SafeTree<T> * newnode = new SafeTree<T>(data, this);
rightnode = newnode;
}
}

void deleteLeft(T & obj) volatile
{
LockingPtr<int> pObj(temp, mutex);

internalDeleteChild(leftnode, obj);
leftnode = 0;
}

void deleteRight(T & obj) volatile
{
LockingPtr<int> pObj(temp, mutex);

internalDeleteChild(rightnode, obj);
rightnode = 0;
}

private:

void internalDeleteChild(SafeTree<T> * child, T & obj)
{
if (child)
{
obj = child->info;
delete child;
}
}

volatile T info;

volatile SafeTree<T> * parentnode;
volatile SafeTree<T> * leftnode;
volatile SafeTree<T> * rightnode;

volatile int temp;

Mutex mutex;
};

int main()
{
SafeTree<int> * root = new SafeTree<int>(4);
root->insertLeft(6);

return EXIT_SUCCESS;
}

[Ian Collins]

Rakesh Kumar wrote:
> Hi All -
> To clarify more about the const_cast<T &>(<volatile object
> reference>) - I have attempted to write a thread-safe binary-tree
> template ( called as SafeTree<T> ). The following code should
> compile.
> Can somebody help me with letting me know if this would be race-
> free. Also please do let me know if there are possible code syntax
> with undefined behavior. Thanks for the help.
>
> #include <iostream>
> #include <cstdlib>
>
> using std::cerr;
>
> class Mutex
> {
> public:
> //Fill Here: Apply platform specific thread details for a mutex.
> //On linux, use pthreads API
> bool lock(bool blocking) volatile

Before we go any further, why have you volatile qualified this members?

--
Ian Collins.

[Rakesh Kumar]

If the mutex happens to be a volatile instance - then it can access
only volatile functions of the same. Hence I had to make it volatile.
I am not sure if that is the correct design though - which is why I
had posted it here.

[Ian Collins]

Rakesh Kumar wrote:
> On Nov 30, 2:55 pm, Ian Collins <ian-n...@hotmail.com> wrote:
>> Rakesh Kumar wrote:
>>> Hi All -
>>> To clarify more about the const_cast<T &>(<volatile object
>>> reference>) - I have attempted to write a thread-safe binary-tree
>>> template ( called as SafeTree<T> ). The following code should
>>> compile.
>>> Can somebody help me with letting me know if this would be race-
>>> free. Also please do let me know if there are possible code syntax
>>> with undefined behavior. Thanks for the help.
>>> #include <iostream>
>>> #include <cstdlib>
>>> using std::cerr;
>>> class Mutex
>>> {
>>> public:
>>> //Fill Here: Apply platform specific thread details for a mutex.
>>> //On linux, use pthreads API
>>> bool lock(bool blocking) volatile
>> Before we go any further, why have you volatile qualified this members?
>>

*Please* don't quote signatures.

>
>
> If the mutex happens to be a volatile instance - then it can access
> only volatile functions of the same. Hence I had to make it volatile.
> I am not sure if that is the correct design though - which is why I
> had posted it here.
>

I think you are confused about the use of volatile.

Typically, volatile has little, if anything to do with threading. I
don't think I've ever seen a volatile qualified member function in real
code. Volatile is generally used to prevent the compiler optimising
away access to a variable, or the placing of a variable in a register in
embedded applications. So volatile is often used to qualify a variable,
but not a member function.

--
Ian Collins.

[Rakesh Kumar]

I agree I am trying to understand more about volatile keyword here.
Here is a much smaller code fragment - illustrating why I would need a
volatile qualified function.

#include <iostream>
#include <cstdlib>

class TypeA
{
public:
void plainVanillaFunction()
{
}
};

class TypeB
{

public:
TypeB()
{
obj = new TypeA();
}

~TypeB()
{
delete obj;
}

volatile TypeA * getTypeA()
{
return obj;
}

private:
volatile TypeA * obj;
};

int main()
{
TypeB b;

volatile TypeA * obj = b.getTypeA();
obj->plainVanillaFunction(); //compiler errors here.
return EXIT_SUCCESS;
}

If I have a class member that happens to volatile ( like the member
obj in TypeB ) - and when I try to retrieve the reference to it - I
cannot invoke non-volatile methods on the same. Hence I am confused
here.