diff options
author | Paul Eggert <eggert@cs.ucla.edu> | 2017-02-05 13:25:37 -0800 |
---|---|---|
committer | Paul Eggert <eggert@cs.ucla.edu> | 2017-02-05 13:30:28 -0800 |
commit | b7fa6b1f1cee9d1b71553fa665843774d2e5cf3d (patch) | |
tree | 3a6df68a8377005aec8872de00df48b2cbf9f714 /src | |
parent | 5e222f673717718cd0ee209487cc06637bd142fc (diff) | |
download | emacs-b7fa6b1f1cee9d1b71553fa665843774d2e5cf3d.tar.gz |
Simplify use of FOR_EACH_TAIL
* 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).
Diffstat (limited to 'src')
-rw-r--r-- | src/data.c | 6 | ||||
-rw-r--r-- | src/fns.c | 16 | ||||
-rw-r--r-- | 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. */ |