Home Home > GIT Browse > linux-next
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKernel Build Daemon <kbuild@suse.de>2019-08-09 12:03:18 +0200
committerKernel Build Daemon <kbuild@suse.de>2019-08-09 12:03:18 +0200
commit26547e8b20c913be0a1546922e357ce9e934fa16 (patch)
tree105f2a2dfd8fd1446408deae8bdfc704eb45ffdd
parent0f00fd8bf6f319ac417d85fd8b140681b3cc511e (diff)
parent398394fe5ff169dc9b36c637d21460d5c91bd048 (diff)
Merge branch 'scripts' into linux-next
-rw-r--r--scripts/git_sort/lib.py80
-rwxr-xr-xscripts/git_sort/merge_tool.py8
-rwxr-xr-xscripts/sort_supported.rb89
3 files changed, 173 insertions, 4 deletions
diff --git a/scripts/git_sort/lib.py b/scripts/git_sort/lib.py
index 9f7da0efb6..4a4f9d3241 100644
--- a/scripts/git_sort/lib.py
+++ b/scripts/git_sort/lib.py
@@ -26,6 +26,7 @@ import re
import signal
import subprocess
import sys
+import weakref
import pygit2_wrapper as pygit2
@@ -558,3 +559,82 @@ def sequence_insert(series, rev, top):
"Please run scripts/series_sort.py.")
return (name, commit_pos - top_index,)
+
+
+# https://github.com/ActiveState/code/tree/master/recipes/Python/576696_OrderedSet_with_Weakrefs
+class Link(object):
+ __slots__ = 'prev', 'next', 'key', '__weakref__'
+
+
+class OrderedSet(collections.MutableSet):
+ 'Set the remembers the order elements were added'
+ # Big-O running times for all methods are the same as for regular sets.
+ # The internal self.__map dictionary maps keys to links in a doubly linked list.
+ # The circular doubly linked list starts and ends with a sentinel element.
+ # The sentinel element never gets deleted (this simplifies the algorithm).
+ # The prev/next links are weakref proxies (to prevent circular references).
+ # Individual links are kept alive by the hard reference in self.__map.
+ # Those hard references disappear when a key is deleted from an OrderedSet.
+
+ def __init__(self, iterable=None):
+ self.__root = root = Link() # sentinel node for doubly linked list
+ root.prev = root.next = root
+ self.__map = {} # key --> link
+ if iterable is not None:
+ self |= iterable
+
+ def __len__(self):
+ return len(self.__map)
+
+ def __contains__(self, key):
+ return key in self.__map
+
+ def add(self, key):
+ # Store new key in a new link at the end of the linked list
+ if key not in self.__map:
+ self.__map[key] = link = Link()
+ root = self.__root
+ last = root.prev
+ link.prev, link.next, link.key = last, root, key
+ last.next = root.prev = weakref.proxy(link)
+
+ def discard(self, key):
+ # Remove an existing item using self.__map to find the link which is
+ # then removed by updating the links in the predecessor and successors.
+ if key in self.__map:
+ link = self.__map.pop(key)
+ link.prev.next = link.next
+ link.next.prev = link.prev
+
+ def __iter__(self):
+ # Traverse the linked list in order.
+ root = self.__root
+ curr = root.next
+ while curr is not root:
+ yield curr.key
+ curr = curr.next
+
+ def __reversed__(self):
+ # Traverse the linked list in reverse order.
+ root = self.__root
+ curr = root.prev
+ while curr is not root:
+ yield curr.key
+ curr = curr.prev
+
+ def pop(self, last=True):
+ if not self:
+ raise KeyError('set is empty')
+ key = next(reversed(self)) if last else next(iter(self))
+ self.discard(key)
+ return key
+
+ def __repr__(self):
+ if not self:
+ return '%s()' % (self.__class__.__name__,)
+ return '%s(%r)' % (self.__class__.__name__, list(self))
+
+ def __eq__(self, other):
+ if isinstance(other, OrderedSet):
+ return len(self) == len(other) and list(self) == list(other)
+ return not self.isdisjoint(other)
diff --git a/scripts/git_sort/merge_tool.py b/scripts/git_sort/merge_tool.py
index fda4c3478f..60433fcbba 100755
--- a/scripts/git_sort/merge_tool.py
+++ b/scripts/git_sort/merge_tool.py
@@ -63,9 +63,9 @@ if __name__ == "__main__":
# (before, inside, after, set(inside),)
local, base, remote = (
- (s[0], s[1], s[2], set([series_conf.firstword(l)
- for l in s[1]
- if series_conf.filter_patches(l)]),)
+ (s[0], s[1], s[2], lib.OrderedSet([series_conf.firstword(l)
+ for l in s[1]
+ if series_conf.filter_patches(l)]),)
for s in [
series_conf.split(open(s_path))
for s_path in (local_path, base_path, remote_path,)
@@ -74,7 +74,7 @@ if __name__ == "__main__":
added = remote[3] - base[3]
removed = base[3] - remote[3]
- moved = set(lib.list_moved_patches(base[1], remote[1]))
+ moved = lib.OrderedSet(lib.list_moved_patches(base[1], remote[1]))
if added or removed:
print("%d commits added, %d commits removed from base to remote." %
diff --git a/scripts/sort_supported.rb b/scripts/sort_supported.rb
new file mode 100755
index 0000000000..f89890299c
--- /dev/null
+++ b/scripts/sort_supported.rb
@@ -0,0 +1,89 @@
+#!/usr/bin/ruby
+
+def max x, y
+ (x >= y) ? x : y
+end
+
+class String
+ def tablen
+ (length + 8) / 8
+ end
+ def tabfill tabs
+ self + "\t" * (tabs - (length / 8))
+ end
+ def ** other
+ star = nil
+ star = length - 1 if self[length - 1] == '*'
+ star = other.length - 1 if other[other.length - 1] == '*'
+ if star then
+ if self[0...star] == other[0...star] then
+ return 1 if star == length - 1
+ return -1
+ end
+ end
+ return self <=> other
+ end
+end
+
+header = []
+supported = []
+maxtabs = [0,0]
+maxlen = [0,0]
+
+File.open("supported.conf"){|f|
+ f.each_line{|l|
+ l.chomp!
+ l.gsub! %r<//>, '/'
+ split = (l.match %r<^([^[:blank:]/]*)[[:blank:]]+(?:([^[:blank:]/]+)[[:blank:]]+)?(?:([^[:blank:]/]+)[[:blank:]]+)?([^[:blank:]]+/[^[:blank:]]+)(?:[[:blank:]]+(.*))?$>)
+ if ! split then
+ header << l
+ else
+ # [[flag, ..],module,comment,is_kmp]
+ s = [[]]
+ slash = false
+ split[1..-1].each{|e|
+ if slash then
+ raise l + split.inspect if s[2]
+ s[2] = e
+ else
+ if e =~ %r</> then
+ slash = true
+ s[1] = e
+ else
+ s[0] << e if e
+ s[3] = true if e =~ /-kmp/
+ end
+ end
+ }
+ supported << s
+ maxtabs[0] = max(maxtabs[0], s[0].join(" ").tablen)
+ maxlen[0] = max(maxlen[0], s[0].join(" ").length)
+ if s[2] then
+ maxtabs[1] = max(maxtabs[1], s[1].tablen)
+ maxlen[1] = max(maxlen[1], s[1].length)
+ end
+ end
+ }
+}
+
+supported = supported.sort{|s1,s2|
+ cmp = 0
+ if s1[3] then
+ if s2[3] then
+ cmp = s1[0] <=> s2[0]
+ else
+ cmp = -1
+ end
+ elsif s2[3]
+ cmp = 1
+ end
+ cmp != 0 ? cmp : s1[1] ** s2[1]
+}
+
+File.open("supported.conf",'wb'){|f|
+ header.each{|l| f.puts l }
+ supported.each{|s|
+ f.puts s[0].join(" ").tabfill(maxtabs[0]) + (s[2] ? s[1].tabfill(maxtabs[1]) : s[1]) + s[2].to_s
+ }
+}
+#STDERR.puts (0..maxlen[1]).each{|n| STDERR.puts ("a"*n).tabfill(maxtabs[1]) + "|"}