Ignore:
Timestamp:
Oct 10, 2012, 2:35:06 AM (8 years ago)
Author:
gb
Message:

COPY-LIST: if we find that the list is "fairly long", check to see
if it's "very long" and change algorithm if so.

CHECK-SEQUENCE-BOUNDS: take length as an &optional arg, since some
callers may want to avoid doing LENGTH multiple times.

CONSTANTLY: return #'TRUE or #'FALSE if appropriate.

REMOVE, REMOVE-IF, REMOVE-IF-NOT: build result, don't do destructive
operations on copy. (Fixes ticket:1015 in the trunk, though other
sequence functions may do similar things.)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/source/level-1/l1-aprims.lisp

    r15466 r15477  
    147147    (let ((result (cons (car list) '()) ))
    148148      (do ((x (cdr list) (cdr x))
     149           (i 0 (1+ i))
     150           (len)
    149151           (splice result
    150152                   (%cdr (%rplacd splice (cons (%car x) '() ))) ))
    151           ((atom x) (unless (null x)
    152                       (%rplacd splice x)) result)))))
     153          ((atom x)
     154           (unless (null x)
     155             (%rplacd splice x))
     156           result)
     157        (declare (fixnum i))
     158        ;; If the argument is "moderately long", check to see if it's
     159        ;; "very long"; if so, it may be much faster to replace the
     160        ;; elements of a list allocated in a single operation than it
     161        ;; is to repeatedly CONS (since the latter tends to fight with
     162        ;; the EGC.)
     163        ;; The definitions of "moderately long" and "very long" are
     164        ;; both somewhat arbitrary.
     165        (when (and (= i 1024)
     166                   (> (setq len (alt-list-length x)) (ash 1 16)))
     167          (do* ((tail (setf (%cdr splice) (%allocate-list 0 len)))
     168                (x x (cdr x)))
     169               ((atom x)
     170                (unless (null x)
     171                  (%rplacd tail x))
     172                (return-from copy-list result))
     173            (%rplaca tail (%car x))
     174            (unless (atom (%cdr x))
     175              (setq tail (cdr tail)))))))))
     176         
    153177
    154178(defun alt-list-length (l)
     
    400424  (seq-dispatch seq (list-reverse seq) (vector-reverse seq)))
    401425
    402 (defun check-sequence-bounds (seq start end)
     426(defun check-sequence-bounds (seq start end &optional (length (length seq)))
     427  (declare (fixnum length))
    403428  (flet ((bad-sequence-interval (seq start end)
    404429           (unless (typep start 'unsigned-byte)
     
    407432             (report-bad-arg end '(or null unsigned-byte)))
    408433           (error "Bad interval for sequence operation on ~s : start = ~s, end = ~s" seq start end)))
    409   (let* ((length (length seq)))
    410     (declare (fixnum length))
    411434    (if (and (typep start 'fixnum)
    412435             (<= 0 (the fixnum start))
     
    418441
    419442      end
    420       (bad-sequence-interval seq start end)))))
     443      (bad-sequence-interval seq start end))))
    421444
    422445 
Note: See TracChangeset for help on using the changeset viewer.