Feedback about my code

morle · ‎02-24-2012

Hi,

I have implemented (tried to) a concurrent list as an exercise about mutexes.

I would like your feedback about it: if I used the mutexes correctly, if the mutexes should be better placed at another place, if I fotgot to use a mutex somewhere and any other advice you would be willing to provide.

Also, I would like your help about two topics.

The first one is the list destructor. I couldn't get it to work(I provide the commented code of the last thing I tried).

The second one is the InsertBefore function. This one inserts a new node before an existing one(since I haven't implemented any iterators for the list, I use the value of a node to search the place where the new one will be inserted). This function works well the first time I use it in main, however, the second time, it segfaults(the second call is commented in main).

Thanks!

[cpp]#include #include #include "tbb/atomic.h" #include "tbb/blocked_range.h" #include "tbb/parallel_for.h" #include "tbb/partitioner.h" #include "tbb/queuing_mutex.h" #include "tbb/spin_rw_mutex.h" typedef tbb::spin_rw_mutex ListMutexType; typedef tbb::spin_rw_mutex NodeMutexType; typedef tbb::queuing_mutex IOMutexType; class EmptyListException: public std::exception { private: std::string M; public: EmptyListException(void):std::exception(){ M = "Empty List"; } virtual ~EmptyListException(void) throw() {} const std::string& What(void) const { return M; } }; template class Node { template friend class List; private: T value; Node* left; Node* right; mutable NodeMutexType NodeMutex; public: static const T max_val; public: Node(void):value(max_val),left(0),right(0){ NodeMutex = NodeMutexType(); } Node(const T& v):value(v),left(0),right(0){ NodeMutex = NodeMutexType(); } Node(const T& v, Node* l, Node* r):value(v),left(l),right{ NodeMutex = NodeMutexType(); } ~Node(void) { NodeMutexType::scoped_lock lock( NodeMutex, true ); right = 0; left = 0; delete right; delete left; } int& Value(void) { NodeMutexType::scoped_lock lock( NodeMutex, false ); return value; } int Value(void) const { NodeMutexType::scoped_lock lock( NodeMutex, false ); return value; } }; template const T Node::max_val = std::numeric_limits::max(); template class List { private: Node* head; Node* tail; tbb::atomic size; mutable ListMutexType ListMutex; public: List(void):size(){ head = new Node(); tail = new Node(); head->right = tail; tail->left = head; ListMutex = ListMutexType(); } // ~List(void) { // THIS IS BEYOND ME // ListMutexType::scoped_lock lock( ListMutex, true ); // if( Empty() ) { // delete head; // delete tail; // } // else { // Node* aux = head; // Node* next = head->right; // while( next != tail ) { // delete aux; // --size; // aux = next; // ++next; // } // delete next; // delete aux; // } // } bool Empty(void) const { ListMutexType::scoped_lock lock( ListMutex, false ); if( head->right == tail ) return true; else return false; } const tbb::atomic& Size(void) const { return size; } const T& InsertFirst( Node* node ) { Node* aux(0); { NodeMutexType::scoped_lock lockhead( head->NodeMutex, true ); aux = head->right; head->right = node; node->left = head; } // end lockhead { NodeMutexType::scoped_lock locknext( aux->NodeMutex, true ); node->right = aux; aux->left = node; } ++size; aux = 0; delete aux; return node->value; } const T& InsertBefore( Node* node, const T& val ) { if( Empty() ) { { NodeMutexType::scoped_lock lockhead( head->NodeMutex, true ); head->right = node; node->left = head; } //end lockhead { NodeMutexType::scoped_lock locktail( tail->NodeMutex, true ); node->right = tail; tail->left = node; } //end locktail } else { Node* it(0); ListMutexType::scoped_lock locklist; locklist.acquire( ListMutex, false ); it = head; while( it->value != val && it != tail ) { ++it; } locklist.release(); Node* aux(0); if( it == tail ) { aux = tail->left; { NodeMutexType::scoped_lock locktail( tail->NodeMutex, true ); tail->left = node; node->right = tail; } { NodeMutexType::scoped_lock lockaux( aux->NodeMutex, true ); aux->right = node; node->left = aux; } } else { aux = it->left; { NodeMutexType::scoped_lock lockit( it->NodeMutex, true ); it->left = node; node->right = it; } { NodeMutexType::scoped_lock lockaux( aux->NodeMutex, true ); aux->right = node; node->left = aux; } } // end else
it = 0; delete it; aux = 0; delete aux; }// end outer else
++size;
return node->value; } int RemoveLast(void) { if( Empty() ) throw EmptyListException(); T toret( Node::max_val ); Node* aux(0); { NodeMutexType::scoped_lock lockend( tail->NodeMutex, true ); aux = tail->left; { NodeMutexType::scoped_lock lockprevious( aux->NodeMutex, true ); toret = aux->value; aux->left->right = aux->right; tail->left = aux->left; } } delete aux; --size; return toret; } }; template class ConcurrentBody { private: List* myl; static IOMutexType IOMutex; public: ConcurrentBody(List* l):myl(l){} ~ConcurrentBody(void){ myl = 0; delete myl; } void operator()(const tbb::blocked_range& r)const{ unsigned int val(0); for( unsigned int i(r.begin());i!=r.end();++i){ if( i%2 == 0 ) { val = myl->InsertFirst( new Node(i) ); IOMutexType::scoped_lock lock( IOMutex ); std::cout << "Inserted " << val << "\n"; } else { val = myl->RemoveLast(); IOMutexType::scoped_lock lock( IOMutex ); std::cout << "Removed " << val << "\n"; } } } }; template IOMutexType ConcurrentBody::IOMutex = IOMutexType(); int main(int argv, char* argc[]) { List l; std::cout << l.Empty() << std::endl; try { std::cout << "Inserted " << l.InsertFirst( new Node(7) ) << "\n"; std::cout << "Is empty: " << l.Empty() << " & size: " << l.Size() << std::endl; std::cout << "Inserted before 7: " << l.InsertBefore( new Node(99), 7 ) << " & size: " << l.Size() << std::endl; //THIS GOES WELL // std::cout << "Inserted before 99: " << l.InsertBefore( new Node(100), 99 ) << " & size: " << l.Size() << std::endl; // THIS SEGFAULTS tbb::parallel_for(tbb::blocked_range(0,8),ConcurrentBody(&l),tbb::auto_partitioner()); std::cout << "Is empty: " << l.Empty() << " & size: " << l.Size() << std::endl; } catch ( const EmptyListException& e ) { std::cerr << "This happened: " << e.What() << "\n"; } catch( const std::exception& e ) { std::cerr << "Oops: " << e.what() << std::endl; } catch( ... ) { std::cerr << "Unexpected\n"; } return 0; }[/cpp]

SergeyKostrov · ‎02-25-2012

>>...
>>The first one is the list destructor. I couldn't get it to work ( I provide the commented code of the last thing I tried ).

>>The second one is the InsertBefore function.

>>...

Hi,
Thanks for the sharing the code! I'll try to lookat these to issues some time next week.
Best regards,
Sergey

SergeyKostrov · ‎02-26-2012

Please take a look at a destructor of aNode class:

...
~Node(void)
{
NodeMutexType::scoped_lock lock( NodeMutex, true );
right = 0; //Assigned a value NULL
left = 0; // Assigned a value NULL
delete right; // It won'tdestroythe object
delete left; // It won't destroy the object
}
...

Shouldn't it be like:

...
~Node(void)
{
NodeMutexType::scoped_lock lock( NodeMutex, true );
delete right;
delete left;
right = 0;
left = 0;
}
...

RafSchietekat · ‎02-27-2012

That should make the delete operations a whole lot more effective. :-)

Of course you could also simply discard the assignments (they're not relevant), or replace the pointers with auto_ptr (if I see an opportunity to get rid of a delete operation, I prefer to take it). One more thing to remember is to always change the copy assignment operator in concert with the copy constructor, or to make it unavailable, e.g., by declaring it privately and never defining it, or by inheriting from boost::noncopyable or somesuch.

I have not otherwise looked at the provided code, though.

(Added) I glanced at Node anyway, and I noticed the initialisation of its mutex: don't do that, because mutexes take care of themselves (even as member variables), and they will likely become noncopyable (as in C++11), preventing such initialisation.

(Added 2012-02-28) Well, if the code is otherwise correct about its use of that mutex, auto_ptr wouldn't work of course...

morle · ‎02-27-2012

Hi,

thanks for your responses!

I didn't realise that ordering in the Node destructor! :)

Why is that?

One more thing to remember is to always change the copy assignment operator in concert with the copy constructor, or to make it unavailable

SergeyKostrov · ‎02-27-2012

Hi,

I've done a code reviewyesterday but I still didn't have time to "play" with the one. I'm simply interested
to know if it works after a'delete' operatorscorrection? What about the 2nd problem?

Best regards,
Sergey

RafSchietekat · ‎02-27-2012

#4 "Why is that?"
C++ assumes semantic equivalence between copy constructor and copy assignment operator in the specification, and allows compilers to substitute one for the other.

jimdempseyatthecove · ‎02-28-2012

>>
~Node(void)
{
NodeMutexType::scoped_lock lock( NodeMutex, true );
delete right;
delete left;
right = 0;
left = 0;
}
<<

The above is still faulty...

Ask yourself "What is to the left of the node to the right?" as well as "What is right of the node to the left?".

The problem with the above is you enter an infinite iteration of deleting nodes (which are in the process of being deleted).

You also have the issue of you are locking the NodeMutex (contained within the node) as opposed to a list mutex.
Should multiple threads attempt to lock the NodeMutex and the delete thread wins, what do you expect to happen with the loser when the scoped lock on the NodeMutex expires?

I suggest you rethink the dtor.

Jim Dempsey

SergeyKostrov · ‎02-29-2012

Quoting jimdempseyatthecove

>>
~Node(void)
{
NodeMutexType::scoped_lock lock( NodeMutex, true );
delete right;
delete left;
right = 0;
left = 0;
}
<<

The above is still faulty...

Ask yourself "What is to the left of the node to the right?" as well as "What is right of the node to the left?".

The problem with the above is you enter an infinite iteration of deleting nodes (which are in the process of being deleted).

This is not right, I agree, andit has to be done in a different way.

RafSchietekat · ‎03-01-2012

"The above is still faulty..."
It's not just one or a few problems, I think. Maybe it would be better to pick an easier training exercise?

jimdempseyatthecove · ‎03-01-2012

>>It's not just one or a few problems, I think. Maybe it would be better to pick an easier training exercise?

True, his insertion and removal (and traversal while insert/remove) have issues as well.

The issues not only expose broken links in his code but if not corrected properly has the potential to expose deadlocks.

The functional requirements for insertionare:

Inhibit additional insertion at your insertion point (until you are done inserting)
Inhibit deletion of nodes to left and right of your insertion point (until you are done inserting)
Optional permit traversal over nodes during insertion
Optional permit use of node being inserted during insertion
Avoid deadlock

The functional requirements for deletion are:

Inhibit insertion of nodes to left and right of your deletion point (until you are done deleting)
Inhibit deletion of nodes to left and right of your deletion point (until you are done deleting)
Inhibit use of node being deleted
Inhibit deletion of node if in-use
Inhibit deletion of node if in process of being deleted (may be different than in use)
Optional permit traversal over node during deletion
Avoid deadlock

These are non-trivial issues if you desire to have concurrent traversal/use/insertion/deletions.
There is often a trade-off between the degree of concurrency and the degree of overhead in managing locks.

Jim Dempsey

morle · ‎03-01-2012

Hi,
thank you all for your responses and your help.

Sergey, thanks for your offering. I would really appreciate it.
Raf, what exercise would you suggest?

Thanks!

SergeyKostrov · ‎03-01-2012

Quoting jimdempseyatthecove

...
The functional requirements for deletion are:

Inhibit insertion of nodes to left and right of your deletion point (until you are done deleting)
Inhibit deletion of nodes to left and right of your deletion point (until you are done deleting)
Inhibit use of node being deleted
Inhibit deletion of node if in-use
Inhibit deletion of node if in process of being deleted (may be different than in use)
Optional permit traversal over node during deletion
Avoid deadlock
...

Jim Dempsey

A release of memory allocated for a linked list could be done in an iterative or recursive ways.
Here is an iterative example:

template< class T > class TList
{
...
inline RTvoid DeleteAll( RTvoid )
{
if( m_iSize == 0 )
return;

TNode< T > *ptNode = RTnull;

while( m_ptTail != RTnull )
{
ptNode = m_ptTail->m_ptPrev;

if( m_ptTail != RTnull )
{
CrtFree( m_ptTail );

if( --m_iSize == 0 )
break;

m_ptTail = ptNode;
m_ptTail->m_ptNext = RTnull;
}
}

m_ptHead = RTnull;
m_ptTail = RTnull;
};
...
};

The 'DeleteAll' method keeps integrity of the linked list when releasing all memory.

SergeyKostrov · ‎03-01-2012

Quoting morle

Hi,
thank you all for your responses and your help.

Sergey, thanks for your offering. I would really appreciate it.
...

I'll release the codes as soon as a stress testing is done.

Best regards,
Sergey

jimdempseyatthecove · ‎03-01-2012

IMHO 'DeleteAll' would

a) Lock the list
b) save head and tail pointers in local storage
c) null head and tail pointers
d) Scan (using copy of head) list from head to tail issuing (non-scoped) try_lock on each node.
e) If any try_lock fails, run backwards in list unlocking, restore head and tail, then unlock the list, then retry
f) If all locks made, copy head and tail, re-scan list to see if any other threads have lock pending on any of the nodes. If so, back out as in e), if not, then delete nodes from (copy of) head to tail.

Note, this requires that you can tell if thread blocked waiting for a mutex so choice of mutex matters.

Much of this busy work could be elieviated with using a reference counter for the list.

Atomically bump count prior to traversing list
If node (pointer)found and used, keep count in bumped state.
When node no longer in use, decriment count (consider using smart pointer object)
If on search, node not found then decriment reference counter.

For DeleteAll, then lock list, examine reference counter, if non-zero, unlock list and retry. If reference counter zero, copy head and tailpointers, null head and tail, check reference counter, if non-zero back out, if zero, delete entire list. (notenode dtor does not delete left and right).

Jim Dempsey

RafSchietekat · ‎03-01-2012

"Raf, what exercise would you suggest?"
I'm afraid I can't really help you with specific advice about that. Try to find something with progressive learning tracks, I suppose. Maybe the Parallel Programmng Community website could put some more emphasis on suggesting good general tutorials?

jimdempseyatthecove · ‎03-02-2012

You also might try a Google search:

concurrent doubly linked list

This will give you some examples.

Jim Dempsey

SergeyKostrov · ‎03-02-2012

template< class T > struct TNodev4
{
TNodev4< T > *m_ptPrev;
TNodev4< T > *m_ptNext;

T m_tValue;
};

template< class T > class TListv4
{
public:
TListv4( RTvoid )
{
m_ptHead = RTnull;
m_ptTail = RTnull;

m_iSize = 0;

m_bSkipNodesRelease = RTfalse;
};

~TListv4( RTvoid )
{
DeleteAll();
};

inline RTbool IsEmpty( RTvoid )
{
return ( RTbool )( ( m_iSize == 0 ) ? RTtrue : RTfalse );
};

inline RTint GetSize( RTvoid )
{
return ( RTint )m_iSize;
};

inline TNodev4< T > * GetHead( RTvoid )
{
return ( TNodev4< T > * )m_ptHead;
};

inline TNodev4< T > * GetTail( RTvoid )
{
return ( TNodev4< T > * )m_ptTail;
};

inline T GetHeadValue( RTvoid )
{
if( m_iSize == 0 )
return ( T )0;
if( m_ptHead == RTnull )
return ( T )0;

return ( T )m_ptHead->m_tValue;
};

inline T GetTailValue( RTvoid )
{
if( m_iSize == 0 )
return ( T )0;
if( m_ptTail == RTnull )
return ( T )0;

return ( T )m_ptTail->m_tValue;
};

inline T GetValue( TNodev4< T > *ptNode )
{
if( m_iSize == 0 )
return ( T )0;
if( ptNode == RTnull )
return ( T )0;

TNodev4< T > *ptTmpNode = RTnull;

for( ptTmpNode = m_ptHead; ptTmpNode != RTnull; ptTmpNode = ptTmpNode->m_ptNext )
{
if( ptNode == ptTmpNode )
return ( T )ptTmpNode->m_tValue;
}

return ( T )0;
};

inline TNodev4< T > * AddHead( T tValue )
{
TNodev4< T > *ptNewNode = ( TNodev4< T > * )CrtMalloc( sizeof( TNodev4< T > ) );
if( ptNewNode == RTnull )
return ( TNodev4< T > * )RTnull;

ptNewNode->m_ptPrev = RTnull;
ptNewNode->m_ptNext = m_ptHead;

if( m_ptHead != RTnull )
m_ptHead->m_ptPrev = ptNewNode;
else
m_ptTail = ptNewNode;

m_ptHead = ptNewNode;

ptNewNode->m_tValue = tValue;

m_iSize++;

return ( TNodev4< T > * )ptNewNode;
};

inline TNodev4< T > * AddTail( T tValue )
{
TNodev4< T > *ptNewNode = ( TNodev4< T > * )CrtMalloc( sizeof( TNodev4< T > ) );
if( ptNewNode == RTnull )
return ( TNodev4< T > * )RTnull;

ptNewNode->m_ptPrev = m_ptTail;
ptNewNode->m_ptNext = RTnull;

if( m_ptTail != RTnull )
m_ptTail->m_ptNext = ptNewNode;
else
m_ptHead = ptNewNode;

m_ptTail = ptNewNode;

ptNewNode->m_tValue = tValue;

m_iSize++;

return ( TNodev4< T > * )ptNewNode;
};

TNodev4< T > * InsertBefore( TNodev4< T > *ptNode, T tValue )
{
if( m_iSize == 0 )
return ( TNodev4< T > * )RTnull;
if( ptNode == RTnull )
return ( TNodev4< T > * )RTnull;

TNodev4< T > *ptNewNode = ( TNodev4< T > * )CrtMalloc( sizeof( TNodev4< T > ) );
if( ptNewNode == RTnull )
return ( TNodev4< T > * )RTnull;

ptNewNode->m_ptPrev = ptNode->m_ptPrev;
ptNewNode->m_ptNext = ptNode;
ptNode->m_ptPrev = ptNewNode;

if( ptNewNode->m_ptPrev == RTnull )
m_ptHead = ptNewNode;
else
ptNewNode->m_ptPrev->m_ptNext = ptNewNode;

ptNewNode->m_tValue = tValue;

m_iSize++;

return ( TNodev4< T > * )ptNewNode;
};

TNodev4< T > * InsertAfter( TNodev4< T > *ptNode, T tValue )
{
if( m_iSize == 0 )
return ( TNodev4< T > * )RTnull;
if( ptNode == RTnull )
return ( TNodev4< T > * )RTnull;

TNodev4< T > *ptNewNode = ( TNodev4< T > * )CrtMalloc( sizeof( TNodev4< T > ) );
if( ptNewNode == RTnull )
return ( TNodev4< T > * )RTnull;

ptNewNode->m_ptPrev = ptNode;
ptNewNode->m_ptNext = ptNode->m_ptNext;
ptNode->m_ptNext = ptNewNode;

if( ptNewNode->m_ptNext == RTnull )
m_ptTail = ptNewNode;
else
ptNewNode->m_ptNext->m_ptPrev = ptNewNode;

ptNewNode->m_tValue = tValue;

m_iSize++;

return ( TNodev4< T > * )ptNewNode;
};

RTvoid Delete( TNodev4< T > *ptDelNode )
{
if( m_iSize == 0 )
return;
if( ptDelNode == RTnull )
return;

TNodev4< T > *ptNode = RTnull;

for( ptNode = m_ptHead; ptNode != RTnull; ptNode = ptNode->m_ptNext )
{
if( ptNode != ptDelNode )
continue;

if( ptNode->m_ptPrev == RTnull && ptNode->m_ptNext != RTnull )
{
ptNode->m_ptNext->m_ptPrev = ptNode->m_ptPrev;
m_ptHead = ptNode->m_ptNext;
}
else
if( ptNode->m_ptPrev != RTnull && ptNode->m_ptNext == RTnull )
{
ptNode->m_ptPrev->m_ptNext = ptNode->m_ptNext;
m_ptTail = ptNode->m_ptPrev;
}
else
if( ptNode->m_ptPrev != RTnull && ptNode->m_ptNext != RTnull )
{
ptNode->m_ptNext->m_ptPrev = ptNode->m_ptPrev;
ptNode->m_ptPrev->m_ptNext = ptNode->m_ptNext;
}
else
break;

CrtFree( ptNode );

m_iSize--;

break;
}

if( m_iSize == 0 )
{
m_ptHead = RTnull;
m_ptTail = RTnull;
}
};

inline RTvoid DeleteAll( RTvoid )
{
if( m_bSkipNodesRelease == RTtrue )
return;
if( m_iSize == 0 )
return;

TNodev4< T > *ptNode = RTnull;

while( m_ptTail != RTnull )
{
ptNode = m_ptTail->m_ptPrev;

if( m_ptTail != RTnull )
{
CrtFree( m_ptTail );

if( --m_iSize == 0 )
break;

m_ptTail = ptNode;
m_ptTail->m_ptNext = RTnull;
}
}

if( m_iSize == 0 )
{
m_ptHead = RTnull;
m_ptTail = RTnull;
}
};

RTvoid Display( RTvoid )
{
if( m_iSize == 0 )
return;

TNodev4< T > *ptNode = RTnull;

for( ptNode = m_ptHead; ptNode != RTnull; ptNode = ptNode->m_ptNext )
{
// CrtPrintf( RTU("%d "), ( RTint16 )ptNode->m_tValue );
CrtPrintf( RTU("%ld "), ( RTint )ptNode->m_tValue );
// CrtPrintf( RTU("%.1f "), ( RTfloat )ptNode->m_tValue );
}

CrtPrintf( RTU("\n") );
};

protected:
TNodev4< T > *m_ptHead;
TNodev4< T > *m_ptTail;

RTint m_iSize;

public:
RTbool m_bSkipNodesRelease;
};

SergeyKostrov · ‎03-02-2012

...
// Sub-Test 4 - Version 4
{
///*
//#define _RTTYPE4RTint16
#define _RTTYPE4RTint
//#define _RTTYPE4RTfloat
//#define _RTTYPE4RTdouble

RTbool bOk = RTfalse;
RTint iSize = -1;

TNodev4< _RTTYPE4 > *pHead = RTnull;
TNodev4< _RTTYPE4 > *pTail = RTnull;
RTint iValHead = -1;
RTint iValTail = -1;

// Step 00
TListv4< _RTTYPE4 > lnkList;

// Step 01
bOk = lnkList.IsEmpty();
iSize = lnkList.GetSize();

lnkList.DeleteAll();
lnkList.Display();

RTint i;
RTint iLnkListSize;

iLnkListSize =32;
//iLnkListSize =512; // 2^09 - For a 16-bit platform
//iLnkListSize =1024; // 2^10
//iLnkListSize =2048; // 2^11
//iLnkListSize =4096; // 2^12
//iLnkListSize =1048576; // 2^20 - For a 32-bit platform
//iLnkListSize =4194304; // 2^22
//iLnkListSize =16777216; // 2^24
//iLnkListSize =67108864; // 2^26
//iLnkListSize = 132378224;// - Max for a 32-bit platform ( 2GB limit NOT exceeded )
//iLnkListSize = 134217728;// 2^27 - For a 64-bit platform ( 2GB limit exceeded )
//iLnkListSize = 268435456;// 2^28

// Step 02
for( i = 0; i < iLnkListSize; i++ )
lnkList.AddHead( ( _RTTYPE4 )i );
lnkList.Display();
CrtPrintf( RTU("Linked List Size: %ld\n"), ( RTint )lnkList.GetSize() );
lnkList.DeleteAll();

// Step 03
for( i = 0; i < iLnkListSize; i++ )
lnkList.AddTail( ( _RTTYPE4 )i );
lnkList.Display();
CrtPrintf( RTU("Linked List Size: %ld\n"), ( RTint )lnkList.GetSize() );
lnkList.DeleteAll();

// Step 04
lnkList.AddHead( 555 ); // Updated
lnkList.AddTail( 777 ); // Updated
pHead = lnkList.GetHead();
iValHead = lnkList.GetHeadValue();
pTail = lnkList.GetTail();
iValTail = lnkList.GetTailValue();

TNodev4< _RTTYPE4 > *pV3 = lnkList.AddHead( 3 );
TNodev4< _RTTYPE4 > *pV2 = lnkList.AddHead( 2 );
TNodev4< _RTTYPE4 > *pV1 = lnkList.AddHead( 1 );
TNodev4< _RTTYPE4 > *pV4 = lnkList.AddTail( 4 );
TNodev4< _RTTYPE4 > *pV5 = lnkList.AddTail( 5 );
TNodev4< _RTTYPE4 > *pV6 = lnkList.AddTail( 6 );
TNodev4< _RTTYPE4 > *pV7 = lnkList.AddTail( 7 );
lnkList.Display();

// Step 05
CrtPrintf( RTU("Node1 Value: %ld\n"), ( _RTTYPE4 )lnkList.GetValue( pV1 ) );
CrtPrintf( RTU("Node2 Value: %ld\n"), ( _RTTYPE4 )lnkList.GetValue( pV2 ) );
CrtPrintf( RTU("Node3 Value: %ld\n"), ( _RTTYPE4 )lnkList.GetValue( pV3 ) );
//CrtPrintf( RTU("Node1 Value: %.1f\n"), ( _RTTYPE4 )lnkList.GetValue( pV1 ) );
//CrtPrintf( RTU("Node2 Value: %.1f\n"), ( _RTTYPE4 )lnkList.GetValue( pV2 ) );
//CrtPrintf( RTU("Node3 Value: %.1f\n"), ( _RTTYPE4 )lnkList.GetValue( pV3 ) );

// Step 06
lnkList.DeleteAll();

pV3 = lnkList.AddHead( 3 );
pV2 = lnkList.AddHead( 2 );
pV1 = lnkList.AddHead( 1 );

pHead = lnkList.GetHead();
iValHead = lnkList.GetHeadValue();
pTail = lnkList.GetTail();
iValTail = lnkList.GetTailValue();

// Step 07
pV4 = lnkList.AddTail( 4 );
pV5 = lnkList.AddTail( 5 );
pV6 = lnkList.AddTail( 6 );
pV7 = lnkList.AddTail( 7 );
lnkList.Display();

pHead = lnkList.GetHead();
iValHead = lnkList.GetHeadValue();
pTail = lnkList.GetTail();
iValTail = lnkList.GetTailValue();

// Step 08
lnkList.Delete( pHead );
lnkList.Display();
lnkList.Delete( pTail );
lnkList.Display();
lnkList.Delete( pV6 );
lnkList.Display();
lnkList.Delete( pV5 );
lnkList.Display();
lnkList.Delete( pV4 );
lnkList.Display();
lnkList.Delete( pV3 );
lnkList.Display();

bOk = lnkList.IsEmpty();
iSize = lnkList.GetSize();

// Step 09
lnkList.DeleteAll();

lnkList.InsertBefore( RTnull, 555 );
lnkList.InsertAfter( RTnull, 777 ); // Updated

// Step 10
lnkList.DeleteAll();

pV3 = lnkList.AddTail( 3 );
pV2 = lnkList.AddTail( 2 );
pV1 = lnkList.AddTail( 1 );
lnkList.Display();
pHead = lnkList.GetHead();
pTail = lnkList.GetTail();
TNodev4< _RTTYPE4 > *pV333 = lnkList.InsertBefore( pHead, 333 );
lnkList.Display();
TNodev4< _RTTYPE4 > *pV222 = lnkList.InsertBefore( pTail, 222 );
lnkList.Display();
TNodev4< _RTTYPE4 > *pV111 = lnkList.InsertBefore( pV2, 111 );
lnkList.Display();

// Step 11
lnkList.DeleteAll();

pV3 = lnkList.AddHead( 3 );
pV2 = lnkList.AddHead( 2 );
pV1 = lnkList.AddHead( 1 );
lnkList.Display();
pHead = lnkList.GetHead();
pTail = lnkList.GetTail();
TNodev4< _RTTYPE4 > *pV777 = lnkList.InsertAfter( pHead, 777 );
lnkList.Display();
TNodev4< _RTTYPE4 > *pV888 = lnkList.InsertAfter( pTail, 888 );
lnkList.Display();
TNodev4< _RTTYPE4 > *pV999 = lnkList.InsertAfter( pV2, 999 );
lnkList.Display();

bOk = lnkList.IsEmpty();
iSize = lnkList.GetSize();

// Step 12
pHead = lnkList.GetHead();
pTail = lnkList.GetTail();

for( i = 0; i < iLnkListSize; i++ )
lnkList.InsertBefore( pHead, ( _RTTYPE4 )i );
for( i = 0; i < iLnkListSize; i++ )
lnkList.InsertBefore( pTail, ( _RTTYPE4 )i );
lnkList.Display();
CrtPrintf( RTU("Linked List Size: %ld\n"), ( RTint )lnkList.GetSize() );

for( i = 0; i < iLnkListSize; i++ )
lnkList.InsertAfter( pHead, ( _RTTYPE4 )-i );
for( i = 0; i < iLnkListSize; i++ )
lnkList.InsertAfter( pTail, ( _RTTYPE4 )-i );
lnkList.Display();
CrtPrintf( RTU("Linked List Size: %ld\n"), ( RTint )lnkList.GetSize() );

lnkList.m_bSkipNodesRelease = RTtrue;
//*/
}
...

SergeyKostrov · ‎03-02-2012

Here are Comments:

- The Linked List is a stress tested with asize of up to 132,378,224 elements on a 32-bit Windows platform

- You will need to add a syncronization functionality

-'malloc-free' CRT-functionsare used instead of 'new-delete' C++ operatorsto increaseperformance

- Take into account that on insert into a Linked List 7 steps must be done and
they must be considered as a "transaction" ( done completely or rejected ):

- Allocate memory
- Update Prev element
- Update Next element
- Update Prev of a new element
- Update Next of a new element
- Set a value for the new element
- Increase a counter of the Linked List

- Take into account that on a delete from a Linked List 5 steps must be done and
they must be considered as a "transaction" ( done completely or rejected ):

- Update Prev element
- Update Next element
- Update Head / Tail element if needed
- Release memory
- Decrease a counter of the Linked List

- In a cases when lots of elements are inserted into a Linked List you can drop-off a memory on exit
of an application by setting:
...
lnkList.m_bSkipNodesRelease = RTtrue;
...

- Code updates:

TNodev4 -> TNode
TListv4 -> TList
RT -> type ( RTnull -> NULL / RTbool -> BOOL, etc )
Crt -> function
RTU("...") -> "" or _T("")
etc

- In cases like TNodev4< __int16 > or TNodev4< char > a structure packing directive:

#pragma pack(1)

could be used for the TNodev4 structure

Good Luck! Please feedback if you find an issue, aproblem or a bug.

Best regards,
Sergey

SergeyKostrov · ‎03-02-2012

...
> Test1150 Start <
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Linked List Size: 32
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Linked List Size: 32
1 2 3 4 5 6 7
Node1 Value: 1
Node2 Value: 2
Node3 Value: 3
1 2 3 4 5 6 7
2 3 4 5 6 7
2 3 4 5 6
2 3 4 5
2 3 4
2 3
2
3 2 1
333 3 2 1
333 3 2 222 1
333 3 111 2 222 1
1 2 3
1 777 2 3
1 777 2 3 888
1 777 2 999 3 888
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 1 777 2 999 3 0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 888
Linked List Size: 70
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 1 -31 -30 -29 -28 -27 -26 -25 -24
-23 -22 -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 777 2 999 3 0 1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 888 -31 -30 -29 -28 -27 -26 -25 -24 -23 -22 -21 -20 -19 -
18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0
Linked List Size: 134
> Test1150 End <
...