octave-nkf/gnulib-hg: lib/fstrcmp.c annotate

annotate lib/fstrcmp.c @ 17907:0a1c2535cad9

euidaccess: Fix Android build * modules/euidaccess (Depends-on): Add fcntl-h to ensure that AT_EACCESS gets declared.

author	Kevin Cernekee <cernekee@google.com>
date	Wed, 11 Feb 2015 15:22:54 -0800
parents	29ead46d1cca
children

rev	line source
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	1 /* Functions to make fuzzy comparisons between strings
17848 ab58d4870664 version-etc: new year Paul Eggert <eggert@cs.ucla.edu> parents: 17630 diff changeset	2 Copyright (C) 1988-1989, 1992-1993, 1995, 2001-2003, 2006, 2008-2015 Free
12518 b5e42ef33b49 update nearly all FSF copyright year lists to include 2009 Jim Meyering <meyering@redhat.com> parents: 12421 diff changeset	3 Software Foundation, Inc.
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	4
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 9151 diff changeset	5 This program is free software: you can redistribute it and/or modify
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	6 it under the terms of the GNU General Public License as published by
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 9151 diff changeset	7 the Free Software Foundation; either version 3 of the License, or
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 9151 diff changeset	8 (at your option) any later version.
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	9
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	10 This program is distributed in the hope that it will be useful,
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	13 GNU General Public License for more details.
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	14
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	15 You should have received a copy of the GNU General Public License
17630 d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic Paul Eggert <eggert@cs.ucla.edu> parents: 17587 diff changeset	16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	18
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	19 #include <config.h>
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	20
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	21 /* Specification. */
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	22 #include "fstrcmp.h"
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	23
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	24 #include <string.h>
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 #include <stdbool.h>
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	26 #include <stddef.h>
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	27 #include <stdio.h>
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	28 #include <stdint.h>
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	29 #include <stdlib.h>
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	30 #include <limits.h>
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	31
10318 8a3539888308 Move the lock and tls source files into a subdirectory. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	32 #include "glthread/lock.h"
8a3539888308 Move the lock and tls source files into a subdirectory. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	33 #include "glthread/tls.h"
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	34 #include "minmax.h"
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	35 #include "xalloc.h"
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	36
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	37
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	38 #define ELEMENT char
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	39 #define EQUAL(x,y) ((x) == (y))
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	40 #define OFFSET ptrdiff_t
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 #define EXTRA_CONTEXT_FIELDS \
10439 95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	42 /* The number of edits beyond which the computation can be aborted. */ \
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	43 ptrdiff_t edit_count_limit; \
10439 95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	44 /* The number of edits (= number of elements inserted, plus the number of \
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	45 elements deleted), temporarily minus edit_count_limit. */ \
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	46 ptrdiff_t edit_count;
10438 1a57c9d644f2 Simplify result computation. Bruno Haible <bruno@clisp.org> parents: 10437 diff changeset	47 #define NOTE_DELETE(ctxt, xoff) ctxt->edit_count++
1a57c9d644f2 Simplify result computation. Bruno Haible <bruno@clisp.org> parents: 10437 diff changeset	48 #define NOTE_INSERT(ctxt, yoff) ctxt->edit_count++
10439 95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	49 #define EARLY_ABORT(ctxt) ctxt->edit_count > 0
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 /* We don't need USE_HEURISTIC, since it is unlikely in typical uses of
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	51 fstrcmp(). */
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 #include "diffseq.h"
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	53
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	54
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	55 /* Because fstrcmp is typically called multiple times, attempt to minimize
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 the number of memory allocations performed. Thus, let a call reuse the
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	57 memory already allocated by the previous call, if it is sufficient.
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	58 To make it multithread-safe, without need for a lock that protects the
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	59 already allocated memory, store the allocated memory per thread. Free
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	60 it only when the thread exits. */
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	61
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	62 static gl_tls_key_t buffer_key; /* TLS key for a 'ptrdiff_t ' /
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	63 static gl_tls_key_t bufmax_key; /* TLS key for a 'uintptr_t' */
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	64
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	65 static void
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	66 keys_init (void)
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	67 {
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	68 gl_tls_key_init (buffer_key, free);
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	69 gl_tls_key_init (bufmax_key, NULL);
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	70 /* The per-thread initial values are NULL and 0, respectively. */
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	71 }
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	72
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	73 /* Ensure that keys_init is called once only. */
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	74 gl_once_define(static, keys_init_once)
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	75
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	76
10455 e8f55251d47e Add data about branch probabilities. Bruno Haible <bruno@clisp.org> parents: 10443 diff changeset	77 /* In the code below, branch probabilities were measured by Ralf Wildenhues,
e8f55251d47e Add data about branch probabilities. Bruno Haible <bruno@clisp.org> parents: 10443 diff changeset	78 by running "msgmerge LL.po coreutils.pot" with msgmerge 0.18 for many
e8f55251d47e Add data about branch probabilities. Bruno Haible <bruno@clisp.org> parents: 10443 diff changeset	79 values of LL. The probability indicates that the condition evaluates
e8f55251d47e Add data about branch probabilities. Bruno Haible <bruno@clisp.org> parents: 10443 diff changeset	80 to true; whether that leads to a branch or a non-branch in the code,
e8f55251d47e Add data about branch probabilities. Bruno Haible <bruno@clisp.org> parents: 10443 diff changeset	81 depends on the compiler's reordering of basic blocks. */
e8f55251d47e Add data about branch probabilities. Bruno Haible <bruno@clisp.org> parents: 10443 diff changeset	82
e8f55251d47e Add data about branch probabilities. Bruno Haible <bruno@clisp.org> parents: 10443 diff changeset	83
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	84 double
10437 aaa73f947c24 New function fstrcmp_bounded. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10318 diff changeset	85 fstrcmp_bounded (const char string1, const char string2, double lower_bound)
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	86 {
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	87 struct context ctxt;
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	88 size_t xvec_length = strlen (string1);
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	89 size_t yvec_length = strlen (string2);
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	90 size_t length_sum = xvec_length + yvec_length;
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	91 ptrdiff_t i;
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	92
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	93 ptrdiff_t fdiag_len;
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	94 ptrdiff_t *buffer;
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	95 uintptr_t bufmax;
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	96
10437 aaa73f947c24 New function fstrcmp_bounded. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10318 diff changeset	97 /* short-circuit obvious comparisons */
10455 e8f55251d47e Add data about branch probabilities. Bruno Haible <bruno@clisp.org> parents: 10443 diff changeset	98 if (xvec_length == 0 \|\| yvec_length == 0) /* Prob: 1% */
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	99 return length_sum == 0;
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	100
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	101 if (! (xvec_length <= length_sum
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	102 && length_sum <= MIN (UINTPTR_MAX, PTRDIFF_MAX) - 3))
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	103 xalloc_die ();
10437 aaa73f947c24 New function fstrcmp_bounded. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10318 diff changeset	104
aaa73f947c24 New function fstrcmp_bounded. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10318 diff changeset	105 if (lower_bound > 0)
aaa73f947c24 New function fstrcmp_bounded. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10318 diff changeset	106 {
aaa73f947c24 New function fstrcmp_bounded. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10318 diff changeset	107 /* Compute a quick upper bound.
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	108 Each edit is an insertion or deletion of an element, hence modifies
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	109 the length of the sequence by at most 1.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	110 Therefore, when starting from a sequence X and ending at a sequence Y,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	111 with N edits, \| yvec_length - xvec_length \| <= N. (Proof by
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	112 induction over N.)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	113 So, at the end, we will have
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	114 edit_count >= \| xvec_length - yvec_length \|.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	115 and hence
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	116 result
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	117 = (xvec_length + yvec_length - edit_count)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	118 / (xvec_length + yvec_length)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	119 <= (xvec_length + yvec_length - \| yvec_length - xvec_length \|)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	120 / (xvec_length + yvec_length)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	121 = 2 * min (xvec_length, yvec_length) / (xvec_length + yvec_length).
10437 aaa73f947c24 New function fstrcmp_bounded. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10318 diff changeset	122 */
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	123 ptrdiff_t length_min = MIN (xvec_length, yvec_length);
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	124 volatile double upper_bound = 2.0 * length_min / length_sum;
10437 aaa73f947c24 New function fstrcmp_bounded. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10318 diff changeset	125
10455 e8f55251d47e Add data about branch probabilities. Bruno Haible <bruno@clisp.org> parents: 10443 diff changeset	126 if (upper_bound < lower_bound) /* Prob: 74% */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	127 /* Return an arbitrary value < LOWER_BOUND. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	128 return 0.0;
10443 13d9d9fee7b5 Use a second, less quick upper bound based on character occurrence counts. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10439 diff changeset	129
13d9d9fee7b5 Use a second, less quick upper bound based on character occurrence counts. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10439 diff changeset	130 #if CHAR_BIT <= 8
13d9d9fee7b5 Use a second, less quick upper bound based on character occurrence counts. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10439 diff changeset	131 /* When X and Y are both small, avoid the overhead of setting up an
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	132 array of size 256. */
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	133 if (length_sum >= 20) /* Prob: 99% */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	134 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	135 /* Compute a less quick upper bound.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	136 Each edit is an insertion or deletion of a character, hence
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	137 modifies the occurrence count of a character by 1 and leaves the
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	138 other occurrence counts unchanged.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	139 Therefore, when starting from a sequence X and ending at a
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	140 sequence Y, and denoting the occurrence count of C in X with
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	141 OCC (X, C), with N edits,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	142 sum_C \| OCC (X, C) - OCC (Y, C) \| <= N.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	143 (Proof by induction over N.)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	144 So, at the end, we will have
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	145 edit_count >= sum_C \| OCC (X, C) - OCC (Y, C) \|,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	146 and hence
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	147 result
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	148 = (xvec_length + yvec_length - edit_count)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	149 / (xvec_length + yvec_length)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	150 <= (xvec_length + yvec_length - sum_C \| OCC(X,C) - OCC(Y,C) \|)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	151 / (xvec_length + yvec_length).
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	152 */
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	153 ptrdiff_t occ_diff[UCHAR_MAX + 1]; /* array C -> OCC(X,C) - OCC(Y,C) */
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	154 ptrdiff_t sum;
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	155 double dsum;
10443 13d9d9fee7b5 Use a second, less quick upper bound based on character occurrence counts. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10439 diff changeset	156
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	157 /* Determine the occurrence counts in X. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	158 memset (occ_diff, 0, sizeof (occ_diff));
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	159 for (i = xvec_length - 1; i >= 0; i--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	160 occ_diff[(unsigned char) string1[i]]++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	161 /* Subtract the occurrence counts in Y. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	162 for (i = yvec_length - 1; i >= 0; i--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	163 occ_diff[(unsigned char) string2[i]]--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	164 /* Sum up the absolute values. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	165 sum = 0;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	166 for (i = 0; i <= UCHAR_MAX; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	167 {
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	168 ptrdiff_t d = occ_diff[i];
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	169 sum += (d >= 0 ? d : -d);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	170 }
10443 13d9d9fee7b5 Use a second, less quick upper bound based on character occurrence counts. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10439 diff changeset	171
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	172 dsum = sum;
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	173 upper_bound = 1.0 - dsum / length_sum;
10443 13d9d9fee7b5 Use a second, less quick upper bound based on character occurrence counts. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10439 diff changeset	174
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	175 if (upper_bound < lower_bound) /* Prob: 66% */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	176 /* Return an arbitrary value < LOWER_BOUND. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	177 return 0.0;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	178 }
10443 13d9d9fee7b5 Use a second, less quick upper bound based on character occurrence counts. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10439 diff changeset	179 #endif
10437 aaa73f947c24 New function fstrcmp_bounded. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10318 diff changeset	180 }
aaa73f947c24 New function fstrcmp_bounded. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10318 diff changeset	181
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	182 /* set the info for each string. */
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	183 ctxt.xvec = string1;
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	184 ctxt.yvec = string2;
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	185
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	186 /* Allocate memory for fdiag and bdiag from a thread-local pool. */
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	187 fdiag_len = length_sum + 3;
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	188 gl_once (keys_init_once, keys_init);
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	189 buffer = gl_tls_get (buffer_key);
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	190 bufmax = (uintptr_t) gl_tls_get (bufmax_key);
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	191 if (fdiag_len > bufmax)
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	192 {
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	193 /* Need more memory. */
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	194 bufmax = 2 * bufmax;
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	195 if (fdiag_len > bufmax)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	196 bufmax = fdiag_len;
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	197 /* Calling xrealloc would be a waste: buffer's contents does not need
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	198 to be preserved. */
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	199 free (buffer);
29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	200 buffer = xnmalloc (bufmax, 2 * sizeof *buffer);
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	201 gl_tls_set (buffer_key, buffer);
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	202 gl_tls_set (bufmax_key, (void *) (uintptr_t) bufmax);
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	203 }
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	204 ctxt.fdiag = buffer + yvec_length + 1;
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	205 ctxt.bdiag = ctxt.fdiag + fdiag_len;
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	206
10439 95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	207 /* The edit_count is only ever increased. The computation can be aborted
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	208 when
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	209 (xvec_length + yvec_length - edit_count) / (xvec_length + yvec_length)
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	210 < lower_bound,
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	211 or equivalently
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	212 edit_count > (xvec_length + yvec_length) * (1 - lower_bound)
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	213 or equivalently
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	214 edit_count > floor((xvec_length + yvec_length) * (1 - lower_bound)).
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	215 We need to add an epsilon inside the floor(...) argument, to neutralize
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	216 rounding errors. */
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	217 ctxt.edit_count_limit =
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	218 (lower_bound < 1.0
17896 29ead46d1cca fstrcmp: don't assume strlen < INT_MAX Paul Eggert <eggert@cs.ucla.edu> parents: 17848 diff changeset	219 ? (ptrdiff_t) (length_sum * (1.0 - lower_bound + 0.000001))
10439 95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	220 : 0);
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	221
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	222 /* Now do the main comparison algorithm */
10439 95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	223 ctxt.edit_count = - ctxt.edit_count_limit;
17630 d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic Paul Eggert <eggert@cs.ucla.edu> parents: 17587 diff changeset	224 if (compareseq (0, xvec_length, 0, yvec_length, &ctxt)) /* Prob: 98% */
10439 95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	225 /* The edit_count passed the limit. Hence the result would be
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	226 < lower_bound. We can return any value < lower_bound instead. */
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	227 return 0.0;
95f2b5d880cb Abort the fstrcmp computation early when a lower bound has been given. Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 10438 diff changeset	228 ctxt.edit_count += ctxt.edit_count_limit;
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	229
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	230 /* The result is
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	231 ((number of chars in common) / (average length of the strings)).
10438 1a57c9d644f2 Simplify result computation. Bruno Haible <bruno@clisp.org> parents: 10437 diff changeset	232 The numerator is
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	233 = xvec_length - (number of calls to NOTE_DELETE)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	234 = yvec_length - (number of calls to NOTE_INSERT)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	235 = 1/2 * (xvec_length + yvec_length - (number of edits)).
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	236 This is admittedly biased towards finding that the strings are
8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	237 similar, however it does produce meaningful results. */
10438 1a57c9d644f2 Simplify result computation. Bruno Haible <bruno@clisp.org> parents: 10437 diff changeset	238 return ((double) (xvec_length + yvec_length - ctxt.edit_count)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 10455 diff changeset	239 / (xvec_length + yvec_length));
9151 8c5ddfde42d6 Fuzzy string comparison. Bruno Haible <bruno@clisp.org> parents: diff changeset	240 }

Mercurial > hg > octave-nkf > gnulib-hg

annotate lib/fstrcmp.c @ 17907:0a1c2535cad9