1 ;;;; Lock-free FIFO queues, from "An Optimistic Approach to Lock-Free FIFO
2 ;;;; Queues" by Edya Ladan-Mozes and Nir Shavit.
4 ;;;; Written by Nikodemus Siivola for SBCL.
6 ;;;; This software is part of the SBCL system. See the README file for
9 ;;;; This software is derived from the CMU CL system, which was written at
10 ;;;; Carnegie Mellon University and released into the public domain. The
11 ;;;; software is in the public domain and is provided with absolutely no
12 ;;;; warranty. See the COPYING and CREDITS files for more information.
15 (:use
:cl
:sb-thread
:sb-sys
:sb-ext
)
27 (in-package :sb-queue
)
29 (defconstant +dummy
+ '.dummy.
)
31 (declaim (inline make-node
))
34 (prev nil
:type
(or null node
))
35 (next nil
:type
(or null node
)))
37 (declaim (inline %make-queue
))
38 (defstruct (queue (:constructor %make-queue
(head tail name
))
41 "Lock-free thread safe queue. ENQUEUE can be used to add objects to the queue,
42 and DEQUEUE retrieves items from the queue in FIFO order."
43 (head (error "No HEAD.") :type node
)
44 (tail (error "No TAIL.") :type node
)
47 (setf (documentation 'queuep
'function
)
48 "Returns true if argument is a QUEUE, NIL otherwise."
49 (documentation 'queue-name
'function
)
50 "Name of a QUEUE. Can be assingned to using SETF. Queue names
51 can be arbitrary printable objects, and need not be unique.")
53 (defun make-queue (&key name initial-contents
)
54 "Returns a new QUEUE with NAME and contents of the INITIAL-CONTENTS
56 (let* ((dummy (make-node :value
+dummy
+))
57 (queue (%make-queue dummy dummy name
)))
60 (declare (dynamic-extent #'enc-1
))
61 (map nil
#'enc-1 initial-contents
))
64 (defun enqueue (value queue
)
65 "Adds VALUE to the end of QUEUE. Returns VALUE."
66 (let ((node (make-node :value value
)))
67 (loop for tail
= (queue-tail queue
)
68 do
(setf (node-next node
) tail
)
69 (when (eq tail
(sb-ext:compare-and-swap
(queue-tail queue
) tail node
))
70 (setf (node-prev tail
) node
)
73 (defun dequeue (queue)
74 "Retrieves the oldest value in QUEUE and returns it as the primary value,
75 and T as secondary value. If the queue is empty, returns NIL as both primary
79 (let* ((head (queue-head queue
))
80 (tail (queue-tail queue
))
81 (first-node-prev (node-prev head
))
82 (val (node-value head
)))
83 (when (eq head
(queue-head queue
))
84 (cond ((not (eq val
+dummy
+))
86 (let ((dummy (make-node :value
+dummy
+ :next tail
)))
87 (when (eq tail
(sb-ext:compare-and-swap
(queue-tail queue
)
89 (setf (node-prev head
) dummy
))
91 (when (null first-node-prev
)
92 (fixList queue tail head
)
94 (when (eq head
(sb-ext:compare-and-swap
(queue-head queue
)
95 head first-node-prev
))
96 ;; This assignment is not present in the paper, but is
97 ;; equivalent to the free(head.ptr) call there: it unlinks
98 ;; the HEAD from the queue -- the code in the paper leaves
99 ;; the dangling pointer in place.
100 (setf (node-next first-node-prev
) nil
)
101 (return-from dequeue
(values val t
))))
103 (return-from dequeue
(values nil nil
)))
104 ((null first-node-prev
)
105 (fixList queue tail head
)
108 (sb-ext:compare-and-swap
(queue-head queue
)
109 head first-node-prev
)))))
112 (defun fixlist (queue tail head
)
113 (let ((current tail
))
114 (loop while
(and (eq head
(queue-head queue
)) (not (eq current head
)))
115 do
(let ((next (node-next current
)))
117 (return-from fixlist nil
))
118 (let ((nextNodePrev (node-prev next
)))
119 (when (not (eq nextNodePrev current
))
120 (setf (node-prev next
) current
))
121 (setf current next
))))))
123 (defun list-queue-contents (queue)
124 "Returns the contents of QUEUE as a list without removing them from the
125 QUEUE. Mainly useful for manual examination of queue state."
127 (labels ((walk (node)
128 ;; Since NEXT pointers are always right, traversing from tail
130 (let ((value (node-value node
))
131 (next (node-next node
)))
132 (unless (eq +dummy
+ value
)
136 (walk (queue-tail queue
)))
139 (defun queue-count (queue)
140 "Returns the number of objects in QUEUE. Mainly useful for manual
141 examination of queue state, and in PRINT-OBJECT methods: inefficient as it
142 walks the entire queue."
144 (declare (unsigned-byte n
))
145 (labels ((walk (node)
146 (let ((value (node-value node
))
147 (next (node-next node
)))
148 (unless (eq +dummy
+ value
)
152 (walk (queue-tail queue
))
155 (defun queue-empty-p (queue)
156 "Returns T if QUEUE is empty, NIL otherwise."
157 (let* ((head (queue-head queue
))
158 (tail (queue-tail queue
))
159 (val (node-value head
)))
160 (and (eq head tail
) (eq val
+dummy
+))))