| 1 |
;;; |
| 2 |
;;; libbox.scm - Boxes |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2000-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 |
(select-module gauche) |
| 35 |
|
| 36 |
;; box is built-in since it is used in equal? implementation. See |
| 37 |
;; %interleave-equal? in libbool.scm. |
| 38 |
|
| 39 |
;; Internally, we have <box> (single-value box) and <mv-box> (multi-value |
| 40 |
;; box) as separate types, to make single-value box efficient. |
| 41 |
|
| 42 |
;; We also EXPERIMENTALLY have <shared-box>, which has an atomic |
| 43 |
;; shared counter to keep track of the number of objects that shares the |
| 44 |
;; box. Notably, if the counter is one, you can be sure that no other |
| 45 |
;; objects refers to the box so that you can modify the object(s) |
| 46 |
;; kept in it without being worried that you affect the mutation |
| 47 |
;; to others. |
| 48 |
;; |
| 49 |
;; Although the counter operation is MT-safe, it is not an alternative |
| 50 |
;; of mutex. If the object can be mutated from multiple threads, you have |
| 51 |
;; to protect it with a separate mutex. |
| 52 |
;; |
| 53 |
;; The counter is neither a reference counter in a strict sense; the |
| 54 |
;; references to a counted box can be kept in an environment, for example. |
| 55 |
;; |
| 56 |
;; See https://srfi-email.schemers.org/srfi-discuss/msg/16912128/ |
| 57 |
;; for the discussion triggered this implementation. |
| 58 |
|
| 59 |
(inline-stub |
| 60 |
(.include "gauche/priv/configP.h" |
| 61 |
"gauche/priv/atomicP.h") |
| 62 |
|
| 63 |
(define-ctype ScmSharedBox |
| 64 |
::(.struct ScmSharedBoxRec |
| 65 |
(SCM_HEADER::|| |
| 66 |
counter::ScmAtomicVar |
| 67 |
numValues::ScmSmallInt |
| 68 |
values::(.array ScmObj (1))))) |
| 69 |
|
| 70 |
(define-cclass <shared-box> :base :private :no-meta |
| 71 |
"ScmSharedBox*" "Scm_SharedBoxClass" |
| 72 |
(c "SCM_CLASS_DEFAULT_CPL") |
| 73 |
() |
| 74 |
(printer (let* ([b::ScmSharedBox* (SCM_SHARED_BOX obj)] |
| 75 |
[cnt::ScmAtomicWord (Scm_AtomicLoad (& (-> b counter)))]) |
| 76 |
(Scm_Printf port "#<shared-box[%d]<%d>" |
| 77 |
(-> b numValues) cnt) |
| 78 |
(dotimes [i (-> b numValues)] |
| 79 |
(Scm_Printf port " %S" (aref (-> b values) i))) |
| 80 |
(Scm_Printf port ">")))) |
| 81 |
|
| 82 |
(.define SCM_SHARED_BOX_SIZE (x) (-> (SCM_SHARED_BOX x) numValues)) |
| 83 |
(.define SCM_SHARED_BOX_VALUES (x) (-> (SCM_SHARED_BOX x) values)) |
| 84 |
) |
| 85 |
|
| 86 |
|
| 87 |
;;; |
| 88 |
;;; API |
| 89 |
;;; |
| 90 |
|
| 91 |
;; We use them in equal? implementation as well, so here we go... |
| 92 |
(define-cproc box (:optarray (argv argc 1) :rest rest) |
| 93 |
(cond |
| 94 |
[(== argc 0) (return (SCM_OBJ (Scm_MakeMVBox 0 SCM_FALSE)))] |
| 95 |
[(SCM_NULLP rest) (return (SCM_OBJ (Scm_MakeBox (aref argv 0))))] |
| 96 |
[else (return (SCM_OBJ (Scm_ListToMVBox (Scm_Cons (aref argv 0) rest))))])) |
| 97 |
|
| 98 |
(define-cproc box? (v) ::<boolean> |
| 99 |
(return (or (SCM_BOXP v) (SCM_MVBOXP v) (SCM_SHARED_BOX_P v)))) |
| 100 |
|
| 101 |
(define-cproc set-box! (b :rest vs) ::<void> |
| 102 |
(cond |
| 103 |
[(SCM_BOXP b) |
| 104 |
(unless (and (SCM_PAIRP vs) (SCM_NULLP (SCM_CDR vs))) |
| 105 |
(Scm_Error "Wrong number of values to set to a single-value box %S: %S" |
| 106 |
b vs)) |
| 107 |
(SCM_BOX_SET b (SCM_CAR vs))] |
| 108 |
[(SCM_MVBOXP b) |
| 109 |
(let* ([argc::ScmSmallInt (Scm_Length vs)] |
| 110 |
[i::ScmSmallInt 0]) |
| 111 |
(unless (== argc (SCM_MVBOX_SIZE b)) |
| 112 |
(Scm_Error "Wrong number of values to set to a multi-value box %S: %S" |
| 113 |
b vs)) |
| 114 |
(for (() (< i argc) (begin (post++ i) (set! vs (SCM_CDR vs)))) |
| 115 |
(set! (aref (SCM_MVBOX_VALUES b) i) (SCM_CAR vs))))] |
| 116 |
[(SCM_SHARED_BOX_P b) |
| 117 |
(let* ([argc::ScmSmallInt (Scm_Length vs)] |
| 118 |
[i::ScmSmallInt 0]) |
| 119 |
(unless (== argc (SCM_SHARED_BOX_SIZE b)) |
| 120 |
(Scm_Error "Wrong number of values to set to a shared box %S: %S" |
| 121 |
b vs)) |
| 122 |
(for (() (< i argc) (begin (post++ i) (set! vs (SCM_CDR vs)))) |
| 123 |
(set! (aref (SCM_SHARED_BOX_VALUES b) i) (SCM_CAR vs))))] |
| 124 |
[else (SCM_TYPE_ERROR b "<box>, <mv-box>, or <shared-box>")])) |
| 125 |
|
| 126 |
(define-cproc unbox (b) |
| 127 |
(setter set-box!) |
| 128 |
(cond |
| 129 |
[(SCM_BOXP b) (return (SCM_BOX_VALUE b))] |
| 130 |
[(SCM_MVBOXP b) (return (Scm_ValuesFromArray (SCM_MVBOX_VALUES b) |
| 131 |
(SCM_MVBOX_SIZE b)))] |
| 132 |
[(SCM_SHARED_BOX_P b) (return (Scm_ValuesFromArray |
| 133 |
(SCM_SHARED_BOX_VALUES b) |
| 134 |
(SCM_SHARED_BOX_SIZE b)))] |
| 135 |
[else (SCM_TYPE_ERROR b "<box> or <mv-box>") (return SCM_UNDEFINED)])) |
| 136 |
|
| 137 |
(define-cproc box-arity (b) ::<int> |
| 138 |
(cond |
| 139 |
[(SCM_BOXP b) (return 1)] |
| 140 |
[(SCM_MVBOXP b) (return (SCM_MVBOX_SIZE b))] |
| 141 |
[(SCM_SHARED_BOX_P b) (return (SCM_SHARED_BOX_SIZE b))] |
| 142 |
[else (SCM_TYPE_ERROR b "<box>, <mv-box>, or <shared-box>")])) |
| 143 |
|
| 144 |
(define-cproc set-box-value! (b i::<fixnum> val) ::<void> |
| 145 |
(cond |
| 146 |
[(SCM_BOXP b) |
| 147 |
(unless (== i 0) (Scm_Error "index out of range for %S: %d" b i)) |
| 148 |
(SCM_BOX_SET b val)] |
| 149 |
[(SCM_MVBOXP b) |
| 150 |
(unless (and (<= 0 i) |
| 151 |
(< i (SCM_MVBOX_SIZE b))) |
| 152 |
(Scm_Error "index out of range for %S: %d" b i)) |
| 153 |
(set! (aref (SCM_MVBOX_VALUES b) i) val)] |
| 154 |
[(SCM_SHARED_BOX_P b) |
| 155 |
(unless (and (<= 0 i) |
| 156 |
(< i (SCM_SHARED_BOX_SIZE b))) |
| 157 |
(Scm_Error "index out of range for %S: %d" b i)) |
| 158 |
(set! (aref (SCM_SHARED_BOX_VALUES b) i) val)] |
| 159 |
[else (SCM_TYPE_ERROR b "<box>, <mv-box>, or <shared-box>")])) |
| 160 |
|
| 161 |
(define-cproc unbox-value (b i::<fixnum>) |
| 162 |
(setter set-box-value!) |
| 163 |
(cond |
| 164 |
[(SCM_BOXP b) |
| 165 |
(unless (== i 0) (Scm_Error "index out of range for %S: %d" b i)) |
| 166 |
(return (SCM_BOX_VALUE b))] |
| 167 |
[(SCM_MVBOXP b) |
| 168 |
(unless (and (<= 0 i) |
| 169 |
(< i (SCM_MVBOX_SIZE b))) |
| 170 |
(Scm_Error "index out of range for %S: %d" b i)) |
| 171 |
(return (aref (SCM_MVBOX_VALUES b) i))] |
| 172 |
[(SCM_SHARED_BOX_P b) |
| 173 |
(unless (and (<= 0 i) |
| 174 |
(< i (SCM_SHARED_BOX_SIZE b))) |
| 175 |
(Scm_Error "index out of range for %S: %d" b i)) |
| 176 |
(return (aref (SCM_SHARED_BOX_VALUES b) i))] |
| 177 |
[else (SCM_TYPE_ERROR b "<box>, <mv-box>, or <shard-box>")])) |
| 178 |
|
| 179 |
;;; |
| 180 |
;;; <shared-box> specific API |
| 181 |
;;; |
| 182 |
;; for now, we hide these API in a separate module. |
| 183 |
|
| 184 |
(define-module gauche.experimental.shared-box) |
| 185 |
(select-module gauche.experimental.shared-box) |
| 186 |
|
| 187 |
(export shared-box shared-box-count shared-box-inc!) |
| 188 |
|
| 189 |
;; API |
| 190 |
(define-cproc shared-box (initial-count::<fixnum> :rest values) |
| 191 |
(let* ([numVals::ScmSmallInt (Scm_Length values)] |
| 192 |
[z::ScmSharedBox* (SCM_NEW2 (.type ScmSharedBox*) |
| 193 |
(+ (sizeof (.type ScmSharedBox)) |
| 194 |
(* (sizeof (.type ScmObj)) |
| 195 |
(- numVals 1))))] |
| 196 |
[i::int 0]) |
| 197 |
(SCM_SET_CLASS z (& Scm_SharedBoxClass)) |
| 198 |
(Scm_AtomicStore (& (-> z counter)) (cast ScmAtomicWord initial-count)) |
| 199 |
(set! (-> z numValues) numVals) |
| 200 |
(dolist [v values] |
| 201 |
(set! (aref (-> z values) (post++ i)) v)) |
| 202 |
(return (SCM_OBJ z)))) |
| 203 |
|
| 204 |
;; API |
| 205 |
(define-cproc shared-box-count (cb::<shared-box>) |
| 206 |
(let* ([v::ScmAtomicWord (Scm_AtomicLoad (& (-> cb counter)))]) |
| 207 |
;; NB: We might need an api to convert ScmAtomicWord to Scheme integer. |
| 208 |
(return (Scm_MakeInteger (cast long v))))) |
| 209 |
|
| 210 |
;; API |
| 211 |
(define-cproc shared-box-inc! (cb::<shared-box> |
| 212 |
:optional (delta::<fixnum> 1)) |
| 213 |
(for () |
| 214 |
(let* ([v::ScmAtomicWord (Scm_AtomicLoad (& (-> cb counter)))] |
| 215 |
[vv::ScmAtomicWord (+ v delta)]) |
| 216 |
(when (Scm_AtomicCompareExchange (& (-> cb counter)) (& v) vv) |
| 217 |
(return (Scm_MakeInteger (cast long v))))))) |