From b7fa6b1f1cee9d1b71553fa665843774d2e5cf3d Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sun, 5 Feb 2017 13:25:37 -0800 Subject: [PATCH] Simplify use of FOR_EACH_TAIL MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit * 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 (Bug#25605). --- 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 8e07bf01b44..12dc2df0bac 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 ac7c1f265a4..4de74a5967f 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 a9011b4a8be..102e8bd70ef 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, @@ -4585,20 +4586,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.39.5