root/lib/strutil/filevercmp.c

/* [previous][next][first][last][top][bottom][index][help]  */

DEFINITIONS

This source file includes following definitions.
  1. file_prefixlen
  2. order
  3. verrevcmp
  4. filevercmp
  5. filenvercmp

   1 /*
   2    Copyright (C) 1995 Ian Jackson <iwj10@cus.cam.ac.uk>
   3    Copyright (C) 2001 Anthony Towns <aj@azure.humbug.org.au>
   4    Copyright (C) 2008-2022 Free Software Foundation, Inc.
   5 
   6    This file is free software: you can redistribute it and/or modify
   7    it under the terms of the GNU Lesser General Public License as
   8    published by the Free Software Foundation, either version 3 of the
   9    License, or (at your option) any later version.
  10 
  11    This file is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU Lesser General Public License for more details.
  15 
  16    You should have received a copy of the GNU Lesser General Public License
  17    along with this program.  If not, see <https://www.gnu.org/licenses/>.
  18  */
  19 
  20 #include <config.h>
  21 
  22 #include <stdlib.h>
  23 #include <limits.h>
  24 
  25 #include "lib/strutil.h"
  26 
  27 /*** global variables ****************************************************************************/
  28 
  29 /*** file scope macro definitions ****************************************************************/
  30 
  31 /*** file scope type declarations ****************************************************************/
  32 
  33 /*** file scope variables ************************************************************************/
  34 
  35 /* --------------------------------------------------------------------------------------------- */
  36 /*** file scope functions ************************************************************************/
  37 /* --------------------------------------------------------------------------------------------- */
  38 
  39 /* Return the length of a prefix of @s that corresponds to the suffix defined by this extended
  40  * regular expression in the C locale: (\.[A-Za-z~][A-Za-z0-9~]*)*$
  41  *
  42  * Use the longest suffix matching this regular expression, except do not use all of s as a suffix
  43  * if s is nonempty.
  44  *
  45  * If *len is -1, s is a string; set *lem to s's length.
  46  * Otherwise, *len should be nonnegative, s is a char array, and *len does not change.
  47  */
  48 static ssize_t
  49 file_prefixlen (const char *s, ssize_t * len)
     /* [previous][next][first][last][top][bottom][index][help]  */
  50 {
  51     size_t n = (size_t) (*len); /* SIZE_MAX if N == -1 */
  52     size_t i = 0;
  53     size_t prefixlen = 0;
  54 
  55     while (TRUE)
  56     {
  57         gboolean done;
  58 
  59         if (*len < 0)
  60             done = s[i] == '\0';
  61         else
  62             done = i == n;
  63 
  64         if (done)
  65         {
  66             *len = (ssize_t) i;
  67             return (ssize_t) prefixlen;
  68         }
  69 
  70         i++;
  71         prefixlen = i;
  72 
  73         while (i + 1 < n && s[i] == '.' && (g_ascii_isalpha (s[i + 1]) || s[i + 1] == '~'))
  74             for (i += 2; i < n && (g_ascii_isalnum (s[i]) || s[i] == '~'); i++)
  75                 ;
  76     }
  77 }
  78 
  79 /* --------------------------------------------------------------------------------------------- */
  80 
  81 /* Return a version sort comparison value for @s's byte at position @pos.
  82  *
  83  * @param s a string
  84  * @param pos a position in @s
  85  * @param len a length of @s. If @pos == @len, sort before all non-'~' bytes.
  86  */
  87 
  88 static int
  89 order (const char *s, size_t pos, size_t len)
     /* [previous][next][first][last][top][bottom][index][help]  */
  90 {
  91     unsigned char c;
  92 
  93     if (pos == len)
  94         return (-1);
  95 
  96     c = s[pos];
  97 
  98     if (g_ascii_isdigit (c))
  99         return 0;
 100     if (g_ascii_isalpha (c))
 101         return c;
 102     if (c == '~')
 103         return (-2);
 104 
 105     g_assert (UCHAR_MAX <= (INT_MAX - 1 - 2) / 2);
 106 
 107     return (int) c + UCHAR_MAX + 1;
 108 }
 109 
 110 /* --------------------------------------------------------------------------------------------- */
 111 
 112 /* Slightly modified verrevcmp function from dpkg
 113  *
 114  * This implements the algorithm for comparison of version strings
 115  * specified by Debian and now widely adopted.  The detailed
 116  * specification can be found in the Debian Policy Manual in the
 117  * section on the 'Version' control field.  This version of the code
 118  * implements that from s5.6.12 of Debian Policy v3.8.0.1
 119  * https://www.debian.org/doc/debian-policy/ch-controlfields.html#s-f-Version
 120  *
 121  * @param s1 first char array to compare
 122  * @param s1_len length of @s1
 123  * @param s2 second char array to compare
 124  * @param s2_len length of @s2
 125  *
 126  * @return an integer less than, equal to, or greater than zero, if @s1 is <, == or > than @s2.
 127  */
 128 static int
 129 verrevcmp (const char *s1, ssize_t s1_len, const char *s2, ssize_t s2_len)
     /* [previous][next][first][last][top][bottom][index][help]  */
 130 {
 131     ssize_t s1_pos = 0;
 132     ssize_t s2_pos = 0;
 133 
 134     while (s1_pos < s1_len || s2_pos < s2_len)
 135     {
 136         int first_diff = 0;
 137 
 138         while ((s1_pos < s1_len && !g_ascii_isdigit (s1[s1_pos]))
 139                || (s2_pos < s2_len && !g_ascii_isdigit (s2[s2_pos])))
 140         {
 141             int s1_c, s2_c;
 142 
 143             s1_c = order (s1, s1_pos, s1_len);
 144             s2_c = order (s2, s2_pos, s2_len);
 145 
 146             if (s1_c != s2_c)
 147                 return (s1_c - s2_c);
 148 
 149             s1_pos++;
 150             s2_pos++;
 151         }
 152 
 153         while (s1_pos < s1_len && s1[s1_pos] == '0')
 154             s1_pos++;
 155         while (s2_pos < s2_len && s2[s2_pos] == '0')
 156             s2_pos++;
 157 
 158         while (s1_pos < s1_len && s2_pos < s2_len
 159                && g_ascii_isdigit (s1[s1_pos]) && g_ascii_isdigit (s2[s2_pos]))
 160         {
 161             if (first_diff == 0)
 162                 first_diff = s1[s1_pos] - s2[s2_pos];
 163 
 164             s1_pos++;
 165             s2_pos++;
 166         }
 167 
 168         if (s1_pos < s1_len && g_ascii_isdigit (s1[s1_pos]))
 169             return 1;
 170         if (s2_pos < s2_len && g_ascii_isdigit (s2[s2_pos]))
 171             return (-1);
 172         if (first_diff != 0)
 173             return first_diff;
 174     }
 175 
 176     return 0;
 177 }
 178 
 179 /* --------------------------------------------------------------------------------------------- */
 180 /*** public functions ****************************************************************************/
 181 /* --------------------------------------------------------------------------------------------- */
 182 
 183 /* Compare version strings.
 184  *
 185  * @param s1 first string to compare
 186  * @param s2 second string to compare
 187  *
 188  * @return an integer less than, equal to, or greater than zero, if @s1 is <, == or > than @s2.
 189  */
 190 int
 191 filevercmp (const char *s1, const char *s2)
     /* [previous][next][first][last][top][bottom][index][help]  */
 192 {
 193     return filenvercmp (s1, -1, s2, -1);
 194 }
 195 
 196 /* --------------------------------------------------------------------------------------------- */
 197 /* Compare version strings.
 198  *
 199  * @param a first string to compare
 200  * @param alen length of @a or (-1)
 201  * @param b second string to compare
 202  * @param blen length of @b or (-1)
 203  *
 204  * @return an integer less than, equal to, or greater than zero, if @s1 is <, == or > than @s2.
 205  */
 206 int
 207 filenvercmp (const char *a, ssize_t alen, const char *b, ssize_t blen)
     /* [previous][next][first][last][top][bottom][index][help]  */
 208 {
 209     gboolean aempty, bempty;
 210     ssize_t aprefixlen, bprefixlen;
 211     gboolean one_pass_only;
 212     int result;
 213 
 214     /* Special case for empty versions. */
 215     aempty = alen < 0 ? a[0] == '\0' : alen == 0;
 216     bempty = blen < 0 ? b[0] == '\0' : blen == 0;
 217 
 218     if (aempty)
 219         return (bempty ? 0 : -1);
 220     if (bempty)
 221         return 1;
 222 
 223     /* Special cases for leading ".": "." sorts first, then "..", then other names with leading ".",
 224        then other names. */
 225     if (a[0] == '.')
 226     {
 227         gboolean adot, bdot;
 228         gboolean adotdot, bdotdot;
 229 
 230         if (b[0] != '.')
 231             return (-1);
 232 
 233         adot = alen < 0 ? a[1] == '\0' : alen == 1;
 234         bdot = blen < 0 ? b[1] == '\0' : blen == 1;
 235 
 236         if (adot)
 237             return (bdot ? 0 : -1);
 238         if (bdot)
 239             return 1;
 240 
 241         adotdot = a[1] == '.' && (alen < 0 ? a[2] == '\0' : alen == 2);
 242         bdotdot = b[1] == '.' && (blen < 0 ? b[2] == '\0' : blen == 2);
 243         if (adotdot)
 244             return (bdotdot ? 0 : -1);
 245         if (bdotdot)
 246             return 1;
 247     }
 248     else if (b[0] == '.')
 249         return 1;
 250 
 251     /* Cut file suffixes. */
 252     aprefixlen = file_prefixlen (a, &alen);
 253     bprefixlen = file_prefixlen (b, &blen);
 254 
 255     /* If both suffixes are empty, a second pass would return the same thing. */
 256     one_pass_only = aprefixlen == alen && bprefixlen == blen;
 257 
 258     result = verrevcmp (a, aprefixlen, b, bprefixlen);
 259 
 260     /* Return the initial result if nonzero, or if no second pass is needed.
 261        Otherwise, restore the suffixes and try again. */
 262     return (result != 0 || one_pass_only ? result : verrevcmp (a, alen, b, blen));
 263 }
 264 
 265 /* --------------------------------------------------------------------------------------------- */

/* [previous][next][first][last][top][bottom][index][help]  */