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
32
33
34
35
36
37
38
39
40
41
42
43
typedef struct node_t {
	TYPE value;
	node_t *next
} NODE;

typedef struct queue_t {
	NODE *head;
	NODE *tail;
	LOCK q_h_lock;
	LOCK q_t_lock;
} Q;

initialize(Q *q) {
   node = new_node()   // Allocate a free node
   node->next = NULL   // Make it the only node in the linked list
   q->head = q->tail = node   // Both head and tail point to it
   q->q_h_lock = q->q_t_lock = FREE   // Locks are initially free
}

enqueue(Q *q, TYPE value) {
   node = new_node()       // Allocate a new node from the free list
   node->value = value     // Copy enqueued value into node
   node->next = NULL       // Set next pointer of node to NULL
   lock(&q->q_t_lock)      // Acquire t_lock in order to access Tail
	  q->tail->next = node // Link node at the end of the queue
	  q->tail = node       // Swing Tail to node
   unlock(&q->q_t_lock)    // Release t_lock
｝

dequeue(Q *q, TYPE *pvalue) {
   lock(&q->q_h_lock)   // Acquire h_lock in order to access Head
	  node = q->head    // Read Head
	  new_head = node->next       // Read next pointer
	  if new_head == NULL         // Is queue empty?
		 unlock(&q->q_h_lock)     // Release h_lock before return
		 return FALSE             // Queue was empty
	  endif
	  *pvalue = new_head->value   // Queue not empty, read value
	  q->head = new_head  // Swing Head to next node
   unlock(&q->q_h_lock)   // Release h_lock
   free(node)             // Free node
   return TRUE            // Queue was not empty, dequeue succeeded
}

1
2
3
4
5
6
7
8
9
10
template <typename T>
bool CompareAndSwap(T* dest, T oldValue, T newValue)
{
  if (*dest == oldValue)
  {
	*dest = newValue;
	return true;
  }
  return false;
}

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
structure pointer_t {ptr: pointer to node_t, count: unsigned integer}
  structure node_t {value: data type, next: pointer_t}
  structure queue_t {Head: pointer_t, Tail: pointer_t}

  initialize(Q: pointer to queue_t)
	 node = new_node()		// Allocate a free node
	 node->next.ptr = NULL	// Make it the only node in the linked list
	 Q->Head.ptr = Q->Tail.ptr = node	// Both Head and Tail point to it

  enqueue(Q: pointer to queue_t, value: data type)
   E1:   node = new_node()	// Allocate a new node from the free list
   E2:   node->value = value	// Copy enqueued value into node
   E3:   node->next.ptr = NULL	// Set next pointer of node to NULL
   E4:   loop			// Keep trying until Enqueue is done
   E5:      tail = Q->Tail	// Read Tail.ptr and Tail.count together
   E6:      next = tail.ptr->next	// Read next ptr and count fields together
   E7:      if tail == Q->Tail	// Are tail and next consistent?
			   // Was Tail pointing to the last node?
   E8:         if next.ptr == NULL
				  // Try to link node at the end of the linked list
   E9:            if CAS(&tail.ptr->next, next, <node, next.count%2B1>)
  E10:               break	// Enqueue is done.  Exit loop
  E11:            endif
  E12:         else		// Tail was not pointing to the last node
				  // Try to swing Tail to the next node
  E13:            CAS(&Q->Tail, tail, <next.ptr, tail.count%2B1>)
  E14:         endif
  E15:      endif
  E16:   endloop
		 // Enqueue is done.  Try to swing Tail to the inserted node
  E17:   CAS(&Q->Tail, tail, <node, tail.count%2B1>)

  dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
   D1:   loop			     // Keep trying until Dequeue is done
   D2:      head = Q->Head	     // Read Head
   D3:      tail = Q->Tail	     // Read Tail
   D4:      next = head.ptr->next    // Read Head.ptr->next
   D5:      if head == Q->Head	     // Are head, tail, and next consistent?
   D6:         if head.ptr == tail.ptr // Is queue empty or Tail falling behind?
   D7:            if next.ptr == NULL  // Is queue empty?
   D8:               return FALSE      // Queue is empty, couldn't dequeue
   D9:            endif
				  // Tail is falling behind.  Try to advance it
  D10:            CAS(&Q->Tail, tail, <next.ptr, tail.count%2B1>)
  D11:         else		     // No need to deal with Tail
				  // Read value before CAS
				  // Otherwise, another dequeue might free the next node
  D12:            *pvalue = next.ptr->value
				  // Try to swing Head to the next node
  D13:            if CAS(&Q->Head, head, <next.ptr, head.count%2B1>)
  D14:               break             // Dequeue is done.  Exit loop
  D15:            endif
  D16:         endif
  D17:      endif
  D18:   endloop
  D19:   free(head.ptr)		     // It is safe now to free the old node
  D20:   return TRUE                   // Queue was not empty, dequeue succeeded