| 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)) |