diff options
Diffstat (limited to 'fibers')
| -rw-r--r-- | fibers/channels.scm | 49 | ||||
| -rw-r--r-- | fibers/deque.scm | 76 |
2 files changed, 77 insertions, 48 deletions
diff --git a/fibers/channels.scm b/fibers/channels.scm index 8a54f61..c37cac9 100644 --- a/fibers/channels.scm +++ b/fibers/channels.scm @@ -31,6 +31,7 @@ #:use-module (srfi srfi-9 gnu) #:use-module (ice-9 atomic) #:use-module (ice-9 match) + #:use-module (fibers deque) #:use-module (fibers internal) #:use-module (fibers operations) #:export (make-channel @@ -39,54 +40,6 @@ put-message get-message)) - -;; A functional double-ended queue ("deque") has a head and a tail, -;; which are both lists. The head is in FIFO order and the tail is in -;; LIFO order. -(define-inlinable (make-deque head tail) - (cons head tail)) - -(define (make-empty-deque) - (make-deque '() '())) - -(define (enqueue dq item) - (match dq - ((head . tail) - (make-deque head (cons item tail))))) - -(define (undequeue dq item) - (match dq - ((head . tail) - (make-deque (cons item head) tail)))) - -;; -> new deque, val | #f, #f -(define (dequeue dq) - (match dq - ((() . ()) (values #f #f)) - ((() . tail) - (dequeue (make-deque (reverse tail) '()))) - (((item . head) . tail) - (values (make-deque head tail) item)))) - -(define (dequeue-match dq pred) - (match dq - ((() . ()) (values #f #f)) - ((() . tail) - (dequeue (make-deque (reverse tail) '()))) - (((item . head) . tail) - (if (pred item) - (values (make-deque head tail) item) - (call-with-values (dequeue-match (make-deque head tail) pred) - (lambda (dq item*) - (values (undequeue dq item) item*))))))) - -(define (enqueue! qbox item) - (let spin ((q (atomic-box-ref qbox))) - (let* ((q* (enqueue q item)) - (q** (atomic-box-compare-and-swap! qbox q q*))) - (unless (eq? q q**) - (spin q**))))) - (define-record-type <channel> (%make-channel getq putq) channel? diff --git a/fibers/deque.scm b/fibers/deque.scm new file mode 100644 index 0000000..309072b --- /dev/null +++ b/fibers/deque.scm @@ -0,0 +1,76 @@ +;; Double-ended queue + +;;;; Copyright (C) 2016 Andy Wingo <wingo@pobox.com> +;;;; +;;;; This library is free software; you can redistribute it and/or +;;;; modify it under the terms of the GNU Lesser General Public +;;;; License as published by the Free Software Foundation; either +;;;; version 3 of the License, or (at your option) any later version. +;;;; +;;;; This library is distributed in the hope that it will be useful, +;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of +;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +;;;; Lesser General Public License for more details. +;;;; +;;;; You should have received a copy of the GNU Lesser General Public +;;;; License along with this library; if not, write to the Free Software +;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + +(define-module (fibers deque) + #:use-module (srfi srfi-9) + #:use-module (ice-9 atomic) + #:use-module (ice-9 match) + #:export (make-deque + make-empty-deque + enqueue + dequeue + dequeue-match + undequeue + enqueue!)) + +;; A functional double-ended queue ("deque") has a head and a tail, +;; which are both lists. The head is in FIFO order and the tail is in +;; LIFO order. +(define-inlinable (make-deque head tail) + (cons head tail)) + +(define (make-empty-deque) + (make-deque '() '())) + +(define (enqueue dq item) + (match dq + ((head . tail) + (make-deque head (cons item tail))))) + +;; -> new deque, val | #f, #f +(define (dequeue dq) + (match dq + ((() . ()) (values #f #f)) + ((() . tail) + (dequeue (make-deque (reverse tail) '()))) + (((item . head) . tail) + (values (make-deque head tail) item)))) + +(define (dequeue-match dq pred) + (match dq + ((() . ()) (values #f #f)) + ((() . tail) + (dequeue (make-deque (reverse tail) '()))) + (((item . head) . tail) + (if (pred item) + (values (make-deque head tail) item) + (call-with-values (dequeue-match (make-deque head tail) pred) + (lambda (dq item*) + (values (undequeue dq item) item*))))))) + +(define (undequeue dq item) + (match dq + ((head . tail) + (make-deque (cons item head) tail)))) + +(define (enqueue! qbox item) + (let spin ((q (atomic-box-ref qbox))) + (let* ((q* (enqueue q item)) + (q** (atomic-box-compare-and-swap! qbox q q*))) + (unless (eq? q q**) + (spin q**))))) |
