Debian Codegraph @

ext/data/queue.scm

raw
1 ;;;
2 ;;; data.queue - queue (fifo) implementation
3 ;;;
4 ;;; Copyright (c) 2010-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 ;; Originally implemented as util.queue; since it is an implementation
35 ;; of a data structure, we renamed it to data.queue.
36 ;;
37 ;; This module supports <queue>, which is fast but not thread-safe,
38 ;; and <mtqueue>, thread-safe queue that can also be used as a fundamental
39 ;; block of multi-thread synchronization.
40 ;;
41 ;; For mt-queue, we use layered mutex; C-level mutex and a Scheme slot
42 ;; that keeps the locker. For lightweight atomic operations such as
43 ;; enqueue!, we just do the job while holding C-level mutex. However,
44 ;; if we need to call back to Scheme while holding a lock, it is dangerous
45 ;; to do so with holding C-level mutex, since Scheme procedure may
46 ;; take indefinitely long. So we use Scheme-level slot to keep the
47 ;; thread that is working on the queue.
48
49 (define-module data.queue
50 (export <queue> <mtqueue>
51 make-queue make-mtqueue queue? mtqueue?
52 queue-length mtqueue-max-length mtqueue-room
53 mtqueue-num-waiting-readers
54 queue-empty? copy-queue
55 queue-push! queue-push-unique! enqueue! enqueue-unique!
56 queue-pop! dequeue! dequeue-all!
57 queue-front queue-rear queue-length
58 queue->list list->queue queue-internal-list
59 find-in-queue remove-from-queue!
60 any-in-queue every-in-queue
61
62 enqueue/wait! queue-push/wait! dequeue/wait! queue-pop/wait!)
63 )
64 (select-module data.queue)
65
66 ;;;
67 ;;; Data structures
68 ;;;
69 (inline-stub
70 (.include <gauche/priv/configP.h>)
71
72 ;;
73 ;; <queue>
74 ;;
75 (define-ctype Queue::(.struct
76 (SCM_INSTANCE_HEADER :: ""
77 len::ScmSize ;; lazily calc'd. -1 for 'to be calculated'
78 head
79 tail)))
80
81 "SCM_CLASS_DECL(QueueClass);"
82
83 (.define QP (obj) (SCM_ISA obj (& QueueClass)))
84 (.define Q (obj) (cast Queue* obj))
85 (.define Q_HEAD (obj) (-> (Q obj) head))
86 (.define Q_TAIL (obj) (-> (Q obj) tail))
87 (.define Q_LENGTH (obj) (-> (Q obj) len)) ; can be -1; should use %qlength().
88 (.define Q_EMPTY_P (obj) (SCM_NULLP (Q_HEAD obj)))
89
90 (define-cfn %qlength (q::Queue*) ::ScmSize ; must be called with lock held
91 (when (< (Q_LENGTH q) 0)
92 (set! (Q_LENGTH q) (Scm_Length (Q_HEAD q))))
93 (return (cast ScmSmallInt (Q_LENGTH q))))
94
95 (define-cfn makeq (klass::ScmClass*)
96 (let* ([z::Queue* (SCM_NEW_INSTANCE Queue klass)])
97 (set! (Q_LENGTH z) 0 (Q_HEAD z) SCM_NIL (Q_TAIL z) SCM_NIL)
98 (return (SCM_OBJ z))))
99
100 (define-cclass <queue>
101 "Queue*" "QueueClass" ()
102 ((length :type <uint> :c-name "len" :setter #f))
103 (allocator (begin (cast void initargs) (return (makeq klass))))
104 (printer (Scm_Printf port "#<queue %d @%p>" (%qlength (Q obj)) obj))
105 (c-predicate "QP")
106 (unboxer "Q"))
107
108 ;;
109 ;; <mtqueue>
110 ;;
111 (define-ctype MtQueue::(.struct
112 (q::Queue
113 closed::_Bool ; if TRUE, reject enqueue!
114 maxlen::ScmSmallInt ; negative if unlimited
115 mutex::ScmInternalMutex
116 locker ; thread holding the lock. see the comment above.
117 lockWait::ScmInternalCond
118 readerWait::ScmInternalCond
119 writerWait::ScmInternalCond
120 readerSem::int ; used by zero-length queue. # of waiting reader
121 )))
122
123 "SCM_CLASS_DECL(MtQueueClass);"
124
125 (.define MTQP (obj) (SCM_ISA obj (& MtQueueClass)))
126 (.define MTQ (obj) (cast MtQueue* obj))
127 (.define MTQ_CLOSED (obj) (-> (MTQ obj) closed))
128 (.define MTQ_MAXLEN (obj) (-> (MTQ obj) maxlen))
129 (.define MTQ_MUTEX (obj) (-> (MTQ obj) mutex))
130 (.define MTQ_LOCKER (obj) (-> (MTQ obj) locker))
131 (.define MTQ_LOCK (obj) (SCM_INTERNAL_MUTEX_LOCK "MTQ_MUTEX q"))
132 (.define MTQ_UNLOCK (obj) (SCM_INTERNAL_MUTEX_UNLOCK "MTQ_MUTEX q"))
133 (.define MTQ_CV (q kind) (-> (MTQ q) kind))
134 (.define MTQ_READER_SEM (q) (-> (MTQ q) readerSem))
135
136 (define-cfn makemtq (klass::ScmClass* maxlen::int)
137 (let* ([z::MtQueue* (SCM_NEW_INSTANCE MtQueue klass)])
138 (set! (Q_LENGTH z) 0 (Q_HEAD z) SCM_NIL (Q_TAIL z) SCM_NIL
139 (MTQ_CLOSED z) FALSE
140 (MTQ_MAXLEN z) maxlen
141 (MTQ_LOCKER z) SCM_FALSE
142 (MTQ_READER_SEM z) 0)
143 (SCM_INTERNAL_MUTEX_INIT (MTQ_MUTEX z))
144 (SCM_INTERNAL_COND_INIT (MTQ_CV z lockWait))
145 (SCM_INTERNAL_COND_INIT (MTQ_CV z readerWait))
146 (SCM_INTERNAL_COND_INIT (MTQ_CV z writerWait))
147 (return (SCM_OBJ z))))
148
149 (define-cfn mtq-maxlen-get (mtq::MtQueue*)
150 (let* ([ml::ScmSmallInt (MTQ_MAXLEN mtq)])
151 (if (< ml 0) (return '#f) (return (SCM_MAKE_INT ml)))))
152
153 (define-cfn mtq-maxlen-set (mtq::MtQueue* maxlen) ::void
154 (cond [(SCM_UINTP maxlen) (set! (MTQ_MAXLEN mtq) (SCM_INT_VALUE maxlen))]
155 [(SCM_FALSEP maxlen) (set! (MTQ_MAXLEN mtq) -1)]
156 [else (SCM_TYPE_ERROR maxlen "non-negative fixnum or #f")]))
157
158 (define-cclass <mtqueue>
159 "MtQueue*" "MtQueueClass" ("QueueClass")
160 ((max-length :getter "return mtq_maxlen_get(obj);"
161 :setter "mtq_maxlen_set(obj, value);")
162 (closed :getter "return SCM_MAKE_BOOL(MTQ_CLOSED(obj));"
163 :setter #f))
164 (allocator
165 (let* ([ml (Scm_GetKeyword ':max-length initargs SCM_FALSE)])
166 (return (makemtq klass (?: (SCM_INTP ml) (SCM_INT_VALUE ml) -1)))))
167 (printer
168 (Scm_Printf port "#<mtqueue %d %s@%p>"
169 (%qlength (Q obj))
170 (?: (MTQ_CLOSED obj) "(closed)" "")
171 obj))
172 (c-predicate "MTQP")
173 (unboxer "MTQ"))
174
175 ;; lock macros
176 (define-cise-expr big-locked?
177 [(_ q) `(and (SCM_VMP (MTQ_LOCKER ,q))
178 (not (== (-> (SCM_VM (MTQ_LOCKER ,q)) state)
179 SCM_VM_TERMINATED)))])
180
181 (define-cise-stmt with-mtq-mutex-lock
182 [(_ q . body)
183 `(begin (SCM_INTERNAL_MUTEX_SAFE_LOCK_BEGIN (MTQ_MUTEX ,q))
184 ,@body
185 (SCM_INTERNAL_MUTEX_SAFE_LOCK_END))])
186
187 (define-cise-stmt wait-mtq-big-lock ;to be called while locking mutex
188 [(_ q) `(while (big-locked? ,q)
189 (SCM_INTERNAL_COND_WAIT (MTQ_CV ,q lockWait) (MTQ_MUTEX ,q)))])
190
191 (define-cise-stmt with-mtq-light-lock
192 [(_ q . stmts) `(with-mtq-mutex-lock ,q (wait-mtq-big-lock ,q) ,@stmts)])
193
194 (define-cise-stmt grab-mtq-big-lock
195 [(_ q) `(with-mtq-light-lock ,q (set! (MTQ_LOCKER ,q) (SCM_OBJ (Scm_VM))))])
196
197 (define-cise-stmt release-mtq-big-lock
198 [(_ q) `(with-mtq-mutex-lock ,q
199 (set! (MTQ_LOCKER ,q) SCM_FALSE)
200 (notify-lockers ,q))])
201
202 (define-cise-stmt notify-lockers
203 [(_ q) `(SCM_INTERNAL_COND_BROADCAST (MTQ_CV ,q lockWait))])
204 (define-cise-stmt notify-writers
205 [(_ q) `(SCM_INTERNAL_COND_BROADCAST (MTQ_CV ,q writerWait))])
206 (define-cise-stmt notify-readers
207 [(_ q) `(SCM_INTERNAL_COND_BROADCAST (MTQ_CV ,q readerWait))])
208
209 (.define CW_TIMEDOUT 1)
210 (.define CW_INTR 2)
211
212 ;; (wait-cv Q SLOT PTIMESPEC STATUS)
213 ;; Wait on Q's condition variable in SLOT. PTIMESPEC is a pointer
214 ;; to ScmTimeSpec or NULL, specifies timeout. Must be called
215 ;; while MTQ_MUTEX(Q) is held. When returns, MTQ_MUTEX(Q) is held,
216 ;; and status contains either 0 (condition met), CW_TIMEOUT (timed out),
217 ;; or CW_INTR (interrupted).
218 (define-cise-stmt wait-cv
219 [(_ q slot ptimespec status)
220 (let1 r (gensym)
221 `(cond [,ptimespec
222 (let* ([,r :: int
223 (SCM_INTERNAL_COND_TIMEDWAIT (-> ,q ,slot)
224 (MTQ_MUTEX ,q)
225 ,ptimespec)])
226 (cond [(== ,r SCM_INTERNAL_COND_TIMEDOUT)
227 (set! ,status CW_TIMEDOUT)]
228 [(== ,r SCM_INTERNAL_COND_INTR)
229 (set! ,status CW_INTR)]
230 [else (set! ,status 0)]))]
231 [else (SCM_INTERNAL_COND_WAIT (-> ,q ,slot) (MTQ_MUTEX ,q))
232 (set! ,status 0)]))])
233
234 ;; (do-with-timeout Q RETVAL TIMEOUT TIMEOUT-VAL CVAR INIT WAIT-CHECK DO-OK)
235 ;; Lock Q and execute INIT, and wait while WAIT-CHECK satisfies. Once
236 ;; WAIT-CHECK returns false, execute a statement DO-OK. CVAR is a
237 ;; condition variable (-> Q CVAR) to be waited on.
238 ;; INIT code may set a local variable ERR. If it is set, it gives up
239 ;; immediately and throws an error.
240 ;; If TIMEOUT isn't NULL and waiting times out, RETVAL is set with
241 ;; TIMEOUT-VAL. (DO-OK is supposed to set RETVAL in it).
242 (define-cise-stmt do-with-timeout
243 [(_ q retval timeout timeout-val cv-slot init wait-check do-ok)
244 (let ([ts (gensym)] [pts (gensym)] [tv (gensym)]
245 [status (gensym)] [inited (gensym)])
246 `(let* ([,ts :: (ScmTimeSpec)] [,status :: int 0]
247 [,tv :: (volatile ScmObj) ,timeout-val]
248 [,pts :: (ScmTimeSpec*) (Scm_GetTimeSpec ,timeout (& ,ts))]
249 [,inited :: int FALSE] [err :: (const char *) NULL])
250 (while TRUE
251 (with-mtq-mutex-lock ,q
252 (unless ,inited ,init (set! ,inited TRUE))
253 (unless err
254 (while TRUE
255 (wait-mtq-big-lock ,q)
256 (cond [,wait-check (wait-cv ,q ,cv-slot ,pts ,status)
257 (when (== ,status 0) (continue))]
258 [else ,do-ok (set! ,status 0)])
259 (set! (MTQ_LOCKER ,q) SCM_FALSE)
260 (notify-lockers ,q)
261 (break))))
262 (when err
263 (Scm_Error "%s: %S" err ,q))
264 (case ,status
265 [(CW_TIMEDOUT) (set! ,retval ,tv)]
266 [(CW_INTR) (Scm_SigCheck (Scm_VM)) (continue)]) ;restart op
267 (break))))])
268
269 (define-cproc %lock-mtq (q::<mtqueue>) ::<void> (grab-mtq-big-lock q))
270 (define-cproc %unlock-mtq (q::<mtqueue>) ::<void> (release-mtq-big-lock q))
271 (define-cproc %notify-writers (q::<mtqueue>) ::<void> (notify-writers q))
272 (define-cproc %notify-readers (q::<mtqueue>) ::<void> (notify-readers q))
273 )
274
275 ;; A common pattern
276 (define-syntax queue-op
277 (syntax-rules ()
278 [(_ q proc)
279 (cond
280 [(mtqueue? q) (%lock-mtq q) (unwind-protect (proc #t) (%unlock-mtq q))]
281 [(queue? q) (proc #f)]
282 [else (error "queue required, but got" q)])]))
283
284 ;;;
285 ;;; Constructors
286 ;;;
287 (inline-stub
288 (define-cproc make-queue ()
289 (return (makeq (& QueueClass))))
290 (define-cproc make-mtqueue (:key (max-length #f))
291 (return (makemtq (& MtQueueClass)
292 (?: (SCM_UINTP max-length)
293 (SCM_INT_VALUE max-length)
294 -1))))
295
296 ;; caller must hold lock
297 (define-cproc %queue-set-content! (q::<queue> list last-pair) ::<void>
298 (if (SCM_PAIRP list)
299 (let* ([tail (?: (SCM_PAIRP last-pair) last-pair (Scm_LastPair list))])
300 (set! (Q_TAIL q) tail
301 (Q_HEAD q) list
302 (Q_LENGTH q) -1))
303 (set! (Q_TAIL q) SCM_NIL
304 (Q_HEAD q) SCM_NIL
305 (Q_LENGTH q) 0)))
306 )
307
308 (define (list->queue lis :optional (class <queue>) :rest initargs)
309 (rlet1 q (apply make class initargs)
310 (%queue-set-content! q (list-copy lis) #f)))
311
312 (define-method copy-queue ((q <queue>))
313 (list->queue (queue->list q) (class-of q)))
314
315 (define-method copy-queue ((q <mtqueue>))
316 (list->queue (queue->list q) (class-of q)
317 :max-length (mtqueue-max-length q)))
318
319 ;;;
320 ;;; Predicates
321 ;;;
322 (inline-stub
323 (define-cproc queue-empty? (q::<queue>) ::<boolean>
324 (if (MTQP q)
325 (let* ([r::int FALSE])
326 (with-mtq-light-lock q (set! r (Q_EMPTY_P q)))
327 (return r))
328 (return (Q_EMPTY_P q))))
329 )
330
331 (define-inline (queue? q) (is-a? q <queue>))
332 (define-inline (mtqueue? q) (is-a? q <mtqueue>))
333
334 ;;;
335 ;;; Queries
336 ;;;
337 (inline-stub
338 (define-cise-expr mtq-overflows ;true if adding CNT elts overflows Q.
339 [(_ q cnt)
340 `(and (>= (MTQ_MAXLEN ,q) 0)
341 (> (+ ,cnt (%qlength (Q ,q))) (MTQ_MAXLEN ,q)))])
342
343 ;; API
344 (define-cproc queue-length (q::<queue>) ::<int> %qlength)
345 (define-cproc mtqueue-max-length (q::<mtqueue>)
346 (return (?: (>= (MTQ_MAXLEN q) 0) (SCM_MAKE_INT (MTQ_MAXLEN q)) '#f)))
347
348 ;; caller must hold lock
349 (define-cproc %mtqueue-overflow? (q::<mtqueue> cnt::<int>) ::<boolean>
350 (return (mtq-overflows q cnt)))
351
352 ;; API
353 (define-cproc mtqueue-room (q::<mtqueue>) ::<number>
354 (let* ([room::ScmSmallInt -1])
355 (with-mtq-light-lock q
356 (when (>= (MTQ_MAXLEN q) 0)
357 (set! room (- (MTQ_MAXLEN q) (%qlength (Q q))))))
358 (if (>= room 0)
359 (return (SCM_MAKE_INT room))
360 (return SCM_POSITIVE_INFINITY))))
361
362 ;; caller must hold big lock
363 ;; %qtail isn't used in data.queue, but used by SRFI-117
364 (define-cproc %qhead (q::<queue>) (return (Q_HEAD q)))
365 (define-cproc %qtail (q::<queue>) (return (Q_TAIL q)))
366
367 (define-cfn queue-peek-both-int (q::Queue* ph::ScmObj* pt::ScmObj*) ::int
368 (when (Q_EMPTY_P q) (return FALSE))
369 (set! (* ph) (SCM_CAR (Q_HEAD q))
370 (* pt) (SCM_CAR (Q_TAIL q)))
371 (return TRUE))
372
373 (define-cproc %queue-peek (q::<queue> :optional fallback) ::(<top> <top>)
374 (let* ([ok::int FALSE] [fb::(volatile ScmObj) fallback] [h] [t])
375 (if (not (MTQP q))
376 (set! ok (queue-peek-both-int q (& h) (& t)))
377 (with-mtq-light-lock q (set! ok (queue-peek-both-int q (& h) (& t)))))
378 (cond [ok (return h t)]
379 [(SCM_UNBOUNDP fb)
380 (Scm_Error "queue is empty: %S" q)
381 (return SCM_UNDEFINED SCM_UNDEFINED)] ;dummy
382 [else (return fb fb)])))
383 )
384
385 ;; APIs
386 (define queue-front
387 (case-lambda
388 [(q) (values-ref (%queue-peek q) 0)]
389 [(q default) (values-ref (%queue-peek q default) 0)]))
390 (define queue-rear
391 (case-lambda
392 [(q) (values-ref (%queue-peek q) 1)]
393 [(q default) (values-ref (%queue-peek q default) 1)]))
394 (define (queue->list q) (queue-op q (^_(list-copy (%qhead q)))))
395 (define (find-in-queue pred q) (queue-op q (^_(find pred (%qhead q)))))
396 (define (any-in-queue pred q) (queue-op q (^_(any pred (%qhead q)))))
397 (define (every-in-queue pred q) (queue-op q (^_(every pred (%qhead q)))))
398
399 ;; This returns internal list of the queue. Many queue operation
400 ;; mutates the internal list, so it is not safe to hold onto the
401 ;; result value. We specifically prohibit getting internal list of
402 ;; mtqueue for the safety.
403 (define (queue-internal-list q)
404 (when (mtqueue? q)
405 (error "Can't get internal list of <mtqueue>:" q))
406 (%qhead q))
407
408 ;;;
409 ;;; Enqueue/dequeue
410 ;;;
411
412 (inline-stub
413 ;; internal enqueue - lock must be held.
414 (define-cfn enqueue_int (q::Queue* cnt::ScmSmallInt head tail) ::void
415 (when (>= (Q_LENGTH q) 0)
416 (set! (Q_LENGTH q) (+ (Q_LENGTH q) cnt)))
417 (cond [(Q_EMPTY_P q) (set! (Q_HEAD q) head (Q_TAIL q) tail)]
418 [else (SCM_SET_CDR (Q_TAIL q) head)
419 (set! (Q_TAIL q) tail)]))
420
421 ;; to call internal enqueue from Scheme. lock must be held.
422 (define-cproc %enqueue! (q::<queue> cnt::<fixnum> head tail) ::<void>
423 (enqueue_int q cnt head tail))
424
425 ;; (q-write-op OP Q CNT HEAD TAIL)
426 ;; If Q isn't mtq, simply call (OP Q CNT HEAD TAIL).
427 ;; If Q is mtq, lock Q, and if queue isn't full, execute
428 ;; (OP Q CNT HEAD TAIL) then notify waiting readers.
429 ;; If queue is full, signals an error.
430 (define-cise-stmt q-write-op
431 [(_ op q cnt head tail)
432 `(if (MTQP ,q)
433 (let* ([ovf::int FALSE]
434 [closed::int FALSE])
435 (with-mtq-light-lock ,q
436 (cond [(MTQ_CLOSED ,q) (set! closed TRUE)]
437 [(mtq-overflows ,q ,cnt) (set! ovf TRUE)]
438 [else (,op ,q ,cnt ,head ,tail) (notify-readers ,q)]))
439 (when closed (Scm_Error "queue is closed: %S" ,q))
440 (when ovf (Scm_Error "queue is full: %S" ,q)))
441 (,op ,q ,cnt ,head ,tail))])
442
443 ;; API
444 (define-cproc enqueue! (q::<queue> obj :rest more-objs)
445 (let* ([head (Scm_Cons obj more-objs)] [tail] [cnt::ScmSmallInt]
446 [qq::(Queue* volatile) q])
447 (if (SCM_NULLP more-objs)
448 (set! tail head cnt 1)
449 (set! tail (Scm_LastPair more-objs) cnt (Scm_Length head)))
450 (q-write-op enqueue_int qq cnt head tail)
451 (return (SCM_OBJ qq))))
452
453 ;; API
454 (define-cproc enqueue/wait! (q::<mtqueue> obj
455 :optional (timeout #f)
456 (timeout-val #f)
457 (close::<boolean> #f))
458 (let* ([cell (SCM_LIST1 obj)] [retval (SCM_OBJ q)])
459 (do-with-timeout q retval timeout timeout-val writerWait
460 (when (MTQ_CLOSED q)
461 (set! err "queue is closed"))
462 (?: (!= (MTQ_MAXLEN q) 0)
463 (mtq-overflows q 1)
464 (== (MTQ_READER_SEM q) 0))
465 (begin (enqueue_int (Q q) 1 cell cell)
466 (set! retval '#t)
467 (when close
468 (set! (MTQ_CLOSED q) TRUE))
469 (notify-readers (Q q))))
470 (return retval)))
471 )
472
473 (define (enqueue-unique! q cmp obj . more-objs)
474 (define (pick lis xs ins)
475 (cond [(null? ins) xs]
476 [(or (member (car ins) lis cmp) (member (car ins) xs cmp))
477 (pick lis xs (cdr ins))]
478 [else (pick lis (cons (car ins) xs) (cdr ins))]))
479 (queue-op q (^(mt?)
480 (let1 xs (pick (%qhead q) '() (cons obj more-objs))
481 (unless (null? xs)
482 (when (and mt? (%mtqueue-overflow? q (length xs)))
483 (error "queue is full:" q))
484 (let1 xs_ (reverse xs)
485 (%enqueue! q (length xs) xs_ (last-pair xs_))
486 (when mt? (%notify-readers q)))))))
487 q)
488
489 (inline-stub
490 ;; queue-push! - add item(s) to the head
491 (define-cfn queue-push-int (q::Queue* cnt::ScmSmallInt head tail) ::void
492 (SCM_SET_CDR tail (Q_HEAD q))
493 (set! (Q_HEAD q) head
494 (Q_TAIL q) (Scm_LastPair tail))
495 (when (>= (Q_LENGTH q) 0)
496 (set! (Q_LENGTH q) (+ (Q_LENGTH q) cnt))))
497
498 (define-cproc queue-push! (q::<queue> obj :rest more-objs)
499 (let* ([objs (Scm_Cons obj more-objs)] [head] [tail] [cnt::ScmSmallInt]
500 [qq::(Queue* volatile) q])
501 (if (SCM_NULLP more-objs)
502 (set! head objs tail objs cnt 1)
503 (set! head (Scm_ReverseX objs)
504 tail (Scm_LastPair head)
505 cnt (Scm_Length head)))
506 (q-write-op queue-push-int qq cnt head tail)
507 (return (SCM_OBJ qq))))
508
509 (define-cproc queue-push/wait! (q::<mtqueue> obj
510 :optional (timeout #f)
511 (timeout-val #f)
512 (close::<boolean> #f))
513 (let* ([cell (SCM_LIST1 obj)] [retval (SCM_OBJ q)])
514 (do-with-timeout q retval timeout timeout-val writerWait
515 (when (MTQ_CLOSED q)
516 (set! err "queue is closed"))
517 (?: (!= (MTQ_MAXLEN q) 0)
518 (mtq-overflows q 1)
519 (== (MTQ_READER_SEM q) 0))
520 (begin (queue_push_int (Q q) 1 cell cell)
521 (when close
522 (set! (MTQ_CLOSED q) TRUE))
523 (notify-readers (Q q))))
524 (return retval)))
525 )
526
527 (define (queue-push-unique! q cmp obj . more-objs)
528 (define (pick lis ins)
529 (cond [(null? ins) lis]
530 [(member (car ins) lis cmp) (pick lis (cdr ins))]
531 [else (pick (cons (car ins) lis) (cdr ins))]))
532 (queue-op q (^[mt?]
533 (let* ([h (%qhead q)]
534 [xs (pick h (cons obj more-objs))])
535 (unless (eq? xs h)
536 (when (and mt? (%mtqueue-overflow? q (- (length xs) (length h))))
537 (error "queue is full" q))
538 (%queue-set-content! q xs #f)
539 (when mt? (%notify-readers q))))))
540 q)
541
542 ;; dequeue!
543 (inline-stub
544 (define-cfn dequeue-int (q::Queue* result::ScmObj*) ::int
545 (cond [(Q_EMPTY_P q) (return TRUE)]
546 [else
547 (let* ([h (Q_HEAD q)])
548 (set! (* result) (SCM_CAR h)
549 (Q_HEAD q) (SCM_CDR h))
550 (set! (SCM_CAR h) SCM_NIL
551 (SCM_CDR h) SCM_NIL) ; to be friendly to GC
552 (when (>= (Q_LENGTH q) 0) (dec! (Q_LENGTH q)))
553 (return FALSE))]))
554
555 (define-cproc dequeue! (q::<queue> :optional fallback)
556 (let* ([empty::int FALSE] [fb::(volatile ScmObj) fallback] [r SCM_UNDEFINED])
557 (if (not (MTQP q))
558 (set! empty (dequeue-int q (& r)))
559 (with-mtq-light-lock q (set! empty (dequeue-int q (& r)))))
560 (if empty
561 (if (SCM_UNBOUNDP fb)
562 (Scm_Error "queue is empty: %S" q)
563 (set! r fb))
564 (when (MTQP q) (notify-writers q)))
565 (return r)))
566
567 (define-cproc dequeue/wait! (q::<mtqueue> :optional (timeout #f)
568 (timeout-val #f)
569 (close::<boolean> #f))
570 (let* ([retval SCM_UNDEFINED])
571 (do-with-timeout q retval timeout timeout-val readerWait
572 (begin (post++ (MTQ_READER_SEM q))
573 (when close (set! (MTQ_CLOSED q) TRUE))
574 (notify-writers (Q q)))
575 (Q_EMPTY_P q)
576 (begin (pre-- (MTQ_READER_SEM q))
577 (dequeue_int (Q q) (& retval))
578 (notify-writers (Q q))))
579 (return retval)))
580
581 (define-cfn dequeue-all-int (q::Queue*)
582 (let* ([lis (Q_HEAD q)])
583 (set! (Q_LENGTH q) 0 (Q_HEAD q) SCM_NIL (Q_TAIL q) SCM_NIL)
584 (return lis)))
585
586 (define-cproc dequeue-all! (q::<queue>)
587 (if (not (MTQP q))
588 (return (dequeue-all-int q))
589 (let* ([r])
590 (with-mtq-light-lock q (set! r (dequeue-all-int q)))
591 (notify-writers q)
592 (return r))))
593 )
594
595 (define queue-pop! dequeue!)
596 (define queue-pop/wait! dequeue/wait!)
597
598 ;; Returns # of readers waiting on mtq. Note that the value might
599 ;; change at any moment after returning this procedure, so for meaningful
600 ;; operation the caller need another mutex to prevent new items
601 ;; from being inserted into the mtq.
602 (define-cproc mtqueue-num-waiting-readers (q::<mtqueue>) ::<int>
603 (let* ([n::int 0])
604 (with-mtq-light-lock q (set! n (MTQ_READER_SEM q)))
605 (return n)))
606
607 (define (remove-from-queue! pred q)
608 (rlet1 removed? #f
609 (queue-op q (^[mt?]
610 (let loop ([rs '()] [xs (%qhead q)] [hit #f])
611 (cond [(null? xs)
612 (when hit
613 (set! removed? #t)
614 (when mt? (%notify-writers q))
615 (%queue-set-content! q (reverse! rs) #f))]
616 [(pred (car xs)) (loop rs (cdr xs) #t)]
617 [else (loop (cons (car xs) rs) (cdr xs) hit)]))))))
618
619 ;; NB: Scheme48 has delete-from-queue!, whose argument order is
620 ;; reversed from 'delete' in SRFI-1. I leave it undefined here.
621 ;;
622 ;; (define (delete-from-queue! q item) ;;Scheme48
623 ;; (remove-from-queue! (lambda (elt) (eq? item elt)) q))