vma-iter: Add support for Android.
[gnulib.git] / lib / fstrcmp.c
blobc61eab9d7d76b330d699ebd4b91c38f4ec13ebb5
1 /* Functions to make fuzzy comparisons between strings
2 Copyright (C) 1988-1989, 1992-1993, 1995, 2001-2003, 2006, 2008-2019 Free
3 Software Foundation, Inc.
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
19 #include <config.h>
21 /* Specification. */
22 #include "fstrcmp.h"
24 #include <string.h>
25 #include <stdbool.h>
26 #include <stddef.h>
27 #include <stdio.h>
28 #include <stdint.h>
29 #include <stdlib.h>
30 #include <limits.h>
32 #include "glthread/lock.h"
33 #include "glthread/tls.h"
34 #include "minmax.h"
35 #include "xalloc.h"
38 #define ELEMENT char
39 #define EQUAL(x,y) ((x) == (y))
40 #define OFFSET ptrdiff_t
41 #define EXTRA_CONTEXT_FIELDS \
42 /* The number of edits beyond which the computation can be aborted. */ \
43 ptrdiff_t edit_count_limit; \
44 /* The number of edits (= number of elements inserted, plus the number of \
45 elements deleted), temporarily minus edit_count_limit. */ \
46 ptrdiff_t edit_count;
47 #define NOTE_DELETE(ctxt, xoff) ctxt->edit_count++
48 #define NOTE_INSERT(ctxt, yoff) ctxt->edit_count++
49 #define EARLY_ABORT(ctxt) ctxt->edit_count > 0
50 /* We don't need USE_HEURISTIC, since it is unlikely in typical uses of
51 fstrcmp(). */
52 #include "diffseq.h"
55 /* Because fstrcmp is typically called multiple times, attempt to minimize
56 the number of memory allocations performed. Thus, let a call reuse the
57 memory already allocated by the previous call, if it is sufficient.
58 To make it multithread-safe, without need for a lock that protects the
59 already allocated memory, store the allocated memory per thread. Free
60 it only when the thread exits. */
62 static gl_tls_key_t buffer_key; /* TLS key for a 'ptrdiff_t *' */
63 static gl_tls_key_t bufmax_key; /* TLS key for a 'uintptr_t' */
65 static void
66 keys_init (void)
68 gl_tls_key_init (buffer_key, free);
69 gl_tls_key_init (bufmax_key, NULL);
70 /* The per-thread initial values are NULL and 0, respectively. */
73 /* Ensure that keys_init is called once only. */
74 gl_once_define(static, keys_init_once)
77 /* In the code below, branch probabilities were measured by Ralf Wildenhues,
78 by running "msgmerge LL.po coreutils.pot" with msgmerge 0.18 for many
79 values of LL. The probability indicates that the condition evaluates
80 to true; whether that leads to a branch or a non-branch in the code,
81 depends on the compiler's reordering of basic blocks. */
84 double
85 fstrcmp_bounded (const char *string1, const char *string2, double lower_bound)
87 struct context ctxt;
88 size_t xvec_length = strlen (string1);
89 size_t yvec_length = strlen (string2);
90 size_t length_sum = xvec_length + yvec_length;
91 ptrdiff_t i;
93 ptrdiff_t fdiag_len;
94 ptrdiff_t *buffer;
95 uintptr_t bufmax;
97 /* short-circuit obvious comparisons */
98 if (xvec_length == 0 || yvec_length == 0) /* Prob: 1% */
99 return length_sum == 0;
101 if (! (xvec_length <= length_sum
102 && length_sum <= MIN (UINTPTR_MAX, PTRDIFF_MAX) - 3))
103 xalloc_die ();
105 if (lower_bound > 0)
107 /* Compute a quick upper bound.
108 Each edit is an insertion or deletion of an element, hence modifies
109 the length of the sequence by at most 1.
110 Therefore, when starting from a sequence X and ending at a sequence Y,
111 with N edits, | yvec_length - xvec_length | <= N. (Proof by
112 induction over N.)
113 So, at the end, we will have
114 edit_count >= | xvec_length - yvec_length |.
115 and hence
116 result
117 = (xvec_length + yvec_length - edit_count)
118 / (xvec_length + yvec_length)
119 <= (xvec_length + yvec_length - | yvec_length - xvec_length |)
120 / (xvec_length + yvec_length)
121 = 2 * min (xvec_length, yvec_length) / (xvec_length + yvec_length).
123 ptrdiff_t length_min = MIN (xvec_length, yvec_length);
124 volatile double upper_bound = 2.0 * length_min / length_sum;
126 if (upper_bound < lower_bound) /* Prob: 74% */
127 /* Return an arbitrary value < LOWER_BOUND. */
128 return 0.0;
130 #if CHAR_BIT <= 8
131 /* When X and Y are both small, avoid the overhead of setting up an
132 array of size 256. */
133 if (length_sum >= 20) /* Prob: 99% */
135 /* Compute a less quick upper bound.
136 Each edit is an insertion or deletion of a character, hence
137 modifies the occurrence count of a character by 1 and leaves the
138 other occurrence counts unchanged.
139 Therefore, when starting from a sequence X and ending at a
140 sequence Y, and denoting the occurrence count of C in X with
141 OCC (X, C), with N edits,
142 sum_C | OCC (X, C) - OCC (Y, C) | <= N.
143 (Proof by induction over N.)
144 So, at the end, we will have
145 edit_count >= sum_C | OCC (X, C) - OCC (Y, C) |,
146 and hence
147 result
148 = (xvec_length + yvec_length - edit_count)
149 / (xvec_length + yvec_length)
150 <= (xvec_length + yvec_length - sum_C | OCC(X,C) - OCC(Y,C) |)
151 / (xvec_length + yvec_length).
153 ptrdiff_t occ_diff[UCHAR_MAX + 1]; /* array C -> OCC(X,C) - OCC(Y,C) */
154 ptrdiff_t sum;
155 double dsum;
157 /* Determine the occurrence counts in X. */
158 memset (occ_diff, 0, sizeof (occ_diff));
159 for (i = xvec_length - 1; i >= 0; i--)
160 occ_diff[(unsigned char) string1[i]]++;
161 /* Subtract the occurrence counts in Y. */
162 for (i = yvec_length - 1; i >= 0; i--)
163 occ_diff[(unsigned char) string2[i]]--;
164 /* Sum up the absolute values. */
165 sum = 0;
166 for (i = 0; i <= UCHAR_MAX; i++)
168 ptrdiff_t d = occ_diff[i];
169 sum += (d >= 0 ? d : -d);
172 dsum = sum;
173 upper_bound = 1.0 - dsum / length_sum;
175 if (upper_bound < lower_bound) /* Prob: 66% */
176 /* Return an arbitrary value < LOWER_BOUND. */
177 return 0.0;
179 #endif
182 /* set the info for each string. */
183 ctxt.xvec = string1;
184 ctxt.yvec = string2;
186 /* Set TOO_EXPENSIVE to be approximate square root of input size,
187 bounded below by 4096. */
188 ctxt.too_expensive = 1;
189 for (i = xvec_length + yvec_length; i != 0; i >>= 2)
190 ctxt.too_expensive <<= 1;
191 if (ctxt.too_expensive < 4096)
192 ctxt.too_expensive = 4096;
194 /* Allocate memory for fdiag and bdiag from a thread-local pool. */
195 fdiag_len = length_sum + 3;
196 gl_once (keys_init_once, keys_init);
197 buffer = gl_tls_get (buffer_key);
198 bufmax = (uintptr_t) gl_tls_get (bufmax_key);
199 if (fdiag_len > bufmax)
201 /* Need more memory. */
202 bufmax = 2 * bufmax;
203 if (fdiag_len > bufmax)
204 bufmax = fdiag_len;
205 /* Calling xrealloc would be a waste: buffer's contents does not need
206 to be preserved. */
207 free (buffer);
208 buffer = xnmalloc (bufmax, 2 * sizeof *buffer);
209 gl_tls_set (buffer_key, buffer);
210 gl_tls_set (bufmax_key, (void *) (uintptr_t) bufmax);
212 ctxt.fdiag = buffer + yvec_length + 1;
213 ctxt.bdiag = ctxt.fdiag + fdiag_len;
215 /* The edit_count is only ever increased. The computation can be aborted
216 when
217 (xvec_length + yvec_length - edit_count) / (xvec_length + yvec_length)
218 < lower_bound,
219 or equivalently
220 edit_count > (xvec_length + yvec_length) * (1 - lower_bound)
221 or equivalently
222 edit_count > floor((xvec_length + yvec_length) * (1 - lower_bound)).
223 We need to add an epsilon inside the floor(...) argument, to neutralize
224 rounding errors. */
225 ctxt.edit_count_limit =
226 (lower_bound < 1.0
227 ? (ptrdiff_t) (length_sum * (1.0 - lower_bound + 0.000001))
228 : 0);
230 /* Now do the main comparison algorithm */
231 ctxt.edit_count = - ctxt.edit_count_limit;
232 if (compareseq (0, xvec_length, 0, yvec_length, 0, &ctxt)) /* Prob: 98% */
233 /* The edit_count passed the limit. Hence the result would be
234 < lower_bound. We can return any value < lower_bound instead. */
235 return 0.0;
236 ctxt.edit_count += ctxt.edit_count_limit;
238 /* The result is
239 ((number of chars in common) / (average length of the strings)).
240 The numerator is
241 = xvec_length - (number of calls to NOTE_DELETE)
242 = yvec_length - (number of calls to NOTE_INSERT)
243 = 1/2 * (xvec_length + yvec_length - (number of edits)).
244 This is admittedly biased towards finding that the strings are
245 similar, however it does produce meaningful results. */
246 return ((double) (xvec_length + yvec_length - ctxt.edit_count)
247 / (xvec_length + yvec_length));