unofficial mirror of bug-gnu-emacs@gnu.org 
 help / color / mirror / code / Atom feed
* bug#25605: [DRAFT PATCH 1/2] Simplify use of FOR_EACH_TAIL
@ 2017-02-01 23:56 Paul Eggert
  2017-02-01 23:56 ` bug#25606: [DRAFT PATCH 2/2] Signal list cycles in ‘length’ etc Paul Eggert
                   ` (2 more replies)
  0 siblings, 3 replies; 35+ messages in thread
From: Paul Eggert @ 2017-02-01 23:56 UTC (permalink / raw)
  To: 25605; +Cc: Paul Eggert

* src/data.c (circular_list): New function.
* src/lisp.h (FOR_EACH_TAIL): Use Brent’s algorithm and C99 for-loop
decl, to eliminate the need for the args TAIL, TORTOISE and N, and
to speed things up a bit on typical hosts with optimization.
All uses changed.
---
 src/data.c |  6 ++++++
 src/fns.c  | 16 +++++++---------
 src/lisp.h | 34 ++++++++++++++++++++--------------
 3 files changed, 33 insertions(+), 23 deletions(-)

diff --git a/src/data.c b/src/data.c
index 8e07bf0..12dc2df 100644
--- a/src/data.c
+++ b/src/data.c
@@ -170,6 +170,12 @@ args_out_of_range_3 (Lisp_Object a1, Lisp_Object a2, Lisp_Object a3)
   xsignal3 (Qargs_out_of_range, a1, a2, a3);
 }
 
+void
+circular_list (Lisp_Object list)
+{
+  xsignal1 (Qcircular_list, list);
+}
+
 \f
 /* Data type predicates.  */
 
diff --git a/src/fns.c b/src/fns.c
index ac7c1f2..4de74a5 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -1544,25 +1544,23 @@ list.
 Write `(setq foo (delq element foo))' to be sure of correctly changing
 the value of a list `foo'.  See also `remq', which does not modify the
 argument.  */)
-  (register Lisp_Object elt, Lisp_Object list)
+  (Lisp_Object elt, Lisp_Object list)
 {
-  Lisp_Object tail, tortoise, prev = Qnil;
-  bool skip;
+  Lisp_Object prev = Qnil;
 
-  FOR_EACH_TAIL (tail, list, tortoise, skip)
+  FOR_EACH_TAIL (list)
     {
-      Lisp_Object tem = XCAR (tail);
+      Lisp_Object tem = XCAR (li.tail);
       if (EQ (elt, tem))
 	{
 	  if (NILP (prev))
-	    list = XCDR (tail);
+	    list = XCDR (li.tail);
 	  else
-	    Fsetcdr (prev, XCDR (tail));
+	    Fsetcdr (prev, XCDR (li.tail));
 	}
       else
-	prev = tail;
+	prev = li.tail;
     }
-  CHECK_LIST_END (tail, list);
   return list;
 }
 
diff --git a/src/lisp.h b/src/lisp.h
index 1ac3816..2d74d44 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3317,6 +3317,7 @@ extern struct Lisp_Symbol *indirect_variable (struct Lisp_Symbol *);
 extern _Noreturn void args_out_of_range (Lisp_Object, Lisp_Object);
 extern _Noreturn void args_out_of_range_3 (Lisp_Object, Lisp_Object,
 					   Lisp_Object);
+extern _Noreturn void circular_list (Lisp_Object);
 extern Lisp_Object do_symval_forwarding (union Lisp_Fwd *);
 enum Set_Internal_Bind {
   SET_INTERNAL_SET,
@@ -4586,20 +4587,25 @@ enum
 	 Lisp_String))							\
      : make_unibyte_string (str, len))
 
-/* Loop over all tails of a list, checking for cycles.
-   FIXME: Make tortoise and n internal declarations.
-   FIXME: Unroll the loop body so we don't need `n'.  */
-#define FOR_EACH_TAIL(hare, list, tortoise, n)	\
-  for ((tortoise) = (hare) = (list), (n) = true;		\
-       CONSP (hare);						\
-       (hare = XCDR (hare), (n) = !(n),				\
-   	((n)							\
-   	 ? (EQ (hare, tortoise)					\
-	    ? xsignal1 (Qcircular_list, list)			\
-	    : (void) 0)						\
-	 /* Move tortoise before the next iteration, in case */ \
-	 /* the next iteration does an Fsetcdr.  */		\
-   	 : (void) ((tortoise) = XCDR (tortoise)))))
+/* Loop over tails of LIST, checking for dotted lists and cycles.
+   In the loop body, ‘li.tail’ is the current cons; the name ‘li’ is
+   short for “list iterator”.  The expression LIST may be evaluated
+   more than once, and so should not have side effects.  The loop body
+   should not modify the list’s top level structure other than by
+   perhaps deleting the current cons.
+
+   Use Brent’s teleporting tortoise-hare algorithm.  See:
+   Brent RP. BIT. 1980;20(2):176-84. doi:10.1007/BF01933190
+   http://maths-people.anu.edu.au/~brent/pd/rpb051i.pdf  */
+
+#define FOR_EACH_TAIL(list)						\
+  for (struct { Lisp_Object tail, tortoise; intptr_t n, max; } li	\
+	 = { list, list, 2, 2 };					\
+       CONSP (li.tail) || (CHECK_LIST_END (li.tail, list), false);	\
+       (li.tail = XCDR (li.tail),					\
+	(li.n-- == 0							\
+	 ? (void) (li.n = li.max <<= 1, li.tortoise = li.tail)		\
+	 : EQ (li.tail, li.tortoise) ? circular_list (list) : (void) 0)))
 
 /* Do a `for' loop over alist values.  */
 
-- 
2.9.3






^ permalink raw reply related	[flat|nested] 35+ messages in thread

end of thread, other threads:[~2017-02-13 14:37 UTC | newest]

Thread overview: 35+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2017-02-01 23:56 bug#25605: [DRAFT PATCH 1/2] Simplify use of FOR_EACH_TAIL Paul Eggert
2017-02-01 23:56 ` bug#25606: [DRAFT PATCH 2/2] Signal list cycles in ‘length’ etc Paul Eggert
2017-02-02 17:28   ` Eli Zaretskii
2017-02-02 23:01     ` Paul Eggert
2017-02-03  7:55       ` Eli Zaretskii
2017-02-03 20:29         ` Paul Eggert
2017-02-04  9:05           ` Eli Zaretskii
2017-02-04 19:11             ` Paul Eggert
2017-02-04 19:52               ` Eli Zaretskii
2017-02-04 21:45                 ` Paul Eggert
2017-02-05 18:45                   ` Eli Zaretskii
2017-02-05 21:17                     ` Paul Eggert
2017-02-02 17:29 ` bug#25605: [DRAFT PATCH 1/2] Simplify use of FOR_EACH_TAIL Eli Zaretskii
2017-02-05 21:30 ` bug#25605: patches installed for 25605, 25606 Paul Eggert
2017-02-06 16:04   ` bug#25605: bug#25606: " Eli Zaretskii
2017-02-07  6:53     ` Paul Eggert
2017-02-07 12:47       ` Philipp Stephani
2017-02-07 16:32         ` bug#25605: " Paul Eggert
2017-02-07 21:47           ` Philipp Stephani
2017-02-07 22:20             ` Paul Eggert
2017-02-07 22:55               ` Philipp Stephani
2017-02-10  9:59       ` bug#25605: " Eli Zaretskii
2017-02-12  8:31         ` Paul Eggert
2017-02-12 16:13           ` bug#25605: " Eli Zaretskii
2017-02-12 18:55             ` Paul Eggert
2017-02-12 19:33               ` Eli Zaretskii
2017-02-12 19:41                 ` bug#25605: " Lars Ingebrigtsen
2017-02-12 19:49                   ` bug#25606: " Lars Ingebrigtsen
2017-02-12 20:22                   ` Eli Zaretskii
2017-02-12 19:43                 ` Paul Eggert
2017-02-13  9:11                 ` Michael Albinus
2017-02-13 14:37                   ` Eli Zaretskii
2017-02-12 19:41               ` Eli Zaretskii
2017-02-12 20:57                 ` bug#25605: " Paul Eggert
2017-02-13  5:37                   ` Eli Zaretskii

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).