pintos-os.org Git - pspp/blob - lib/fstrcmp.c

   1 /* Functions to make fuzzy comparisons between strings
   2    Copyright (C) 1988-1989, 1992-1993, 1995, 2001-2003, 2006, 2008
   3    Free Software Foundation, Inc.
   4
   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.
   9
  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.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18
  19    Derived from GNU diff 2.7, analyze.c et al.
  20
  21    The basic idea is to consider two vectors as similar if, when
  22    transforming the first vector into the second vector through a
  23    sequence of edits (inserts and deletes of one element each),
  24    this sequence is short - or equivalently, if the ordered list
  25    of elements that are untouched by these edits is long.  For a
  26    good introduction to the subject, read about the "Levenshtein
  27    distance" in Wikipedia.
  28
  29    The basic algorithm is described in:
  30    "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
  31    Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
  32    see especially section 4.2, which describes the variation used below.
  33
  34    The basic algorithm was independently discovered as described in:
  35    "Algorithms for Approximate String Matching", E. Ukkonen,
  36    Information and Control Vol. 64, 1985, pp. 100-118.
  37
  38    Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
  39    heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
  40    at the price of producing suboptimal output for large inputs with
  41    many differences.  */
  42
  43 #include <config.h>
  44
  45 /* Specification.  */
  46 #include "fstrcmp.h"
  47
  48 #include <string.h>
  49 #include <stdbool.h>
  50 #include <stdio.h>
  51 #include <stdlib.h>
  52 #include <limits.h>
  53
  54 #include "glthread/lock.h"
  55 #include "glthread/tls.h"
  56 #include "minmax.h"
  57 #include "xalloc.h"
  58
  59 #ifndef uintptr_t
  60 # define uintptr_t unsigned long
  61 #endif
  62
  63
  64 #define ELEMENT char
  65 #define EQUAL(x,y) ((x) == (y))
  66 #define OFFSET int
  67 #define EXTRA_CONTEXT_FIELDS \
  68   /* The number of elements inserted or deleted. */ \
  69   int xvec_edit_count; \
  70   int yvec_edit_count;
  71 #define NOTE_DELETE(ctxt, xoff) ctxt->xvec_edit_count++
  72 #define NOTE_INSERT(ctxt, yoff) ctxt->yvec_edit_count++
  73 /* We don't need USE_HEURISTIC, since it is unlikely in typical uses of
  74    fstrcmp().  */
  75 #include "diffseq.h"
  76
  77
  78 /* Because fstrcmp is typically called multiple times, attempt to minimize
  79    the number of memory allocations performed.  Thus, let a call reuse the
  80    memory already allocated by the previous call, if it is sufficient.
  81    To make it multithread-safe, without need for a lock that protects the
  82    already allocated memory, store the allocated memory per thread.  Free
  83    it only when the thread exits.  */
  84
  85 static gl_tls_key_t buffer_key; /* TLS key for a 'int *' */
  86 static gl_tls_key_t bufmax_key; /* TLS key for a 'size_t' */
  87
  88 static void
  89 keys_init (void)
  90 {
  91   gl_tls_key_init (buffer_key, free);
  92   gl_tls_key_init (bufmax_key, NULL);
  93   /* The per-thread initial values are NULL and 0, respectively.  */
  94 }
  95
  96 /* Ensure that keys_init is called once only.  */
  97 gl_once_define(static, keys_init_once)
  98
  99
 100 double
 101 fstrcmp_bounded (const char *string1, const char *string2, double lower_bound)
 102 {
 103   struct context ctxt;
 104   int xvec_length = strlen (string1);
 105   int yvec_length = strlen (string2);
 106   int i;
 107
 108   size_t fdiag_len;
 109   int *buffer;
 110   size_t bufmax;
 111
 112   /* short-circuit obvious comparisons */
 113   if (xvec_length == 0 || yvec_length == 0)
 114     return (xvec_length == 0 && yvec_length == 0 ? 1.0 : 0.0);
 115
 116   if (lower_bound > 0)
 117     {
 118       /* Compute a quick upper bound.
 119          Each edit is an insertion or deletion of an element, hence modifies
 120          the length of the sequence by at most 1.
 121          Therefore, when starting from a sequence X and ending at a sequence Y,
 122          with N edits,  | yvec_length - xvec_length | <= N.  (Proof by
 123          induction over N.)
 124          So, at the end, we will have
 125            xvec_edit_count + yvec_edit_count >= | xvec_length - yvec_length |.
 126          and hence
 127            result
 128              = (xvec_length + yvec_length - (xvec_edit_count + yvec_edit_count))
 129                / (xvec_length + yvec_length)
 130              <= (xvec_length + yvec_length - | yvec_length - xvec_length |)
 131                 / (xvec_length + yvec_length)
 132              = 2 * min (xvec_length, yvec_length) / (xvec_length + yvec_length).
 133        */
 134       volatile double upper_bound =
 135         (double) (2 * MIN (xvec_length, yvec_length))
 136         / (xvec_length + yvec_length);
 137
 138       if (upper_bound < lower_bound)
 139         /* Return an arbitrary value < LOWER_BOUND.  */
 140         return 0.0;
 141     }
 142
 143   /* set the info for each string.  */
 144   ctxt.xvec = string1;
 145   ctxt.yvec = string2;
 146
 147   /* Set TOO_EXPENSIVE to be approximate square root of input size,
 148      bounded below by 256.  */
 149   ctxt.too_expensive = 1;
 150   for (i = xvec_length + yvec_length;
 151        i != 0;
 152        i >>= 2)
 153     ctxt.too_expensive <<= 1;
 154   if (ctxt.too_expensive < 256)
 155     ctxt.too_expensive = 256;
 156
 157   /* Allocate memory for fdiag and bdiag from a thread-local pool.  */
 158   fdiag_len = xvec_length + yvec_length + 3;
 159   gl_once (keys_init_once, keys_init);
 160   buffer = (int *) gl_tls_get (buffer_key);
 161   bufmax = (size_t) (uintptr_t) gl_tls_get (bufmax_key);
 162   if (fdiag_len > bufmax)
 163     {
 164       /* Need more memory.  */
 165       bufmax = 2 * bufmax;
 166       if (fdiag_len > bufmax)
 167         bufmax = fdiag_len;
 168       /* Calling xrealloc would be a waste: buffer's contents does not need
 169          to be preserved.  */
 170       if (buffer != NULL)
 171         free (buffer);
 172       buffer = (int *) xnmalloc (bufmax, 2 * sizeof (int));
 173       gl_tls_set (buffer_key, buffer);
 174       gl_tls_set (bufmax_key, (void *) (uintptr_t) bufmax);
 175     }
 176   ctxt.fdiag = buffer + yvec_length + 1;
 177   ctxt.bdiag = ctxt.fdiag + fdiag_len;
 178
 179   /* Now do the main comparison algorithm */
 180   ctxt.xvec_edit_count = 0;
 181   ctxt.yvec_edit_count = 0;
 182   compareseq (0, xvec_length, 0, yvec_length, 0,
 183               &ctxt);
 184
 185   /* The result is
 186         ((number of chars in common) / (average length of the strings)).
 187      This is admittedly biased towards finding that the strings are
 188      similar, however it does produce meaningful results.  */
 189   return ((double) (xvec_length + yvec_length
 190                     - ctxt.yvec_edit_count - ctxt.xvec_edit_count)
 191           / (xvec_length + yvec_length));
 192 }