From eb83344fc7c08ec08b51e7700f1ac2632afa462c Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 20 Aug 2018 15:52:29 -0700 Subject: Speed up (nthcdr N L) when L is circular Also, fix bug when N is a positive bignum, a problem reported by Eli Zaretskii and Pip Cet in: https://lists.gnu.org/r/emacs-devel/2018-08/msg00690.html * src/fns.c (Fnthcdr): If a cycle is found, reduce the count modulo the cycle length before continuing. This reduces the worst-case cost of (nthcdr N L) from N to min(N, C) where C is the number of distinct cdrs of L. Reducing modulo the cycle length also allows us to do arithmetic with machine words instead of with GMP. * test/src/fns-tests.el (test-nthcdr-circular): New test. --- test/src/fns-tests.el | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'test') diff --git a/test/src/fns-tests.el b/test/src/fns-tests.el index f722ed6333e..92dc18fa034 100644 --- a/test/src/fns-tests.el +++ b/test/src/fns-tests.el @@ -624,4 +624,20 @@ (should (eq (gethash b2 hash) (funcall test b1 b2))))))) +(ert-deftest test-nthcdr-circular () + (dolist (len '(1 2 5 37 120 997 1024)) + (let ((cycle (make-list len nil))) + (setcdr (last cycle) cycle) + (dolist (n (list (1- most-negative-fixnum) most-negative-fixnum + -1 0 1 + (1- len) len (1+ len) + most-positive-fixnum (1+ most-positive-fixnum) + (* 2 most-positive-fixnum) + (* most-positive-fixnum most-positive-fixnum) + (ash 1 12345))) + (let ((a (nthcdr n cycle)) + (b (if (<= n 0) cycle (nthcdr (mod n len) cycle)))) + (should (equal (list (eq a b) n len) + (list t n len)))))))) + (provide 'fns-tests) -- cgit v1.2.3