[pacman-dev] Version comparison algorithm.
richard.o.dodd at gmail.com
Sat Mar 16 14:02:22 UTC 2019
I'm writing to ask about the version comparison function `rpmvercmp` in
`libalpm/version.cL83`. The algorithm is complex and I'm trying to
understand its behavior. I want to hash using the package name and version
as a key, and so I need a hash function where `i1 == i2 => hash(i1) ==
hash(i2)` according to the version comparison operation. I'll describe how
the algorithm behaves and then ask my questions.
The algorithm works on a byte string and uses ascii comparison rules (no
- First, split the input up into blocks of *alpha*, *digit* or
- For each pair of blocks
- If the types are different, then *non-alphanum* is newer than
*numeric*, which is newer than *alpha*
- If the types are the same, then the rules are
- For *non-alphanum*, compare lengths, longer is newer, equal lengths
are equal segments (so *--* and *::* are the same)
- For *alpha* just do a lexicographic comparison (so *b* is newer
than *a* etc.)
- For *numeric*, do a numeric comparison. (this can be done by
skipping leading zeros, then comparing length, then comparing
lexicographically, to avoid overflow on integer conversion)
- If one input is longer than the other, and all sections so far have
been equal, then if the next section of the longer is *alpha*, it is older,
and if it is *numeric* it is newer. (so "1a" is older than "1", "a1" is
newer than "a").
- If the inputs have the same number of sections that are all equal, then
they are equal.
1. Is the algorithm correctly described here.
2. This should mean that if I hash length for *non-numeric*, the string
with stripped zeros for *numeric*, and just the string for *alpha*, the has
law should be upheld. Is this correct?
More information about the pacman-dev