GNU bug report logs - #25605
[DRAFT PATCH 1/2] Simplify use of FOR_EACH_TAIL

Previous Next

Full log

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: bug-gnu-emacs <at> gnu.org
Cc: Paul Eggert <eggert <at> cs.ucla.edu>
Subject: [DRAFT PATCH 1/2] Simplify use of FOR_EACH_TAIL
Date: Wed,  1 Feb 2017 15:56:21 -0800

* 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);
+}
+
 
 /* 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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.