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 :
struct Insert
{
struct Arguments
{
Node *p; Node *x; }args;
struct LocalVariables
{
Node *x_rlink_llink; Node **x_rlink_llink_address; Node *x_rlink; Node **x_rlink_address; }lv;
};
struct Delete
{
struct Arguments
{
Node *x; }args;
struct LocalVariables
{
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; Node *replacement_x_rlink; }lv;
};
enum OperationName
{
NONE,INSERT,DELET
};
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; Node *first; Node *end;};
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()
{
l.announce=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign ); assert(l.announce);
l.announce->opName=NONE;
l.first=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign ); 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.
int Insert(Node *p,Node *x)
{
if(p==0||x==0) return 0;
AnnounceOp *curAnnouncedOp;
AnnounceOp *nextAnnounceOp=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign ); 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) {
_aligned_free(nextAnnounceOp);
return 0;
}
p->llink=x; p->rlink=x->rlink; if(p->rlink==0||p->llink==0) goto label;
nextAnnounceOp->opName=INSERT; nextAnnounceOp->insert.args.p=p;
nextAnnounceOp->insert.args.x=x;
nextAnnounceOp->insert.lv.x_rlink=x->rlink;
if(nextAnnounceOp->insert.lv.x_rlink==0) goto label; Node *hp2=nextAnnounceOp->insert.lv.x_rlink; if(x->rlink!=nextAnnounceOp->insert.lv.x_rlink) goto label; nextAnnounceOp->insert.lv.x_rlink_address=&x->rlink;
nextAnnounceOp->insert.lv.x_rlink_llink=nextAnnounceOp->insert.lv.x_rlink->llink;
if(nextAnnounceOp->insert.lv.x_rlink_llink==0) goto label; Node *hp1=nextAnnounceOp->insert.lv.x_rlink_llink; if(nextAnnounceOp->insert.lv.x_rlink->llink!=nextAnnounceOp->insert.lv.x_rlink_llink) goto label; nextAnnounceOp->insert.lv.x_rlink_llink_address=&nextAnnounceOp->insert.lv.x_rlink->llink;
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)
{
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.
void InsertHelper(AnnounceOp *curAnnouncedOp)
{
InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->insert.lv.x_rlink_address),(LONG)curAnnouncedOp->insert.args.p,(LONG)curAnnouncedOp->insert.lv.x_rlink);
InterlockedCompareExchange(reinterpret_cast<volatile>(curAnnouncedOp->insert.lv.x_rlink_llink_address),(LONG)curAnnouncedOp->insert.args.p,(LONG)curAnnouncedOp->insert.lv.x_rlink_llink);
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)
{
}
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.
void DeleteHelper(AnnounceOp *curAnnouncedOp)
{
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);
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)
{
}
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)
{
}
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 ); assert(nextAnnounceOp);
Node *replacement_x_llink=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign ); assert(replacement_x_llink);
Node *replacement_x_rlink=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign ); 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) {
_aligned_free(nextAnnounceOp);
_aligned_free(replacement_x_llink);
_aligned_free(replacement_x_rlink);
return 0;
}
nextAnnounceOp->opName=DELET;
nextAnnounceOp->del.args.x=x;
nextAnnounceOp->del.lv.x_llink=x->llink; Node *hp1=nextAnnounceOp->del.lv.x_llink; if(nextAnnounceOp->del.lv.x_llink!=x->llink||nextAnnounceOp->del.lv.x_llink==0) goto label1; nextAnnounceOp->del.lv.x_llink_address=&x->llink;
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; nextAnnounceOp->del.lv.replacement_x_rlink=replacement_x_rlink; replacement_x_llink->data=nextAnnounceOp->del.lv.x_llink->data; replacement_x_rlink->data=nextAnnounceOp->del.lv.x_rlink->data; 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;
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)
{
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;
}
