Andrew's git - gitweb.git/blob

f86ac562e294c59c829ff6da60eb0f99c712c0b4
   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
  24static const struct string_list *prereleases;
  25static int initialized;
  26
  27/*
  28 * off is the offset of the first different character in the two strings
  29 * s1 and s2. If either s1 or s2 contains a prerelease suffix containing
  30 * that offset, then that string will be forced to be on top.
  31 *
  32 * If both s1 and s2 contain a (different) suffix around that position,
  33 * their order is determined by the order of those two suffixes in the
  34 * configuration.
  35 * If any of the strings contains more than one different suffixes around
  36 * that position, then that string is sorted according to the contained
  37 * suffix which comes first in the configuration.
  38 *
  39 * Return non-zero if *diff contains the return value for versioncmp()
  40 */
  41static int swap_prereleases(const char *s1,
  42                            const char *s2,
  43                            int off,
  44                            int *diff)
  45{
  46        int i, i1 = -1, i2 = -1;
  47
  48        for (i = 0; i < prereleases->nr; i++) {
  49                const char *suffix = prereleases->items[i].string;
  50                int j, start, suffix_len = strlen(suffix);
  51                if (suffix_len < off)
  52                        start = off - suffix_len + 1;
  53                else
  54                        start = 0;
  55                for (j = start; j <= off; j++)
  56                        if (i1 == -1 && starts_with(s1 + j, suffix)) {
  57                                i1 = i;
  58                                break;
  59                        }
  60                for (j = start; j <= off; j++)
  61                        if (i2 == -1 && starts_with(s2 + j, suffix)) {
  62                                i2 = i;
  63                                break;
  64                        }
  65        }
  66        if (i1 == -1 && i2 == -1)
  67                return 0;
  68        if (i1 >= 0 && i2 >= 0)
  69                *diff = i1 - i2;
  70        else if (i1 >= 0)
  71                *diff = -1;
  72        else /* if (i2 >= 0) */
  73                *diff = 1;
  74        return 1;
  75}
  76
  77/*
  78 * Compare S1 and S2 as strings holding indices/version numbers,
  79 * returning less than, equal to or greater than zero if S1 is less
  80 * than, equal to or greater than S2 (for more info, see the texinfo
  81 * doc).
  82 */
  83
  84int versioncmp(const char *s1, const char *s2)
  85{
  86        const unsigned char *p1 = (const unsigned char *) s1;
  87        const unsigned char *p2 = (const unsigned char *) s2;
  88        unsigned char c1, c2;
  89        int state, diff;
  90
  91        /*
  92         * Symbol(s)    0       [1-9]   others
  93         * Transition   (10) 0  (01) d  (00) x
  94         */
  95        static const uint8_t next_state[] = {
  96                /* state    x    d    0  */
  97                /* S_N */  S_N, S_I, S_Z,
  98                /* S_I */  S_N, S_I, S_I,
  99                /* S_F */  S_N, S_F, S_F,
 100                /* S_Z */  S_N, S_F, S_Z
 101        };
 102
 103        static const int8_t result_type[] = {
 104                /* state   x/x  x/d  x/0  d/x  d/d  d/0  0/x  0/d  0/0  */
 105
 106                /* S_N */  CMP, CMP, CMP, CMP, LEN, CMP, CMP, CMP, CMP,
 107                /* S_I */  CMP, -1,  -1,  +1,  LEN, LEN, +1,  LEN, LEN,
 108                /* S_F */  CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP,
 109                /* S_Z */  CMP, +1,  +1,  -1,  CMP, CMP, -1,  CMP, CMP
 110        };
 111
 112        if (p1 == p2)
 113                return 0;
 114
 115        c1 = *p1++;
 116        c2 = *p2++;
 117        /* Hint: '0' is a digit too.  */
 118        state = S_N + ((c1 == '0') + (isdigit (c1) != 0));
 119
 120        while ((diff = c1 - c2) == 0) {
 121                if (c1 == '\0')
 122                        return diff;
 123
 124                state = next_state[state];
 125                c1 = *p1++;
 126                c2 = *p2++;
 127                state += (c1 == '0') + (isdigit (c1) != 0);
 128        }
 129
 130        if (!initialized) {
 131                initialized = 1;
 132                prereleases = git_config_get_value_multi("versionsort.prereleasesuffix");
 133        }
 134        if (prereleases && swap_prereleases(s1, s2, (const char *) p1 - s1 - 1,
 135                                            &diff))
 136                return diff;
 137
 138        state = result_type[state * 3 + (((c2 == '0') + (isdigit (c2) != 0)))];
 139
 140        switch (state) {
 141        case CMP:
 142                return diff;
 143
 144        case LEN:
 145                while (isdigit (*p1++))
 146                        if (!isdigit (*p2++))
 147                                return 1;
 148
 149                return isdigit (*p2) ? -1 : diff;
 150
 151        default:
 152                return state;
 153        }
 154}