From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-Status: No, score=-4.1 required=3.0 tests=AWL,BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 52D191F66E for ; Mon, 24 Aug 2020 22:21:53 +0000 (UTC) Received: from localhost ([::1]:36456 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kAKqe-0002VD-6g for normalperson@yhbt.net; Mon, 24 Aug 2020 18:21:52 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:53832) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kAKqa-0002V2-7N for bug-gnulib@gnu.org; Mon, 24 Aug 2020 18:21:48 -0400 Received: from zimbra.cs.ucla.edu ([131.179.128.68]:50280) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kAKqV-0002TA-R1 for bug-gnulib@gnu.org; Mon, 24 Aug 2020 18:21:47 -0400 Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 1E1981600FD for ; Mon, 24 Aug 2020 15:21:40 -0700 (PDT) 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 DzVSyjTT1eUl; Mon, 24 Aug 2020 15:21:38 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id D61FD1600EF; Mon, 24 Aug 2020 15:21:38 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu 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 nv4VG5Xwvr4W; Mon, 24 Aug 2020 15:21:38 -0700 (PDT) Received: from day.example.com (cpe-75-82-69-226.socal.res.rr.com [75.82.69.226]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id AEF67160091; Mon, 24 Aug 2020 15:21:38 -0700 (PDT) From: Paul Eggert To: bug-gnulib@gnu.org Subject: [PATCH] diffseq: new option NOTE_ORDERED Date: Mon, 24 Aug 2020 15:21:28 -0700 Message-Id: <20200824222128.15900-1-eggert@cs.ucla.edu> X-Mailer: git-send-email 2.17.1 Received-SPF: pass client-ip=131.179.128.68; envelope-from=eggert@cs.ucla.edu; helo=zimbra.cs.ucla.edu X-detected-operating-system: by eggs.gnu.org: First seen = 2020/08/24 18:21:40 X-ACL-Warn: Detected OS = Linux 3.1-3.10 X-Spam_score_int: -41 X-Spam_score: -4.2 X-Spam_bar: ---- X-Spam_report: (-4.2 / 5.0 requ) BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: bug-gnulib@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Gnulib discussion list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Paul Eggert Errors-To: bug-gnulib-bounces+normalperson=yhbt.net@gnu.org Sender: "bug-gnulib" Problem reported by Phil Sainty . * NEWS: Mention this. * lib/diffseq.h (NOTE_ORDERED): New macro. (IF_LINT2): Remove; no longer needed. (compareseq): If (!NOTE_ORDERED), recurse on the smaller subproblem and iterate to do the larger. --- ChangeLog | 10 ++++ NEWS | 5 ++ lib/diffseq.h | 128 +++++++++++++++++++++++++++++++++----------------- 3 files changed, 99 insertions(+), 44 deletions(-) diff --git a/ChangeLog b/ChangeLog index c6b057e68..33cea278b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2020-08-24 Paul Eggert + + diffseq: new option NOTE_ORDERED + Problem reported by Phil Sainty . + * NEWS: Mention this. + * lib/diffseq.h (NOTE_ORDERED): New macro. + (IF_LINT2): Remove; no longer needed. + (compareseq): If (!NOTE_ORDERED), recurse on the smaller + subproblem and iterate to do the larger. + 2020-08-23 Paul Eggert sys_types: let Autoconf 2.70 do pid_t diff --git a/NEWS b/NEWS index ed88a7ea2..18465b260 100644 --- a/NEWS +++ b/NEWS @@ -60,6 +60,11 @@ User visible incompatible changes Date Modules Changes +2020-08-24 diffseq If you do not define NOTE_ORDERED to true, + the NOTE_DELETE and NOTE_INSERT actions might + not be done in order, to help cut down worst-case + recursion stack space from O(N) to O(log N). + 2020-08-01 libtextstyle-optional You now need to invoke gl_LIBTEXTSTYLE_OPTIONAL explicitly, because this macro now takes an optional diff --git a/lib/diffseq.h b/lib/diffseq.h index c89363ac9..26e10bdd0 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -51,10 +51,14 @@ EXTRA_CONTEXT_FIELDS Declarations of fields for 'struct context'. NOTE_DELETE(ctxt, xoff) Record the removal of the object xvec[xoff]. NOTE_INSERT(ctxt, yoff) Record the insertion of the object yvec[yoff]. + NOTE_ORDERED (Optional) A boolean expression saying that + NOTE_DELETE and NOTE_INSERT calls must be + issued in offset order. EARLY_ABORT(ctxt) (Optional) A boolean expression that triggers an early abort of the computation. USE_HEURISTIC (Optional) Define if you want to support the heuristic for large vectors. + It is also possible to use this file with abstract arrays. In this case, xvec and yvec are not represented in memory. They only exist conceptually. In this case, the list of defines above is amended as follows: @@ -63,6 +67,7 @@ XVECREF_YVECREF_EQUAL(ctxt, xoff, yoff) A three-argument macro: References xvec[xoff] and yvec[yoff] and tests these elements for equality. + Before including this file, you also need to include: #include #include @@ -78,6 +83,10 @@ # define EARLY_ABORT(ctxt) false #endif +#ifndef NOTE_ORDERED +# define NOTE_ORDERED false +#endif + /* Use this to suppress gcc's "...may be used before initialized" warnings. Beware: The Code argument must not contain commas. */ #ifndef IF_LINT @@ -88,15 +97,6 @@ # endif #endif -/* As above, but when Code must contain one comma. */ -#ifndef IF_LINT2 -# if defined GCC_LINT || defined lint -# define IF_LINT2(Code1, Code2) Code1, Code2 -# else -# define IF_LINT2(Code1, Code2) /* empty */ -# endif -#endif - /* * Context of comparison operation. */ @@ -468,49 +468,89 @@ compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, #define XREF_YREF_EQUAL(x,y) XVECREF_YVECREF_EQUAL (ctxt, x, y) #endif - /* Slide down the bottom initial diagonal. */ - while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xoff, yoff)) + while (true) { - xoff++; - yoff++; - } + /* Slide down the bottom initial diagonal. */ + while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xoff, yoff)) + { + xoff++; + yoff++; + } - /* Slide up the top initial diagonal. */ - while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xlim - 1, ylim - 1)) - { - xlim--; - ylim--; - } + /* Slide up the top initial diagonal. */ + while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xlim - 1, ylim - 1)) + { + xlim--; + ylim--; + } - /* Handle simple cases. */ - if (xoff == xlim) - while (yoff < ylim) - { - NOTE_INSERT (ctxt, yoff); - if (EARLY_ABORT (ctxt)) - return true; - yoff++; - } - else if (yoff == ylim) - while (xoff < xlim) - { - NOTE_DELETE (ctxt, xoff); - if (EARLY_ABORT (ctxt)) - return true; - xoff++; - } - else - { - struct partition part IF_LINT2 (= { .xmid = 0, .ymid = 0 }); + /* Handle simple cases. */ + if (xoff == xlim) + { + while (yoff < ylim) + { + NOTE_INSERT (ctxt, yoff); + if (EARLY_ABORT (ctxt)) + return true; + yoff++; + } + break; + } + if (yoff == ylim) + { + while (xoff < xlim) + { + NOTE_DELETE (ctxt, xoff); + if (EARLY_ABORT (ctxt)) + return true; + xoff++; + } + break; + } + + struct partition part; /* Find a point of correspondence in the middle of the vectors. */ diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt); /* Use the partitions to split this problem into subproblems. */ - if (compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt)) - return true; - if (compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt)) - return true; + OFFSET xoff1, xlim1, yoff1, ylim1, xoff2, xlim2, yoff2, ylim2; + bool find_minimal1, find_minimal2; + if (!NOTE_ORDERED + && ((xlim + ylim) - (part.xmid + part.ymid) + < (part.xmid + part.ymid) - (xoff + yoff))) + { + /* The second problem is smaller and the caller doesn't + care about order, so do the second problem first to + lessen recursion. */ + xoff1 = part.xmid; xlim1 = xlim; + yoff1 = part.ymid; ylim1 = ylim; + find_minimal1 = part.hi_minimal; + + xoff2 = xoff; xlim2 = part.xmid; + yoff2 = yoff; ylim2 = part.ymid; + find_minimal2 = part.lo_minimal; + } + else + { + xoff1 = xoff; xlim1 = part.xmid; + yoff1 = yoff; ylim1 = part.ymid; + find_minimal1 = part.lo_minimal; + + xoff2 = part.xmid; xlim2 = xlim; + yoff2 = part.ymid; ylim2 = ylim; + find_minimal2 = part.hi_minimal; + } + + /* Recurse to do one subproblem. */ + bool early = compareseq (xoff1, xlim1, yoff1, ylim1, find_minimal1, ctxt); + if (early) + return early; + + /* Iterate to do the other subproblem. */ + xoff = xoff2; xlim = xlim2; + yoff = yoff2; ylim = ylim2; + find_minimal = find_minimal2; } return false; -- 2.17.1