(def %array-available-elements)
(def %array-data-vector)
(def %array-displacement)
- (def %array-displaced-p))
+ (def %array-displaced-p)
+ (def %array-diplaced-from))
(defun %array-rank (array)
(%array-rank array))
(setf (%array-fill-pointer-p array) nil)))
(setf (%array-available-elements array) total-size)
(setf (%array-data-vector array) data)
+ (setf (%array-displaced-from array) nil)
(cond (displaced-to
(when (or initial-element-p initial-contents-p)
(error "Neither :INITIAL-ELEMENT nor :INITIAL-CONTENTS ~
(array-total-size displaced-to))
(error "~S doesn't have enough elements." displaced-to))
(setf (%array-displacement array) offset)
- (setf (%array-displaced-p array) t)))
+ (setf (%array-displaced-p array) t)
+ (%save-displaced-array-backpointer array data)))
(t
(setf (%array-displaced-p array) nil)))
(let ((axis 0))
;;; the type information is available. Finally, for each of these
;;; routines also provide a slow path, taken for arrays that are not
;;; vectors or not simple.
-(macrolet ((%define (table-name extra-params)
- `(funcall
- (the function
- (let ((tag 0)
- (offset
- #.(ecase sb!c:*backend-byte-order*
- (:little-endian
- (- sb!vm:other-pointer-lowtag))
- (:big-endian
- (- (1- sb!vm:n-word-bytes) sb!vm:other-pointer-lowtag)))))
- ;; WIDETAG-OF needs extra code to handle
- ;; LIST and FUNCTION lowtags. We're only
- ;; dispatching on other pointers, so let's
- ;; do the lowtag extraction manually.
- (when (sb!vm::%other-pointer-p array)
- (setf tag
- (sb!sys:sap-ref-8 (int-sap (get-lisp-obj-address array))
- offset)))
- ;; SYMBOL-GLOBAL-VALUE is a performance hack
- ;; for threaded builds.
- (svref (sb!vm::symbol-global-value ',table-name) tag)))
- array index ,@extra-params))
- (define (accessor-name slow-accessor-name table-name extra-params
- check-bounds)
- `(progn
- (defvar ,table-name)
- (defun ,accessor-name (array index ,@extra-params)
- (declare (optimize speed
- ;; (SAFETY 0) is ok. All calls to
- ;; these functions are generated by
- ;; the compiler, so argument count
- ;; checking isn't needed. Type checking
- ;; is done implicitly via the widetag
- ;; dispatch.
- (safety 0)))
- (%define ,table-name ,extra-params))
- (defun ,slow-accessor-name (array index ,@extra-params)
- (declare (optimize speed (safety 0)))
- (if (not (%array-displaced-p array))
- ;; The reasonably quick path of non-displaced complex
- ;; arrays.
- (let ((array (%array-data-vector array)))
- (%define ,table-name ,extra-params))
- ;; The real slow path.
- (with-array-data
- ((vector array)
- (index (locally
- (declare (optimize (speed 1) (safety 1)))
- (,@check-bounds index)))
- (end)
- :force-inline t)
- (declare (ignore end))
- (,accessor-name vector index ,@extra-params)))))))
+(macrolet ((def (name table-name)
+ `(progn
+ (defvar ,table-name)
+ (defmacro ,name (array-var)
+ `(the function
+ (let ((tag 0)
+ (offset
+ #.(ecase sb!c:*backend-byte-order*
+ (:little-endian
+ (- sb!vm:other-pointer-lowtag))
+ (:big-endian
+ (- (1- sb!vm:n-word-bytes) sb!vm:other-pointer-lowtag)))))
+ ;; WIDETAG-OF needs extra code to handle LIST and
+ ;; FUNCTION lowtags. We're only dispatching on
+ ;; other pointers, so let's do the lowtag
+ ;; extraction manually.
+ (when (sb!vm::%other-pointer-p ,array-var)
+ (setf tag
+ (sb!sys:sap-ref-8 (int-sap (get-lisp-obj-address ,array-var))
+ offset)))
+ ;; SYMBOL-GLOBAL-VALUE is a performance hack
+ ;; for threaded builds.
+ (svref (sb!vm::symbol-global-value ',',table-name) tag)))))))
+ (def !find-data-vector-setter *data-vector-setters*)
+ (def !find-data-vector-setter/check-bounds *data-vector-setters/check-bounds*)
+ (def !find-data-vector-reffer *data-vector-reffers*)
+ (def !find-data-vector-reffer/check-bounds *data-vector-reffers/check-bounds*))
+
+(macrolet ((%ref (accessor-getter extra-params)
+ `(funcall (,accessor-getter array) array index ,@extra-params))
+ (define (accessor-name slow-accessor-name accessor-getter
+ extra-params check-bounds)
+ `(progn
+ (defun ,accessor-name (array index ,@extra-params)
+ (declare (optimize speed
+ ;; (SAFETY 0) is ok. All calls to
+ ;; these functions are generated by
+ ;; the compiler, so argument count
+ ;; checking isn't needed. Type checking
+ ;; is done implicitly via the widetag
+ ;; dispatch.
+ (safety 0)))
+ (%ref ,accessor-getter ,extra-params))
+ (defun ,slow-accessor-name (array index ,@extra-params)
+ (declare (optimize speed (safety 0)))
+ (if (not (%array-displaced-p array))
+ ;; The reasonably quick path of non-displaced complex
+ ;; arrays.
+ (let ((array (%array-data-vector array)))
+ (%ref ,accessor-getter ,extra-params))
+ ;; The real slow path.
+ (with-array-data
+ ((vector array)
+ (index (locally
+ (declare (optimize (speed 1) (safety 1)))
+ (,@check-bounds index)))
+ (end)
+ :force-inline t)
+ (declare (ignore end))
+ (,accessor-name vector index ,@extra-params)))))))
(define hairy-data-vector-ref slow-hairy-data-vector-ref
- *data-vector-reffers* nil (progn))
+ !find-data-vector-reffer
+ nil (progn))
(define hairy-data-vector-set slow-hairy-data-vector-set
- *data-vector-setters* (new-value) (progn))
+ !find-data-vector-setter
+ (new-value) (progn))
(define hairy-data-vector-ref/check-bounds
slow-hairy-data-vector-ref/check-bounds
- *data-vector-reffers/check-bounds* nil
- (%check-bound array (array-dimension array 0)))
+ !find-data-vector-reffer/check-bounds
+ nil (%check-bound array (array-dimension array 0)))
(define hairy-data-vector-set/check-bounds
slow-hairy-data-vector-set/check-bounds
- *data-vector-setters/check-bounds* (new-value)
- (%check-bound array (array-dimension array 0))))
+ !find-data-vector-setter/check-bounds
+ (new-value) (%check-bound array (array-dimension array 0))))
(defun hairy-ref-error (array index &optional new-value)
(declare (ignore index new-value))
(defun data-vector-ref-with-offset (array index offset)
(hairy-data-vector-ref array (+ index offset)))
+(declaim (ftype (function (array integer integer &optional t) nil)
+ invalid-array-index-error))
+(defun invalid-array-index-error (array index bound &optional axis)
+ (error 'invalid-array-index-error
+ :array array
+ :axis axis
+ :datum index
+ :expected-type `(integer 0 (,bound))))
+
;;; SUBSCRIPTS has a dynamic-extent list structure and is destroyed
(defun %array-row-major-index (array subscripts
&optional (invalid-index-error-p t))
(declare (fixnum dim))
(unless (and (fixnump index) (< -1 index dim))
(if invalid-index-error-p
- (error 'simple-type-error
- :format-control "invalid index ~W~[~;~:; on axis ~:*~W~] in ~S"
- :format-arguments (list index axis array)
- :datum index
- :expected-type `(integer 0 (,dim)))
+ (invalid-array-index-error array index dim axis)
(return-from %array-row-major-index nil)))
(incf result (* chunk-size (the fixnum index)))
(setf chunk-size (* chunk-size dim))))
(length (length (the (simple-array * (*)) array))))
(unless (and (fixnump index) (< -1 index length))
(if invalid-index-error-p
- ;; FIXME: perhaps this should share a format-string
- ;; with INVALID-ARRAY-INDEX-ERROR or
- ;; INDEX-TOO-LARGE-ERROR?
- (error 'simple-type-error
- :format-control "invalid index ~W in ~S"
- :format-arguments (list index array)
- :datum index
- :expected-type `(integer 0 (,length)))
+ (invalid-array-index-error array index length)
(return-from %array-row-major-index nil)))
index))))
t))
(defun array-row-major-index (array &rest subscripts)
- (declare (dynamic-extent subscripts))
+ (declare (truly-dynamic-extent subscripts))
(%array-row-major-index array subscripts))
(defun aref (array &rest subscripts)
#!+sb-doc
"Return the element of the ARRAY specified by the SUBSCRIPTS."
- (declare (dynamic-extent subscripts))
+ (declare (truly-dynamic-extent subscripts))
(row-major-aref array (%array-row-major-index array subscripts)))
(defun %aset (array &rest stuff)
- (declare (dynamic-extent stuff))
+ (declare (truly-dynamic-extent stuff))
(let ((subscripts (butlast stuff))
(new-value (car (last stuff))))
(setf (row-major-aref array (%array-row-major-index array subscripts))
#!-sb-fluid (declaim (inline (setf aref)))
(defun (setf aref) (new-value array &rest subscripts)
- (declare (dynamic-extent subscripts))
+ (declare (truly-dynamic-extent subscripts))
(declare (type array array))
(setf (row-major-aref array (%array-row-major-index array subscripts))
new-value))
(error "Axis number ~W is too big; ~S only has ~D dimension~:P."
axis-number array (%array-rank array)))
(t
- ;; ANSI sayeth (ADJUST-ARRAY dictionary entry):
- ;;
- ;; "If A is displaced to B, the consequences are
- ;; unspecified if B is adjusted in such a way that it no
- ;; longer has enough elements to satisfy A.
- ;;
- ;; In situations where this matters we should be doing a
- ;; bounds-check, which in turn uses ARRAY-DIMENSION -- so
- ;; this seems like a good place to signal an error.
- (multiple-value-bind (target offset) (array-displacement array)
- (when (and target
- (> (array-total-size array)
- (- (array-total-size target) offset)))
- (error 'displaced-to-array-too-small-error
- :format-control "~@<The displaced-to array is too small. ~S ~
- elements after offset required, ~S available.~:@>"
- :format-arguments (list (array-total-size array)
- (- (array-total-size target) offset))))
- (%array-dimension array axis-number)))))
+ (%array-dimension array axis-number))))
(defun array-dimensions (array)
#!+sb-doc
(declare (array array))
(and (array-header-p array) (%array-fill-pointer-p array)))
+(defun fill-pointer-error (vector arg)
+ (cond (arg
+ (aver (array-has-fill-pointer-p vector))
+ (let ((max (%array-available-elements vector)))
+ (error 'simple-type-error
+ :datum arg
+ :expected-type (list 'integer 0 max)
+ :format-control "The new fill pointer, ~S, is larger than the length of the vector (~S.)"
+ :format-arguments (list arg max))))
+ (t
+ (error 'simple-type-error
+ :datum vector
+ :expected-type '(and vector (satisfies array-has-fill-pointer-p))
+ :format-control "~S is not an array with a fill pointer."
+ :format-arguments (list vector)))))
+
(defun fill-pointer (vector)
#!+sb-doc
"Return the FILL-POINTER of the given VECTOR."
- (declare (vector vector))
- (if (and (array-header-p vector) (%array-fill-pointer-p vector))
+ (if (array-has-fill-pointer-p vector)
(%array-fill-pointer vector)
- (error 'simple-type-error
- :datum vector
- :expected-type '(and vector (satisfies array-has-fill-pointer-p))
- :format-control "~S is not an array with a fill pointer."
- :format-arguments (list vector))))
+ (fill-pointer-error vector nil)))
(defun %set-fill-pointer (vector new)
- (declare (vector vector) (fixnum new))
- (if (and (array-header-p vector) (%array-fill-pointer-p vector))
- (if (> new (%array-available-elements vector))
- (error
- "The new fill pointer, ~S, is larger than the length of the vector."
- new)
- (setf (%array-fill-pointer vector) new))
- (error 'simple-type-error
- :datum vector
- :expected-type '(and vector (satisfies array-has-fill-pointer-p))
- :format-control "~S is not an array with a fill pointer."
- :format-arguments (list vector))))
+ (flet ((oops (x)
+ (fill-pointer-error vector x)))
+ (if (array-has-fill-pointer-p vector)
+ (if (> new (%array-available-elements vector))
+ (oops new)
+ (setf (%array-fill-pointer vector) new))
+ (oops nil))))
;;; FIXME: It'd probably make sense to use a MACROLET to share the
;;; guts of VECTOR-PUSH between VECTOR-PUSH-EXTEND. Such a macro
(cond ((= fill-pointer (%array-available-elements array))
nil)
(t
- (setf (aref array fill-pointer) new-el)
+ (locally (declare (optimize (safety 0)))
+ (setf (aref array fill-pointer) new-el))
(setf (%array-fill-pointer array) (1+ fill-pointer))
fill-pointer))))
(defun vector-push-extend (new-element
vector
&optional
- (extension (1+ (length vector))))
- (declare (vector vector) (fixnum extension))
+ (min-extension
+ (let ((length (length vector)))
+ (min (1+ length)
+ (- array-dimension-limit length)))))
+ (declare (vector vector) (fixnum min-extension))
(let ((fill-pointer (fill-pointer vector)))
(declare (fixnum fill-pointer))
(when (= fill-pointer (%array-available-elements vector))
- (adjust-array vector (+ fill-pointer extension)))
+ (adjust-array vector (+ fill-pointer (max 1 min-extension))))
;; disable bounds checking
(locally (declare (optimize (safety 0)))
(setf (aref vector fill-pointer) new-element))
(set-array-header array array-data array-size
(get-new-fill-pointer array array-size
fill-pointer)
- 0 dimensions nil)
+ 0 dimensions nil nil)
(if (array-header-p array)
;; simple multidimensional or single dimensional array
(make-array dimensions
(set-array-header array displaced-to array-size
(get-new-fill-pointer array array-size
fill-pointer)
- displacement dimensions t)
+ displacement dimensions t nil)
;; simple multidimensional or single dimensional array
(make-array dimensions
:element-type element-type
(set-array-header array new-data new-length
(get-new-fill-pointer array new-length
fill-pointer)
- 0 dimensions nil)
+ 0 dimensions nil nil)
new-data))))
(t
(let ((old-length (%array-available-elements array))
initial-element-p))
(if (adjustable-array-p array)
(set-array-header array new-data new-length
- new-length 0 dimensions nil)
+ nil 0 dimensions nil nil)
(let ((new-array
(make-array-header
sb!vm:simple-array-widetag array-rank)))
(set-array-header new-array new-data new-length
- new-length 0 dimensions nil)))))))))))
+ nil 0 dimensions nil t)))))))))))
(defun get-new-fill-pointer (old-array new-array-size fill-pointer)
vector)
(t (subseq vector 0 new-length))))
+(defun %save-displaced-array-backpointer (array data)
+ (when (array-header-p data)
+ (let* ((old (%array-displaced-from data))
+ (new (cons (make-weak-pointer array) old)))
+ (loop until (eq old (%compare-and-swap-array-displaced-from data old new))
+ do (setf old (%array-displaced-from data)
+ new (rplacd new (remove-if-not #'weak-pointer-value old)))))))
+
;;; Fill in array header with the provided information, and return the array.
(defun set-array-header (array data length fill-pointer displacement dimensions
- &optional displacedp)
+ displacedp newp)
+ (if newp
+ (setf (%array-displaced-from array) nil)
+ ;; ANSI sayeth (ADJUST-ARRAY dictionary entry):
+ ;;
+ ;; "If A is displaced to B, the consequences are unspecified if B is
+ ;; adjusted in such a way that it no longer has enough elements to
+ ;; satisfy A.
+ ;;
+ ;; so check the backpointers and signal an error if appropriate.
+ (dolist (p (%array-displaced-from array))
+ (let ((from (weak-pointer-value p)))
+ (when from
+ (let ((requires (+ (%array-available-elements from)
+ (%array-displacement from))))
+ (unless (>= length requires)
+ (error 'simple-reference-error
+ :format-control "Cannot shrink ~S to ~S elements: displaced array ~S requires at least ~S elements."
+ :format-arguments (list 'adjust-array length from requires))))))))
+ (%save-displaced-array-backpointer array data)
(setf (%array-data-vector array) data)
(setf (%array-available-elements array) length)
(cond (fill-pointer
(setf (%array-dimension array 0) dimensions))
(setf (%array-displaced-p array) displacedp)
array)
+
+;;; User visible extension
+(declaim (ftype (function (array) (values (simple-array * (*)) &optional))
+ array-storage-vector))
+(defun array-storage-vector (array)
+ "Returns the underlying storage vector of ARRAY, which must be a non-displaced array.
+
+In SBCL, if ARRAY is a of type \(SIMPLE-ARRAY * \(*)), it is its own storage
+vector. Multidimensional arrays, arrays with fill pointers, and adjustable
+arrays have an underlying storage vector with the same ARRAY-ELEMENT-TYPE as
+ARRAY, which this function returns.
+
+Important note: the underlying vector is an implementation detail. Even though
+this function exposes it, changes in the implementation may cause this
+function to be removed without further warning."
+ ;; KLUDGE: Without TRULY-THE the system is not smart enough to figure out that
+ ;; the return value is always of the known type.
+ (truly-the (simple-array * (*))
+ (if (array-header-p array)
+ (if (%array-displaced-p array)
+ (error "~S cannot be used with displaced arrays. Use ~S instead."
+ 'array-storage-vector 'array-displacement)
+ (%array-data-vector array))
+ array)))
\f
+;;;; used by SORT
+
+;;; temporary vector for stable sorting vectors, allocated for each new thread
+(defvar *merge-sort-temp-vector* (vector))
+(declaim (simple-vector *merge-sort-temp-vector*))
+
;;;; ZAP-ARRAY-DATA for ADJUST-ARRAY
;;; a temporary to be used when OLD-DATA and NEW-DATA are EQ.
(unless (typep initial-element element-type)
(error "~S can't be used to initialize an array of type ~S."
initial-element element-type)))
- (without-interrupts
- ;; Need to disable interrupts while using the temp-vector.
- ;; An interrupt handler that also happened to call
- ;; ADJUST-ARRAY could otherwise stomp on our data here.
- (let ((temp (zap-array-data-temp new-length
- initial-element initial-element-p)))
- (declare (simple-vector temp))
- (zap-array-data-aux old-data old-dims offset temp new-dims)
- (dotimes (i new-length)
- (setf (aref new-data i) (aref temp i)
- ;; zero out any garbage right away
- (aref temp i) 0)))))
+ (let ((temp (zap-array-data-temp new-length
+ initial-element initial-element-p)))
+ (declare (simple-vector temp))
+ (zap-array-data-aux old-data old-dims offset temp new-dims)
+ (dotimes (i new-length)
+ (setf (aref new-data i) (aref temp i)
+ ;; zero out any garbage right away
+ (aref temp i) 0))))
(t
;; When OLD-DATA and NEW-DATA are not EQ, NEW-DATA has
;; already been filled with any
projects / sbcl.git / blobdiff