From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.lisp.guile.bugs Subject: bug#17049: [PATCH v3] Make reverse! forego the cost of SCM_VALIDATE_LIST Date: Tue, 1 Apr 2014 16:24:29 +0200 Message-ID: <1396362269-11654-1-git-send-email-dak@gnu.org> References: <87k3b9kuoz.fsf@yeeloong.lan> NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1396362322 13682 80.91.229.3 (1 Apr 2014 14:25:22 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 1 Apr 2014 14:25:22 +0000 (UTC) Cc: David Kastrup To: 17049@debbugs.gnu.org Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Tue Apr 01 16:25:12 2014 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WUzck-0004Ok-Bq for guile-bugs@m.gmane.org; Tue, 01 Apr 2014 16:25:10 +0200 Original-Received: from localhost ([::1]:60690 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUzcj-0007DW-UO for guile-bugs@m.gmane.org; Tue, 01 Apr 2014 10:25:09 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:55263) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUzcg-0007CA-DG for bug-guile@gnu.org; Tue, 01 Apr 2014 10:25:07 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WUzcd-0006AO-Cl for bug-guile@gnu.org; Tue, 01 Apr 2014 10:25:06 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:58236) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUzcd-00069Y-28 for bug-guile@gnu.org; Tue, 01 Apr 2014 10:25:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WUzcc-000715-9w for bug-guile@gnu.org; Tue, 01 Apr 2014 10:25:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Tue, 01 Apr 2014 14:25:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17049 X-GNU-PR-Package: guile X-GNU-PR-Keywords: patch Original-Received: via spool by 17049-submit@debbugs.gnu.org id=B17049.139636228926943 (code B ref 17049); Tue, 01 Apr 2014 14:25:02 +0000 Original-Received: (at 17049) by debbugs.gnu.org; 1 Apr 2014 14:24:49 +0000 Original-Received: from localhost ([127.0.0.1]:59418 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUzcO-00070U-AX for submit@debbugs.gnu.org; Tue, 01 Apr 2014 10:24:48 -0400 Original-Received: from fencepost.gnu.org ([208.118.235.10]:59493) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUzcK-00070J-QU for 17049@debbugs.gnu.org; Tue, 01 Apr 2014 10:24:45 -0400 Original-Received: from localhost ([127.0.0.1]:38567 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUzcJ-0000T6-Tg; Tue, 01 Apr 2014 10:24:44 -0400 Original-Received: by lola (Postfix, from userid 1000) id 7F785E04FA; Tue, 1 Apr 2014 16:24:43 +0200 (CEST) X-Mailer: git-send-email 1.9.1 In-Reply-To: <87k3b9kuoz.fsf@yeeloong.lan> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.bugs:7442 Archived-At: * libguile/list.c (scm_reverse_x): Do not validate first argument to reverse! in advance. Instead undo reversal in error case. Signed-off-by: David Kastrup --- libguile/list.c | 41 ++++++++++++++++++++++++++++++++++++----- 1 file changed, 36 insertions(+), 5 deletions(-) diff --git a/libguile/list.c b/libguile/list.c index 1f44ad0..41cc937 100644 --- a/libguile/list.c +++ b/libguile/list.c @@ -374,18 +374,49 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0, "@code{reverse!}") #define FUNC_NAME s_scm_reverse_x { - SCM_VALIDATE_LIST (1, lst); + SCM old_lst = lst; + SCM tail = SCM_BOOL_F; + if (SCM_UNBNDP (new_tail)) new_tail = SCM_EOL; - while (!SCM_NULL_OR_NIL_P (lst)) + if (SCM_NULL_OR_NIL_P (lst)) + return new_tail; + + /* SCM_VALIDATE_LIST would run through the whole list to make sure it + is not eventually circular. In contrast to most list operations, + reverse! cannot get stuck in an infinite loop but arrives back at + the start when given an eventually or fully circular list. Because + of that, we can save the cost of an upfront proper list check at + the price of having to do a double reversal in the error case. + */ + + while (scm_is_pair (lst)) { SCM old_tail = SCM_CDR (lst); - SCM_SETCDR (lst, new_tail); - new_tail = lst; + SCM_SETCDR (lst, tail); + tail = lst; lst = old_tail; } - return new_tail; + + if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst))) + { + SCM_SETCDR (old_lst, new_tail); + return tail; + } + + /* We did not start with a proper list. Undo the reversal. */ + + while (scm_is_pair (tail)) + { + SCM old_tail = SCM_CDR (tail); + SCM_SETCDR (tail, lst); + lst = tail; + tail = old_tail; + } + + SCM_WRONG_TYPE_ARG (1, lst); + return lst; } #undef FUNC_NAME -- 1.9.1