lib/strutil/strverscmp.c

   1 /*
   2    Compare strings while treating digits characters numerically.
   3
   4    Copyright (C) 1997, 2002, 2011
   5    The Free Software Foundation, Inc.
   6
   7    This file is part of the GNU C Library.
   8    Contributed by Jean-Fran�ois Bignolles <bignolle ecoledoc ibp fr>, 1997.
   9
  10    This file is part of the Midnight Commander.
  11
  12    The Midnight Commander is free software: you can redistribute it
  13    and/or modify it under the terms of the GNU General Public License as
  14    published by the Free Software Foundation, either version 3 of the License,
  15    or (at your option) any later version.
  16
  17    The Midnight Commander is distributed in the hope that it will be useful,
  18    but WITHOUT ANY WARRANTY; without even the implied warranty of
  19    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20    GNU General Public License for more details.
  21
  22    You should have received a copy of the GNU General Public License
  23    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  24  */
  25
  26 #include <ctype.h>
  27 #ifdef HAVE_STRVERSCMP
  28 #include <string.h>
  29 #endif /* HAVE_STRVERSCMP */
  30
  31 #include "lib/strutil.h"
  32
  33 /* states: S_N: normal, S_I: comparing integral part, S_F: comparing
  34    fractionnal parts, S_Z: idem but with leading Zeroes only */
  35 #define  S_N    0x0
  36 #define  S_I    0x4
  37 #define  S_F    0x8
  38 #define  S_Z    0xC
  39
  40 /* result_type: CMP: return diff; LEN: compare using len_diff/diff */
  41 #define  CMP    2
  42 #define  LEN    3
  43
  44
  45 /* Compare S1 and S2 as strings holding indices/version numbers,
  46    returning less than, equal to or greater than zero if S1 is less than,
  47    equal to or greater than S2 (for more info, see the texinfo doc).
  48  */
  49
  50 int
  51 str_verscmp (const char *s1, const char *s2)
  52 {
  53 #ifdef HAVE_STRVERSCMP
  54     return strverscmp (s1, s2);
  55 #else /* HAVE_STRVERSCMP */
  56     unsigned char *p1 = (unsigned char *) s1;
  57     unsigned char *p2 = (unsigned char *) s2;
  58     unsigned char c1, c2;
  59     int state;
  60     int diff;
  61
  62     /* Symbol(s)    0       [1-9]   others  (padding)
  63        Transition   (10) 0  (01) d  (00) x  (11) -   */
  64     static const unsigned int next_state[] = {
  65         /* state    x    d    0    - */
  66         /* S_N */ S_N, S_I, S_Z, S_N,
  67         /* S_I */ S_N, S_I, S_I, S_I,
  68         /* S_F */ S_N, S_F, S_F, S_F,
  69         /* S_Z */ S_N, S_F, S_Z, S_Z
  70     };
  71
  72     static const int result_type[] = {
  73         /* state   x/x  x/d  x/0  x/-  d/x  d/d  d/0  d/-
  74            0/x  0/d  0/0  0/-  -/x  -/d  -/0  -/- */
  75
  76         /* S_N */ CMP, CMP, CMP, CMP, CMP, LEN, CMP, CMP,
  77         CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP,
  78         /* S_I */ CMP, -1, -1, CMP, +1, LEN, LEN, CMP,
  79         +1, LEN, LEN, CMP, CMP, CMP, CMP, CMP,
  80         /* S_F */ CMP, CMP, CMP, CMP, CMP, LEN, CMP, CMP,
  81         CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP,
  82         /* S_Z */ CMP, +1, +1, CMP, -1, CMP, CMP, CMP,
  83         -1, CMP, CMP, CMP
  84     };
  85
  86     if (p1 == p2)
  87         return 0;
  88
  89     c1 = *p1++;
  90     c2 = *p2++;
  91     /* Hint: '0' is a digit too.  */
  92     state = S_N | ((c1 == '0') + (isdigit (c1) != 0));
  93
  94     while ((diff = c1 - c2) == 0 && c1 != '\0')
  95     {
  96         state = next_state[state];
  97         c1 = *p1++;
  98         c2 = *p2++;
  99         state |= (c1 == '0') + (isdigit (c1) != 0);
 100     }
 101
 102     state = result_type[state << 2 | (((c2 == '0') + (isdigit (c2) != 0)))];
 103
 104     switch (state)
 105     {
 106     case CMP:
 107         return diff;
 108
 109     case LEN:
 110         while (isdigit (*p1++))
 111             if (!isdigit (*p2++))
 112                 return 1;
 113
 114         return isdigit (*p2) ? -1 : diff;
 115
 116     default:
 117         return state;
 118     }
 119 #endif /* HAVE_STRVERSCMP */
 120
 121 }