[lxc-devel] [lxd/master] lxc: Bundle sortorder
stgraber on Github
lxc-bot at linuxcontainers.org
Tue Aug 18 16:08:21 UTC 2020
A non-text attachment was scrubbed...
Name: not available
Type: text/x-mailbox
Size: 354 bytes
Desc: not available
URL: <http://lists.linuxcontainers.org/pipermail/lxc-devel/attachments/20200818/33340dcd/attachment.bin>
-------------- next part --------------
From 5c06ea105ed1fe82cc7bd63e1687b413ff78ead8 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?St=C3=A9phane=20Graber?= <stgraber at ubuntu.com>
Date: Tue, 18 Aug 2020 12:07:41 -0400
Subject: [PATCH] lxc: Bundle sortorder
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Signed-off-by: Stéphane Graber <stgraber at ubuntu.com>
---
lxc/utils.go | 9 +++---
lxc/utils_sortorder.go | 69 ++++++++++++++++++++++++++++++++++++++++++
2 files changed, 73 insertions(+), 5 deletions(-)
create mode 100644 lxc/utils_sortorder.go
diff --git a/lxc/utils.go b/lxc/utils.go
index 6dcbb9b285..4935fd4adf 100644
--- a/lxc/utils.go
+++ b/lxc/utils.go
@@ -8,7 +8,6 @@ import (
"strings"
"github.com/pkg/errors"
- "vbom.ml/util/sortorder"
lxd "github.com/lxc/lxd/client"
"github.com/lxc/lxd/shared/api"
@@ -42,7 +41,7 @@ func (a stringList) Less(i, j int) bool {
return true
}
- return sortorder.NaturalLess(a[i][x], a[j][x])
+ return NaturalLess(a[i][x], a[j][x])
}
// Instance name sorting
@@ -65,7 +64,7 @@ func (a byName) Less(i, j int) bool {
return true
}
- return sortorder.NaturalLess(a[i][0], a[j][0])
+ return NaturalLess(a[i][0], a[j][0])
}
// Storage volume sorting
@@ -85,7 +84,7 @@ func (a byNameAndType) Less(i, j int) bool {
jType := strings.Split(a[j][0], " ")[0]
if iType != jType {
- return sortorder.NaturalLess(a[i][0], a[j][0])
+ return NaturalLess(a[i][0], a[j][0])
}
if a[i][1] == "" {
@@ -96,7 +95,7 @@ func (a byNameAndType) Less(i, j int) bool {
return true
}
- return sortorder.NaturalLess(a[i][1], a[j][1])
+ return NaturalLess(a[i][1], a[j][1])
}
// Batch operations
diff --git a/lxc/utils_sortorder.go b/lxc/utils_sortorder.go
new file mode 100644
index 0000000000..28c82c92a9
--- /dev/null
+++ b/lxc/utils_sortorder.go
@@ -0,0 +1,69 @@
+package main
+
+// This is copied from https://github.com/fvbommel/util/blob/master/sortorder/natsort.go
+// As this is the only function we need from this repository and its
+// download link is often unreliable, we are directly copying the function
+// here.
+//
+// Source repository license: MIT
+
+// NaturalLess compares two strings using natural ordering. This means that e.g.
+// "abc2" < "abc12".
+//
+// Non-digit sequences and numbers are compared separately. The former are
+// compared bytewise, while the latter are compared numerically (except that
+// the number of leading zeros is used as a tie-breaker, so e.g. "2" < "02")
+//
+// Limitation: only ASCII digits (0-9) are considered.
+func NaturalLess(str1, str2 string) bool {
+ idx1, idx2 := 0, 0
+ for idx1 < len(str1) && idx2 < len(str2) {
+ c1, c2 := str1[idx1], str2[idx2]
+ dig1, dig2 := isdigit(c1), isdigit(c2)
+ switch {
+ case dig1 != dig2: // Digits before other characters.
+ return dig1 // True if LHS is a digit, false if the RHS is one.
+ case !dig1: // && !dig2, because dig1 == dig2
+ // UTF-8 compares bytewise-lexicographically, no need to decode
+ // codepoints.
+ if c1 != c2 {
+ return c1 < c2
+ }
+ idx1++
+ idx2++
+ default: // Digits
+ // Eat zeros.
+ for ; idx1 < len(str1) && str1[idx1] == '0'; idx1++ {
+ }
+ for ; idx2 < len(str2) && str2[idx2] == '0'; idx2++ {
+ }
+ // Eat all digits.
+ nonZero1, nonZero2 := idx1, idx2
+ for ; idx1 < len(str1) && isdigit(str1[idx1]); idx1++ {
+ }
+ for ; idx2 < len(str2) && isdigit(str2[idx2]); idx2++ {
+ }
+ // If lengths of numbers with non-zero prefix differ, the shorter
+ // one is less.
+ if len1, len2 := idx1-nonZero1, idx2-nonZero2; len1 != len2 {
+ return len1 < len2
+ }
+ // If they're equal, string comparison is correct.
+ if nr1, nr2 := str1[nonZero1:idx1], str2[nonZero2:idx2]; nr1 != nr2 {
+ return nr1 < nr2
+ }
+ // Otherwise, the one with less zeros is less.
+ // Because everything up to the number is equal, comparing the index
+ // after the zeros is sufficient.
+ if nonZero1 != nonZero2 {
+ return nonZero1 < nonZero2
+ }
+ }
+ // They're identical so far, so continue comparing.
+ }
+ // So far they are identical. At least one is ended. If the other continues,
+ // it sorts last.
+ return len(str1) < len(str2)
+}
+
+func isdigit(b byte) bool { return '0' <= b && b <= '9' }
More information about the lxc-devel
mailing list