From 220a9ecba1b62e09703cb0a3c122797d4498ccc2 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 1 Jan 2018 01:19:57 +0000 Subject: Merge from Gnulib This incorporates: 2018-01-01 maint: Run 'make update-copyright' 2017-12-29 Add cross-compilation results for GNU/Hurd. 2017-12-12 explicit_bzero: port to macOS + Clang 9.0.0 --- lib/diffseq.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index b6f9f6f9d19..9244729380d 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -1,6 +1,6 @@ /* Analyze differences between two vectors. - Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2017 Free Software + Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2018 Free Software Foundation, Inc. This program is free software: you can redistribute it and/or modify -- cgit v1.2.1 From 26bed8ba10eeaf0a340a8d0d760c5578dddec867 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Tue, 1 Jan 2019 00:59:58 +0000 Subject: Update copyright year to 2019 Run 'TZ=UTC0 admin/update-copyright $(git ls-files)'. --- lib/diffseq.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index 9244729380d..88a6c4d7ada 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -1,7 +1,7 @@ /* Analyze differences between two vectors. - Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2018 Free Software - Foundation, Inc. + Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2019 Free + Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -- cgit v1.2.1 From 115498702da91dc75d05bd0dea64f98cc6157327 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 31 Dec 2018 18:19:36 -0800 Subject: Update from Gnulib This incorporates mostly just copyright-year changes, plus recent minor updates from glibc for the non-Emacs regular expression code. --- lib/diffseq.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index 88a6c4d7ada..c6aac3d8120 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -1,7 +1,7 @@ /* Analyze differences between two vectors. - Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2019 Free - Software Foundation, Inc. + Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2019 Free Software + Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -- cgit v1.2.1 From 78669517dc3db4d6d51fb26d71073fc0c196ab5d Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sun, 22 Sep 2019 23:50:59 -0700 Subject: Update from Gnulib This incorporates: 2019-09-22 Update some URLs 2019-09-15 fcntl-h: fix compilation error of creat.c on MSVC 2019-09-15 creat: new module 2019-09-15 access: new module 2019-09-09 Add option to assume best, not worst, when cross-compiling. * build-aux/config.guess, build-aux/config.sub, doc/misc/texinfo.tex: * lib/careadlinkat.c, lib/careadlinkat.h, lib/count-leading-zeros.h: * lib/count-trailing-zeros.h, lib/diffseq.h, lib/fcntl.in.h: * lib/ftoastr.c, lib/get-permissions.c: * lib/ieee754.in.h, lib/inttypes.in.h, lib/mktime.c, lib/open.c: * lib/pathmax.h, lib/pipe2.c, lib/stddef.in.h, lib/stdint.in.h: * lib/stdlib.in.h, lib/str-two-way.h, lib/string.in.h, lib/time.in.h: * lib/timegm.c, lib/unistd.in.h, m4/canonicalize.m4: * m4/extern-inline.m4, m4/fcntl_h.m4, m4/fdopendir.m4: * m4/getgroups.m4, m4/getopt.m4, m4/gettimeofday.m4: * m4/gnulib-common.m4, m4/largefile.m4: * m4/lstat.m4, m4/memmem.m4, m4/mktime.m4, m4/nocrash.m4, m4/open.m4: * m4/pselect.m4, m4/putenv.m4, m4/readlink.m4, m4/regex.m4: * m4/symlink.m4, m4/unistd_h.m4, m4/utimens.m4, m4/utimes.m4: Copy from Gnulib. * lib/gnulib.mk.in, m4/gnulib-comp.m4: Regenerate. * m4/open-slash.m4: New file, copied from Gnulib. --- lib/diffseq.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index c6aac3d8120..c48da0c98d9 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -28,13 +28,13 @@ The basic algorithm is described in: "An O(ND) Difference Algorithm and its Variations", Eugene W. Myers, Algorithmica Vol. 1, 1986, pp. 251-266, - . + . See especially section 4.2, which describes the variation used below. The basic algorithm was independently discovered as described in: "Algorithms for Approximate String Matching", Esko Ukkonen, Information and Control Vol. 64, 1985, pp. 100-118, - . + . Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N) -- cgit v1.2.1 From 365e01cc9f64ce6ca947ccfd8612d60763280a37 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Wed, 1 Jan 2020 00:19:43 +0000 Subject: Update copyright year to 2020 Run "TZ=UTC0 admin/update-copyright $(git ls-files)". --- lib/diffseq.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index c48da0c98d9..16e06053b43 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -1,7 +1,7 @@ /* Analyze differences between two vectors. - Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2019 Free Software - Foundation, Inc. + Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2020 Free + Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -- cgit v1.2.1 From 64d1b9fd8a97d355d7fe23025d82bebe52c1af1c Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Wed, 1 Jan 2020 03:11:22 +0000 Subject: Update from gnulib This incorporates: 2019-12-23 mktime, nstrftime: tweak division performance 2019-12-22 count-leading-zeros: assume 'long long' 2019-12-22 count-one-bits: assume 'long long' 2019-12-22 count-trailing-zeros: assume 'long long' 2019-12-12 inttypes-incomplete: assume 'long long' 2019-12-22 malloca: assume 'long long' 2019-12-22 stdint: assume 'long long' 2019-12-22 strtoll, strtoimax, strtoumax: assume 'long long' 2019-12-22 prefer lib_SOURCES to unconditional AC_LIBOBJ 2019-12-19 nstrftime: avoid a shadowing warning 2019-12-18 improve port of AC_C_RESTRICT to Oracle C++ 2019-12-12 stdalign: port to xlclang 16.01 2019-12-11 stddef, unistd: fix compilation error in C++ mode on MSVC 2019-12-08 fix compilation errors in C++ mode on Haiku 2019-12-08 fix compilation errors in 32-bit C++ mode on HP-UX 11/ia64 2019-12-08 fix compilation error in C++ mode on OpenBSD * build-aux/config.guess, doc/misc/texinfo.tex: * lib/count-leading-zeros.h, lib/count-one-bits.h: * lib/count-trailing-zeros.h, lib/inttypes.in.h, lib/malloca.h: * lib/mktime.c, lib/nstrftime.c, lib/signal.in.h, lib/stdalign.in.h: * lib/stddef.in.h, lib/stdint.in.h, lib/stdio.in.h, lib/stdlib.in.h: * lib/strtoimax.c, lib/unistd.in.h, m4/gnulib-common.m4: * m4/inttypes.m4, m4/largefile.m4, m4/malloca.m4, m4/strtoimax.m4: * m4/strtoll.m4: Copy from Gnulib. Also, change copyright notices in some other Gnulib-copied files to exactly match Gnulib, as Gnulib updated them in a trivially different way. * lib/gnulib.mk.in, m4/gnulib-comp.m4: Regenerate. --- lib/diffseq.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index 16e06053b43..c89363ac9ee 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -1,7 +1,7 @@ /* Analyze differences between two vectors. - Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2020 Free - Software Foundation, Inc. + Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2020 Free Software + Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -- cgit v1.2.1 From d494f9e81a6d11dcf6c22333cd950989b2051dff Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 24 Aug 2020 16:18:48 -0700 Subject: Update from Gnulib This incorporates: * lib/diffseq.h, m4/inttypes.m4: Copy from Gnulib. * m4/gnulib-comp.m4: Regenerate. --- lib/diffseq.h | 128 ++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 84 insertions(+), 44 deletions(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index c89363ac9ee..26e10bdd043 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; -- cgit v1.2.1 From ba05d005e5a81bc123ad8da928b1bccb6b160e7a Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Fri, 1 Jan 2021 01:13:56 -0800 Subject: Update copyright year to 2021 Run "TZ=UTC0 admin/update-copyright". --- lib/diffseq.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index 26e10bdd043..570f09d6be0 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -1,7 +1,7 @@ /* Analyze differences between two vectors. - Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2020 Free Software - Foundation, Inc. + Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2021 Free + Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -- cgit v1.2.1 From 1b59478f4cf442f5201500b0a9c66f4332fce640 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Fri, 1 Jan 2021 01:51:18 -0800 Subject: Update from Gnulib by running admin/merge-gnulib. --- lib/diffseq.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index 570f09d6be0..1cac430eddd 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -1,7 +1,7 @@ /* Analyze differences between two vectors. - Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2021 Free - Software Foundation, Inc. + Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2021 Free Software + Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -- cgit v1.2.1 From 19dcb237b5b02b36580294ab309124f346a66024 Mon Sep 17 00:00:00 2001 From: Eli Zaretskii Date: Sat, 1 Jan 2022 02:45:51 -0500 Subject: ; Add 2022 to copyright years. --- lib/diffseq.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index 1cac430eddd..eb646b58cce 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -1,7 +1,7 @@ /* Analyze differences between two vectors. - Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2021 Free Software - Foundation, Inc. + Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2022 Free + Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -- cgit v1.2.1 From c899d9742a3dee2069eb3a4ee9380833b5574a95 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Tue, 4 Jan 2022 13:13:25 -0800 Subject: Update from gnulib --- lib/diffseq.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index eb646b58cce..0c901a6ecfd 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -1,7 +1,7 @@ /* Analyze differences between two vectors. - Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2022 Free - Software Foundation, Inc. + Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2022 Free Software + Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -- cgit v1.2.1 From 308e63ccfcc6a6b1285bb17eff641f48639fb329 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Wed, 23 Feb 2022 11:11:52 -0800 Subject: Update from Gnulib by running admin/merge-gnulib --- lib/diffseq.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/diffseq.h') diff --git a/lib/diffseq.h b/lib/diffseq.h index 0c901a6ecfd..0f76ea1d5ad 100644 --- a/lib/diffseq.h +++ b/lib/diffseq.h @@ -5,7 +5,7 @@ This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or + the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, -- cgit v1.2.1