Click here to Skip to main content
13,146,014 members (46,696 online)
Click here to Skip to main content
Add your own
alternative version

Stats

25K views
490 downloads
22 bookmarked
Posted 9 Feb 2014

A Lock Free Doubly Linked List

, 12 Feb 2014
Rate this:
Please Sign up or sign in to vote.

Abstract  

Lock  based synchronization suffers from problems like priority inversion and deadlock Even then lock free synchronization has not gain much attention. This is due to the fact that it is very difficult to write lock-free code that is correct and works well. We presents a lock free doubly linked list implementation that is practical and easier to understand. This is the second lock-free implementation (first is by H°akan Sundell) that only needs the single-word compare-and-swap atomic primitive. The experimental results show that the proposed solution favorably compares with H°akan Sundell lock free doubly linked list.

Introduction

Doubly Linked list is a list of items where items can be anywhere in memory. Each item contains two fields. Next field points to next item in the list. Prev field points to prev item in the list. These two fields allow list traversal in either direction. Doubly Linked List support insert and delete operation. These operations are trivial to implement. But in a multithreaded environment most common method is mutual exclusion which suffers from deadlocks and priority inversion scenarios. The answer to these problems is lock freedom. In lock free system, when a thread takes few steps then the system as a whole makes progress. By definition lock free system are free from deadlocks. However there is a risk of starvation. Wait free systems are lock free and moreover they avoid the starvations as well.

Related Work  

[Greenwald99] suggested a general lock-free doubly linked list implementation based on the non-available DCAS atomic primitive.

[Valois 95] sketched out an implementation of a lock-free doubly linked list structure using Compare-And-Swap (CAS), though without any support for deletions

[Håkan Sundell 2008] solution is to treat the doubly linked list as being a singly linked list with auxiliary information in the prev pointers, with the next pointers being updated before the prev pointers. Thus, the next pointers always form a consistent singly linked list, but the prev pointers only give hints for where to find the previous node. This is possible because of the observation that a “late” non-updated prev pointer will always point to a node that is directly or some steps before the current node, and from that “hint” position it is always possible to traverse through the next pointers to reach the directly previous node.

Algorithm

In this section we give a detailed description of all the fundamental operations of a general doubly linked list data structure. In order to make the doubly linked list lock free, we are using Compare-And-Swap (CAS).

The Lock-free Linked List data structure is defined as follows: 

__declspec(align(InterLockedAlign)) struct Node
{
	int data;
__declspec(align(InterLockedAlign))	Node *rlink;
__declspec(align(InterLockedAlign))Node *llink;
};

This "Node" struct is the same found in common sequential implementations of doubly linked list. There is one difference that it is 32 bit aligned.

The lock free linked list data structure differs from sequential linked list in following ways;

-Each operation in the sequential doubly linked list (Insert, Delete) has an argument list and local variables.

In lock free doubly linked list, the values of arguments and local variables of an operation are recorded in the corresponding structure for that operation. For example following are the stuct's for Insert and delete operation :

//Following is the structure for Insert operation
struct Insert
{
	//Following is the structure for arguments passed to Insert
	struct Arguments
	{
		Node *p;//node to be inserted
		Node *x;//p is inserted next to x
	}args;
	struct LocalVariables
	{
		Node *x_rlink_llink;//This announces the value of x->rlink->llink which needs to be set to p.
		Node **x_rlink_llink_address;//This announces the address of x->rlink->llink which is used as destination in InterlockedCompareExchange.
		Node *x_rlink;//This announces the value of x->rlink which needs to be set to p.
		Node **x_rlink_address;//This announces the address of x->rlink which is used as destination in InterlockedCompareExchange.
	}lv;
};
//Following is the structure for Delete operation
struct Delete
{
	//Following is the structure for arguments passed to Delete
	struct Arguments
	{
		Node *x;//node to be deleted.
	}args;
	struct LocalVariables
	{
		//Following variables announce the values and addresses of pointers found in nodes around x (including x as well).
		Node *x_llink;
		Node **x_llink_address;
		Node *x_rlink;
		Node **x_rlink_address;
		Node *x_llink_rlink;
		Node **x_llink_rlink_address;
		Node *x_rlink_llink;
		Node **x_rlink_llink_address;
		Node *x_llink_llink;
		Node **x_llink_llink_address;
		Node *x_rlink_rlink;
		Node **x_rlink_rlink_address;
		Node *x_llink_llink_rlink;
		Node **x_llink_llink_rlink_address;
		Node *x_rlink_rlink_llink;
		Node **x_rlink_rlink_llink_address;

		Node *replacement_x_llink;//This points to the replacement for the node left to x.
		Node *replacement_x_rlink;//This points to the replacement for the node right to x.
	}lv;
};
enum OperationName
{
	NONE,INSERT,DELET
};
//Following structure contains the operations defined earlier.
struct AnnounceOp
{
	OperationName opName;
	union
	{
		struct Insert insert;
		struct Delete del;
	};
};

The idea really is that when a thread tries to start an operation, it records the call in invocation structure (AnnounceOp) whose fields include operation name (OperationName) and anonymous unions of structures for each operation

__declspec(align(InterLockedAlign))struct LinkedList
{
	volatile AnnounceOp *announce;//current announcement
	Node *first;//first node
	Node *end;//end node	
};

LinkedList l;

Finally, the lock free doubly linked list is a struct containing Announce Op, first and end nodes. “initialize” function sets up the doubly linked list as initially containing four dummy nodes. “initialize” function does not need any lock-free synchronization because initialization should always run in isolation.

void initialize()
{
	//current announcement is that no operation is in progress	
	l.announce=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign );//new AnnounceOp;
	assert(l.announce);
	l.announce->opName=NONE;

	//create 4 node doubly linked list
	l.first=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign );//new Node;
	assert(l.first);
	l.end=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign );
	assert(l.end);
	l.first->rlink=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign );
	assert(l.first->rlink);
	l.first->rlink->rlink=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign );
	assert(l.first->rlink->rlink);
	l.first->llink=0;
	l.first->rlink->llink=l.first;
	l.first->rlink->rlink->rlink=l.end;
	l.first->rlink->rlink->llink=l.first->rlink;
	l.end->rlink=0;
	l.end->llink=l.first->rlink->rlink;
}

The major difficulty in constructing doubly lock free linked list arises from the situation when nodes can get deleted during traversal. One solution is to restart the traversal when a deleted node is en-countered. Insertion is straight forward. Announce the start of insertion. After that using CAS swing the rlink field of node at insertion point to new node and swing the llink field of node next to insertion point to new node. If the operation succeeds then the new node has been linked into the list otherwise retry the operation.

Deletion is not so straight forward because when an insertion after the node to be deleted occurs in between when we read the rlink field of node (to be deleted) and swing the rlink field of predecessor of node (to be deleted) to that value. This can cause the newly inserted node to be deleted along with the node which we really meant to delete. Similarly another problem can occur in case of concurrent deletion of adjacent nodes where a node (to be deleted) still remains even after successful execution of delete operation.

Given doubly linked list initially contains four dummy nodes start, end and 2 nodes in between. We have dummy start node because we don’t want to change the start and end during any operation. We have dummy end node because we require that NULL pointer should not have special meaning like end of list marker as NULL pointer is used to de-link the memory cells from the doubly linked list requires that NULL pointer should not have special meaning like end of list marker. We have the middle dummy node because we don’t want the start to change but we require replacement of nodes any where to prevent ABA problem. In this way, we can avoid replacement of start node as insertions are always done after the middle dummy node. One drawback of using CAS is ABA problem. The ABA problem can be avoided by making sure that a variable never attains the same value again while some other thread has read that value and that thread is going to use it in CAS. This can be achieved in general by using only pointer type for variables and making sure that pointers don’t attain the same value again by replacing existing memory cells with new memory cells. We have the 2 middle dummy nodes because we don’t want the start to change but we also require replacement of nodes any where to prevent ABA problem. In this way, we can avoid replacement of start node as insertions are always done between the two middle dummy nodes.

The first part of insert (see Listing 1) and delete (see Appendix B) operation performs parameter validations. After that goes variable declarations to hold temporary values (if any). After that comes a while loop which tries to perform the operation. In the start, it tries to prepare a consistent shallow copy of the current state of the AnnounceOp.

After successfully making the copy, the rest is two cases to consider:

  • CASE 1: If there is no current invocation then that thread tries to start the operation by recording the operation name, arguments and local variables in invocation structure. It tries to update announce variable atomically using CAS. After that it calls the second part of operation.
  • CASE 2: If there is a current invocation then it means some operation might be in progress and this thread tries to help the operation by calling the second part of that corresponding operation.

//insert node p to the right of node x
int Insert(Node *p,Node *x)
{
	if(p==0||x==0) return 0;
	AnnounceOp *curAnnouncedOp;
	AnnounceOp *nextAnnounceOp=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign );//To announce an insert operation.
	assert(nextAnnounceOp);
	while(1)
	{		
		curAnnouncedOp=(AnnounceOp *)l.announce;		
		AnnounceOp *hp0=curAnnouncedOp;
		if(curAnnouncedOp!=l.announce) continue;
		if(curAnnouncedOp->opName==NONE)
		{
			try
			{
				if(l.first==x||l.end==x||l.end->llink==x)//insertion should not be after first or after end or after one node before end
				{
					_aligned_free(nextAnnounceOp);
					return 0;
				}
				p->llink=x;//set p's left as x
				p->rlink=x->rlink;//set p's right as x's right
				if(p->rlink==0||p->llink==0)  goto label;
				nextAnnounceOp->opName=INSERT;//set INSERT as the next operation
				nextAnnounceOp->insert.args.p=p;
				nextAnnounceOp->insert.args.x=x;
				
				//announce the value of x->rlink which needs to be set to p
				nextAnnounceOp->insert.lv.x_rlink=x->rlink;
				if(nextAnnounceOp->insert.lv.x_rlink==0)  goto label;//node x is no more in the linked list
				Node *hp2=nextAnnounceOp->insert.lv.x_rlink;//set hazard pointer
				if(x->rlink!=nextAnnounceOp->insert.lv.x_rlink)  goto label;//check that hazard pointer has been set accurately
				nextAnnounceOp->insert.lv.x_rlink_address=&x->rlink;//announce the address of x->rlink to be used as destination in InterlockedCompareExchange

				//announce the value of x->rlink->llink which needs to be set to p
				nextAnnounceOp->insert.lv.x_rlink_llink=nextAnnounceOp->insert.lv.x_rlink->llink;
				if(nextAnnounceOp->insert.lv.x_rlink_llink==0)  goto label;//node next to node x is unlinked
				Node *hp1=nextAnnounceOp->insert.lv.x_rlink_llink;//set hazard pointer
				if(nextAnnounceOp->insert.lv.x_rlink->llink!=nextAnnounceOp->insert.lv.x_rlink_llink)  goto label;//check hazard pointer is set correctly
				nextAnnounceOp->insert.lv.x_rlink_llink_address=&nextAnnounceOp->insert.lv.x_rlink->llink;//announce the address of x->rlink->llink to be used as destination in InterlockedCompareExchange.
				
				
				
				//Check that announced addresses has not changed
				/*if(&x->rlink->llink!=nextAnnounceOp->insert.lv.x_rlink_llink_address)  goto label;
				if(&x->rlink!=nextAnnounceOp->insert.lv.x_rlink_address)  goto label;*/

				//To announce the start of insert operation.
				void *v1=reinterpret_cast<void>(nextAnnounceOp);
				void *v2=reinterpret_cast<void>(curAnnouncedOp);
				void *res=(void *)InterlockedCompareExchange(reinterpret_cast<volatile>(&l.announce),(LONG)v1,(LONG)v2);
				if(res==v2)
				{
					//RetireNode(curAnnouncedOp);
					InsertHelper(nextAnnounceOp);
					return 1;
				}
			}
			catch(...)
			{
				printf("Exception in Insert\n");
				_aligned_free(nextAnnounceOp);
				return 0;
			}
		}
		else if(curAnnouncedOp->opName==INSERT)
		{
			InsertHelper(curAnnouncedOp);
		}
		else if(curAnnouncedOp->opName==DELET)
		{
			DeleteHelper(curAnnouncedOp);
		}
	}
label:
	_aligned_free(nextAnnounceOp);
	return 0;
}

Listing 1

The second part of Insert operation (see Listing2) tries to link the new node by performing the CAS on x->rlink followed by another CAS which tries to link the new node by performing the CAS on x->rlink->llink. Finally a CAS which tries to announce the operation as complete.

//Second part of insert
void InsertHelper(AnnounceOp *curAnnouncedOp)
{	
	//set x's right link to node p (newly created node)
	InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->insert.lv.x_rlink_address),(LONG)curAnnouncedOp->insert.args.p,(LONG)curAnnouncedOp->insert.lv.x_rlink);
	//set the left pointer of node next to x to point to p
	InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->insert.lv.x_rlink_llink_address),(LONG)curAnnouncedOp->insert.args.p,(LONG)curAnnouncedOp->insert.lv.x_rlink_llink);	
	//To announce that insert operation is complete.
	AnnounceOp *nextAnnounceOp=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign );
	assert(nextAnnounceOp);
	nextAnnounceOp->opName=NONE;
	void *v1=reinterpret_cast<void>(nextAnnounceOp);
	void *v2=reinterpret_cast<void>(curAnnouncedOp);
	if(InterlockedCompareExchange(reinterpret_cast<volatile>(&l.announce),(LONG)v1,(LONG)v2)==(LONG)v2)
	{
		//RetireNode(v2);
	}
	else
	{
		_aligned_free(nextAnnounceOp);
	}
}

Listing 2

In case of deletion, we cannot simply set the rlink pointer of predecessor of node to its successor because it can result in ABA problem. Suppose a thread T1 inserts a node B after A and before C. Some other thread T2 was helping that insertion but before linking B it was preempted. Now, another thread T3 comes and deletes B. Finally, thread T2 resumes helping and links the deleted node again (see Fig 1).

Figure 1

One solution to this problem is when deletion is performed the predecessor and successor of node is replaced, so in the given scenario A will be replaced by A1 and deleted node will not be linked by A1.

Now we come to the second part of Delete operation (see Listing 3). The second part of Delete operation replaces node predecessor and successor with the copy created in first part and tries to mark the deleted node, its predecessors and successor as indeed deleted from the linked list by setting their rlink and llink pointers to 0 using CAS. Finally this is followed by another CAS to announce the operation as complete.

//Second part of delete
void DeleteHelper(AnnounceOp *curAnnouncedOp)
{
	//replace 2 nodes around x including x with two new nodes
	InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->del.lv.x_llink_llink_rlink_address),(LONG)curAnnouncedOp->del.lv.replacement_x_llink,(LONG)curAnnouncedOp->del.lv.x_llink_llink_rlink);
	InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->del.lv.x_rlink_rlink_llink_address),(LONG)curAnnouncedOp->del.lv.replacement_x_rlink,(LONG)curAnnouncedOp->del.lv.x_rlink_rlink_llink);
	//Set 3 retired nodes pointer fields to 0
	InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->del.lv.x_llink_llink_address),(LONG)0,(LONG)curAnnouncedOp->del.lv.x_llink_llink);
	InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->del.lv.x_llink_rlink_address),(LONG)0,(LONG)curAnnouncedOp->del.lv.x_llink_rlink);
	InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->del.lv.x_rlink_rlink_address),(LONG)0,(LONG)curAnnouncedOp->del.lv.x_rlink_rlink);
	InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->del.lv.x_rlink_llink_address),(LONG)0,(LONG)curAnnouncedOp->del.lv.x_rlink_llink);
	InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->del.lv.x_llink_address),(LONG)0,(LONG)curAnnouncedOp->del.lv.x_llink);
	if(InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->del.lv.x_rlink_address),(LONG)0,(LONG)curAnnouncedOp->del.lv.x_rlink)==(LONG)curAnnouncedOp->del.lv.x_rlink)
	{
		//RetireNode(x);
		//RetireNode(curAnnouncedOp->del.lv.x_llink);
		//RetireNode(curAnnouncedOp->del.lv.x_rlink);
	}
	//To announce that delete operation is complete.
	AnnounceOp *nextAnnounceOp=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign );
	assert(nextAnnounceOp);
	nextAnnounceOp->opName=NONE;
	void *v1=reinterpret_cast<void *>(nextAnnounceOp);
	void *v2=reinterpret_cast<void *>(curAnnouncedOp);
	if(InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(&l.announce),(LONG)v1,(LONG)v2)==(LONG)v2)
	{
		//RetireNode(curAnnouncedOp);
	}
	else
	{
		_aligned_free(nextAnnounceOp);
	}
}

Listing 3

Correctness

The intuition behind the proof is that once a thread T1 is successful in announcing an operation, it is guaranteed that its operation will complete within next bounded number of steps that the system takes. Each time an iterations of while 1 loop in the insert and delete operation is taken, some thread successfully makes progress towards completing an operation. The insert and delete operations on the list are linearized by successful CAS in their respective first parts. The last thing to show is that the writes to shared locations in the data structure are performed in the same order as in the corresponding sequential implementation. It follows from the fact that a successful InterlockedCompareExchange by insert or delete operation on linked list instance.AnnounceOp guarantees that the writes to the variables in AnnounceOp structure are valid but the writes to the rest of the shared variables need more attention because of ABA problems. In the case of lock free doubly linked list, we have tackled the issue by replacing the predecessor and successor of the node to be deleted. This ensures that a node’s rlink and llink field will never be the same again until no thread has hazardous [Michael 2004] reference to it. In a garbage-collected environment, memory reclamation is automatic. Without garbage collection, however, we need to be care full in reclaiming memory because it can give rise to dangling reference (a reference to a reclaimed memory cell). We assume that Hazard Pointers [Michael 2004] will be used for safe memory reclamation. The hazard pointer methodology at an abstract level is that a thread sets a global (hazard) pointer equal to a shared pointers value before using this value in ABA prone com-parison And make sure that when the value of the shared pointer is set to a new value using CAS then that value is not among those values that shared pointer previously attained and a hazard pointer has that value. This ensures that if a thread has set a hazard pointer to the value of a shared pointer then that value cannot be involved in an ABA prone comparison because the function that calculates the new value of shared pointer will not return that value. We have applied the hazard pointer methodology to lock free doubly linked list. You can see hazard pointers and RetireNode function in comments. please read[Michael 2004] for further details.

Informally, every operation in the lock free doubly linked list takes effect when the final CAS announces the operation as complete. This implies that every operation in the lockfree doubly linked list takes effect instantaneously at some point between invocation and response, so linearizability simply follows from it. The doubly linked list is lock-free because an announced operation makes progress by attempting CAS operations. A successful CAS takes the operation one step closer to completion. And an unsuccessful CAS means the operation has already made progress. In this way a announced operation will take finite number of CAS to complete.

Experimental Evaluation

Performance tests were performed on an Intel(R) Core(TM) i3-2310M CPU @ 2.10GHz 2.10 GHz with 3 GB of RAM. The operating system used was Windows 7 Professional. We ran the performance tests when no other users used the system

In this section we present performance results of [Håkan Sundell 2008] and proposed doubly Linked List. The experiment was carried out by varying the following parameters:

  • Number of threads vary from 1 to 16 (plotted on x-axis)
  • Every thread performed 15000 or 30000 insertions call it O where O equals 15000 or 30000
  • Every thread performed 15000 or 30000 deletions
  • One time out of 10 or 50 or 90 we select to break the traversal and perform insertion or deletion. Call it T where T equals 10 or 50 or 90

When one out of ten times we choose to break traversal, this means that most of the time we are inserting or deleting nodes. In that case, [Håkan Sundell 2008] performs better. (see Appendix A) On the other hand, when one out of fifty times we choose to break traversal, this means that most of the time we are traversing nodes. In that case, proposed doubly linked list performs better than[Håkan Sundell 2008] (see Appendix A). The graph shows that the proposed doubly linked list performs two times faster than[Håkan Sundell 2008]. The reason behind is that traversal functions exposed by [Håkan Sundell 2008]performs slow. When T=90, then more time is spend in traversal, therefore [Håkan Sundell 2008] performance degrades

Summary

This article presents second lock free doubly linked list (first by [Håkan Sundell 2008])which uses available atomic primitive(CAS).

We have performed experiments that compare our doubly linked list with [Håkan Sundell 2008]. The experiments show that our implementation performs significantly better in situations where most of the time doubly linked list is traversed.

Reference 

  • [Michael 2004]Michael, M.M. “Hazard pointers: Safe memory reclamation for lock-free objects,” IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 8, Aug. 2004.
  • [Valois 95] J. D. Valois, “Lock-free data structures,” Ph.D. dissertation, Rensselaer Polytechnic Institute, Troy, New York, 1995.
  • [Greenwald99] M. Greenwald, “Non-blocking synchronization and system design,” Ph.D. dissertation, Stanford University, Palo Alto, CA, 1999.
  • [Håkan Sundell 2008]Håkan Sundell, Philippas TsigasLock-free deques and doubly linked lists, PDC 2008

Appendix A

X-axis:No of Threads

Y-axis:Time(seconds)

Figure 2 T=10 O= 150000

Figure 3 T=10 O=30000

Figure 4 T=50 O=15000

Figure 5 T=50 O=30000

Figure 6 T=90 O=15000

Appendix B

int Delete(Node *x)
{
	if(x==0) return 0;
	AnnounceOp *curAnnouncedOp;
	AnnounceOp *nextAnnounceOp=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign );//new AnnounceOp;//To announce a delete operation.
	assert(nextAnnounceOp);
	Node *replacement_x_llink=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign );//new Node;
	assert(replacement_x_llink);
	Node *replacement_x_rlink=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign );//new Node;
	assert(replacement_x_rlink);
	while(1)
	{
		curAnnouncedOp=(AnnounceOp *)l.announce;		
		AnnounceOp *hp0=curAnnouncedOp;
		if(curAnnouncedOp!=l.announce) continue;
		if(curAnnouncedOp->opName==NONE)
		{	
			try
			{
				if(l.first==x||l.end==x||l.first->rlink==x||l.end->llink==x) //check x is not one of the four dummy nodes
				{
					_aligned_free(nextAnnounceOp);
					_aligned_free(replacement_x_llink);
					_aligned_free(replacement_x_rlink);
					return 0;
				}
				//set Delete as the next operation
				nextAnnounceOp->opName=DELET;
				nextAnnounceOp->del.args.x=x;
				
				nextAnnounceOp->del.lv.x_llink=x->llink;//announce the value of x->llink to be used in CAS
				Node *hp1=nextAnnounceOp->del.lv.x_llink;//set hazard pointer
				if(nextAnnounceOp->del.lv.x_llink!=x->llink||nextAnnounceOp->del.lv.x_llink==0) goto label1;//check hazard pointer is set accurately and x->llink is not zero
				nextAnnounceOp->del.lv.x_llink_address=&x->llink;//announce the address of x->llink to be used in CAS
				
				//Following statements are on the same pattern as above i.e. announce the value of variable
				//set hazard pointer. check hazard pointer is set accurately. Announce the address of that variable

				nextAnnounceOp->del.lv.x_rlink=x->rlink;
				Node *hp2=nextAnnounceOp->del.lv.x_rlink;
				if(nextAnnounceOp->del.lv.x_rlink!=x->rlink||nextAnnounceOp->del.lv.x_rlink==0)  goto label1;
				nextAnnounceOp->del.lv.x_rlink_address=&x->rlink;
				
				nextAnnounceOp->del.lv.x_llink_rlink=nextAnnounceOp->del.lv.x_llink->rlink;
				Node *hp3=nextAnnounceOp->del.lv.x_llink_rlink;
				if(nextAnnounceOp->del.lv.x_llink_rlink!=nextAnnounceOp->del.lv.x_llink->rlink||nextAnnounceOp->del.lv.x_llink_rlink==0)  goto label1;
				nextAnnounceOp->del.lv.x_llink_rlink_address=&nextAnnounceOp->del.lv.x_llink->rlink;
				
				nextAnnounceOp->del.lv.x_rlink_llink=nextAnnounceOp->del.lv.x_rlink->llink;
				Node *hp4=nextAnnounceOp->del.lv.x_rlink_llink;
				if(nextAnnounceOp->del.lv.x_rlink_llink!=nextAnnounceOp->del.lv.x_rlink->llink||nextAnnounceOp->del.lv.x_rlink_llink==0)  goto label1;
				nextAnnounceOp->del.lv.x_rlink_llink_address=&nextAnnounceOp->del.lv.x_rlink->llink;

				nextAnnounceOp->del.lv.x_rlink_rlink=nextAnnounceOp->del.lv.x_rlink->rlink;
				Node *hp5=nextAnnounceOp->del.lv.x_rlink_rlink;
				if(nextAnnounceOp->del.lv.x_rlink_rlink!=nextAnnounceOp->del.lv.x_rlink->rlink||nextAnnounceOp->del.lv.x_rlink_rlink==0)  goto label1;
				nextAnnounceOp->del.lv.x_rlink_rlink_address=&nextAnnounceOp->del.lv.x_rlink->rlink;				
				
				nextAnnounceOp->del.lv.x_llink_llink=nextAnnounceOp->del.lv.x_llink->llink;
				Node *hp6=nextAnnounceOp->del.lv.x_llink_llink;
				if(nextAnnounceOp->del.lv.x_llink_llink!=nextAnnounceOp->del.lv.x_llink->llink||nextAnnounceOp->del.lv.x_llink_llink==0)  goto label1;
				nextAnnounceOp->del.lv.x_llink_llink_address=&nextAnnounceOp->del.lv.x_llink->llink;
			
				nextAnnounceOp->del.lv.x_llink_llink_rlink=nextAnnounceOp->del.lv.x_llink_llink->rlink;
				Node *hp7=nextAnnounceOp->del.lv.x_llink_llink_rlink;
				if(nextAnnounceOp->del.lv.x_llink_llink_rlink!=nextAnnounceOp->del.lv.x_llink_llink->rlink||nextAnnounceOp->del.lv.x_llink_llink_rlink==0)  goto label1;
				nextAnnounceOp->del.lv.x_llink_llink_rlink_address=&nextAnnounceOp->del.lv.x_llink_llink->rlink;

				nextAnnounceOp->del.lv.x_rlink_rlink_llink=nextAnnounceOp->del.lv.x_rlink_rlink->llink;
				Node *hp8=nextAnnounceOp->del.lv.x_rlink_rlink_llink;
				if(nextAnnounceOp->del.lv.x_rlink_rlink_llink!=nextAnnounceOp->del.lv.x_rlink_rlink->llink||nextAnnounceOp->del.lv.x_rlink_rlink_llink==0)  goto label1;
				nextAnnounceOp->del.lv.x_rlink_rlink_llink_address=&nextAnnounceOp->del.lv.x_rlink_rlink->llink;
			
				nextAnnounceOp->del.lv.replacement_x_llink=replacement_x_llink;//announce the replacement for the node left to x
				nextAnnounceOp->del.lv.replacement_x_rlink=replacement_x_rlink;//announce the replacement for the node right to x
				replacement_x_llink->data=nextAnnounceOp->del.lv.x_llink->data;//copy data
				replacement_x_rlink->data=nextAnnounceOp->del.lv.x_rlink->data;//copy data
				//build the chain 
	//x_llink_llink//replacement_x_llink//replacement_x_rlink//x_rlink_rlink
	//	---------	-------             --------               -------
	//	|		|	|	   |-----------|        |              |      |
	//	|		|===|      |===========|        |==============|      |
	//	 -------	-------             --------                -------
				replacement_x_llink->rlink=replacement_x_rlink;
				replacement_x_llink->llink=nextAnnounceOp->del.lv.x_llink_llink;
				replacement_x_rlink->llink=replacement_x_llink;
				replacement_x_rlink->rlink=nextAnnounceOp->del.lv.x_rlink_rlink;//x->rlink->rlink;

				//check addresses has not changed
				/*if(nextAnnounceOp->del.lv.x_llink_address!=&x->llink) goto label1;
				if(nextAnnounceOp->del.lv.x_rlink_address!=&x->rlink)  goto label1;
				if(nextAnnounceOp->del.lv.x_llink_rlink_address!=&x->llink->rlink)  goto label1;
				if(nextAnnounceOp->del.lv.x_rlink_llink_address!=&x->rlink->llink)  goto label1;
				if(nextAnnounceOp->del.lv.x_rlink_rlink_address!=&x->rlink->rlink)  goto label1;
				if(nextAnnounceOp->del.lv.x_llink_llink_address!=&x->llink->llink)  goto label1;
				if(nextAnnounceOp->del.lv.x_llink_llink_rlink_address!=&x->llink->llink->rlink)  goto label1;
				if(nextAnnounceOp->del.lv.x_rlink_rlink_llink_address!=&x->rlink->rlink->llink)  goto label1;*/

				//To announce the start of delete operation.
				void *v1=reinterpret_cast<void *>(nextAnnounceOp);
				void *v2=reinterpret_cast<void *>(curAnnouncedOp);
				void *res=(void *)InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(&l.announce),(LONG)v1,(LONG)v2);
				if(res==v2)
				{
					//RetireNode(curAnnouncedOp);
					DeleteHelper(nextAnnounceOp);
					return 1;
				}
			}
			catch(...)
			{
				printf("Exception in Delete\n");
				_aligned_free(nextAnnounceOp);
				_aligned_free(replacement_x_llink);
				_aligned_free(replacement_x_rlink);
				return 0;
			}
		}
		else if(curAnnouncedOp->opName==INSERT)
		{
			InsertHelper(curAnnouncedOp);
		}
		else if(curAnnouncedOp->opName==DELET)
		{
			DeleteHelper(curAnnouncedOp);
		}
	}
label1:
	_aligned_free(nextAnnounceOp);
	_aligned_free(replacement_x_llink);
	_aligned_free(replacement_x_rlink);
	return 0;
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

SarmadAsghar
Team Leader VF
Pakistan Pakistan
No Biography provided

You may also be interested in...

Comments and Discussions

 
NewsSafe Memory Reclamation Next Part of this article Pin
SarmadAsghar7-Feb-15 1:17
professionalSarmadAsghar7-Feb-15 1:17 
QuestionComments reply Pin
SarmadAsghar11-Feb-14 4:52
professionalSarmadAsghar11-Feb-14 4:52 
QuestionFew comments Pin
waleri9-Feb-14 21:57
memberwaleri9-Feb-14 21:57 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.170915.1 | Last Updated 12 Feb 2014
Article Copyright 2014 by SarmadAsghar
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid