1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
|
##
## func delegation tools
## These are some helper methods to make dealing with delegation
## dictionary trees a little more sane when dealing with delegation
## and related functions.
##
## Copyright 2008, Red Hat, Inc.
## Steve Salevan <ssalevan@redhat.com>
##
## This software may be freely redistributed under the terms of the GNU
## general public license.
##
## You should have received a copy of the GNU General Public License
## along with this program; if not, write to the Free Software
## Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
##
import fnmatch
class groupby(object):
"""
Borrowing the groupby iterator class directly
from the Python API as it does not exist in Pythons < 2.4
"""
def __init__(self, iterable, key=None):
if key is None:
key = lambda x: x
self.keyfunc = key
self.it = iter(iterable)
self.tgtkey = self.currkey = self.currvalue = xrange(0)
def __iter__(self):
return self
def next(self):
while self.currkey == self.tgtkey:
self.currvalue = self.it.next() # Exit on StopIteration
self.currkey = self.keyfunc(self.currvalue)
self.tgtkey = self.currkey
return (self.currkey, self._grouper(self.tgtkey))
def _grouper(self, tgtkey):
while self.currkey == tgtkey:
yield self.currvalue
self.currvalue = self.it.next() # Exit on StopIteration
self.currkey = self.keyfunc(self.currvalue)
def group_paths(ungrouped_list):
"""
Given a list of multi-element path lists,
groups them together into a list of single-element paths (which
exist directly under the current overlord) and a dictionary of paths
to send to next hops in the delegation chain, containing a list of lists
keyed by their common next hop.
"""
single_paths = [path[0] for path in ungrouped_list if len(path) == 1]
non_single_paths = [path for path in ungrouped_list if len(path) > 1]
path_group = dict([(key,[path[1:len(path)] for path in list(gen)])
for key, gen in groupby(non_single_paths,
key=lambda x:x[0])])
return (single_paths,path_group)
def get_paths_for_glob(glob, minionmap):
"""
Given a glob, returns shortest path to all minions
matching it in the delegation dictionary tree
"""
pathlist = []
for elem in match_glob_in_tree(glob,minionmap):
result = get_shortest_path(elem,minionmap)
if result not in pathlist: #prevents duplicates
pathlist.append(result)
return pathlist
def list_all_minions(minionmap):
"""
Given a minion map, returns a flat list of all minions
contained within it
"""
minionlist = []
for minion in minionmap.keys():
if minion not in minionlist:
minionlist.append(minion)
for minion in list_all_minions(minionmap[minion]):
if minion not in minionlist:
minionlist.append(minion)
return minionlist
def flatten_list(bumpy_list):
"""
Flattens gnarly nested lists into much
nicer, flat lists
"""
flat_list = []
for item in bumpy_list:
if isinstance(item, list):
for elem in flatten_list(item):
flat_list.append(elem)
else:
flat_list.append(item)
return flat_list
def match_glob_on_toplevel(pattern, minionmap):
"""
Searches through the top level of a dictionary
for all keys (minion FQDNs) matching the given
glob, returns matches
"""
matched = []
for k,v in minionmap.iteritems():
if fnmatch.fnmatch(k,pattern):
matched.append(k)
return matched
def match_glob_in_tree(pattern, minionmap):
"""
Searches through given tree dictionary for all
keys (minion FQDNs) matching the given glob,
returns matches
"""
matched = []
for k,v in minionmap.iteritems():
for result in match_glob_in_tree(pattern, v):
matched.append(result)
if fnmatch.fnmatch(k,pattern):
matched.append(k)
return matched
def minion_exists_under_node(minion, minionmap):
"""
A little wrapper around the match_glob_on_toplevel
method that you can use if you want to get a boolean
result denoting minion existence under your current
node
"""
return len(match_glob_on_toplevel(minion,minionmap)) > 0
def get_shortest_path(minion, minionmap):
"""
Given a minion that exists in the given tree,
this method returns all paths from the top
node to the minion in the form of a flat list
"""
def lensort(a,b):
if len(a) > len(b):
return 1
return -1
results = get_all_paths(minion,minionmap)
results.sort(lensort)
return results[0]
def get_all_paths(minion, minionmap):
"""
Given a minion that exists in the given tree,
this method returns all paths that exist from the top
node to the minion in the delegation dictionary tree
"""
#This is an ugly kludge of franken-code. If someone with
#more knowledge of graph theory than myself can improve this
#module, please, please do so. - ssalevan 7/2/08
seq_list = []
if minion_exists_under_node(minion, minionmap):
return [[minion]] #minion found, terminate branch
if minionmap == {}:
return [[]] #no minion found, terminate branch
for k,v in minionmap.iteritems():
branch_list = []
branch_list.append(k)
for branchlet in get_all_paths(minion, v):
branch_list.append(branchlet)
single_branch = flatten_list(branch_list)
if minion in single_branch:
seq_list.append(single_branch)
return seq_list
if __name__ == "__main__":
mymap = {'anthony':{'longpath1':{'longpath2':{'longpath3':{}}}},
'phil':{'steve':{'longpath3':{}}},
'tony':{'mike':{'anthony':{}}},
'just_a_minion':{}
}
print "- Testing an element that exists in multiple lists of varying length:"
for elem in match_glob_in_tree('*path3',mymap):
print "Element: %s, all paths: %s" % (elem, get_all_paths(elem,mymap))
print "best path: %s" % get_shortest_path(elem, mymap)
print "- Testing an element that is simply a minion and has no sub-nodes:"
for elem in match_glob_in_tree('*minion',mymap):
print "Element: %s, best path: %s" % (elem, get_shortest_path(elem,mymap))
print "- OK, now the whole thing:"
for elem in match_glob_in_tree('*',mymap):
print "Element: %s, best path: %s" % (elem, get_shortest_path(elem,mymap))
print "- And finally, with all duplicates removed:"
for elem in get_paths_for_glob('*',mymap):
print "Valid Path: %s" % elem
print "- And grouped together:"
print group_paths(get_paths_for_glob('*',mymap))
|
