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 """Utility functions with algorithms.
31
32 """
33
34 import re
35 import time
36 import itertools
37
38 from ganeti import compat
39 from ganeti.utils import text
40
41
42 _SORTER_GROUPS = 8
43 _SORTER_RE = re.compile("^%s(.*)$" % (_SORTER_GROUPS * r"(\D+|\d+)?"))
44
45
47 """Returns a list with unique elements.
48
49 Element order is preserved.
50
51 @type seq: sequence
52 @param seq: the sequence with the source elements
53 @rtype: list
54 @return: list of unique elements from seq
55
56 """
57 seen = set()
58 return [i for i in seq if i not in seen and not seen.add(i)]
59
60
62 """Joins dictionaries with no conflicting keys.
63
64 Enforces the constraint that the two key sets must be disjoint, and then
65 merges the two dictionaries in a new dictionary that is returned to the
66 caller.
67
68 @type dict_a: dict
69 @param dict_a: the first dictionary
70 @type dict_b: dict
71 @param dict_b: the second dictionary
72 @rtype: dict
73 @return: a new dictionary containing all the key/value pairs contained in the
74 two dictionaries.
75
76 """
77 assert not (set(dict_a) & set(dict_b)), ("Duplicate keys found while joining"
78 " %s and %s" % (dict_a, dict_b))
79 result = dict_a.copy()
80 result.update(dict_b)
81 return result
82
83
85 """Identifies duplicates in a list.
86
87 Does not preserve element order.
88
89 @type seq: sequence
90 @param seq: Sequence with source elements
91 @rtype: list
92 @return: List of duplicate elements from seq
93
94 """
95 dup = set()
96 seen = set()
97
98 for item in seq:
99 if item in seen:
100 dup.add(item)
101 else:
102 seen.add(item)
103
104 return list(dup)
105
106
107
108
110 """Return the set of keys defined multiple times in the given dicts.
111
112 >>> GetRepeatedKeys({"foo": 1, "bar": 2},
113 ... {"foo": 5, "baz": 7}
114 ... )
115 set("foo")
116
117 @type dicts: dict
118 @param dicts: The dictionaries to check for duplicate keys.
119 @rtype: set
120 @return: Keys used more than once across all dicts
121
122 """
123 if len(dicts) < 2:
124 return set()
125
126 keys = []
127 for dictionary in dicts:
128 keys.extend(dictionary)
129
130 return set(FindDuplicates(keys))
131
132
134 """Attempts to convert a string to an integer.
135
136 """
137 if val and val.isdigit():
138 return int(val)
139 else:
140 return val
141
142
144 """Extract key for sorting.
145
146 """
147 return [_NiceSortTryInt(grp)
148 for grp in _SORTER_RE.match(str(value)).groups()]
149
150
152 """Sort a list of strings based on digit and non-digit groupings.
153
154 Given a list of names C{['a1', 'a10', 'a11', 'a2']} this function
155 will sort the list in the logical order C{['a1', 'a2', 'a10',
156 'a11']}.
157
158 The sort algorithm breaks each name in groups of either only-digits
159 or no-digits. Only the first eight such groups are considered, and
160 after that we just use what's left of the string.
161
162 @type values: list
163 @param values: the names to be sorted
164 @type key: callable or None
165 @param key: function of one argument to extract a comparison key from each
166 list element, must return string
167 @rtype: list
168 @return: a copy of the name list sorted with our algorithm
169
170 """
171 if key is None:
172 keyfunc = NiceSortKey
173 else:
174 keyfunc = lambda value: NiceSortKey(key(value))
175
176 return sorted(values, key=keyfunc)
177
178
180 """Inverts the key/value mapping of a dict.
181
182 @param dict_in: The dict to invert
183 @return: the inverted dict
184
185 """
186 return dict(zip(dict_in.values(), dict_in.keys()))
187
188
190 """Inserts C{other} at given C{pos} into C{src}.
191
192 @note: This function does not modify C{src} in place but returns a new copy
193
194 @type src: list
195 @param src: The source list in which we want insert elements
196 @type pos: int
197 @param pos: The position where we want to start insert C{other}
198 @type other: list
199 @param other: The other list to insert into C{src}
200 @return: A copy of C{src} with C{other} inserted at C{pos}
201
202 """
203 new = src[:pos]
204 new.extend(other)
205 new.extend(src[pos:])
206
207 return new
208
209
211 """Converts a sequence to a dictionary with duplicate detection.
212
213 @type seq: sequen
214 @param seq: Input sequence
215 @type key: callable
216 @param key: Function for retrieving dictionary key from sequence element
217 @rtype: dict
218
219 """
220 keys = map(key, seq)
221
222 duplicates = FindDuplicates(keys)
223 if duplicates:
224 raise ValueError("Duplicate keys found: %s" % text.CommaJoin(duplicates))
225
226 assert len(keys) == len(seq)
227
228 return dict(zip(keys, seq))
229
230
232 """Helper function for C{FlatToDict}.
233
234 This function is recursively called
235
236 @param data: The input data as described in C{FlatToDict}, already splitted
237 @returns: The so far converted dict
238
239 """
240 if not compat.fst(compat.fst(data)):
241 assert len(data) == 1, \
242 "not bottom most element, found %d elements, expected 1" % len(data)
243 return compat.snd(compat.fst(data))
244
245 keyfn = lambda e: compat.fst(e).pop(0)
246 return dict([(k, _MakeFlatToDict(list(g)))
247 for (k, g) in itertools.groupby(sorted(data), keyfn)])
248
249
251 """Converts a flat structure to a fully fledged dict.
252
253 It accept a list of tuples in the form::
254
255 [
256 ("foo/bar", {"key1": "data1", "key2": "data2"}),
257 ("foo/baz", {"key3" :"data3" }),
258 ]
259
260 where the first element is the key separated by C{field_sep}.
261
262 This would then return::
263
264 {
265 "foo": {
266 "bar": {"key1": "data1", "key2": "data2"},
267 "baz": {"key3" :"data3" },
268 },
269 }
270
271 @type data: list of tuple
272 @param data: Input list to convert
273 @type field_sep: str
274 @param field_sep: The separator for the first field of the tuple
275 @returns: A dict based on the input list
276
277 """
278 return _MakeFlatToDict([(keys.split(field_sep), value)
279 for (keys, value) in data])
280
281
283 """Class to calculate remaining timeout when doing several operations.
284
285 """
286 __slots__ = [
287 "_allow_negative",
288 "_start_time",
289 "_time_fn",
290 "_timeout",
291 ]
292
293 - def __init__(self, timeout, allow_negative, _time_fn=time.time):
294 """Initializes this class.
295
296 @type timeout: float
297 @param timeout: Timeout duration
298 @type allow_negative: bool
299 @param allow_negative: Whether to return values below zero
300 @param _time_fn: Time function for unittests
301
302 """
303 object.__init__(self)
304
305 if timeout is not None and timeout < 0.0:
306 raise ValueError("Timeout must not be negative")
307
308 self._timeout = timeout
309 self._allow_negative = allow_negative
310 self._time_fn = _time_fn
311
312 self._start_time = None
313
314 - def Remaining(self):
315 """Returns the remaining timeout.
316
317 """
318 if self._timeout is None:
319 return None
320
321
322 if self._start_time is None:
323 self._start_time = self._time_fn()
324
325
326 remaining_timeout = self._start_time + self._timeout - self._time_fn()
327
328 if not self._allow_negative:
329
330 return max(0.0, remaining_timeout)
331
332 return remaining_timeout
333