(defstruct (queue (:constructor %make-queue (head tail name))
(:copier nil)
(:predicate queuep))
- "Lock-free thread safe queue."
+ "Lock-free thread safe FIFO queue.
+
+Use ENQUEUE to add objects to the queue, and DEQUEUE to remove them."
(head (error "No HEAD.") :type node)
(tail (error "No TAIL.") :type node)
(name nil))
(tail (queue-tail queue))
(first-node-prev (node-prev head))
(val (node-value head)))
+ (barrier (:read))
(when (eq head (queue-head queue))
(cond ((not (eq val +dummy+))
(if (eq tail head)
(go :continue)))
(when (eq head (sb-ext:compare-and-swap (queue-head queue)
head first-node-prev))
- ;; This assignment is not present in the paper, but is
- ;; equivalent to the free(head.ptr) call there: it unlinks
- ;; the HEAD from the queue -- the code in the paper leaves
- ;; the dangling pointer in place.
- (setf (node-next first-node-prev) nil)
+ ;; These assignment is not present in the paper, but are
+ ;; equivalent to the free(head.ptr) call there.
+ ;;
+ ;; First we unlink the HEAD from the queue -- the code in
+ ;; the paper leaves the dangling pointer in place.
+ ;;
+ ;; Then we NIL out the slots in HEAD to help the GC,
+ ;; otherwise conservativism might lead to massive chains of
+ ;; nodes being retained.
+ (setf (node-next first-node-prev) nil
+ (node-prev head) nil
+ (node-next head) nil
+ (node-value head) nil)
(return-from dequeue (values val t))))
((eq tail head)
(return-from dequeue (values nil nil)))
(defun list-queue-contents (queue)
"Returns the contents of QUEUE as a list without removing them from the
-QUEUE. Mainly useful for manual examination of queue state."
+QUEUE. Mainly useful for manual examination of queue state, as the list
+may be out of date by the time it is returned."
(let (all)
(labels ((walk (node)
;; Since NEXT pointers are always right, traversing from tail
(defun queue-count (queue)
"Returns the number of objects in QUEUE. Mainly useful for manual
examination of queue state, and in PRINT-OBJECT methods: inefficient as it
-walks the entire queue."
+must walk the entire queue."
(let ((n 0))
(declare (unsigned-byte n))
(labels ((walk (node)