From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.bugs Subject: bug#25605: [DRAFT PATCH 1/2] Simplify use of FOR_EACH_TAIL Date: Wed, 1 Feb 2017 15:56:21 -0800 Message-ID: <20170201235622.30836-1-eggert@cs.ucla.edu> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1485993434 13195 195.159.176.226 (1 Feb 2017 23:57:14 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 1 Feb 2017 23:57:14 +0000 (UTC) Cc: Paul Eggert To: 25605@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Thu Feb 02 00:57:09 2017 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cZ4lx-0003Eu-M8 for geb-bug-gnu-emacs@m.gmane.org; Thu, 02 Feb 2017 00:57:09 +0100 Original-Received: from localhost ([::1]:53580 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZ4m3-00019K-37 for geb-bug-gnu-emacs@m.gmane.org; Wed, 01 Feb 2017 18:57:15 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:54816) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZ4lt-00017q-GD for bug-gnu-emacs@gnu.org; Wed, 01 Feb 2017 18:57:06 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cZ4lq-0007uE-F3 for bug-gnu-emacs@gnu.org; Wed, 01 Feb 2017 18:57:05 -0500 Original-Received: from debbugs.gnu.org ([208.118.235.43]:55498) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1cZ4lq-0007u7-CN for bug-gnu-emacs@gnu.org; Wed, 01 Feb 2017 18:57:02 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1cZ4lq-0007Vj-62 for bug-gnu-emacs@gnu.org; Wed, 01 Feb 2017 18:57:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 01 Feb 2017 23:57:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 25605 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.148599340728837 (code B ref -1); Wed, 01 Feb 2017 23:57:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 1 Feb 2017 23:56:47 +0000 Original-Received: from localhost ([127.0.0.1]:53694 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cZ4lb-0007V3-5J for submit@debbugs.gnu.org; Wed, 01 Feb 2017 18:56:47 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:35454) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cZ4lZ-0007Up-Ja for submit@debbugs.gnu.org; Wed, 01 Feb 2017 18:56:46 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cZ4lT-0007lu-5O for submit@debbugs.gnu.org; Wed, 01 Feb 2017 18:56:40 -0500 Original-Received: from lists.gnu.org ([2001:4830:134:3::11]:44211) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cZ4lT-0007lk-2w for submit@debbugs.gnu.org; Wed, 01 Feb 2017 18:56:39 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:54632) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZ4lR-0000EN-0L for bug-gnu-emacs@gnu.org; Wed, 01 Feb 2017 18:56:38 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cZ4lN-0007ja-VK for bug-gnu-emacs@gnu.org; Wed, 01 Feb 2017 18:56:37 -0500 Original-Received: from zimbra.cs.ucla.edu ([131.179.128.68]:48732) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cZ4lN-0007iL-M7 for bug-gnu-emacs@gnu.org; Wed, 01 Feb 2017 18:56:33 -0500 Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id A001F16007F for ; Wed, 1 Feb 2017 15:56:30 -0800 (PST) Original-Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id gAeOAgth1GQD; Wed, 1 Feb 2017 15:56:29 -0800 (PST) Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 4A04A16007E; Wed, 1 Feb 2017 15:56:29 -0800 (PST) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Original-Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id fVrYOQ40QT5h; Wed, 1 Feb 2017 15:56:29 -0800 (PST) Original-Received: from Penguin.CS.UCLA.EDU (Penguin.CS.UCLA.EDU [131.179.64.200]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 28BCA160061; Wed, 1 Feb 2017 15:56:29 -0800 (PST) X-Mailer: git-send-email 2.9.3 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:128876 Archived-At: * src/data.c (circular_list): New function. * src/lisp.h (FOR_EACH_TAIL): Use Brent=E2=80=99s algorithm and C99 for-l= oop 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); } =20 +void +circular_list (Lisp_Object list) +{ + xsignal1 (Qcircular_list, list); +} + =0C /* Data type predicates. */ =20 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 =3D Qnil; - bool skip; + Lisp_Object prev =3D Qnil; =20 - FOR_EACH_TAIL (tail, list, tortoise, skip) + FOR_EACH_TAIL (list) { - Lisp_Object tem =3D XCAR (tail); + Lisp_Object tem =3D XCAR (li.tail); if (EQ (elt, tem)) { if (NILP (prev)) - list =3D XCDR (tail); + list =3D XCDR (li.tail); else - Fsetcdr (prev, XCDR (tail)); + Fsetcdr (prev, XCDR (li.tail)); } else - prev =3D tail; + prev =3D li.tail; } - CHECK_LIST_END (tail, list); return list; } =20 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 (struc= t 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)) =20 -/* 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) =3D (hare) =3D (list), (n) =3D true; \ - CONSP (hare); \ - (hare =3D XCDR (hare), (n) =3D !(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) =3D XCDR (tortoise))))) +/* Loop over tails of LIST, checking for dotted lists and cycles. + In the loop body, =E2=80=98li.tail=E2=80=99 is the current cons; the = name =E2=80=98li=E2=80=99 is + short for =E2=80=9Clist iterator=E2=80=9D. The expression LIST may b= e evaluated + more than once, and so should not have side effects. The loop body + should not modify the list=E2=80=99s top level structure other than b= y + perhaps deleting the current cons. + + Use Brent=E2=80=99s 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 \ + =3D { list, list, 2, 2 }; \ + CONSP (li.tail) || (CHECK_LIST_END (li.tail, list), false); \ + (li.tail =3D XCDR (li.tail), \ + (li.n-- =3D=3D 0 \ + ? (void) (li.n =3D li.max <<=3D 1, li.tortoise =3D li.tail) \ + : EQ (li.tail, li.tortoise) ? circular_list (list) : (void) 0))) =20 /* Do a `for' loop over alist values. */ =20 --=20 2.9.3