versioncmp.c

   1 #include "cache.h"
   2 #include "string-list.h"
   3
   4 /*
   5  * versioncmp(): copied from string/strverscmp.c in glibc commit
   6  * ee9247c38a8def24a59eb5cfb7196a98bef8cfdc, reformatted to Git coding
   7  * style. The implementation is under LGPL-2.1 and Git relicenses it
   8  * to GPLv2.
   9  */
  10
  11 /*
  12  * states: S_N: normal, S_I: comparing integral part, S_F: comparing
  13  * fractionnal parts, S_Z: idem but with leading Zeroes only
  14  */
  15 #define  S_N    0x0
  16 #define  S_I    0x3
  17 #define  S_F    0x6
  18 #define  S_Z    0x9
  19
  20 /* result_type: CMP: return diff; LEN: compare using len_diff/diff */
  21 #define  CMP    2
  22 #define  LEN    3
  23
  24 static const struct string_list *prereleases;
  25 static int initialized;
  26
  27 /*
  28  * p1 and p2 point to the first different character in two strings. If
  29  * either p1 or p2 starts with a prerelease suffix, it will be forced
  30  * to be on top.
  31  *
  32  * If both p1 and p2 start with (different) suffix, the order is
  33  * determined by config file.
  34  *
  35  * Note that we don't have to deal with the situation when both p1 and
  36  * p2 start with the same suffix because the common part is already
  37  * consumed by the caller.
  38  *
  39  * Return non-zero if *diff contains the return value for versioncmp()
  40  */
  41 static int swap_prereleases(const void *p1_,
  42                             const void *p2_,
  43                             int *diff)
  44 {
  45         const char *p1 = p1_;
  46         const char *p2 = p2_;
  47         int i, i1 = -1, i2 = -1;
  48
  49         for (i = 0; i < prereleases->nr; i++) {
  50                 const char *suffix = prereleases->items[i].string;
  51                 if (i1 == -1 && starts_with(p1, suffix))
  52                         i1 = i;
  53                 if (i2 == -1 && starts_with(p2, suffix))
  54                         i2 = i;
  55         }
  56         if (i1 == -1 && i2 == -1)
  57                 return 0;
  58         if (i1 >= 0 && i2 >= 0)
  59                 *diff = i1 - i2;
  60         else if (i1 >= 0)
  61                 *diff = -1;
  62         else /* if (i2 >= 0) */
  63                 *diff = 1;
  64         return 1;
  65 }
  66
  67 /*
  68  * Compare S1 and S2 as strings holding indices/version numbers,
  69  * returning less than, equal to or greater than zero if S1 is less
  70  * than, equal to or greater than S2 (for more info, see the texinfo
  71  * doc).
  72  */
  73
  74 int versioncmp(const char *s1, const char *s2)
  75 {
  76         const unsigned char *p1 = (const unsigned char *) s1;
  77         const unsigned char *p2 = (const unsigned char *) s2;
  78         unsigned char c1, c2;
  79         int state, diff;
  80
  81         /*
  82          * Symbol(s)    0       [1-9]   others
  83          * Transition   (10) 0  (01) d  (00) x
  84          */
  85         static const uint8_t next_state[] = {
  86                 /* state    x    d    0  */
  87                 /* S_N */  S_N, S_I, S_Z,
  88                 /* S_I */  S_N, S_I, S_I,
  89                 /* S_F */  S_N, S_F, S_F,
  90                 /* S_Z */  S_N, S_F, S_Z
  91         };
  92
  93         static const int8_t result_type[] = {
  94                 /* state   x/x  x/d  x/0  d/x  d/d  d/0  0/x  0/d  0/0  */
  95
  96                 /* S_N */  CMP, CMP, CMP, CMP, LEN, CMP, CMP, CMP, CMP,
  97                 /* S_I */  CMP, -1,  -1,  +1,  LEN, LEN, +1,  LEN, LEN,
  98                 /* S_F */  CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP,
  99                 /* S_Z */  CMP, +1,  +1,  -1,  CMP, CMP, -1,  CMP, CMP
 100         };
 101
 102         if (p1 == p2)
 103                 return 0;
 104
 105         c1 = *p1++;
 106         c2 = *p2++;
 107         /* Hint: '0' is a digit too.  */
 108         state = S_N + ((c1 == '0') + (isdigit (c1) != 0));
 109
 110         while ((diff = c1 - c2) == 0) {
 111                 if (c1 == '\0')
 112                         return diff;
 113
 114                 state = next_state[state];
 115                 c1 = *p1++;
 116                 c2 = *p2++;
 117                 state += (c1 == '0') + (isdigit (c1) != 0);
 118         }
 119
 120         if (!initialized) {
 121                 initialized = 1;
 122                 prereleases = git_config_get_value_multi("versionsort.prereleasesuffix");
 123         }
 124         if (prereleases && swap_prereleases(p1 - 1, p2 - 1, &diff))
 125                 return diff;
 126
 127         state = result_type[state * 3 + (((c2 == '0') + (isdigit (c2) != 0)))];
 128
 129         switch (state) {
 130         case CMP:
 131                 return diff;
 132
 133         case LEN:
 134                 while (isdigit (*p1++))
 135                         if (!isdigit (*p2++))
 136                                 return 1;
 137
 138                 return isdigit (*p2) ? -1 : diff;
 139
 140         default:
 141                 return state;
 142         }
 143 }